1 // A hashtable implementation with vectorized hashcode function.
3 // A hashtable is array of pointers, or the values 0 and 1, which mark
4 // unused and cleared slots respectively.
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).
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.
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.
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);
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);
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);
48 // Add the given element.
49 void htadd(htable *table,unsigned char *p);
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);
56 // Delete the given element.
57 void htdelete(htable *table,unsigned char *p);
59 // Dump the table with user-defined item dumper
60 void htdump(htable *table,void (*dumpitem)(int i,unsigned char *p));
62 // Special macro for htable initialization giving the record type, the
63 // key field and hashcode funtion.
64 // type = (base) data type for the elements
65 // member = the key field
66 // hashcodefn = function computing hashcode for a key
67 // assigns .compare = memcmp
68 #define HTABLEINIT(type,member,hashcodefn) \
69 { .data = 0, .size = 0, .fill = 0, \
70 .holes = 0, .offset = offsetof( type, member ), \
71 .esize = sizeof( ((type *)0)->member ), .hashcode = hashcodefn, \
72 .lock = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP }
74 #define HTHOLE ((unsigned char *)1)