htable.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "htable.h"
   4
   5 //// Generic hash table implementation
   6
   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* ) );
  13         table->size = 256;
  14     }
  15     unsigned int hash = (*table->hashcode)( table, key ) % table->size;
  16     unsigned int i = hash;
  17     int hole = -1;
  18     for ( ;; ) {
  19         unsigned char *x = table->data[ i++ ];
  20         if ( x == 0 ) {
  21             return ( hole >= 0 )? -hole : - (int) i;
  22         }
  23         if ( x == (unsigned char *)1 ) {
  24             if ( hole < 0 ) {
  25                 hole = i;
  26             }
  27         } else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
  28             return i-1;
  29         }
  30         if ( i >= table->size ) {
  31             i = 0;
  32         }
  33         if ( i == hash ) {
  34             break;
  35         }
  36     }
  37     return -1;
  38 }
  39
  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 );
  45     if ( i < 0 ) {
  46         *x = 0;
  47         pthread_mutex_unlock( &table->lock );
  48         return 0;
  49     }
  50     *x = table->data[ i ];
  51     pthread_mutex_unlock( &table->lock );
  52     return 1;
  53 }
  54
  55 // Forward
  56 static void htgrow(htable *table);
  57
  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 ) {
  62         htgrow( table );
  63     }
  64     int i = htindex( table, p + table->offset );
  65     if ( i < 0 ) {
  66         i = -i - 1;
  67         if ( table->data[ i ] != 0 ) {
  68             table->holes--;
  69         } else {
  70             table->fill++;
  71         }
  72     } else {
  73         // There is a match already what to do?
  74     }
  75     table->data[ i ] = p;
  76     pthread_mutex_unlock( &table->lock );
  77 }
  78
  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) {
  83     if ( *i < 0 ) {
  84         return 0;
  85     }
  86     unsigned char **p = table->data + *i;
  87     unsigned char **e = table->data + table->size;
  88     for ( ; p < e; p++ ) {
  89         (*i) += 1;
  90         if ( *p != 0 || *p != (unsigned char*)1 ) {
  91             return *p;
  92         }
  93     }
  94     (*i) = -1;
  95     return 0;
  96 }
  97
  98 static void htrehash(htable *table,unsigned int size) {
  99     htable old = *table;
 100     table->data = calloc( size, sizeof( unsigned char * ) );
 101     table->size = size;
 102     table->fill = 0;
 103     table->holes = 0;
 104     int i = 0;
 105     unsigned char *p;
 106     while ( ( p = htnext( &old, &i ) ) != 0 ) {
 107         htadd( table, p );
 108     }
 109     free( old.data );
 110 }
 111
 112 static void htgrow(htable *table) {
 113     if ( table->data == 0 ) {
 114         table->data = calloc( 256, sizeof( unsigned char * ) );
 115         table->size = 256;
 116         table->fill = 0;
 117         table->holes = 0;
 118         return;
 119     }
 120     htrehash( table, table->size << 8 );
 121 }
 122
 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 );
 127     if ( i >= 0 ) {
 128         table->data[ i ] = (unsigned char *)1;
 129         table->holes += 1;
 130         if ( table->holes > table->fill / 2 ) {
 131             htrehash( table, table->size );
 132         }
 133     }
 134     pthread_mutex_unlock( &table->lock );
 135 }