db2/include/db_shash.h

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  *
   7  *      @(#)db_shash.h  10.3 (Sleepycat) 4/10/98
   8  */
   9
  10 /* Hash Headers */
  11 typedef SH_TAILQ_HEAD(hash_head) DB_HASHTAB;
  12
  13 /*
  14  * HASHLOOKUP --
  15  *
  16  * Look up something in a shared memory hash table.  The "elt" argument
  17  * should be a key, and cmp_func must know how to compare a key to whatever
  18  * structure it is that appears in the hash table.  The comparison function
  19  * cmp_func is called as: cmp_func(lookup_elt, table_elt);
  20  * begin: address of the beginning of the hash table.
  21  * type: the structure type of the elements that are linked in each bucket.
  22  * field: the name of the field by which the "type" structures are linked.
  23  * elt: the item for which we are searching in the hash table.
  24  * result: the variable into which we'll store the element if we find it.
  25  * nelems: the number of buckets in the hash table.
  26  * hash_func: the hash function that operates on elements of the type of elt
  27  * cmp_func: compare elements of the type of elt with those in the table (of
  28  *      type "type").
  29  *
  30  * If the element is not in the hash table, this macro exits with result
  31  * set to NULL.
  32  */
  33 #define HASHLOOKUP(begin, type, field, elt, r, n, hash, cmp) do {       \
  34         DB_HASHTAB *__bucket;                                           \
  35         u_int32_t __ndx;                                                \
  36                                                                         \
  37         __ndx = hash(elt) % (n);                                        \
  38         __bucket = &begin[__ndx];                                       \
  39         for (r = SH_TAILQ_FIRST(__bucket, type);                        \
  40             r != NULL; r = SH_TAILQ_NEXT(r, field, type))               \
  41                 if (cmp(elt, r))                                        \
  42                         break;                                          \
  43 } while(0)
  44
  45 /*
  46  * HASHINSERT --
  47  *
  48  * Insert a new entry into the hash table.  This assumes that lookup has
  49  * failed; don't call it if you haven't already called HASHLOOKUP.
  50  * begin: the beginning address of the hash table.
  51  * type: the structure type of the elements that are linked in each bucket.
  52  * field: the name of the field by which the "type" structures are linked.
  53  * elt: the item to be inserted.
  54  * nelems: the number of buckets in the hash table.
  55  * hash_func: the hash function that operates on elements of the type of elt
  56  */
  57 #define HASHINSERT(begin, type, field, elt, n, hash) do {               \
  58         u_int32_t __ndx;                                                \
  59         DB_HASHTAB *__bucket;                                           \
  60                                                                         \
  61         __ndx = hash(elt) % (n);                                        \
  62         __bucket = &begin[__ndx];                                       \
  63         SH_TAILQ_INSERT_HEAD(__bucket, elt, field, type);               \
  64 } while(0)
  65
  66 /*
  67  * HASHREMOVE --
  68  *      Remove the entry with a key == elt.
  69  * begin: address of the beginning of the hash table.
  70  * type: the structure type of the elements that are linked in each bucket.
  71  * field: the name of the field by which the "type" structures are linked.
  72  * elt: the item to be deleted.
  73  * nelems: the number of buckets in the hash table.
  74  * hash_func: the hash function that operates on elements of the type of elt
  75  * cmp_func: compare elements of the type of elt with those in the table (of
  76  *      type "type").
  77  */
  78 #define HASHREMOVE(begin, type, field, elt, n, hash, cmp) {             \
  79         u_int32_t __ndx;                                                \
  80         DB_HASHTAB *__bucket;                                           \
  81         SH_TAILQ_ENTRY *__entp;                                         \
  82                                                                         \
  83         __ndx = hash(elt) % (n);                                        \
  84         __bucket = &begin[__ndx];                                       \
  85         HASHLOOKUP(begin, type, field, elt, __entp, n, hash, cmp);      \
  86         SH_TAILQ_REMOVE(__bucket, __entp, field, type);                 \
  87 }
  88
  89 /*
  90  * HASHREMOVE_EL --
  91  *      Given the object "obj" in the table, remove it.
  92  * begin: address of the beginning of the hash table.
  93  * type: the structure type of the elements that are linked in each bucket.
  94  * field: the name of the field by which the "type" structures are linked.
  95  * obj: the object in the table that we with to delete.
  96  * nelems: the number of buckets in the hash table.
  97  * hash_func: the hash function that operates on elements of the type of elt
  98  */
  99 #define HASHREMOVE_EL(begin, type, field, obj, n, hash) {               \
 100         u_int32_t __ndx;                                                \
 101         DB_HASHTAB *__bucket;                                           \
 102                                                                         \
 103         __ndx = hash(obj) % (n);                                        \
 104         __bucket = &begin[__ndx];                                       \
 105         SH_TAILQ_REMOVE(__bucket, obj, field, type);                    \
 106 }