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