Add usage documentation for hash_table

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.

On 10/12/12, Diego Novillo <dnovillo@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)
>

On 2012-10-13 14:40 , Lawrence Crowl wrote:
> On 10/12/12, Diego Novillo <dnovillo@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.

You mean I should s/Element/Descriptor/?  Done.

I included the formatting changes in the doc patch, but I can easily 
split the patch if you prefer.

OK with those changes?


Diego.