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 #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