diff options
| -rw-r--r-- | gcc/ChangeLog | 12 | ||||
| -rw-r--r-- | gcc/alloc-pool.c | 70 | ||||
| -rw-r--r-- | gcc/cfg.c | 12 | ||||
| -rw-r--r-- | gcc/coverage.c | 17 | ||||
| -rw-r--r-- | gcc/dse.c | 12 | ||||
| -rw-r--r-- | gcc/hash-table.h | 429 | ||||
| -rw-r--r-- | gcc/java/jcf-io.c | 12 | ||||
| -rw-r--r-- | gcc/objc/objc-act.c | 11 | ||||
| -rw-r--r-- | gcc/tree-ssa-coalesce.c | 9 | ||||
| -rw-r--r-- | gcc/tree-ssa-pre.c | 18 | ||||
| -rw-r--r-- | gcc/tree-ssa-tail-merge.c | 13 | ||||
| -rw-r--r-- | gcc/tree-ssa-threadupdate.c | 11 | ||||
| -rw-r--r-- | gcc/valtrack.h | 15 |
13 files changed, 414 insertions, 227 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 826a58d..47a7a4e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2012-10-25 Lawrence Crowl <crowl@google.com> + + * 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. + 2012-10-25 Jan Hubicka <jh@suse.cz> * ipa-cp.c (ipcp_discover_new_direct_edges): If something was turned diff --git a/gcc/alloc-pool.c b/gcc/alloc-pool.c index bedcf1f..68d66ee 100644 --- a/gcc/alloc-pool.c +++ b/gcc/alloc-pool.c @@ -22,7 +22,7 @@ along with GCC; see the file COPYING3. If not see #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 <alloc_pool_descriptor> +{ + 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_hasher> 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, size_t size, size_t num) 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 <struct output_info *, + print_alloc_pool_statistics> (&info); fprintf (stderr, "--------------------------------------------------------------------------------------------------------------\n"); fprintf (stderr, "%-22s %7lu %10lu\n", "Total", info.total_created, info.total_allocated); @@ -988,19 +988,21 @@ struct htab_bb_copy_original_entry struct bb_copy_hasher : typed_noop_remove <htab_bb_copy_original_entry> { - 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; } diff --git a/gcc/coverage.c b/gcc/coverage.c index f9b12e8..b634c82 100644 --- a/gcc/coverage.c +++ b/gcc/coverage.c @@ -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); @@ -654,19 +654,21 @@ clear_alias_set_lookup (alias_set_type alias_set) struct invariant_group_base_hasher : typed_noop_remove <group_info> { - 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); diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 3aa66a7..a80100f 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -21,7 +21,142 @@ 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 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 <some_type> + // 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_hasher> 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 <pointer_hash <whatever_type>> whatever_type_hash_table; + +*/ #ifndef TYPED_HASHTAB_H @@ -53,7 +188,7 @@ xcallocator <Type>::control_alloc (size_t count) } -/* Allocate memory for COUNT data blocks. */ +/* Allocate memory for COUNT data blocks. */ template <typename Type> inline Type * @@ -71,7 +206,7 @@ xcallocator <Type>::control_free (Type *memory) { return ::free (memory); } - + /* Free memory for data blocks. */ @@ -83,50 +218,71 @@ xcallocator <Type>::data_free (Type *memory) } -/* Remove method dispatching to free. */ +/* Helpful type for removing with free. */ -template <typename Element> +template <typename Type> struct typed_free_remove { - static inline void remove (Element *p) { free (p); } + static inline void remove (Type *p); }; -/* No-op remove method. */ -template <typename Element> +/* Remove with free. */ + +template <typename Type> +inline void +typed_free_remove <Type>::remove (Type *p) +{ + free (p); +} + + +/* Helpful type for a no-op remove. */ + +template <typename Type> struct typed_noop_remove { - static inline void remove (Element *) {} + static inline void remove (Type *p); }; +/* Remove doing nothing. */ + +template <typename Type> +inline void +typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED) +{ +} + + /* Pointer hash with a no-op remove method. */ -template <typename Element> -struct pointer_hash : typed_noop_remove <Element> +template <typename Type> +struct pointer_hash : typed_noop_remove <Type> { - 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 <typename Element> +template <typename Type> inline hashval_t -pointer_hash<Element>::hash (const T *candidate) +pointer_hash <Type>::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 <typename Element> +template <typename Type> inline int -pointer_hash<Element>::equal (const T *existing, - const T *candidate) +pointer_hash <Type>::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 <Element> when hashing pointers instead of objects. + Use typed_pointer_hash <Value> 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 <Element> when hashing pointers instead of objects. + Use typed_pointer_equal <Value> 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 <Element> when not freeing objects. - Use typed_free_remove <Element> when doing a simple object free. + Derive from typed_null_remove <Value> when not freeing objects. + Derive from typed_free_remove <Value> 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 <typename Descr, +template <typename Descriptor, template <typename Type> 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 <T> *htab; + hash_table_control <value_type> *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 <typename Argument, - int (*Callback) (T **slot, Argument argument)> + int (*Callback) (value_type **slot, Argument argument)> void traverse_noresize (Argument argument); template <typename Argument, - 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 <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline -hash_table <Descr, Allocator>::hash_table () +hash_table <Descriptor, Allocator>::hash_table () : htab (NULL) { } @@ -259,10 +417,10 @@ hash_table <Descr, Allocator>::hash_table () /* See if the table has been created, as opposed to constructed. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline bool -hash_table <Descr, Allocator>::is_created () +hash_table <Descriptor, Allocator>::is_created () { return htab != NULL; } @@ -270,45 +428,44 @@ hash_table <Descr, Allocator>::is_created () /* Like find_with_hash, but compute the hash value from the element. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> -inline typename Descr::T * -hash_table <Descr, Allocator>::find (const T *comparable) +inline typename Descriptor::value_type * +hash_table <Descriptor, Allocator>::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 <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> -inline typename Descr::T ** -hash_table <Descr, Allocator> -::find_slot (const T *comparable, enum insert_option insert) +inline typename Descriptor::value_type ** +hash_table <Descriptor, Allocator> +::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 <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline void -hash_table <Descr, Allocator> -::remove_elt (const T *comparable) +hash_table <Descriptor, Allocator>::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 <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline size_t -hash_table <Descr, Allocator>::size() +hash_table <Descriptor, Allocator>::size() { return htab->size; } @@ -316,10 +473,10 @@ hash_table <Descr, Allocator>::size() /* Return the current number of elements in this hash table. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline size_t -hash_table <Descr, Allocator>::elements() +hash_table <Descriptor, Allocator>::elements() { return htab->n_elements - htab->n_deleted; } @@ -328,10 +485,10 @@ hash_table <Descr, Allocator>::elements() /* Return the fraction of fixed collisions during all work with given hash table. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> inline double -hash_table <Descr, Allocator>::collisions() +hash_table <Descriptor, Allocator>::collisions() { if (htab->searches == 0) return 0.0; @@ -342,19 +499,19 @@ hash_table <Descr, Allocator>::collisions() /* Create a hash table with at least the given number of INITIAL_SLOTS. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator>::create (size_t size) +hash_table <Descriptor, Allocator>::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 <hash_table_control <T> > ::control_alloc (1); + htab = Allocator <hash_table_control <value_type> > ::control_alloc (1); gcc_assert (htab != NULL); - htab->entries = Allocator <T*> ::data_alloc (size); + htab->entries = Allocator <value_type*> ::data_alloc (size); gcc_assert (htab->entries != NULL); htab->size = size; htab->size_prime_index = size_prime_index; @@ -364,20 +521,20 @@ 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 Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator>::dispose () +hash_table <Descriptor, Allocator>::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 <T *> ::data_free (entries); - Allocator <hash_table_control <T> > ::control_free (htab); + Allocator <value_type *> ::data_free (entries); + Allocator <hash_table_control <value_type> > ::control_free (htab); htab = NULL; } @@ -389,15 +546,14 @@ 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 Descriptor, template <typename Type> class Allocator> -typename Descr::T ** -hash_table <Descr, Allocator> -::find_empty_slot_for_expand (hashval_t hash) +typename Descriptor::value_type ** +hash_table <Descriptor, 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; - 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 <Descr, Allocator> table entries is changed. If memory allocation fails, this function will abort. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator>::expand () +hash_table <Descriptor, Allocator>::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 <Descr, Allocator>::expand () nsize = osize; } - nentries = Allocator <T *> ::data_alloc (nsize); + nentries = Allocator <value_type *> ::data_alloc (nsize); gcc_assert (nentries != NULL); htab->entries = nentries; htab->size = nsize; @@ -470,11 +626,11 @@ hash_table <Descr, Allocator>::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 <Descr, Allocator>::expand () } while (p < olimit); - Allocator <T *> ::data_free (oentries); + Allocator <value_type *> ::data_free (oentries); } @@ -491,15 +647,15 @@ 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 Descriptor, template <typename Type> class Allocator> -typename Descr::T * -hash_table <Descr, Allocator> -::find_with_hash (const T *comparable, hashval_t hash) +typename Descriptor::value_type * +hash_table <Descriptor, Allocator> +::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 <Descr, Allocator> 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 <Descr, Allocator> 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 <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 Descriptor, template <typename Type> class Allocator> -typename Descr::T ** -hash_table <Descr, Allocator> -::find_slot_with_hash (const T *comparable, hashval_t hash, +typename Descriptor::value_type ** +hash_table <Descriptor, Allocator> +::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 <Descr, Allocator> 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 <Descr, Allocator> 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 <Descr, Allocator> 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 <Descr, Allocator> if (first_deleted_slot) { htab->n_deleted--; - *first_deleted_slot = static_cast <T *> (HTAB_EMPTY_ENTRY); + *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); return first_deleted_slot; } @@ -604,18 +761,18 @@ hash_table <Descr, Allocator> /* This function clears all entries in the given hash table. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator>::empty () +hash_table <Descriptor, Allocator>::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 <Descr, Allocator>::empty () int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); int nsize = prime_tab[nindex].prime; - Allocator <T *> ::data_free (htab->entries); - htab->entries = Allocator <T *> ::data_alloc (nsize); + Allocator <value_type *> ::data_free (htab->entries); + htab->entries = Allocator <value_type *> ::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 <Descr, Allocator>::empty () useful when you've already done the lookup and don't want to do it again. */ -template <typename Descr, +template <typename Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator> -::clear_slot (T **slot) +hash_table <Descriptor, Allocator>::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 <T *> (HTAB_DELETED_ENTRY); + *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); htab->n_deleted++; } @@ -660,21 +816,21 @@ 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 Descriptor, template <typename Type> class Allocator> void -hash_table <Descr, Allocator> -::remove_elt_with_hash (const T *comparable, hashval_t hash) +hash_table <Descriptor, Allocator> +::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 <T *> (HTAB_DELETED_ENTRY); + *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); htab->n_deleted++; } @@ -683,23 +839,22 @@ 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 Descriptor, template <typename Type> class Allocator> template <typename Argument, - int (*Callback) (typename Descr::T **slot, Argument argument)> + int (*Callback) (typename Descriptor::value_type **slot, Argument argument)> void -hash_table <Descr, Allocator> -::traverse_noresize (Argument argument) +hash_table <Descriptor, Allocator>::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 <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 Descriptor, template <typename Type> class Allocator> template <typename Argument, - int (*Callback) (typename Descr::T **slot, Argument argument)> + int (*Callback) (typename Descriptor::value_type **slot, + Argument argument)> void -hash_table <Descr, Allocator> -::traverse (Argument argument) +hash_table <Descriptor, Allocator>::traverse (Argument argument) { size_t size = htab->size; if (elements () * 8 < size && size > 32) diff --git a/gcc/java/jcf-io.c b/gcc/java/jcf-io.c index 97a3c0f..6a24f78 100644 --- a/gcc/java/jcf-io.c +++ b/gcc/java/jcf-io.c @@ -276,19 +276,21 @@ find_classfile (char *filename, JCF *jcf, const char *dep_name) struct charstar_hash : typed_noop_remove <char> { - 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; } diff --git a/gcc/objc/objc-act.c b/gcc/objc/objc-act.c index cf0cc84..ed1a28f 100644 --- a/gcc/objc/objc-act.c +++ b/gcc/objc/objc-act.c @@ -3827,19 +3827,20 @@ objc_get_class_ivars (tree class_name) struct decl_name_hash : typed_noop_remove <tree_node> { - 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); } diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 6217825..f0d66cc 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -1261,9 +1261,10 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl, struct ssa_name_var_hash : typed_noop_remove <union tree_node> { - 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); } diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index bc3381bd..6a07598 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -173,7 +173,8 @@ typedef struct pre_expr_d : typed_noop_remove <pre_expr_d> 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_remove <pre_expr_d> /* 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_d *e1, const struct pre_expr_d *e2) /* 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_free_remove<expr_pred_trans_d> 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_trans_d *e) } 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; diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c index 79fb1a6..f9dc880 100644 --- a/gcc/tree-ssa-tail-merge.c +++ b/gcc/tree-ssa-tail-merge.c @@ -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 *const_same_succ; /* 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_same_succ e2) /* 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; diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index ad64876..eca88a9 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -127,20 +127,21 @@ struct redirection_data : typed_free_remove<redirection_data> 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; diff --git a/gcc/valtrack.h b/gcc/valtrack.h index 303ffa4..44f2d21 100644 --- a/gcc/valtrack.h +++ b/gcc/valtrack.h @@ -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); } |