include/linux/ghash.h

   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 /* LINKAGE - empty or "static", depending on whether you want the definitions to
 157  *      be public or not
 158  * NAME - a string to stick in names to make this hash table type distinct from
 159  *      any others
 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
 164  *      field
 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
 173  * DEF_HASH.
 174  */
 175
 176 #define DEF_HASH_STRUCTS(NAME,HASHSIZE,TYPE) \
 177 \
 178 struct NAME##_table {\
 179         TYPE * hashtable[HASHSIZE];\
 180         int nr_entries;\
 181 };\
 182 \
 183 struct NAME##_ptrs {\
 184         TYPE * next_hash;\
 185         TYPE * prev_hash;\
 186 };
 187
 188 #define DEF_HASH(LINKAGE,NAME,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,HASHFN)\
 189 \
 190 LINKAGE void insert_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
 191 {\
 192         int ix = HASHFN(elem->KEY);\
 193         TYPE ** base = &tbl->hashtable[ix];\
 194         TYPE * ptr = *base;\
 195         TYPE * prev = NULL;\
 196 \
 197         tbl->nr_entries++;\
 198         while(ptr && KEYCMP(ptr->KEY, elem->KEY)) {\
 199                 base = &ptr->PTRS.next_hash;\
 200                 prev = ptr;\
 201                 ptr = *base;\
 202         }\
 203         elem->PTRS.next_hash = ptr;\
 204         elem->PTRS.prev_hash = prev;\
 205         if(ptr) {\
 206                 ptr->PTRS.prev_hash = elem;\
 207         }\
 208         *base = elem;\
 209 }\
 210 \
 211 LINKAGE void remove_##NAME##_hash(struct NAME##_table * tbl, TYPE * elem)\
 212 {\
 213         TYPE * next = elem->PTRS.next_hash;\
 214         TYPE * prev = elem->PTRS.prev_hash;\
 215 \
 216         tbl->nr_entries--;\
 217         if(next)\
 218                 next->PTRS.prev_hash = prev;\
 219         if(prev)\
 220                 prev->PTRS.next_hash = next;\
 221         else {\
 222                 int ix = HASHFN(elem->KEY);\
 223                 tbl->hashtable[ix] = next;\
 224         }\
 225 }\
 226 \
 227 LINKAGE TYPE * find_##NAME##_hash(struct NAME##_table * tbl, KEYTYPE pos)\
 228 {\
 229         int ix = HASHFN(pos);\
 230         TYPE * ptr = tbl->hashtable[ix];\
 231         while(ptr && KEYCMP(ptr->KEY, pos))\
 232                 ptr = ptr->PTRS.next_hash;\
 233         return ptr;\
 234 }
 235
 236 #endif