5 //// Generic hash table implementation
7 // Determine the index for a key. On match, it returns the index into
8 // the table. On mismatch it returns -i-1 for the first free spot
9 // where the keyed element would fit.
10 static int htindex(htable *table,unsigned char *key) {
11 if ( table->data == 0 ) {
12 table->data = calloc( 256, sizeof( unsigned char* ) );
16 ( (unsigned int) (*table->hashcode)( table, key ) ) % table->size;
17 unsigned int i = hash;
20 unsigned char *x = table->data[ i ];
22 return ( hole >= 0 )? (- hole - 1 ): ( - (int) i - 1 );
28 } else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
32 if ( i >= table->size ) {
42 // Find the keyed element, and assign the x pointer, or assign 0.
43 // Returns 1 if element is found and 0 otherwise.
44 int htfind(htable *table,void *key,unsigned char **x) {
45 pthread_mutex_lock( &table->lock );
46 int i = htindex( table, key );
49 pthread_mutex_unlock( &table->lock );
52 *x = table->data[ i ];
53 pthread_mutex_unlock( &table->lock );
58 static void htgrow(htable *table);
60 // Add the given element.
61 void htadd(htable *table,unsigned char *p) {
62 pthread_mutex_lock( &table->lock );
63 if ( table->fill >= table->size / 2 ) {
66 int i = htindex( table, p + table->offset );
69 if ( table->data[ i ] != 0 ) {
75 // There is a match already what to do?
78 pthread_mutex_unlock( &table->lock );
81 // Return the next element starting at i, or 0 if there are no more.
82 // Also increment the index to be of the element + 1, or -1 if there
83 // are no more elements.
84 static unsigned char *htnext(htable *table,int *i) {
88 unsigned char **p = table->data + *i;
89 unsigned char **e = table->data + table->size;
90 for ( ; p < e; p++ ) {
92 if ( *p != 0 && *p != HTHOLE ) {
100 static void htrehash(htable *table,unsigned int size) {
102 table->data = calloc( size, sizeof( unsigned char * ) );
108 while ( ( p = htnext( &old, &i ) ) != 0 ) {
114 static void htgrow(htable *table) {
115 if ( table->data == 0 ) {
116 table->data = calloc( 256, sizeof( unsigned char * ) );
122 htrehash( table, table->size << 8 );
125 // Delete the given element.
126 void htdelete(htable *table,unsigned char *p) {
127 pthread_mutex_lock( &table->lock );
128 int i = htindex( table, p + table->offset );
130 table->data[ i ] = HTHOLE;
132 if ( table->holes > table->fill / 2 ) {
133 htrehash( table, table->size );
136 pthread_mutex_unlock( &table->lock );
139 void htdump(htable *table,void (*dumpitem)(int i,unsigned char *p)) {
141 for ( i = 0 ; i < table->size; i++ ) {
142 if ( table->data[ i ] && table->data[ i ] != HTHOLE ) {
143 dumpitem( i, table->data[ i ] );