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 } 107