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_removeMyType
+ {
+ 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_removeMyType, it does
not
+ need to provide a 'remove' function. It inherits it from
+ typed_noop_remove.
+
+ To instantiate a hash table for MyType:
+
+ hash_tableMyType 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
