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