LXR linux-old/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\
  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