htable/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 =
  16         ( (unsigned int) (*table->hashcode)( table, key ) ) % table->size;
  17     unsigned int i = hash;
  18     int hole = -1;
  19     for ( ;; ) {
  20         unsigned char *x = table->data[ i ];
  21         if ( x == 0 ) {
  22             return ( hole >= 0 )? (- hole - 1 ): ( - (int) i - 1 );
  23         }
  24         if ( x == HTHOLE ) {
  25             if ( hole < 0 ) {
  26                 hole = i;
  27             }
  28         } else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
  29             return i;
  30         }
  31         i++;
  32         if ( i >= table->size ) {
  33             i = 0;
  34         }
  35         if ( i == hash ) {
  36             break;
  37         }
  38     }
  39     return - hole - 1;
  40 }
  41
  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 );
  47     if ( i < 0 ) {
  48         *x = 0;
  49         pthread_mutex_unlock( &table->lock );
  50         return 0;
  51     }
  52     *x = table->data[ i ];
  53     pthread_mutex_unlock( &table->lock );
  54     return 1;
  55 }
  56
  57 // Forward
  58 static void htgrow(htable *table);
  59
  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 ) {
  64         htgrow( table );
  65     }
  66     int i = htindex( table, p + table->offset );
  67     if ( i < 0 ) {
  68         i = -i - 1;
  69         if ( table->data[ i ] != 0 ) {
  70             table->holes--;
  71         } else {
  72             table->fill++;
  73         }
  74     } else {
  75         // There is a match already what to do?
  76     }
  77     table->data[ i ] = p;
  78     pthread_mutex_unlock( &table->lock );
  79 }
  80
  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) {
  85     if ( *i < 0 ) {
  86         return 0;
  87     }
  88     unsigned char **p = table->data + *i;
  89     unsigned char **e = table->data + table->size;
  90     for ( ; p < e; p++ ) {
  91         (*i) += 1;
  92         if ( *p != 0 && *p != HTHOLE ) {
  93             return *p;
  94         }
  95     }
  96     (*i) = -1;
  97     return 0;
  98 }
  99
 100 static void htrehash(htable *table,unsigned int size) {
 101     htable old = *table;
 102     table->data = calloc( size, sizeof( unsigned char * ) );
 103     table->size = size;
 104     table->fill = 0;
 105     table->holes = 0;
 106     int i = 0;
 107     unsigned char *p;
 108     while ( ( p = htnext( &old, &i ) ) != 0 ) {
 109         htadd( table, p );
 110     }
 111     free( old.data );
 112 }
 113
 114 static void htgrow(htable *table) {
 115     if ( table->data == 0 ) {
 116         table->data = calloc( 256, sizeof( unsigned char * ) );
 117         table->size = 256;
 118         table->fill = 0;
 119         table->holes = 0;
 120         return;
 121     }
 122     htrehash( table, table->size << 8 );
 123 }
 124
 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 );
 129     if ( i >= 0 ) {
 130         table->data[ i ] = HTHOLE;
 131         table->holes += 1;
 132         if ( table->holes > table->fill / 2 ) {
 133             htrehash( table, table->size );
 134         }
 135     }
 136     pthread_mutex_unlock( &table->lock );
 137 }
 138
 139 void htdump(htable *table,void (*dumpitem)(int i,unsigned char *p)) {
 140     int i;
 141     for ( i = 0 ; i < table->size; i++ ) {
 142         if ( table->data[ i ] && table->data[ i ] != HTHOLE ) {
 143             dumpitem( i, table->data[ i ] );
 144         }
 145     }
 146 }