~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~
ghash.h

Version: ~ [ 2.4.0 ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~
  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 \
 17 struct NAME##_table {\
 18         TYPE * hashtable[HASHSIZE];\
 19         TYPE * sorted_list;\
 20         int nr_entries;\
 21 };\
 22 \
 23 struct 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 \
 32 LINKAGE 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 \
 82 LINKAGE 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 \
107 LINKAGE 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 \
118 LINKAGE 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 \
158 struct NAME##_table {\
159         TYPE * hashtable[HASHSIZE];\
160         int nr_entries;\
161 };\
162 \
163 struct 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 \
170 LINKAGE 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 \
191 LINKAGE 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 \
207 LINKAGE 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
~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~
This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.
Linux Cross Reference Linux/include/linux/ghash.h

Linux Cross Reference
Linux/include/linux/ghash.h
