htable.h

   1 // A hashtable implementation with vectorized hashcode function.
   2 //
   3 // A hashtable is array of pointers, or the values 0 and 1, which mark
   4 // unused and cleared slots respectively.
   5 //
   6 // Hash collision is handled by using the next usused or cleared slot
   7 // by increasing, cycled indexing. An addition when the fill exceeds
   8 // half the size causes a rehash into a new, double size table,
   9 // without any cleared slots (i.e., the fill might be reduced after
  10 // rehash, due to cleared slots).
  11 //
  12 // The fill count includes cleared entries, which counts deleted
  13 // entries. A deletion that makes the number of cleared slots to
  14 // exceed half the fill also causes a rehash into a new, same size
  15 // table, without any cleared clots.
  16 //
  17 // The data elements have a key part, which is a contiguous portion of
  18 // bytes at a given offset. The offset and size of the key are the
  19 // same for all elements.
  20 //
  21 #ifndef HTABLE_H
  22 #define HTABLE_H
  23
  24 #define __USE_GNU 1
  25 #include <pthread.h>
  26
  27 // The hashtable head data structure: htable
  28 typedef struct _htable {
  29     unsigned char **data; // array of entries
  30     unsigned int size;    // total array size
  31     unsigned int offset;  // offset into elements for the key part
  32     unsigned int esize;   // byte size of the key part
  33     unsigned int fill;    // number of added elements
  34     unsigned int holes;   // number of deleted
  35     int (*hashcode)(struct _htable *table,unsigned char *key);
  36     pthread_mutex_t lock;
  37 } htable;
  38
  39 // Determine the index for a key. On match, it returns the index into
  40 // the table. On mismatch it returns -i-1 for the first free spot
  41 // where the keyed element would fit.
  42 //int htindex(htable *table,unsigned char *key);
  43
  44 // Find the keyed element, and assign the x pointer, or assign 0.
  45 // Returns 1 if element is found and 0 otherwise.
  46 int htfind(htable *table,void *key,unsigned char **x);
  47
  48 // Add the given element.
  49 void htadd(htable *table,unsigned char *p);
  50
  51 // Return the next element starting at i, or 0 if there are no more.
  52 // Also increment the index to be of the element + 1, or -1 if there
  53 // are no more elements.
  54 //unsigned char *htnext(htable *table,int *i);
  55
  56 // Delete the given element.
  57 void htdelete(htable *table,unsigned char *p);
  58
  59 // Special macro for htable initialization giving the record type, the
  60 // key field and hashcode funtion.
  61 // type = (base) data type for the elements
  62 // member = the key field
  63 // hashcodefn = function computing hashcode for a key
  64 // assigns .compare = memcmp
  65 #define HTABLEINIT(type,member,hashcodefn)                              \
  66     { .data = 0, .size = 0, .fill = 0,                                  \
  67             .holes = 0, .offset = offsetof( type, member ),             \
  68             .esize = sizeof( ((type *)0)->member ), .hashcode = hashcodefn, \
  69             .lock = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP }
  70
  71 #endif // HTABLE_H