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* ) );
15 unsigned int hash = (*table->hashcode)( table, key ) % table->size;
16 unsigned int i = hash;
19 unsigned char *x = table->data[ i++ ];
21 return ( hole >= 0 )? -hole : - (int) i;
23 if ( x == (unsigned char *)1 ) {
27 } else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
30 if ( i >= table->size ) {
40 // Find the keyed element, and assign the x pointer, or assign 0.
41 // Returns 1 if element is found and 0 otherwise.
42 int htfind(htable *table,void *key,unsigned char **x) {
43 pthread_mutex_lock( &table->lock );
44 int i = htindex( table, key );
47 pthread_mutex_unlock( &table->lock );
50 *x = table->data[ i ];
51 pthread_mutex_unlock( &table->lock );
56 static void htgrow(htable *table);
58 // Add the given element.
59 void htadd(htable *table,unsigned char *p) {
60 pthread_mutex_lock( &table->lock );
61 if ( table->fill >= table->size / 2 ) {
64 int i = htindex( table, p + table->offset );
67 if ( table->data[ i ] != 0 ) {
73 // There is a match already what to do?
76 pthread_mutex_unlock( &table->lock );
79 // Return the next element starting at i, or 0 if there are no more.
80 // Also increment the index to be of the element + 1, or -1 if there
81 // are no more elements.
82 static unsigned char *htnext(htable *table,int *i) {
86 unsigned char **p = table->data + *i;
87 unsigned char **e = table->data + table->size;
88 for ( ; p < e; p++ ) {
90 if ( *p != 0 && *p != (unsigned char*)1 ) {
98 static void htrehash(htable *table,unsigned int size) {
100 table->data = calloc( size, sizeof( unsigned char * ) );
106 while ( ( p = htnext( &old, &i ) ) != 0 ) {
112 static void htgrow(htable *table) {
113 if ( table->data == 0 ) {
114 table->data = calloc( 256, sizeof( unsigned char * ) );
120 htrehash( table, table->size << 8 );
123 // Delete the given element.
124 void htdelete(htable *table,unsigned char *p) {
125 pthread_mutex_lock( &table->lock );
126 int i = htindex( table, p + table->offset );
128 table->data[ i ] = (unsigned char *)1;
130 if ( table->holes > table->fill / 2 ) {
131 htrehash( table, table->size );
134 pthread_mutex_unlock( &table->lock );