Go to the previous, next section.

Hash Tables

SUIF hash tables are implemented by the hash_table class in the files `hash.h' and `hash.cc'. Each hash table is a fixed-size array of hash_chain buckets. A hash_chain is just a move-to-front list. See section Move-to-front Lists. The entries in a hash table are derived from the hash_e class, which contains a single unsigned value used as the signature.

If you wish to store pointers in a hash table, you can use the hash_e class directly (assuming that the pointers can fit into the unsigned signature fields). Otherwise, you need to create a derived hash_e class. The only other thing needed is a function to compare two hash_e entries to determine if they are equal. You can then create a new hash_table object. Even if you are using a derived hash_e class, it may be easier to just type cast the pointers than to derive a new hash_table class that includes the correct type casts.

The hash table enter method tries to add a new entry. If the entry was already in the table it returns TRUE and does not enter a duplicate; otherwise, it adds the new entry and returns FALSE. The lookup method checks to see if a particular entry is in the table. If so, it returns the pointer to the entry.

Go to the previous, next section.