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.
===================================================================
@@ -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;
===================================================================
@@ -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;
===================================================================
@@ -276,19 +276,21 @@ find_classfile (char *filename, JCF *jcf
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;
}
===================================================================
@@ -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);
}
===================================================================
@@ -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);
}
===================================================================
@@ -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;
}
===================================================================
@@ -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 <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_
}
-/* 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 *
{
return ::free (memory);
}
-
+
/* Free memory for data blocks. */
@@ -83,50 +218,71 @@ xcallocator <Type>::data_free (Type *mem
}
-/* 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_tabl
/* 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_create
/* 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>::collision
/* 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 (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 <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)
===================================================================
@@ -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 <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, 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 <struct output_info *,
+ print_alloc_pool_statistics> (&info);
fprintf (stderr,
"--------------------------------------------------------------------------------------------------------------\n");
fprintf (stderr, "%-22s %7lu %10lu\n",
"Total", info.total_created, info.total_allocated);
===================================================================
@@ -654,19 +654,21 @@ clear_alias_set_lookup (alias_set_type a
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);
===================================================================
@@ -1261,9 +1261,10 @@ coalesce_partitions (var_map map, ssa_co
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);
}
===================================================================
@@ -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);
===================================================================
@@ -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)
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? 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;