From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30704 invoked by alias); 26 Oct 2012 09:46:36 -0000 Received: (qmail 30693 invoked by uid 22791); 26 Oct 2012 09:46:35 -0000 X-SWARE-Spam-Status: No, hits=-5.0 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,TW_TM X-Spam-Check-By: sourceware.org Received: from mail-oa0-f47.google.com (HELO mail-oa0-f47.google.com) (209.85.219.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 26 Oct 2012 09:46:22 +0000 Received: by mail-oa0-f47.google.com with SMTP id h1so2628620oag.20 for ; Fri, 26 Oct 2012 02:46:21 -0700 (PDT) MIME-Version: 1.0 Received: by 10.182.21.142 with SMTP id v14mr18029923obe.46.1351244780892; Fri, 26 Oct 2012 02:46:20 -0700 (PDT) Received: by 10.76.95.202 with HTTP; Fri, 26 Oct 2012 02:46:20 -0700 (PDT) In-Reply-To: References: Date: Fri, 26 Oct 2012 09:54:00 -0000 Message-ID: Subject: Re: From: Richard Biener To: Lawrence Crowl Cc: gcc-patches List , Diego Novillo Content-Type: text/plain; charset=ISO-8859-1 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2012-10/txt/msg02401.txt.bz2 On Thu, Oct 25, 2012 at 10:56 PM, Lawrence Crowl wrote: > Change hash_table to support a comparator type different from the > value type stored in the hash table. The 'find' functions now may > take a different type from the value type. This requires introducing > a second typedef into the Descriptor conceptual type. Change the > Descriptor concept to use typedefs value_type and compare_type instead > of T. Change all users to match. > > Add usage documentation to hash-table.h. > > Tested on x86-64. > > Okay for trunk? Can you elaborate on why this is needed? Thanks, Richard. > > Index: gcc/ChangeLog > > 2012-10-25 Lawrence Crowl > > * hash-table.h: Add usage documentation. > (template struct typed_free_remove): Clarify documentation. > Rename template parameter. > (struct typed_noop_remove): Likewise. > (descriptor concept): Change typedef T to value_type. > Add typedef compare_type. Use more precise template parameter name, > Descriptor instead of Descr. Update users to match. > (struct hash_table): Change 'find' parameters to use compare_type > instead of the value type. > > > Index: gcc/tree-ssa-tail-merge.c > =================================================================== > --- gcc/tree-ssa-tail-merge.c (revision 192820) > +++ gcc/tree-ssa-tail-merge.c (working copy) > @@ -226,10 +226,11 @@ struct same_succ_def > hashval_t hashval; > > /* hash_table support. */ > - typedef same_succ_def T; > - static inline hashval_t hash (const same_succ_def *); > - static int equal (const same_succ_def *, const same_succ_def *); > - static void remove (same_succ_def *); > + typedef same_succ_def value_type; > + typedef same_succ_def compare_type; > + static inline hashval_t hash (const value_type *); > + static int equal (const value_type *, const compare_type *); > + static void remove (value_type *); > }; > typedef struct same_succ_def *same_succ; > typedef const struct same_succ_def *const_same_succ; > @@ -237,7 +238,7 @@ typedef const struct same_succ_def *cons > /* hash routine for hash_table support, returns hashval of E. */ > > inline hashval_t > -same_succ_def::hash (const same_succ_def *e) > +same_succ_def::hash (const value_type *e) > { > return e->hashval; > } > @@ -528,7 +529,7 @@ inverse_flags (const_same_succ e1, const > /* Compares SAME_SUCCs E1 and E2. */ > > int > -same_succ_def::equal (const_same_succ e1, const_same_succ e2) > +same_succ_def::equal (const value_type *e1, const compare_type *e2) > { > unsigned int i, first1, first2; > gimple_stmt_iterator gsi1, gsi2; > Index: gcc/tree-ssa-threadupdate.c > =================================================================== > --- gcc/tree-ssa-threadupdate.c (revision 192820) > +++ gcc/tree-ssa-threadupdate.c (working copy) > @@ -127,20 +127,21 @@ struct redirection_data : typed_free_rem > struct el *incoming_edges; > > /* hash_table support. */ > - typedef redirection_data T; > - static inline hashval_t hash (const redirection_data *); > - static inline int equal (const redirection_data *, const redirection_data *); > + typedef redirection_data value_type; > + typedef redirection_data compare_type; > + static inline hashval_t hash (const value_type *); > + static inline int equal (const value_type *, const compare_type *); > }; > > inline hashval_t > -redirection_data::hash (const redirection_data *p) > +redirection_data::hash (const value_type *p) > { > edge e = p->outgoing_edge; > return e->dest->index; > } > > inline int > -redirection_data::equal (const redirection_data *p1, const > redirection_data *p2) > +redirection_data::equal (const value_type *p1, const compare_type *p2) > { > edge e1 = p1->outgoing_edge; > edge e2 = p2->outgoing_edge; > Index: gcc/java/jcf-io.c > =================================================================== > --- gcc/java/jcf-io.c (revision 192820) > +++ gcc/java/jcf-io.c (working copy) > @@ -276,19 +276,21 @@ find_classfile (char *filename, JCF *jcf > > struct charstar_hash : typed_noop_remove > { > - typedef const char T; > - static inline hashval_t hash (const T *candidate); > - static inline bool equal (const T *existing, const T *candidate); > + typedef const char value_type; > + typedef const char compare_type; > + static inline hashval_t hash (const value_type *candidate); > + static inline bool equal (const value_type *existing, > + const compare_type *candidate); > }; > > inline hashval_t > -charstar_hash::hash (const T *candidate) > +charstar_hash::hash (const value_type *candidate) > { > return htab_hash_string (candidate); > } > > inline bool > -charstar_hash::equal (const T *existing, const T *candidate) > +charstar_hash::equal (const value_type *existing, const compare_type > *candidate) > { > return strcmp (existing, candidate) == 0; > } > Index: gcc/valtrack.h > =================================================================== > --- gcc/valtrack.h (revision 192820) > +++ gcc/valtrack.h (working copy) > @@ -46,32 +46,33 @@ struct dead_debug_global_entry > struct dead_debug_hash_descr > { > /* The hash table contains pointers to entries of this type. */ > - typedef struct dead_debug_global_entry T; > + typedef struct dead_debug_global_entry value_type; > + typedef struct dead_debug_global_entry compare_type; > /* Hash on the pseudo number. */ > - static inline hashval_t hash (T const *my); > + static inline hashval_t hash (const value_type *my); > /* Entries are identical if they refer to the same pseudo. */ > - static inline bool equal (T const *my, T const *other); > + static inline bool equal (const value_type *my, const compare_type *other); > /* Release entries when they're removed. */ > - static inline void remove (T *p); > + static inline void remove (value_type *p); > }; > > /* Hash on the pseudo number. */ > inline hashval_t > -dead_debug_hash_descr::hash (T const *my) > +dead_debug_hash_descr::hash (const value_type *my) > { > return REGNO (my->reg); > } > > /* Entries are identical if they refer to the same pseudo. */ > inline bool > -dead_debug_hash_descr::equal (T const *my, T const *other) > +dead_debug_hash_descr::equal (const value_type *my, const compare_type *other) > { > return my->reg == other->reg; > } > > /* Release entries when they're removed. */ > inline void > -dead_debug_hash_descr::remove (T *p) > +dead_debug_hash_descr::remove (value_type *p) > { > XDELETE (p); > } > Index: gcc/objc/objc-act.c > =================================================================== > --- gcc/objc/objc-act.c (revision 192820) > +++ gcc/objc/objc-act.c (working copy) > @@ -3827,19 +3827,20 @@ objc_get_class_ivars (tree class_name) > > struct decl_name_hash : typed_noop_remove > { > - typedef tree_node T; > - static inline hashval_t hash (const T *); > - static inline bool equal (const T *, const T *); > + typedef tree_node value_type; > + typedef tree_node compare_type; > + static inline hashval_t hash (const value_type *); > + static inline bool equal (const value_type *, const compare_type *); > }; > > inline hashval_t > -decl_name_hash::hash (const T *q) > +decl_name_hash::hash (const value_type *q) > { > return (hashval_t) ((intptr_t)(DECL_NAME (q)) >> 3); > } > > inline bool > -decl_name_hash::equal (const T *a, const T *b) > +decl_name_hash::equal (const value_type *a, const compare_type *b) > { > return DECL_NAME (a) == DECL_NAME (b); > } > Index: gcc/cfg.c > =================================================================== > --- gcc/cfg.c (revision 192820) > +++ gcc/cfg.c (working copy) > @@ -988,19 +988,21 @@ struct htab_bb_copy_original_entry > > struct bb_copy_hasher : typed_noop_remove > { > - typedef htab_bb_copy_original_entry T; > - static inline hashval_t hash (const T *); > - static inline bool equal (const T *existing, const T * candidate); > + typedef htab_bb_copy_original_entry value_type; > + typedef htab_bb_copy_original_entry compare_type; > + static inline hashval_t hash (const value_type *); > + static inline bool equal (const value_type *existing, > + const compare_type * candidate); > }; > > inline hashval_t > -bb_copy_hasher::hash (const T *data) > +bb_copy_hasher::hash (const value_type *data) > { > return data->index1; > } > > inline bool > -bb_copy_hasher::equal (const T *data, const T *data2) > +bb_copy_hasher::equal (const value_type *data, const compare_type *data2) > { > return data->index1 == data2->index1; > } > Index: gcc/hash-table.h > =================================================================== > --- gcc/hash-table.h (revision 192820) > +++ gcc/hash-table.h (working copy) > @@ -21,7 +21,142 @@ along with GCC; see the file COPYING3. > > > /* This file implements a typed hash table. > - The implementation borrows from libiberty's hashtab. */ > + The implementation borrows from libiberty's htab_t in hashtab.h. > + > + > + INTRODUCTION TO TYPES > + > + Users of the hash table generally need to be aware of three types. > + > + 1. The type being placed into the hash table. This type is called > + the value type. > + > + 2. The type used to describe how to handle the value type within > + the hash table. This descriptor type provides the hash table with > + several things. > + > + - A typedef named 'value_type' to the value type (from above). > + > + - A static member function named 'hash' that takes a value_type > + pointer and returns a hashval_t value. > + > + - A typedef named 'compare_type' that is used to test when an value > + is found. This type is the comparison type. Usually, it will be the > + same as value_type. If it is not the same type, you must generally > + explicitly compute hash values and pass them to the hash table. > + > + - A static member function named 'equal' that takes a value_type > + pointer and a compare_type pointer, and returns a bool. > + > + - A static function named 'remove' that takes an value_type pointer > + and frees the memory allocated by it. This function 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). > + > + 3. The type of the hash table itself. (More later.) > + > + In very special circumstances, users may need to know about a fourth type. > + > + 4. The template type used to describe how hash table memory > + is allocated. This type is called the allocator type. It is > + parameterized on the value type. It provides four functions. > + > + - A static member function named 'control_alloc'. This function > + allocates the control data blocks for the table. > + > + - A static member function named 'control_free'. This function > + frees the control data blocks for the table. > + > + - A static member function named 'data_alloc'. This function > + allocates the data elements in the table. > + > + - A static member function named 'data_free'. This function > + deallocates the data elements in the table. > + > + Hash table are instantiated with two type arguments. > + > + * The descriptor type, (2) above. > + > + * The allocator type, (4) above. In general, you will not need to > + provide your own allocator type. By default, hash tables will use > + the class template xcallocator, which uses malloc/free for allocation. > + > + > + DEFINING A DESCRIPTOR TYPE > + > + The first task in using the hash table is to describe the element type. > + We compose this into a few steps. > + > + 1. Decide on a removal policy for values stored in the table. > + This header provides class templates for the two most common > + policies. > + > + * typed_free_remove implements the static 'remove' member function > + by calling free(). > + > + * typed_noop_remove implements the static 'remove' member function > + by doing nothing. > + > + You can use these policies by simply deriving the descriptor type > + from one of those class template, with the appropriate argument. > + > + Otherwise, you need to write the static 'remove' member function > + in the descriptor class. > + > + 2. Choose a hash function. Write the static 'hash' member function. > + > + 3. Choose an equality testing function. In most cases, its two > + arguments will be value_type pointers. If not, the first argument must > + be a value_type pointer, and the second argument a compare_type pointer. > + > + > + AN EXAMPLE DESCRIPTOR TYPE > + > + Suppose you want to put some_type into the hash table. You could define > + the descriptor type as follows. > + > + struct some_type_hasher : typed_noop_remove > + // Deriving from typed_noop_remove means that we get a 'remove' that does > + // nothing. This choice is good for raw values. > + { > + typedef some_type value_type; > + typedef some_type compare_type; > + static inline hashval_t hash (const value_type *); > + static inline bool equal (const value_type *, const compare_type *); > + }; > + > + inline hashval_t > + some_type_hasher::hash (const value_type *e) > + { ... compute and return a hash value for E ... } > + > + inline bool > + some_type_hasher::equal (const value_type *p1, const compare_type *p2) > + { ... compare P1 vs P2. Return true if they are the 'same' ... } > + > + > + AN EXAMPLE HASH_TABLE DECLARATION > + > + To instantiate a hash table for some_type: > + > + hash_table some_type_hash_table; > + > + There is no need to mention some_type directly, as the hash table will > + obtain it using some_type_hasher::value_type. > + > + 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. > + > + > + EASY DESCRIPTORS FOR POINTERS > + > + The class template pointer_hash provides everything you need to hash > + pointers (as opposed to what they point to). So, to instantiate a hash > + table over pointers to whatever_type, > + > + hash_table > whatever_type_hash_table; > + > +*/ > > > #ifndef TYPED_HASHTAB_H > @@ -53,7 +188,7 @@ xcallocator ::control_alloc (size_ > } > > > -/* Allocate memory for COUNT data blocks. */ > +/* Allocate memory for COUNT data blocks. */ > > template > inline Type * > @@ -71,7 +206,7 @@ xcallocator ::control_free (Type * > { > return ::free (memory); > } > - > + > > /* Free memory for data blocks. */ > > @@ -83,50 +218,71 @@ xcallocator ::data_free (Type *mem > } > > > -/* Remove method dispatching to free. */ > +/* Helpful type for removing with free. */ > > -template > +template > struct typed_free_remove > { > - static inline void remove (Element *p) { free (p); } > + static inline void remove (Type *p); > }; > > -/* No-op remove method. */ > > -template > +/* Remove with free. */ > + > +template > +inline void > +typed_free_remove ::remove (Type *p) > +{ > + free (p); > +} > + > + > +/* Helpful type for a no-op remove. */ > + > +template > struct typed_noop_remove > { > - static inline void remove (Element *) {} > + static inline void remove (Type *p); > }; > > > +/* Remove doing nothing. */ > + > +template > +inline void > +typed_noop_remove ::remove (Type *p ATTRIBUTE_UNUSED) > +{ > +} > + > + > /* Pointer hash with a no-op remove method. */ > > -template > -struct pointer_hash : typed_noop_remove > +template > +struct pointer_hash : typed_noop_remove > { > - typedef Element T; > + typedef Type value_type; > + typedef Type compare_type; > > static inline hashval_t > - hash (const T *); > + hash (const value_type *); > > static inline int > - equal (const T *existing, const T * candidate); > + equal (const value_type *existing, const compare_type *candidate); > }; > > -template > +template > inline hashval_t > -pointer_hash::hash (const T *candidate) > +pointer_hash ::hash (const value_type *candidate) > { > /* This is a really poor hash function, but it is what the current code uses, > so I am reusing it to avoid an additional axis in testing. */ > return (hashval_t) ((intptr_t)candidate >> 3); > } > > -template > +template > inline int > -pointer_hash::equal (const T *existing, > - const T *candidate) > +pointer_hash ::equal (const value_type *existing, > + const compare_type *candidate) > { > return existing == candidate; > } > @@ -185,37 +341,38 @@ struct hash_table_control > > /* User-facing hash table type. > > - The table stores elements of type Element. > + The table stores elements of type Descriptor::value_type. > > - It hashes elements with the hash function. > + It hashes values with the hash member function. > The table currently works with relatively weak hash functions. > - Use typed_pointer_hash when hashing pointers instead of objects. > + Use typed_pointer_hash when hashing pointers instead of objects. > > - It compares elements with the equal function. > + It compares elements with the equal member function. > Two elements with the same hash may not be equal. > - Use typed_pointer_equal when hashing pointers instead > of objects. > + Use typed_pointer_equal when hashing pointers instead of objects. > > - It removes elements with the remove function. > + It removes elements with the remove member function. > This feature is useful for freeing memory. > - Use typed_null_remove when not freeing objects. > - Use typed_free_remove when doing a simple object free. > + Derive from typed_null_remove when not freeing objects. > + Derive from typed_free_remove when doing a simple object free. > > - Use the Allocator template to allocate and free memory. > + Specify the template Allocator to allocate and free memory. > The default is xcallocator. > > */ > > -template +template template class Allocator = xcallocator> > class hash_table > { > public: > - typedef typename Descr::T T; > + typedef typename Descriptor::value_type value_type; > + typedef typename Descriptor::compare_type compare_type; > > private: > - hash_table_control *htab; > + hash_table_control *htab; > > - T **find_empty_slot_for_expand (hashval_t hash); > + value_type **find_empty_slot_for_expand (hashval_t hash); > void expand (); > > public: > @@ -223,35 +380,36 @@ public: > void create (size_t initial_slots); > bool is_created (); > void dispose (); > - T *find (const T *comparable); > - T *find_with_hash (const T *comparable, hashval_t hash); > - T **find_slot (const T *comparable, enum insert_option insert); > - T **find_slot_with_hash (const T *comparable, hashval_t hash, > - enum insert_option insert); > + value_type *find (const compare_type *comparable); > + value_type *find_with_hash (const compare_type *comparable, hashval_t hash); > + value_type **find_slot (const compare_type *comparable, > + enum insert_option insert); > + value_type **find_slot_with_hash (const compare_type *comparable, > + hashval_t hash, enum insert_option insert); > void empty (); > - void clear_slot (T **slot); > - void remove_elt (const T *comparable); > - void remove_elt_with_hash (const T *comparable, hashval_t hash); > + void clear_slot (value_type **slot); > + void remove_elt (const compare_type *comparable); > + void remove_elt_with_hash (const compare_type *comparable, hashval_t hash); > size_t size(); > size_t elements(); > double collisions(); > > template - int (*Callback) (T **slot, Argument argument)> > + int (*Callback) (value_type **slot, Argument argument)> > void traverse_noresize (Argument argument); > > template - int (*Callback) (T **slot, Argument argument)> > + int (*Callback) (value_type **slot, Argument argument)> > void traverse (Argument argument); > }; > > > /* Construct the hash table. The only useful operation next is create. */ > > -template +template template class Allocator> > inline > -hash_table ::hash_table () > +hash_table ::hash_table () > : htab (NULL) > { > } > @@ -259,10 +417,10 @@ hash_table ::hash_tabl > > /* See if the table has been created, as opposed to constructed. */ > > -template +template template class Allocator> > inline bool > -hash_table ::is_created () > +hash_table ::is_created () > { > return htab != NULL; > } > @@ -270,45 +428,44 @@ hash_table ::is_create > > /* Like find_with_hash, but compute the hash value from the element. */ > > -template +template template class Allocator> > -inline typename Descr::T * > -hash_table ::find (const T *comparable) > +inline typename Descriptor::value_type * > +hash_table ::find (const compare_type *comparable) > { > - return find_with_hash (comparable, Descr::hash (comparable)); > + return find_with_hash (comparable, Descriptor::hash (comparable)); > } > > > /* Like find_slot_with_hash, but compute the hash value from the element. */ > > -template +template template class Allocator> > -inline typename Descr::T ** > -hash_table > -::find_slot (const T *comparable, enum insert_option insert) > +inline typename Descriptor::value_type ** > +hash_table > +::find_slot (const compare_type *comparable, enum insert_option insert) > { > - return find_slot_with_hash (comparable, Descr::hash (comparable), insert); > + return find_slot_with_hash (comparable, Descriptor::hash > (comparable), insert); > } > > > /* Like remove_elt_with_hash, but compute the hash value from the element. */ > > -template +template template class Allocator> > inline void > -hash_table > -::remove_elt (const T *comparable) > +hash_table ::remove_elt (const compare_type *comparable) > { > - remove_elt_with_hash (comparable, Descr::hash (comparable)); > + remove_elt_with_hash (comparable, Descriptor::hash (comparable)); > } > > > /* Return the current size of this hash table. */ > > -template +template template class Allocator> > inline size_t > -hash_table ::size() > +hash_table ::size() > { > return htab->size; > } > @@ -316,10 +473,10 @@ hash_table ::size() > > /* Return the current number of elements in this hash table. */ > > -template +template template class Allocator> > inline size_t > -hash_table ::elements() > +hash_table ::elements() > { > return htab->n_elements - htab->n_deleted; > } > @@ -328,10 +485,10 @@ hash_table ::elements( > /* Return the fraction of fixed collisions during all work with given > hash table. */ > > -template +template template class Allocator> > inline double > -hash_table ::collisions() > +hash_table ::collisions() > { > if (htab->searches == 0) > return 0.0; > @@ -342,19 +499,19 @@ hash_table ::collision > > /* Create a hash table with at least the given number of INITIAL_SLOTS. */ > > -template +template template class Allocator> > void > -hash_table ::create (size_t size) > +hash_table ::create (size_t size) > { > unsigned int size_prime_index; > > size_prime_index = hash_table_higher_prime_index (size); > size = prime_tab[size_prime_index].prime; > > - htab = Allocator > ::control_alloc (1); > + htab = Allocator > ::control_alloc (1); > gcc_assert (htab != NULL); > - htab->entries = Allocator ::data_alloc (size); > + htab->entries = Allocator ::data_alloc (size); > gcc_assert (htab->entries != NULL); > htab->size = size; > htab->size_prime_index = size_prime_index; > @@ -364,20 +521,20 @@ hash_table ::create (s > /* 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 +template template class Allocator> > void > -hash_table ::dispose () > +hash_table ::dispose () > { > size_t size = htab->size; > - T **entries = htab->entries; > + value_type **entries = htab->entries; > > for (int i = size - 1; i >= 0; i--) > if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) > - Descr::remove (entries[i]); > + Descriptor::remove (entries[i]); > > - Allocator ::data_free (entries); > - Allocator > ::control_free (htab); > + Allocator ::data_free (entries); > + Allocator > ::control_free (htab); > htab = NULL; > } > > @@ -389,15 +546,14 @@ hash_table ::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 +template template class Allocator> > -typename Descr::T ** > -hash_table > -::find_empty_slot_for_expand (hashval_t hash) > +typename Descriptor::value_type ** > +hash_table ::find_empty_slot_for_expand (hashval_t hash) > { > hashval_t index = hash_table_mod1 (hash, htab->size_prime_index); > size_t size = htab->size; > - T **slot = htab->entries + index; > + value_type **slot = htab->entries + index; > hashval_t hash2; > > if (*slot == HTAB_EMPTY_ENTRY) > @@ -428,15 +584,15 @@ hash_table > table entries is changed. If memory allocation fails, this function > will abort. */ > > -template +template template class Allocator> > void > -hash_table ::expand () > +hash_table ::expand () > { > - T **oentries; > - T **olimit; > - T **p; > - T **nentries; > + value_type **oentries; > + value_type **olimit; > + value_type **p; > + value_type **nentries; > size_t nsize, osize, elts; > unsigned int oindex, nindex; > > @@ -459,7 +615,7 @@ hash_table ::expand () > nsize = osize; > } > > - nentries = Allocator ::data_alloc (nsize); > + nentries = Allocator ::data_alloc (nsize); > gcc_assert (nentries != NULL); > htab->entries = nentries; > htab->size = nsize; > @@ -470,11 +626,11 @@ hash_table ::expand () > p = oentries; > do > { > - T *x = *p; > + value_type *x = *p; > > if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) > { > - T **q = find_empty_slot_for_expand (Descr::hash (x)); > + value_type **q = find_empty_slot_for_expand (Descriptor::hash (x)); > > *q = x; > } > @@ -483,7 +639,7 @@ hash_table ::expand () > } > while (p < olimit); > > - Allocator ::data_free (oentries); > + Allocator ::data_free (oentries); > } > > > @@ -491,15 +647,15 @@ hash_table ::expand () > COMPARABLE element starting with the given HASH value. It cannot > be used to insert or delete an element. */ > > -template +template template class Allocator> > -typename Descr::T * > -hash_table > -::find_with_hash (const T *comparable, hashval_t hash) > +typename Descriptor::value_type * > +hash_table > +::find_with_hash (const compare_type *comparable, hashval_t hash) > { > hashval_t index, hash2; > size_t size; > - T *entry; > + value_type *entry; > > htab->searches++; > size = htab->size; > @@ -507,7 +663,7 @@ hash_table > > entry = htab->entries[index]; > if (entry == HTAB_EMPTY_ENTRY > - || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry, comparable))) > + || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, > comparable))) > return entry; > > hash2 = hash_table_mod2 (hash, htab->size_prime_index); > @@ -520,7 +676,8 @@ hash_table > > entry = htab->entries[index]; > if (entry == HTAB_EMPTY_ENTRY > - || (entry != HTAB_DELETED_ENTRY && Descr::equal (entry, comparable))) > + || (entry != HTAB_DELETED_ENTRY > + && Descriptor::equal (entry, comparable))) > return entry; > } > } > @@ -534,17 +691,17 @@ hash_table > write the value you want into the returned slot. When inserting an > entry, NULL may be returned if memory allocation fails. */ > > -template +template template class Allocator> > -typename Descr::T ** > -hash_table > -::find_slot_with_hash (const T *comparable, hashval_t hash, > +typename Descriptor::value_type ** > +hash_table > +::find_slot_with_hash (const compare_type *comparable, hashval_t hash, > enum insert_option insert) > { > - T **first_deleted_slot; > + value_type **first_deleted_slot; > hashval_t index, hash2; > size_t size; > - T *entry; > + value_type *entry; > > size = htab->size; > if (insert == INSERT && size * 3 <= htab->n_elements * 4) > @@ -563,9 +720,9 @@ hash_table > goto empty_entry; > else if (entry == HTAB_DELETED_ENTRY) > first_deleted_slot = &htab->entries[index]; > - else if (Descr::equal (entry, comparable)) > + else if (Descriptor::equal (entry, comparable)) > return &htab->entries[index]; > - > + > hash2 = hash_table_mod2 (hash, htab->size_prime_index); > for (;;) > { > @@ -573,7 +730,7 @@ hash_table > index += hash2; > if (index >= size) > index -= size; > - > + > entry = htab->entries[index]; > if (entry == HTAB_EMPTY_ENTRY) > goto empty_entry; > @@ -582,7 +739,7 @@ hash_table > if (!first_deleted_slot) > first_deleted_slot = &htab->entries[index]; > } > - else if (Descr::equal (entry, comparable)) > + else if (Descriptor::equal (entry, comparable)) > return &htab->entries[index]; > } > > @@ -593,7 +750,7 @@ hash_table > if (first_deleted_slot) > { > htab->n_deleted--; > - *first_deleted_slot = static_cast (HTAB_EMPTY_ENTRY); > + *first_deleted_slot = static_cast (HTAB_EMPTY_ENTRY); > return first_deleted_slot; > } > > @@ -604,18 +761,18 @@ hash_table > > /* This function clears all entries in the given hash table. */ > > -template +template template class Allocator> > void > -hash_table ::empty () > +hash_table ::empty () > { > size_t size = htab->size; > - T **entries = htab->entries; > + value_type **entries = htab->entries; > int i; > > for (i = size - 1; i >= 0; i--) > if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) > - Descr::remove (entries[i]); > + Descriptor::remove (entries[i]); > > /* Instead of clearing megabyte, downsize the table. */ > if (size > 1024*1024 / sizeof (PTR)) > @@ -623,13 +780,13 @@ hash_table ::empty () > int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); > int nsize = prime_tab[nindex].prime; > > - Allocator ::data_free (htab->entries); > - htab->entries = Allocator ::data_alloc (nsize); > + Allocator ::data_free (htab->entries); > + htab->entries = Allocator ::data_alloc (nsize); > htab->size = nsize; > htab->size_prime_index = nindex; > } > else > - memset (entries, 0, size * sizeof (T *)); > + memset (entries, 0, size * sizeof (value_type *)); > htab->n_deleted = 0; > htab->n_elements = 0; > } > @@ -639,19 +796,18 @@ hash_table ::empty () > useful when you've already done the lookup and don't want to do it > again. */ > > -template +template template class Allocator> > void > -hash_table > -::clear_slot (T **slot) > +hash_table ::clear_slot (value_type **slot) > { > if (slot < htab->entries || slot >= htab->entries + htab->size > || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) > abort (); > > - Descr::remove (*slot); > + Descriptor::remove (*slot); > > - *slot = static_cast (HTAB_DELETED_ENTRY); > + *slot = static_cast (HTAB_DELETED_ENTRY); > htab->n_deleted++; > } > > @@ -660,21 +816,21 @@ hash_table > from hash table starting with the given HASH. If there is no > matching element in the hash table, this function does nothing. */ > > -template +template template class Allocator> > void > -hash_table > -::remove_elt_with_hash (const T *comparable, hashval_t hash) > +hash_table > +::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) > { > - T **slot; > + value_type **slot; > > slot = find_slot_with_hash (comparable, hash, NO_INSERT); > if (*slot == HTAB_EMPTY_ENTRY) > return; > > - Descr::remove (*slot); > + Descriptor::remove (*slot); > > - *slot = static_cast (HTAB_DELETED_ENTRY); > + *slot = static_cast (HTAB_DELETED_ENTRY); > htab->n_deleted++; > } > > @@ -683,23 +839,22 @@ hash_table > each live entry. If CALLBACK returns false, the iteration stops. > ARGUMENT is passed as CALLBACK's second argument. */ > > -template +template template class Allocator> > template - int (*Callback) (typename Descr::T **slot, Argument argument)> > + int (*Callback) (typename Descriptor::value_type **slot, Argument argument)> > void > -hash_table > -::traverse_noresize (Argument argument) > +hash_table ::traverse_noresize (Argument argument) > { > - T **slot; > - T **limit; > + value_type **slot; > + value_type **limit; > > slot = htab->entries; > limit = slot + htab->size; > > do > { > - T *x = *slot; > + value_type *x = *slot; > > if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) > if (! Callback (slot, argument)) > @@ -712,13 +867,13 @@ hash_table > /* Like traverse_noresize, but does resize the table when it is too empty > to improve effectivity of subsequent calls. */ > > -template +template template class Allocator> > template - int (*Callback) (typename Descr::T **slot, Argument argument)> > + int (*Callback) (typename Descriptor::value_type **slot, > + Argument argument)> > void > -hash_table > -::traverse (Argument argument) > +hash_table ::traverse (Argument argument) > { > size_t size = htab->size; > if (elements () * 8 < size && size > 32) > Index: gcc/alloc-pool.c > =================================================================== > --- gcc/alloc-pool.c (revision 192820) > +++ gcc/alloc-pool.c (working copy) > @@ -22,7 +22,7 @@ along with GCC; see the file COPYING3. > #include "config.h" > #include "system.h" > #include "alloc-pool.h" > -#include "hashtab.h" > +#include "hash-table.h" > > #define align_eight(x) (((x+7) >> 3) << 3) > > @@ -83,38 +83,42 @@ struct alloc_pool_descriptor > int elt_size; > }; > > +struct alloc_pool_hasher : typed_noop_remove > +{ > + typedef alloc_pool_descriptor value_type; > + typedef char compare_type; > + static inline hashval_t hash (const alloc_pool_descriptor *); > + static inline bool equal (const value_type *, const compare_type *); > +}; > + > /* Hashtable mapping alloc_pool names to descriptors. */ > -static htab_t alloc_pool_hash; > +static hash_table alloc_pool_hash; > > /* Hashtable helpers. */ > -static hashval_t > -hash_descriptor (const void *p) > +inline hashval_t > +alloc_pool_hasher::hash (const value_type *d) > { > - const struct alloc_pool_descriptor *const d = > - (const struct alloc_pool_descriptor * )p; > return htab_hash_pointer (d->name); > } > -static int > -eq_descriptor (const void *p1, const void *p2) > + > +inline bool > +alloc_pool_hasher::equal (const value_type *d, > + const compare_type *p2) > { > - const struct alloc_pool_descriptor *const d = > - (const struct alloc_pool_descriptor *) p1; > return d->name == p2; > } > > /* For given name, return descriptor, create new if needed. */ > static struct alloc_pool_descriptor * > -alloc_pool_descriptor (const char *name) > +allocate_pool_descriptor (const char *name) > { > struct alloc_pool_descriptor **slot; > > - if (!alloc_pool_hash) > - alloc_pool_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL); > + if (!alloc_pool_hash.is_created ()) > + alloc_pool_hash.create (10); > > - slot = (struct alloc_pool_descriptor **) > - htab_find_slot_with_hash (alloc_pool_hash, name, > - htab_hash_pointer (name), > - INSERT); > + slot = alloc_pool_hash.find_slot_with_hash (name, > + htab_hash_pointer (name), INSERT); > if (*slot) > return *slot; > *slot = XCNEW (struct alloc_pool_descriptor); > @@ -158,7 +162,7 @@ create_alloc_pool (const char *name, siz > > if (GATHER_STATISTICS) > { > - struct alloc_pool_descriptor *desc = alloc_pool_descriptor (name); > + struct alloc_pool_descriptor *desc = allocate_pool_descriptor (name); > desc->elt_size = size; > desc->created++; > } > @@ -205,7 +209,7 @@ empty_alloc_pool (alloc_pool pool) > > if (GATHER_STATISTICS) > { > - struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); > + struct alloc_pool_descriptor *desc = allocate_pool_descriptor > (pool->name); > desc->current -= (pool->elts_allocated - pool->elts_free) * > pool->elt_size; > } > > @@ -253,7 +257,7 @@ pool_alloc (alloc_pool pool) > > if (GATHER_STATISTICS) > { > - struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); > + struct alloc_pool_descriptor *desc = allocate_pool_descriptor > (pool->name); > > desc->allocated += pool->elt_size; > desc->current += pool->elt_size; > @@ -357,7 +361,7 @@ pool_free (alloc_pool pool, void *ptr) > > if (GATHER_STATISTICS) > { > - struct alloc_pool_descriptor *desc = alloc_pool_descriptor (pool->name); > + struct alloc_pool_descriptor *desc = allocate_pool_descriptor > (pool->name); > desc->current -= pool->elt_size; > } > } > @@ -371,19 +375,20 @@ struct output_info > unsigned long total_allocated; > }; > > -/* Called via htab_traverse. Output alloc_pool descriptor pointed out by SLOT > - and update statistics. */ > -static int > -print_statistics (void **slot, void *b) > +/* Called via hash_table.traverse. Output alloc_pool descriptor pointed out by > + SLOT and update statistics. */ > +int > +print_alloc_pool_statistics (alloc_pool_descriptor **slot, > + struct output_info *i) > { > - struct alloc_pool_descriptor *d = (struct alloc_pool_descriptor *) *slot; > - struct output_info *i = (struct output_info *) b; > + struct alloc_pool_descriptor *d = *slot; > > if (d->allocated) > { > - fprintf (stderr, "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) > %10lu(%10lu)\n", d->name, > - d->elt_size, d->created, d->allocated, d->allocated / d->elt_size, > - d->peak, d->peak / d->elt_size, > + fprintf (stderr, > + "%-22s %6d %10lu %10lu(%10lu) %10lu(%10lu) %10lu(%10lu)\n", > + d->name, d->elt_size, d->created, d->allocated, > + d->allocated / d->elt_size, d->peak, d->peak / d->elt_size, > d->current, d->current / d->elt_size); > i->total_allocated += d->allocated; > i->total_created += d->created; > @@ -400,14 +405,15 @@ dump_alloc_pool_statistics (void) > if (! GATHER_STATISTICS) > return; > > - if (!alloc_pool_hash) > + if (!alloc_pool_hash.is_created ()) > return; > > fprintf (stderr, "\nAlloc-pool Kind Elt size Pools > Allocated (elts) Peak (elts) Leak (elts)\n"); > fprintf (stderr, > "--------------------------------------------------------------------------------------------------------------\n"); > info.total_created = 0; > info.total_allocated = 0; > - htab_traverse (alloc_pool_hash, print_statistics, &info); > + alloc_pool_hash.traverse + print_alloc_pool_statistics> (&info); > fprintf (stderr, > "--------------------------------------------------------------------------------------------------------------\n"); > fprintf (stderr, "%-22s %7lu %10lu\n", > "Total", info.total_created, info.total_allocated); > Index: gcc/dse.c > =================================================================== > --- gcc/dse.c (revision 192820) > +++ gcc/dse.c (working copy) > @@ -654,19 +654,21 @@ clear_alias_set_lookup (alias_set_type a > > struct invariant_group_base_hasher : typed_noop_remove > { > - typedef group_info T; > - static inline hashval_t hash (const T *); > - static inline bool equal (const T *, const T *); > + typedef group_info value_type; > + typedef group_info compare_type; > + static inline hashval_t hash (const value_type *); > + static inline bool equal (const value_type *, const compare_type *); > }; > > inline bool > -invariant_group_base_hasher::equal (const T *gi1, const T *gi2) > +invariant_group_base_hasher::equal (const value_type *gi1, > + const compare_type *gi2) > { > return rtx_equal_p (gi1->rtx_base, gi2->rtx_base); > } > > inline hashval_t > -invariant_group_base_hasher::hash (const T *gi) > +invariant_group_base_hasher::hash (const value_type *gi) > { > int do_not_record; > return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false); > Index: gcc/tree-ssa-coalesce.c > =================================================================== > --- gcc/tree-ssa-coalesce.c (revision 192820) > +++ gcc/tree-ssa-coalesce.c (working copy) > @@ -1261,9 +1261,10 @@ coalesce_partitions (var_map map, ssa_co > > struct ssa_name_var_hash : typed_noop_remove > { > - typedef union tree_node T; > - static inline hashval_t hash (const_tree); > - static inline int equal (const_tree, const_tree); > + typedef union tree_node value_type; > + typedef union tree_node compare_type; > + static inline hashval_t hash (const value_type *); > + static inline int equal (const value_type *, const compare_type *); > }; > > inline hashval_t > @@ -1273,7 +1274,7 @@ ssa_name_var_hash::hash (const_tree n) > } > > inline int > -ssa_name_var_hash::equal (const_tree n1, const_tree n2) > +ssa_name_var_hash::equal (const value_type *n1, const compare_type *n2) > { > return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); > } > Index: gcc/coverage.c > =================================================================== > --- gcc/coverage.c (revision 192820) > +++ gcc/coverage.c (working copy) > @@ -79,10 +79,11 @@ typedef struct counts_entry > struct gcov_ctr_summary summary; > > /* hash_table support. */ > - typedef counts_entry T; > - static inline hashval_t hash (const counts_entry *); > - static int equal (const counts_entry *, const counts_entry *); > - static void remove (counts_entry *); > + typedef counts_entry value_type; > + typedef counts_entry compare_type; > + static inline hashval_t hash (const value_type *); > + static int equal (const value_type *, const compare_type *); > + static void remove (value_type *); > } counts_entry_t; > > static GTY(()) struct coverage_data *functions_head = 0; > @@ -150,20 +151,20 @@ get_gcov_unsigned_t (void) > } > > inline hashval_t > -counts_entry::hash (const counts_entry_t *entry) > +counts_entry::hash (const value_type *entry) > { > return entry->ident * GCOV_COUNTERS + entry->ctr; > } > > inline int > -counts_entry::equal (const counts_entry_t *entry1, > - const counts_entry_t *entry2) > +counts_entry::equal (const value_type *entry1, > + const compare_type *entry2) > { > return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr; > } > > inline void > -counts_entry::remove (counts_entry_t *entry) > +counts_entry::remove (value_type *entry) > { > free (entry->counts); > free (entry); > Index: gcc/tree-ssa-pre.c > =================================================================== > --- gcc/tree-ssa-pre.c (revision 192820) > +++ gcc/tree-ssa-pre.c (working copy) > @@ -173,7 +173,8 @@ typedef struct pre_expr_d : typed_noop_r > pre_expr_union u; > > /* hash_table support. */ > - typedef pre_expr_d T; > + typedef pre_expr_d value_type; > + typedef pre_expr_d compare_type; > static inline hashval_t hash (const pre_expr_d *); > static inline int equal (const pre_expr_d *, const pre_expr_d *); > } *pre_expr; > @@ -186,7 +187,7 @@ typedef struct pre_expr_d : typed_noop_r > /* Compare E1 and E1 for equality. */ > > inline int > -pre_expr_d::equal (const struct pre_expr_d *e1, const struct pre_expr_d *e2) > +pre_expr_d::equal (const value_type *e1, const compare_type *e2) > { > if (e1->kind != e2->kind) > return false; > @@ -211,7 +212,7 @@ pre_expr_d::equal (const struct pre_expr > /* Hash E. */ > > inline hashval_t > -pre_expr_d::hash (const struct pre_expr_d *e) > +pre_expr_d::hash (const value_type *e) > { > switch (e->kind) > { > @@ -499,9 +500,10 @@ typedef struct expr_pred_trans_d : typed > hashval_t hashcode; > > /* hash_table support. */ > - typedef expr_pred_trans_d T; > - static inline hashval_t hash (const expr_pred_trans_d *); > - static inline int equal (const expr_pred_trans_d *, const > expr_pred_trans_d *); > + typedef expr_pred_trans_d value_type; > + typedef expr_pred_trans_d compare_type; > + static inline hashval_t hash (const value_type *); > + static inline int equal (const value_type *, const compare_type *); > } *expr_pred_trans_t; > typedef const struct expr_pred_trans_d *const_expr_pred_trans_t; > > @@ -512,8 +514,8 @@ expr_pred_trans_d::hash (const expr_pred > } > > inline int > -expr_pred_trans_d::equal (const expr_pred_trans_d *ve1, > - const expr_pred_trans_d *ve2) > +expr_pred_trans_d::equal (const value_type *ve1, > + const compare_type *ve2) > { > basic_block b1 = ve1->pred; > basic_block b2 = ve2->pred; > > -- > Lawrence Crowl