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