On 10/12/12, Diego Novillo <dnovi...@google.com> wrote:
> Add usage documentation for hash_table.
>
> Andrew, does this help?
>
> Lawrence, I think I've gotten the details right, but please confirm.
The patch merges the descriptor class with the element class,
which we do not currently do and which I don't think we should do.
If that class is used in a tree, it would be illegal.
I'll work with Diego to address the issue.
>
> 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)
>
--
Lawrence Crowl
