..
.ie t .ds o \(bu
.el .ds o o
-.TH hash 3 "2 August 1999" mLib
+.TH hash 3 "2 August 1999" "Straylight/Edgeware" "mLib utilities library"
.SH "NAME"
hash \- low-level hashtable implementation
.\" @hash_create
The implementation is not complete. Many decisions have been left to
the user, including:
.hP \*o
-How keys should be represented, hashed and compared.
+how keys should be represented, hashed and compared;
.hP \*o
-How objects contained within the table should be allocated.
+how objects contained within the table should be allocated; and
.hP \*o
-When the hashtable should be extended.
+when the hashtable should be extended.
.PP
A complete hashtable implementation will need to take the above
decisions. If you just want a prepackaged solution, see
.B hash_table
structure. It contains two members:
.TP
-.B mask
+.B "uint32 mask"
The current bitmask to be applied to hashes. This is one less than the
current number of bins in the hashtable, and is applied to hash values
in order to decide which bin an item should be in.
.TP
-.B v
+.B "hash_base **v"
The bin vector. It is an array of pointers to hashtable items.
.PP
A hashtable item consists of a
only contains the bare minimum of information needed to maintain the
hashtable at a low level. It contains the following members:
.TP
-.B next
+.B "hash_base *next"
Pointer to the next item in the bin list. The final item has a null
.B next
pointer. The entry in the bin vector is null if the bin list is empty.
It is up to the high-level implementation to insert items into the list.
.TP
-.B hash
+.B "uint32 hash"
The hash for this item. This must be the full 32-bit hash for the
current item. It is used during hashtable expansion to determine which
bin an item should be moved to.