17 \h'-\w'\\$1\ 'u'\\$1\ \c
22 .TH hash 3 "2 August 1999" "Straylight/Edgeware" "mLib utilities library"
24 hash \- low-level hashtable implementation
39 .B "#include <mLib/hash.h>"
41 .BI "void hash_create(hash_table *" t ", size_t " n );
42 .BI "void hash_destroy(hash_table *" t );
43 .BI "hash_base **hash_bin(hash_table *" t ", uint32 " hash );
44 .BI "int hash_extend(hash_table *" t );
45 .BI "void hash_remove(hash_table *" t ", hash_base * " b );
46 .BI "void hash_mkiter(hash_iter *" i ", hash_table *" t );
47 .BI "hash_base *hash_next(hash_iter *" i );
49 .BI "hash_base **HASH_BIN(hash_table *" t ", uint32 " hash );
50 .BI "void HASH_MKITER(hash_iter *" i ", hash_table *" t );
51 .BI "void HASH_NEXT(hash_iter *" i ", " b );
56 functions provide the basis for an extensible hashtable implementation.
57 The implementation is not complete. Many decisions have been left to
60 How keys should be represented, hashed and compared.
62 How objects contained within the table should be allocated.
64 When the hashtable should be extended.
66 A complete hashtable implementation will need to take the above
67 decisions. If you just want a prepackaged solution, see
70 .SH "IMPLEMENTATION DETAILS"
71 Each item in the hashtable is assigned a 32-bit integer
73 a number computed somehow from the item's data such that two items which
74 are considered equal will yield the same hash. Ideally, different items
75 will yield different hashes. It is important for this implementation
76 that all bits of the hash are similarly good.
78 In order to look up an item, the high bits of the hash are masked off
79 and the remainder used as an index into a vector of
81 Each bin contains a list of items with identical low-order bits of their
84 A table expansion involves doubling the size of the bin vector. Each
85 bin list is then split into two, items being placed into a new bin
86 depending on the setting of the next lowest hash bit. By expanding the
87 hashtable as needed, lookups remain constant-time.
89 A low-level hashtable is represented by a
91 structure. It contains two members:
94 The current bitmask to be applied to hashes. This is one less than the
95 current number of bins in the hashtable, and is applied to hash values
96 in order to decide which bin an item should be in.
99 The bin vector. It is an array of pointers to hashtable items.
101 A hashtable item consists of a
103 structure. A full hashtable implementation will need to extend this
104 structure by adding keying information and other data; the
106 only contains the bare minimum of information needed to maintain the
107 hashtable at a low level. It contains the following members:
110 Pointer to the next item in the bin list. The final item has a null
112 pointer. The entry in the bin vector is null if the bin list is empty.
113 It is up to the high-level implementation to insert items into the list.
116 The hash for this item. This must be the full 32-bit hash for the
117 current item. It is used during hashtable expansion to determine which
118 bin an item should be moved to.
119 .SH "FUNCTIONALITY PROVIDED"
120 This section describes the functions and macros provided for building
121 hashtables. Code examples are given throughout. They assume the
122 following definitions:
124 /* --- A table of items --- */
126 typedef struct item_table {
131 /* --- An item --- */
133 typedef struct item {
139 The implementation presented here is simple but relatively bad. The
142 presents a more realistic example, but is rather more complex.
143 .SS "Initialization and finalization"
144 An empty hashtable is initialized by calling
146 with the address of a
148 structure to be filled in and the initial number of hash bins to create.
150 For example, an item table might be initialized like this:
152 void item_createtab(item_table *t)
154 hash_create(&t->t, ITEM_INITSZ);
155 t->load = ITEM_INITLOAD;
158 A hashtable can be destroyed by calling
160 with the address of the
162 structure. This does not attempt to deallocate the individual items;
163 that must be done beforehand.
165 The usual way to deallocate the individual hashtable items is using the
166 iteration constructs described below.
168 void item_destroytab(item_table *t)
172 for (hash_mkiter(&i, &t->t); (b = hash_next(&i)) != 0; ) {
173 item *ii = (item *)b;
182 .SS "Searching, adding and removing"
183 Items must be searched for and added by hand.
187 returns the address of the bin list haed for a particular hashtable and
188 hash value. The function
190 works the same way and provides the same result, but since the macro is
191 very simple its use is preferred. However, it will evaluate its
192 arguments multiple times.
194 Once the bin list has been found, it's fairly easy to search for an
195 exact match. A simple search might look something like this:
197 item *lookup(item_table *t, const char *k)
199 uint32 h = hash(k); /* Hash @k@ somehow */
200 hash_base **bin = HASH_BIN(&t->t, h);
202 for (b = *bin; b; b = b->next) {
204 if (h == i->b.hash && strcmp(k, i->k) == 0)
210 Insertion is also relatively trivial given the bin list head. Insertion
211 may make the hashtable too large, so it might be necessary to extend
212 it. Extension is performed by
214 which is passed only the address of the hashtable. It returns nonzero
215 if extension was successful.
217 item *add(item_table *t, const char *k, /* ... */)
223 /* --- See if the item is already there --- */
225 if ((i = = lookup(t, k)) != 0)
228 /* --- Make a new hashtable item --- */
234 /* --- Link it into the bin list --- */
236 h = i->b.hash = hash(k);
237 bin = HASH_BIN(&t->t, h);
241 /* --- Maybe extend the hashtable --- */
245 else if (hash_extend(&t->t))
246 t->load = recalc_load(t);
255 implementation is rather more sophisticated in its approach but the idea
256 is the same. In particular,
258 provides a single interface for lookup and insertion which prevents the
259 unnecessary rehashing performed by the above code.
261 Removal of items is more straightforward. The function
263 will unlink a given item from its bin list, after which point it is safe
266 Iteration allows code to be performed on all the items in a hashtable.
267 This is done using an
269 object, represented by a
271 structure. An iterator is initialized by calling
275 yields a different item from the hashtable until there are none left, a
276 condition signified by a null return value.
282 do the same jobs as the above functions. However,
284 has a slightly bizarre argument passing convention: its second argument
287 which is updated to contain the address of the next item.
289 The finalization code above contained an example of iteration.
294 Mark Wooding, <mdw@nsict.org>