diff options
Diffstat (limited to 'gcc/hash-table.h')
| -rw-r--r-- | gcc/hash-table.h | 590 |
1 files changed, 27 insertions, 563 deletions
diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 447eaff1b1c..f6375d1ec71 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -278,7 +278,6 @@ struct pointer_hash : typed_noop_remove <Type> { typedef Type *value_type; typedef Type *compare_type; - typedef int store_values_directly; static inline hashval_t hash (const value_type &); @@ -310,7 +309,6 @@ struct ggc_hasher { typedef T value_type; typedef T compare_type; - typedef int store_values_directly; static void remove (T) {} @@ -342,7 +340,6 @@ struct ggc_cache_hasher { typedef T value_type; typedef T compare_type; - typedef int store_values_directly; static void remove (T &) {} @@ -438,26 +435,6 @@ hash_table_mod2 (hashval_t hash, unsigned int index) return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift); } -/* The below is some template meta programming to decide if we should use the - hash table partial specialization that directly stores value_type instead of - pointers to value_type. If the Descriptor type defines the type - Descriptor::store_values_directly then values are stored directly otherwise - pointers to them are stored. */ -template<typename T> struct notype { typedef void type; }; - -template<typename T, typename = void> -struct storage_tester -{ - static const bool value = false; -}; - -template<typename T> -struct storage_tester<T, typename notype<typename - T::store_values_directly>::type> -{ - static const bool value = true; -}; - template<typename Traits> struct has_is_deleted { @@ -576,9 +553,7 @@ struct mark_empty_helper<Type *, Traits, false> /* User-facing hash table type. - The table stores elements of type Descriptor::value_type, or pointers to - objects of type value_type if the descriptor does not define the type - store_values_directly. + The table stores elements of type Descriptor::value_type. It hashes values with the hash member function. The table currently works with relatively weak hash functions. @@ -601,518 +576,9 @@ struct mark_empty_helper<Type *, Traits, false> */ template <typename Descriptor, - template<typename Type> class Allocator= xcallocator, - bool Storage = storage_tester<Descriptor>::value> + template<typename Type> class Allocator = xcallocator> class hash_table { -}; - -template <typename Descriptor, - template<typename Type> class Allocator> -class hash_table<Descriptor, Allocator, false> -{ - typedef typename Descriptor::value_type value_type; - typedef typename Descriptor::compare_type compare_type; - -public: - hash_table (size_t CXX_MEM_STAT_INFO); - ~hash_table (); - - /* Current size (in entries) of the hash table. */ - size_t size () const { return m_size; } - - /* Return the current number of elements in this hash table. */ - size_t elements () const { return m_n_elements - m_n_deleted; } - - /* Return the current number of elements in this hash table. */ - size_t elements_with_deleted () const { return m_n_elements; } - - /* This function clears all entries in the given hash table. */ - void empty (); - - /* This function clears a specified SLOT in a hash table. It is - useful when you've already done the lookup and don't want to do it - again. */ - - void clear_slot (value_type **); - - /* This function searches for a hash table entry equal to the given - COMPARABLE element starting with the given HASH value. It cannot - be used to insert or delete an element. */ - value_type *find_with_hash (const compare_type *, hashval_t); - -/* Like find_slot_with_hash, but compute the hash value from the element. */ - value_type *find (const value_type *value) - { - return find_with_hash (value, Descriptor::hash (value)); - } - - value_type **find_slot (const value_type *value, insert_option insert) - { - return find_slot_with_hash (value, Descriptor::hash (value), insert); - } - - /* This function searches for a hash table slot containing an entry - equal to the given COMPARABLE element and starting with the given - HASH. To delete an entry, call this with insert=NO_INSERT, then - call clear_slot on the slot returned (possibly after doing some - checks). To insert an entry, call this with insert=INSERT, then - write the value you want into the returned slot. When inserting an - entry, NULL may be returned if memory allocation fails. */ - value_type **find_slot_with_hash (const compare_type *comparable, - hashval_t hash, enum insert_option insert); - - /* This function deletes an element with the given COMPARABLE value - from hash table starting with the given HASH. If there is no - matching element in the hash table, this function does nothing. */ - void remove_elt_with_hash (const compare_type *, hashval_t); - -/* Like remove_elt_with_hash, but compute the hash value from the element. */ - void remove_elt (const value_type *value) - { - remove_elt_with_hash (value, Descriptor::hash (value)); - } - - /* This function scans over the entire hash table calling CALLBACK for - each live entry. If CALLBACK returns false, the iteration stops. - ARGUMENT is passed as CALLBACK's second argument. */ - template <typename Argument, - int (*Callback) (value_type **slot, Argument argument)> - void traverse_noresize (Argument argument); - - /* Like traverse_noresize, but does resize the table when it is too empty - to improve effectivity of subsequent calls. */ - template <typename Argument, - int (*Callback) (value_type **slot, Argument argument)> - void traverse (Argument argument); - - class iterator - { - public: - iterator () : m_slot (NULL), m_limit (NULL) {} - - iterator (value_type **slot, value_type **limit) : - m_slot (slot), m_limit (limit) {} - - inline value_type *operator * () { return *m_slot; } - void slide (); - inline iterator &operator ++ (); - bool operator != (const iterator &other) const - { - return m_slot != other.m_slot || m_limit != other.m_limit; - } - - private: - value_type **m_slot; - value_type **m_limit; - }; - - iterator begin () const - { - iterator iter (m_entries, m_entries + m_size); - iter.slide (); - return iter; - } - - iterator end () const { return iterator (); } - - double collisions () const - { - return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; - } - -private: - - value_type **find_empty_slot_for_expand (hashval_t); - void expand (); - - /* Table itself. */ - typename Descriptor::value_type **m_entries; - - size_t m_size; - - /* Current number of elements including also deleted elements. */ - size_t m_n_elements; - - /* Current number of deleted elements in the table. */ - size_t m_n_deleted; - - /* The following member is used for debugging. Its value is number - of all calls of `htab_find_slot' for the hash table. */ - unsigned int m_searches; - - /* The following member is used for debugging. Its value is number - of collisions fixed for time of work with the hash table. */ - unsigned int m_collisions; - - /* Current size (in entries) of the hash table, as an index into the - table of primes. */ - unsigned int m_size_prime_index; -}; - -template<typename Descriptor, template<typename Type> class Allocator> -hash_table<Descriptor, Allocator, false>::hash_table (size_t size - MEM_STAT_DECL) : - m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0) -{ - unsigned int size_prime_index; - - size_prime_index = hash_table_higher_prime_index (size); - size = prime_tab[size_prime_index].prime; - - m_entries = Allocator <value_type*> ::data_alloc (size); - gcc_assert (m_entries != NULL); - m_size = size; - m_size_prime_index = size_prime_index; -} - -template<typename Descriptor, template<typename Type> class Allocator> -hash_table<Descriptor, Allocator, false>::~hash_table () -{ - for (size_t i = m_size - 1; i < m_size; i--) - if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY) - Descriptor::remove (m_entries[i]); - - Allocator <value_type *> ::data_free (m_entries); -} - -/* Similar to find_slot, but without several unwanted side effects: - - Does not call equal when it finds an existing entry. - - Does not change the count of elements/searches/collisions in the - hash table. - 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 Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, false>::value_type ** -hash_table<Descriptor, Allocator, false> -::find_empty_slot_for_expand (hashval_t hash) -{ - hashval_t index = hash_table_mod1 (hash, m_size_prime_index); - size_t size = m_size; - value_type **slot = m_entries + index; - hashval_t hash2; - - if (*slot == HTAB_EMPTY_ENTRY) - return slot; - gcc_checking_assert (*slot != HTAB_DELETED_ENTRY); - - hash2 = hash_table_mod2 (hash, m_size_prime_index); - for (;;) - { - index += hash2; - if (index >= size) - index -= size; - - slot = m_entries + index; - if (*slot == HTAB_EMPTY_ENTRY) - return slot; - gcc_checking_assert (*slot != HTAB_DELETED_ENTRY); - } -} - -/* The following function changes size of memory allocated for the - entries and repeatedly inserts the table elements. The occupancy - of the table after the call will be about 50%. Naturally the hash - table must already exist. Remember also that the place of the - table entries is changed. If memory allocation fails, this function - will abort. */ - -template<typename Descriptor, template<typename Type> class Allocator> -void -hash_table<Descriptor, Allocator, false>::expand () -{ - value_type **oentries = m_entries; - unsigned int oindex = m_size_prime_index; - size_t osize = size (); - value_type **olimit = oentries + osize; - size_t elts = elements (); - - /* Resize only when table after removal of unused elements is either - too full or too empty. */ - unsigned int nindex; - size_t nsize; - if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) - { - nindex = hash_table_higher_prime_index (elts * 2); - nsize = prime_tab[nindex].prime; - } - else - { - nindex = oindex; - nsize = osize; - } - - value_type **nentries = Allocator <value_type *> ::data_alloc (nsize); - gcc_assert (nentries != NULL); - m_entries = nentries; - m_size = nsize; - m_size_prime_index = nindex; - m_n_elements -= m_n_deleted; - m_n_deleted = 0; - - value_type **p = oentries; - do - { - value_type *x = *p; - - if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) - { - value_type **q = find_empty_slot_for_expand (Descriptor::hash (x)); - - *q = x; - } - - p++; - } - while (p < olimit); - - Allocator <value_type *> ::data_free (oentries); -} - -template<typename Descriptor, template<typename Type> class Allocator> -void -hash_table<Descriptor, Allocator, false>::empty () -{ - size_t size = m_size; - value_type **entries = m_entries; - int i; - - for (i = size - 1; i >= 0; i--) - if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) - Descriptor::remove (entries[i]); - - /* Instead of clearing megabyte, downsize the table. */ - if (size > 1024*1024 / sizeof (PTR)) - { - int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); - int nsize = prime_tab[nindex].prime; - - Allocator <value_type *> ::data_free (m_entries); - m_entries = Allocator <value_type *> ::data_alloc (nsize); - m_size = nsize; - m_size_prime_index = nindex; - } - else - memset (entries, 0, size * sizeof (value_type *)); - m_n_deleted = 0; - m_n_elements = 0; -} - -/* This function clears a specified SLOT in a hash table. It is - useful when you've already done the lookup and don't want to do it - again. */ - -template<typename Descriptor, template<typename Type> class Allocator> -void -hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot) -{ - gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () - || *slot == HTAB_EMPTY_ENTRY - || *slot == HTAB_DELETED_ENTRY)); - - Descriptor::remove (*slot); - - *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); - m_n_deleted++; -} - -/* This function searches for a hash table entry equal to the given - COMPARABLE element starting with the given HASH value. It cannot - be used to insert or delete an element. */ - -template<typename Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, false>::value_type * -hash_table<Descriptor, Allocator, false> -::find_with_hash (const compare_type *comparable, hashval_t hash) -{ - m_searches++; - size_t size = m_size; - hashval_t index = hash_table_mod1 (hash, m_size_prime_index); - - value_type *entry = m_entries[index]; - if (entry == HTAB_EMPTY_ENTRY - || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) - return entry; - - hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); - for (;;) - { - m_collisions++; - index += hash2; - if (index >= size) - index -= size; - - entry = m_entries[index]; - if (entry == HTAB_EMPTY_ENTRY - || (entry != HTAB_DELETED_ENTRY - && Descriptor::equal (entry, comparable))) - return entry; - } -} - -/* This function searches for a hash table slot containing an entry - equal to the given COMPARABLE element and starting with the given - HASH. To delete an entry, call this with insert=NO_INSERT, then - call clear_slot on the slot returned (possibly after doing some - checks). To insert an entry, call this with insert=INSERT, then - write the value you want into the returned slot. When inserting an - entry, NULL may be returned if memory allocation fails. */ - -template<typename Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, false>::value_type ** -hash_table<Descriptor, Allocator, false> -::find_slot_with_hash (const compare_type *comparable, hashval_t hash, - enum insert_option insert) -{ - if (insert == INSERT && m_size * 3 <= m_n_elements * 4) - expand (); - - m_searches++; - - value_type **first_deleted_slot = NULL; - hashval_t index = hash_table_mod1 (hash, m_size_prime_index); - hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); - value_type *entry = m_entries[index]; - size_t size = m_size; - if (entry == HTAB_EMPTY_ENTRY) - goto empty_entry; - else if (entry == HTAB_DELETED_ENTRY) - first_deleted_slot = &m_entries[index]; - else if (Descriptor::equal (entry, comparable)) - return &m_entries[index]; - - for (;;) - { - m_collisions++; - index += hash2; - if (index >= size) - index -= size; - - entry = m_entries[index]; - if (entry == HTAB_EMPTY_ENTRY) - goto empty_entry; - else if (entry == HTAB_DELETED_ENTRY) - { - if (!first_deleted_slot) - first_deleted_slot = &m_entries[index]; - } - else if (Descriptor::equal (entry, comparable)) - return &m_entries[index]; - } - - empty_entry: - if (insert == NO_INSERT) - return NULL; - - if (first_deleted_slot) - { - m_n_deleted--; - *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); - return first_deleted_slot; - } - - m_n_elements++; - return &m_entries[index]; -} - -/* This function deletes an element with the given COMPARABLE value - from hash table starting with the given HASH. If there is no - matching element in the hash table, this function does nothing. */ - -template<typename Descriptor, template<typename Type> class Allocator> -void -hash_table<Descriptor, Allocator, false> -::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) -{ - value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT); - if (*slot == HTAB_EMPTY_ENTRY) - return; - - Descriptor::remove (*slot); - - *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); - m_n_deleted++; -} - -/* This function scans over the entire hash table calling CALLBACK for - each live entry. If CALLBACK returns false, the iteration stops. - ARGUMENT is passed as CALLBACK's second argument. */ - -template<typename Descriptor, template<typename Type> class Allocator> -template<typename Argument, - int (*Callback) (typename hash_table<Descriptor, Allocator, - false>::value_type **slot, - Argument argument)> -void -hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument) -{ - value_type **slot = m_entries; - value_type **limit = slot + size (); - - do - { - value_type *x = *slot; - - if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) - if (! Callback (slot, argument)) - break; - } - while (++slot < limit); -} - -/* Like traverse_noresize, but does resize the table when it is too empty - to improve effectivity of subsequent calls. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -template <typename Argument, - int (*Callback) (typename hash_table<Descriptor, Allocator, - false>::value_type **slot, - Argument argument)> -void -hash_table<Descriptor, Allocator, false>::traverse (Argument argument) -{ - size_t size = m_size; - if (elements () * 8 < size && size > 32) - expand (); - - traverse_noresize <Argument, Callback> (argument); -} - -/* Slide down the iterator slots until an active entry is found. */ - -template<typename Descriptor, template<typename Type> class Allocator> -void -hash_table<Descriptor, Allocator, false>::iterator::slide () -{ - for ( ; m_slot < m_limit; ++m_slot ) - { - value_type *x = *m_slot; - if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) - return; - } - m_slot = NULL; - m_limit = NULL; -} - -/* Bump the iterator. */ - -template<typename Descriptor, template<typename Type> class Allocator> -inline typename hash_table<Descriptor, Allocator, false>::iterator & -hash_table<Descriptor, Allocator, false>::iterator::operator ++ () -{ - ++m_slot; - slide (); - return *this; -} - -/* A partial specialization used when values should be stored directly. */ - -template <typename Descriptor, - template<typename Type> class Allocator> -class hash_table<Descriptor, Allocator, true> -{ typedef typename Descriptor::value_type value_type; typedef typename Descriptor::compare_type compare_type; @@ -1296,7 +762,7 @@ private: }; template<typename Descriptor, template<typename Type> class Allocator> -hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc +hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc MEM_STAT_DECL) : m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0), m_ggc (ggc) @@ -1312,7 +778,7 @@ hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc } template<typename Descriptor, template<typename Type> class Allocator> -hash_table<Descriptor, Allocator, true>::~hash_table () +hash_table<Descriptor, Allocator>::~hash_table () { for (size_t i = m_size - 1; i < m_size; i--) if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i])) @@ -1327,9 +793,8 @@ hash_table<Descriptor, Allocator, true>::~hash_table () /* This function returns an array of empty hash table elements. */ template<typename Descriptor, template<typename Type> class Allocator> -inline typename hash_table<Descriptor, Allocator, true>::value_type * -hash_table<Descriptor, Allocator, true>::alloc_entries - (size_t n MEM_STAT_DECL) const +inline typename hash_table<Descriptor, Allocator>::value_type * +hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const { value_type *nentries; @@ -1353,9 +818,8 @@ hash_table<Descriptor, Allocator, true>::alloc_entries HASH is the hash value for the element to be inserted. */ template<typename Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, true>::value_type * -hash_table<Descriptor, Allocator, true> -::find_empty_slot_for_expand (hashval_t hash) +typename hash_table<Descriptor, Allocator>::value_type * +hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) { hashval_t index = hash_table_mod1 (hash, m_size_prime_index); size_t size = m_size; @@ -1393,7 +857,7 @@ hash_table<Descriptor, Allocator, true> template<typename Descriptor, template<typename Type> class Allocator> void -hash_table<Descriptor, Allocator, true>::expand () +hash_table<Descriptor, Allocator>::expand () { value_type *oentries = m_entries; unsigned int oindex = m_size_prime_index; @@ -1447,7 +911,7 @@ hash_table<Descriptor, Allocator, true>::expand () template<typename Descriptor, template<typename Type> class Allocator> void -hash_table<Descriptor, Allocator, true>::empty () +hash_table<Descriptor, Allocator>::empty () { size_t size = m_size; value_type *entries = m_entries; @@ -1484,7 +948,7 @@ hash_table<Descriptor, Allocator, true>::empty () template<typename Descriptor, template<typename Type> class Allocator> void -hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot) +hash_table<Descriptor, Allocator>::clear_slot (value_type *slot) { gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () || is_empty (*slot) || is_deleted (*slot))); @@ -1500,8 +964,8 @@ hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot) be used to insert or delete an element. */ template<typename Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, true>::value_type & -hash_table<Descriptor, Allocator, true> +typename hash_table<Descriptor, Allocator>::value_type & +hash_table<Descriptor, Allocator> ::find_with_hash (const compare_type &comparable, hashval_t hash) { m_searches++; @@ -1537,8 +1001,8 @@ hash_table<Descriptor, Allocator, true> entry, NULL may be returned if memory allocation fails. */ template<typename Descriptor, template<typename Type> class Allocator> -typename hash_table<Descriptor, Allocator, true>::value_type * -hash_table<Descriptor, Allocator, true> +typename hash_table<Descriptor, Allocator>::value_type * +hash_table<Descriptor, Allocator> ::find_slot_with_hash (const compare_type &comparable, hashval_t hash, enum insert_option insert) { @@ -1599,7 +1063,7 @@ hash_table<Descriptor, Allocator, true> template<typename Descriptor, template<typename Type> class Allocator> void -hash_table<Descriptor, Allocator, true> +hash_table<Descriptor, Allocator> ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) { value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); @@ -1619,11 +1083,11 @@ hash_table<Descriptor, Allocator, true> template<typename Descriptor, template<typename Type> class Allocator> template<typename Argument, - int (*Callback) (typename hash_table<Descriptor, Allocator, - true>::value_type *slot, - Argument argument)> + int (*Callback) + (typename hash_table<Descriptor, Allocator>::value_type *slot, + Argument argument)> void -hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument) +hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument) { value_type *slot = m_entries; value_type *limit = slot + size (); @@ -1645,11 +1109,11 @@ hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument) template <typename Descriptor, template <typename Type> class Allocator> template <typename Argument, - int (*Callback) (typename hash_table<Descriptor, Allocator, - true>::value_type *slot, - Argument argument)> + int (*Callback) + (typename hash_table<Descriptor, Allocator>::value_type *slot, + Argument argument)> void -hash_table<Descriptor, Allocator, true>::traverse (Argument argument) +hash_table<Descriptor, Allocator>::traverse (Argument argument) { size_t size = m_size; if (elements () * 8 < size && size > 32) @@ -1662,7 +1126,7 @@ hash_table<Descriptor, Allocator, true>::traverse (Argument argument) template<typename Descriptor, template<typename Type> class Allocator> void -hash_table<Descriptor, Allocator, true>::iterator::slide () +hash_table<Descriptor, Allocator>::iterator::slide () { for ( ; m_slot < m_limit; ++m_slot ) { @@ -1677,8 +1141,8 @@ hash_table<Descriptor, Allocator, true>::iterator::slide () /* Bump the iterator. */ template<typename Descriptor, template<typename Type> class Allocator> -inline typename hash_table<Descriptor, Allocator, true>::iterator & -hash_table<Descriptor, Allocator, true>::iterator::operator ++ () +inline typename hash_table<Descriptor, Allocator>::iterator & +hash_table<Descriptor, Allocator>::iterator::operator ++ () { ++m_slot; slide (); |