2 * include/linux/ghash.h -- generic hashing with fuzzy retrieval
4 * (C) 1997 Thomas Schoebel-Theuer
6 * The algorithms implemented here seem to be a completely new invention,
7 * and I'll publish the fundamentals in a paper.
12 /* HASHSIZE _must_ be a power of two!!! */
15 #define DEF_HASH_FUZZY_STRUCTS(NAME,HASHSIZE,TYPE) \
17 struct NAME##_table {\
18 TYPE * hashtable[HASHSIZE];\
30 #define DEF_HASH_FUZZY(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
32 LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
34 int ix = HASHFN(elem->KEY);\
35 TYPE ** base = &tbl->hashtable[ix];\
40 while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
41 base = &ptr->PTRS.next_hash;\
45 elem->PTRS.next_hash = ptr;\
46 elem->PTRS.prev_hash = prev;\
48 ptr->PTRS.prev_hash = elem;\
54 ptr = tbl->sorted_list;\
57 prev = ptr->PTRS.prev_sorted;\
60 TYPE * next = ptr->PTRS.next_hash;\
61 if(next && KEYCMP(next->KEY, elem->KEY)) {\
64 } else if(KEYCMP(ptr->KEY, elem->KEY)) {\
66 ptr = ptr->PTRS.next_sorted;\
70 elem->PTRS.next_sorted = ptr;\
71 elem->PTRS.prev_sorted = prev;\
73 ptr->PTRS.prev_sorted = elem;\
76 prev->PTRS.next_sorted = elem;\
78 tbl->sorted_list = elem;\
82 LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
84 TYPE * next = elem->PTRS.next_hash;\
85 TYPE * prev = elem->PTRS.prev_hash;\
89 next->PTRS.prev_hash = prev;\
91 prev->PTRS.next_hash = next;\
93 int ix = HASHFN(elem->KEY);\
94 tbl->hashtable[ix] = next;\
97 next = elem->PTRS.next_sorted;\
98 prev = elem->PTRS.prev_sorted;\
100 next->PTRS.prev_sorted = prev;\
102 prev->PTRS.next_sorted = next;\
104 tbl->sorted_list = next;\
107 LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
109 int ix = hashfn(pos);\
110 TYPE * ptr = tbl->hashtable[ix];\
111 while(ptr && KEYCMP(ptr->KEY, pos))\
112 ptr = ptr->PTRS.next_hash;\
113 if(ptr && !KEYEQ(ptr->KEY, pos))\
118 LINKAGE TYPE * find_##NAME##_hash_fuzzy(struct NAME##_table * tbl, KEYTYPE pos)\
125 ptr = tbl->sorted_list;\
126 if(!ptr || KEYCMP(pos, ptr->KEY))\
132 next = tbl->hashtable[(ix+offset) & ((HASHSIZE)-1)];\
133 if(next && (KEYCMP(next->KEY, pos) || KEYEQ(next->KEY, pos))\
134 && KEYCMP(ptr->KEY, next->KEY))\
139 next = ptr->PTRS.next_hash;\
141 if(KEYCMP(next->KEY, pos)) {\
146 next = ptr->PTRS.next_sorted;\
147 if(next && KEYCMP(next->KEY, pos)) {\
156 /* LINKAGE - empty or "static", depending on whether you want the definitions to
158 * NAME - a string to stick in names to make this hash table type distinct from
160 * HASHSIZE - number of buckets
161 * TYPE - type of data contained in the buckets - must be a structure, one
162 * field is of type NAME_ptrs, another is the hash key
163 * PTRS - TYPE must contain a field of type NAME_ptrs, PTRS is the name of that
165 * KEYTYPE - type of the key field within TYPE
166 * KEY - name of the key field within TYPE
167 * KEYCMP - pointer to function that compares KEYTYPEs to each other - the
168 * prototype is int KEYCMP(KEYTYPE, KEYTYPE), it returns zero for equal,
169 * non-zero for not equal
170 * HASHFN - the hash function - the prototype is int HASHFN(KEYTYPE),
171 * it returns a number in the range 0 ... HASHSIZE - 1
172 * Call DEF_HASH_STRUCTS, define your hash table as a NAME_table, then call
176 #define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) \
178 struct NAME##_table {\
179 TYPE * hashtable[HASHSIZE];\
183 struct NAME##_ptrs {\
188 #define DEF_HASH(LINKAGE,NAME,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,HASHFN)\
190 LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
192 int ix = HASHFN(elem->KEY);\
193 TYPE ** base = &tbl->hashtable[ix];\
198 while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
199 base = &ptr->PTRS.next_hash;\
203 elem->PTRS.next_hash = ptr;\
204 elem->PTRS.prev_hash = prev;\
206 ptr->PTRS.prev_hash = elem;\
211 LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
213 TYPE * next = elem->PTRS.next_hash;\
214 TYPE * prev = elem->PTRS.prev_hash;\
218 next->PTRS.prev_hash = prev;\
220 prev->PTRS.next_hash = next;\
222 int ix = HASHFN(elem->KEY);\
223 tbl->hashtable[ix] = next;\
227 LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
229 int ix = HASHFN(pos);\
230 TYPE * ptr = tbl->hashtable[ix];\
231 while(ptr && KEYCMP(ptr->KEY, pos))\
232 ptr = ptr->PTRS.next_hash;\