Add usage documentation for hash_table.
Andrew, does this help?
Lawrence, I think I've gotten the details right, but please
confirm.
Tested by re-building stage 1.
* hash-table.h: Add usage documentation.
Tidy formatting.
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 3aa66a7..0c51be6 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -21,8 +21,121 @@ along with GCC; see the file COPYING3. If not see
/* This file implements a typed hash table.
- The implementation borrows from libiberty's hashtab. */
+ The implementation borrows from libiberty's htab_t.
+ Hash tables are instantiated with two type arguments:
+
+ 1- Element: A type describing the elements in the table.
+ This type must provide 3 declarations:
+
+ - A typedef to create the type Element::T. This is the type
+ of the elements stored in the table. So, if you want the
+ hash table of MyType elements, declare 'typedef MyType T;'.
+
+ - A function named 'hash' that takes a pointer to Element::T
+ and returns a hashval_t value. This is the hashing
+ function.
+
+ - A function named 'equal' that takes two pointers to
+ Element::T and returns an int. This is the comparison
+ function. It should return nonzero if the elements are
+ equal, 0 otherwise.
+
+ - A static function named 'remove' that takes an Element::T
+ pointer and frees the memory allocated by it. This is used
+ when individual elements of the table need to be disposed of
+ (e.g., when deleting a hash table, removing elements from
+ the table, etc).
+
+ 2- Allocator: A template type implementing allocation and deallocation for
+ the table itself.
+
+ This type takes as argument a type passed on by the hash table
+ allocation and deallocation functions. It must provide four
+ static functions:
+
+ - Allocator::control_alloc: This allocates the control data
+ blocks for the table.
+
+ - Allocator::control_free: This frees the control data blocks
+ for the table.
+
+ - Allocator::data_alloc: This allocates the data elements in
+ the table.
+
+ - Allocator::data_free: This deallocates the data elements in
+ the table.
+
+ In general, you will not need to provide your own Allocator type.
+ By default, hash tables will use the class xcallocator, which uses
+ malloc/free for allocation.
+
+ Additionally, this file provides two common types for implementing
+ element removal:
+
+ - typed_free_remove: it implements the method 'remove' to call
+ free().
+
+ - typed_noop_remove: it implements the method 'remove' to do
+ nothing.
+
+ To use either of these removal strategies, simply make your type a
+ derived class of one of these two.
+
+ Example usage:
+
+ 1- A hash table for MyType:
+
+ // Derive from typed_noop_remove so element removal does nothing.
+ class MyType : typed_noop_remove<MyType>
+ {
+ int f1;
+ OtherType f2;
+
+ // Hash table support. Need a typedef and 2 static functions.
+
+ // 'T' is the type used in all the hash table functions.
+ typedef MyType T;
+
+ // The hashing function. 'T' and 'MyType' are equivalent here.
+ static inline hashval_t hash (const MyType *);
+
+ // The equality function. 'T' and 'MyType' are equivalent here.
+ static inline int equal (const MyType *, const MyType *);
+ };
+
+ inline hashval_t
+ MyType::hash (const MyType *e)
+ { ... compute and return a hash value for E ... }
+
+ inline int
+ MyType::equal (const MyType *p1, const MyType *p2)
+ { ... compare P1 vs P2. Return 1 if they are the same ... }
+
+
+ Note that since MyType derives from typed_noop_remove<MyType>, it does not
+ need to provide a 'remove' function. It inherits it from
+ typed_noop_remove.
+
+ To instantiate a hash table for MyType:
+
+ hash_table<MyType> mytype_hash;
+
+ You can then used any of the functions in hash_table's public interface.
+ See hash_table for details. The interface is very similar to libiberty's
+ htab_t.
+
+
+ 2- A hash table of pointers.
+
+ This file provides the template type 'pointer_hash' which can be
+ used to create hash tables of pointers to any type. This class uses
+ the same hashing function used by libiberty's hash_pointer.
+
+ To create a hash table of pointers to MyType:
+
+ hash_table <pointer_hash <MyType>> ptr_htab;
+*/
#ifndef TYPED_HASHTAB_H
#define TYPED_HASHTAB_H
@@ -71,7 +184,7 @@ xcallocator <Type>::control_free (Type *memory)
{
return ::free (memory);
}
-
+
/* Free memory for data blocks. */
@@ -125,8 +238,7 @@ pointer_hash<Element>::hash (const T *candidate)
template <typename Element>
inline int
-pointer_hash<Element>::equal (const T *existing,
- const T *candidate)
+pointer_hash<Element>::equal (const T *existing, const T *candidate)
{
return existing == candidate;
}
@@ -185,17 +297,17 @@ struct hash_table_control
/* User-facing hash table type.
- The table stores elements of type Element.
+ The table stores elements of type Element::T.
- It hashes elements with the hash function.
+ It hashes elements with the hash function in Element.
The table currently works with relatively weak hash functions.
Use typed_pointer_hash <Element> when hashing pointers instead of objects.
- It compares elements with the equal function.
+ It compares elements with the equal function in Element.
Two elements with the same hash may not be equal.
Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
- It removes elements with the remove function.
+ It removes elements with the remove function in the Allocator.
This feature is useful for freeing memory.
Use typed_null_remove <Element> when not freeing objects.
Use typed_free_remove <Element> when doing a simple object free.
@@ -248,8 +360,7 @@ public:
/* Construct the hash table. The only useful operation next is create. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline
hash_table <Descr, Allocator>::hash_table ()
: htab (NULL)
@@ -259,8 +370,7 @@ hash_table <Descr, Allocator>::hash_table ()
/* See if the table has been created, as opposed to constructed. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline bool
hash_table <Descr, Allocator>::is_created ()
{
@@ -270,8 +380,7 @@ hash_table <Descr, Allocator>::is_created ()
/* Like find_with_hash, but compute the hash value from the element. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline typename Descr::T *
hash_table <Descr, Allocator>::find (const T *comparable)
{
@@ -281,11 +390,10 @@ hash_table <Descr, Allocator>::find (const T *comparable)
/* Like find_slot_with_hash, but compute the hash value from the element. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline typename Descr::T **
-hash_table <Descr, Allocator>
-::find_slot (const T *comparable, enum insert_option insert)
+hash_table <Descr, Allocator>::find_slot (const T *comparable,
+ enum insert_option insert)
{
return find_slot_with_hash (comparable, Descr::hash (comparable), insert);
}
@@ -293,11 +401,9 @@ hash_table <Descr, Allocator>
/* Like remove_elt_with_hash, but compute the hash value from the element. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline void
-hash_table <Descr, Allocator>
-::remove_elt (const T *comparable)
+hash_table <Descr, Allocator>::remove_elt (const T *comparable)
{
remove_elt_with_hash (comparable, Descr::hash (comparable));
}
@@ -305,8 +411,7 @@ hash_table <Descr, Allocator>
/* Return the current size of this hash table. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline size_t
hash_table <Descr, Allocator>::size()
{
@@ -316,8 +421,7 @@ hash_table <Descr, Allocator>::size()
/* Return the current number of elements in this hash table. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline size_t
hash_table <Descr, Allocator>::elements()
{
@@ -328,8 +432,7 @@ hash_table <Descr, Allocator>::elements()
/* Return the fraction of fixed collisions during all work with given
hash table. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
inline double
hash_table <Descr, Allocator>::collisions()
{
@@ -342,8 +445,7 @@ hash_table <Descr, Allocator>::collisions()
/* Create a hash table with at least the given number of INITIAL_SLOTS. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
void
hash_table <Descr, Allocator>::create (size_t size)
{
@@ -364,8 +466,7 @@ hash_table <Descr, Allocator>::create (size_t size)
/* Dispose of a hash table. Free all memory and return this hash table to
the non-created state. Naturally the hash table must already exist. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
void
hash_table <Descr, Allocator>::dispose ()
{
@@ -389,11 +490,9 @@ hash_table <Descr, Allocator>::dispose ()
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
typename Descr::T **
-hash_table <Descr, Allocator>
-::find_empty_slot_for_expand (hashval_t hash)
+hash_table <Descr, Allocator>::find_empty_slot_for_expand (hashval_t hash)
{
hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
size_t size = htab->size;
@@ -428,8 +527,7 @@ hash_table <Descr, Allocator>
table entries is changed. If memory allocation fails, this function
will abort. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
void
hash_table <Descr, Allocator>::expand ()
{
@@ -491,11 +589,10 @@ hash_table <Descr, Allocator>::expand ()
COMPARABLE element starting with the given HASH value. It cannot
be used to insert or delete an element. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
typename Descr::T *
-hash_table <Descr, Allocator>
-::find_with_hash (const T *comparable, hashval_t hash)
+hash_table <Descr, Allocator>::find_with_hash (const T *comparable,
+ hashval_t hash)
{
hashval_t index, hash2;
size_t size;
@@ -534,12 +631,11 @@ hash_table <Descr, Allocator>
write the value you want into the returned slot. When inserting an
entry, NULL may be returned if memory allocation fails. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
typename Descr::T **
-hash_table <Descr, Allocator>
-::find_slot_with_hash (const T *comparable, hashval_t hash,
- enum insert_option insert)
+hash_table <Descr, Allocator>::find_slot_with_hash (const T *comparable,
+ hashval_t hash,
+ enum insert_option insert)
{
T **first_deleted_slot;
hashval_t index, hash2;
@@ -565,7 +661,7 @@ hash_table <Descr, Allocator>
first_deleted_slot = &htab->entries[index];
else if (Descr::equal (entry, comparable))
return &htab->entries[index];
-
+
hash2 = hash_table_mod2 (hash, htab->size_prime_index);
for (;;)
{
@@ -573,7 +669,7 @@ hash_table <Descr, Allocator>
index += hash2;
if (index >= size)
index -= size;
-
+
entry = htab->entries[index];
if (entry == HTAB_EMPTY_ENTRY)
goto empty_entry;
@@ -639,15 +735,15 @@ hash_table <Descr, Allocator>::empty ()
useful when you've already done the lookup and don't want to do it
again. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
void
-hash_table <Descr, Allocator>
-::clear_slot (T **slot)
+hash_table <Descr, Allocator>::clear_slot (T **slot)
{
- if (slot < htab->entries || slot >= htab->entries + htab->size
- || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
- abort ();
+ if (slot < htab->entries
+ || slot >= htab->entries + htab->size
+ || *slot == HTAB_EMPTY_ENTRY
+ || *slot == HTAB_DELETED_ENTRY)
+ gcc_unreachable ();
Descr::remove (*slot);
@@ -660,11 +756,10 @@ hash_table <Descr, Allocator>
from hash table starting with the given HASH. If there is no
matching element in the hash table, this function does nothing. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
void
-hash_table <Descr, Allocator>
-::remove_elt_with_hash (const T *comparable, hashval_t hash)
+hash_table <Descr, Allocator>::remove_elt_with_hash (const T *comparable,
+ hashval_t hash)
{
T **slot;
@@ -683,13 +778,11 @@ hash_table <Descr, Allocator>
each live entry. If CALLBACK returns false, the iteration stops.
ARGUMENT is passed as CALLBACK's second argument. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
template <typename Argument,
int (*Callback) (typename Descr::T **slot, Argument argument)>
void
-hash_table <Descr, Allocator>
-::traverse_noresize (Argument argument)
+hash_table <Descr, Allocator>::traverse_noresize (Argument argument)
{
T **slot;
T **limit;
@@ -712,13 +805,11 @@ hash_table <Descr, Allocator>
/* Like traverse_noresize, but does resize the table when it is too empty
to improve effectivity of subsequent calls. */
-template <typename Descr,
- template <typename Type> class Allocator>
+template <typename Descr, template <typename Type> class Allocator>
template <typename Argument,
int (*Callback) (typename Descr::T **slot, Argument argument)>
void
-hash_table <Descr, Allocator>
-::traverse (Argument argument)
+hash_table <Descr, Allocator>::traverse (Argument argument)
{
size_t size = htab->size;
if (elements () * 8 < size && size > 32)
