1/*
2 * include/linux/ghash.h -- generic hashing with fuzzy retrieval
3 *
4 * (C) 1997 Thomas Schoebel-Theuer
5 *
6 * The algorithms implemented here seem to be a completely new invention,
7 * and I'll publish the fundamentals in a paper.
8 */
9
10#ifndef _GHASH_H
11#define _GHASH_H
12/* HASHSIZE _must_ be a power of two!!! */
13
14
15#define DEF_HASH_FUZZY_STRUCTS(NAME,HASHSIZE,TYPE) \
16\
17struct NAME##_table {\
18	TYPE * hashtable[HASHSIZE];\
19	TYPE * sorted_list;\
20	int nr_entries;\
21};\
22\
23struct NAME##_ptrs {\
24	TYPE * next_hash;\
25	TYPE * prev_hash;\
26	TYPE * next_sorted;\
27	TYPE * prev_sorted;\
28};
29
30#define DEF_HASH_FUZZY(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
31\
32LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
33{\
34	int ix = HASHFN(elem->KEY);\
35	TYPE ** base = &tbl->hashtable[ix];\
36	TYPE * ptr = *base;\
37	TYPE * prev = NULL;\
38\
39	tbl->nr_entries++;\
40	while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
41		base = &ptr->PTRS.next_hash;\
42		prev = ptr;\
43		ptr = *base;\
44	}\
45	elem->PTRS.next_hash = ptr;\
46	elem->PTRS.prev_hash = prev;\
47	if(ptr) {\
48		ptr->PTRS.prev_hash = elem;\
49	}\
50	*base = elem;\
51\
52	ptr = prev;\
53	if(!ptr) {\
54		ptr = tbl->sorted_list;\
55		prev = NULL;\
56	} else {\
57		prev = ptr->PTRS.prev_sorted;\
58	}\
59	while(ptr) {\
60		TYPE * next = ptr->PTRS.next_hash;\
61		if(next && KEYCMP(next->KEY, elem->KEY)) {\
62			prev = ptr;\
63			ptr = next;\
64		} else if(KEYCMP(ptr->KEY, elem->KEY)) {\
65			prev = ptr;\
66			ptr = ptr->PTRS.next_sorted;\
67		} else\
68			break;\
69	}\
70	elem->PTRS.next_sorted = ptr;\
71	elem->PTRS.prev_sorted = prev;\
72	if(ptr) {\
73		ptr->PTRS.prev_sorted = elem;\
74	}\
75	if(prev) {\
76		prev->PTRS.next_sorted = elem;\
77	} else {\
78		tbl->sorted_list = elem;\
79	}\
80}\
81\
82LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
83{\
84	TYPE * next = elem->PTRS.next_hash;\
85	TYPE * prev = elem->PTRS.prev_hash;\
86\
87	tbl->nr_entries--;\
88	if(next)\
89		next->PTRS.prev_hash = prev;\
90	if(prev)\
91		prev->PTRS.next_hash = next;\
92	else {\
93		int ix = HASHFN(elem->KEY);\
94		tbl->hashtable[ix] = next;\
95	}\
96\
97	next = elem->PTRS.next_sorted;\
98	prev = elem->PTRS.prev_sorted;\
99	if(next)\
100		next->PTRS.prev_sorted = prev;\
101	if(prev)\
102		prev->PTRS.next_sorted = next;\
103	else\
104		tbl->sorted_list = next;\
105}\
106\
107LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
108{\
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))\
114		ptr = NULL;\
115	return ptr;\
116}\
117\
118LINKAGE TYPE * find_##NAME##_hash_fuzzy(struct NAME##_table * tbl, KEYTYPE pos)\
119{\
120	int ix;\
121	int offset;\
122	TYPE * ptr;\
123	TYPE * next;\
124\
125	ptr = tbl->sorted_list;\
126	if(!ptr || KEYCMP(pos, ptr->KEY))\
127		return NULL;\
128	ix = HASHFN(pos);\
129	offset = HASHSIZE;\
130	do {\
131		offset >>= 1;\
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))\
135			ptr = next;\
136	} while(offset);\
137\
138	for(;;) {\
139		next = ptr->PTRS.next_hash;\
140		if(next) {\
141			if(KEYCMP(next->KEY, pos)) {\
142				ptr = next;\
143				continue;\
144			}\
145		}\
146		next = ptr->PTRS.next_sorted;\
147		if(next && KEYCMP(next->KEY, pos)) {\
148			ptr = next;\
149			continue;\
150		}\
151		return ptr;\
152	}\
153	return NULL;\
154}
155
156#define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) \
157\
158struct NAME##_table {\
159	TYPE * hashtable[HASHSIZE];\
160	int nr_entries;\
161};\
162\
163struct NAME##_ptrs {\
164	TYPE * next_hash;\
165	TYPE * prev_hash;\
166};
167
168#define DEF_HASH(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
169\
170LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
171{\
172	int ix = HASHFN(elem->KEY);\
173	TYPE ** base = &tbl->hashtable[ix];\
174	TYPE * ptr = *base;\
175	TYPE * prev = NULL;\
176\
177	tbl->nr_entries++;\
178	while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
179		base = &ptr->PTRS.next_hash;\
180		prev = ptr;\
181		ptr = *base;\
182	}\
183	elem->PTRS.next_hash = ptr;\
184	elem->PTRS.prev_hash = prev;\
185	if(ptr) {\
186		ptr->PTRS.prev_hash = elem;\
187	}\
188	*base = elem;\
189}\
190\
191LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
192{\
193	TYPE * next = elem->PTRS.next_hash;\
194	TYPE * prev = elem->PTRS.prev_hash;\
195\
196	tbl->nr_entries--;\
197	if(next)\
198		next->PTRS.prev_hash = prev;\
199	if(prev)\
200		prev->PTRS.next_hash = next;\
201	else {\
202		int ix = HASHFN(elem->KEY);\
203		tbl->hashtable[ix] = next;\
204	}\
205}\
206\
207LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
208{\
209	int ix = hashfn(pos);\
210	TYPE * ptr = tbl->hashtable[ix];\
211	while(ptr && KEYCMP(ptr->KEY, pos))\
212		ptr = ptr->PTRS.next_hash;\
213	if(ptr && !KEYEQ(ptr->KEY, pos))\
214		ptr = NULL;\
215	return ptr;\
216}
217
218#endif
219