diff options
Diffstat (limited to 'gcc/hash-table.h')
| -rw-r--r-- | gcc/hash-table.h | 672 |
1 files changed, 232 insertions, 440 deletions
diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 034385c19f2..41cc19e52fb 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -60,12 +60,6 @@ along with GCC; see the file COPYING3. If not see 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. @@ -211,23 +205,11 @@ along with GCC; see the file COPYING3. If not see template <typename Type> struct xcallocator { - static Type *control_alloc (size_t count); static Type *data_alloc (size_t count); - static void control_free (Type *memory); static void data_free (Type *memory); }; -/* Allocate memory for COUNT control blocks. */ - -template <typename Type> -inline Type * -xcallocator <Type>::control_alloc (size_t count) -{ - return static_cast <Type *> (xcalloc (count, sizeof (Type))); -} - - /* Allocate memory for COUNT data blocks. */ template <typename Type> @@ -238,16 +220,6 @@ xcallocator <Type>::data_alloc (size_t count) } -/* Free memory for control blocks. */ - -template <typename Type> -inline void -xcallocator <Type>::control_free (Type *memory) -{ - return ::free (memory); -} - - /* Free memory for data blocks. */ template <typename Type> @@ -348,37 +320,6 @@ extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index); extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index); -/* Internal implementation type. */ - -template <typename T> -struct hash_table_control -{ - /* Table itself. */ - T **entries; - - /* Current size (in entries) of the hash table. */ - size_t size; - - /* Current number of elements including also deleted elements. */ - size_t n_elements; - - /* Current number of deleted elements in the table. */ - size_t 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 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 collisions; - - /* Current size (in entries) of the hash table, as an index into the - table of primes. */ - unsigned int size_prime_index; -}; - - /* User-facing hash table type. The table stores elements of type Descriptor::value_type. @@ -400,213 +341,174 @@ struct hash_table_control The default is xcallocator. */ - template <typename Descriptor, - template <typename Type> class Allocator = xcallocator> + template<typename Type> class Allocator= xcallocator> class hash_table { -public: typedef typename Descriptor::value_type value_type; typedef typename Descriptor::compare_type compare_type; - class iterator - { - public: - inline iterator (); - inline iterator (value_type **, value_type **); - inline value_type &operator * (); - void slide (); - inline iterator &operator ++ (); - inline bool operator != (const iterator &) const; - private: - value_type **m_slot; - value_type **m_limit; - }; - -private: - hash_table_control <value_type> *htab; - - value_type **find_empty_slot_for_expand (hashval_t hash); - void expand (); - public: - hash_table (); - void create (size_t initial_slots); - bool is_created (); - void dispose (); - value_type *find (const value_type *value); - value_type *find_with_hash (const compare_type *comparable, hashval_t hash); - value_type **find_slot (const value_type *value, 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 (value_type **slot); - void remove_elt (const value_type *value); - void remove_elt_with_hash (const compare_type *comparable, hashval_t hash); - size_t size (); - size_t elements (); - size_t elements_with_deleted (); - double collisions (); - - template <typename Argument, - int (*Callback) (value_type **slot, Argument argument)> - void traverse_noresize (Argument argument); - - template <typename Argument, - int (*Callback) (value_type **slot, Argument argument)> - void traverse (Argument argument); + hash_table (size_t); + ~hash_table (); - iterator begin (); - iterator end (); -}; + /* 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; } -/* Construct the hash table. The only useful operation next is create. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline -hash_table <Descriptor, Allocator>::hash_table () -: htab (NULL) -{ -} + /* 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 (); -/* See if the table has been created, as opposed to constructed. */ + /* 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> -inline bool -hash_table <Descriptor, Allocator>::is_created () -{ - return htab != NULL; -} + 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_with_hash, but compute the hash value from the element. */ +/* 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)); + } -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename Descriptor::value_type * -hash_table <Descriptor, Allocator>::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); -/* Like find_slot_with_hash, but compute the hash value from the element. */ + /* 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); -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename Descriptor::value_type ** -hash_table <Descriptor, Allocator> -::find_slot (const value_type *value, enum insert_option insert) -{ - return find_slot_with_hash (value, Descriptor::hash (value), insert); -} +/* 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 remove_elt_with_hash, but compute the hash value from the element. */ + /* 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); -template <typename Descriptor, - template <typename Type> class Allocator> -inline void -hash_table <Descriptor, Allocator>::remove_elt (const value_type *value) -{ - remove_elt_with_hash (value, Descriptor::hash (value)); -} + class iterator + { + public: + iterator () : m_slot (NULL), m_limit (NULL) {} + iterator (value_type **slot, value_type **limit) : + m_slot (slot), m_limit (limit) {} -/* Return the current size of this hash table. */ + 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; + } -template <typename Descriptor, - template <typename Type> class Allocator> -inline size_t -hash_table <Descriptor, Allocator>::size () -{ - return htab->size; -} + private: + value_type **m_slot; + value_type **m_limit; + }; + iterator begin () const + { + iterator iter (m_entries, m_entries + m_size); + iter.slide (); + return iter; + } -/* Return the current number of elements in this hash table. */ + iterator end () const { return iterator (); } -template <typename Descriptor, - template <typename Type> class Allocator> -inline size_t -hash_table <Descriptor, Allocator>::elements () -{ - return htab->n_elements - htab->n_deleted; -} + double collisions () const + { + return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; + } +private: -/* Return the current number of elements in this hash table. */ + value_type **find_empty_slot_for_expand (hashval_t); + void expand (); -template <typename Descriptor, - template <typename Type> class Allocator> -inline size_t -hash_table <Descriptor, Allocator>::elements_with_deleted () -{ - return htab->n_elements; -} + /* Table itself. */ + typename Descriptor::value_type **m_entries; + size_t m_size; - /* Return the fraction of fixed collisions during all work with given - hash table. */ + /* Current number of elements including also deleted elements. */ + size_t m_n_elements; -template <typename Descriptor, - template <typename Type> class Allocator> -inline double -hash_table <Descriptor, Allocator>::collisions () -{ - if (htab->searches == 0) - return 0.0; + /* Current number of deleted elements in the table. */ + size_t m_n_deleted; - return static_cast <double> (htab->collisions) / htab->searches; -} + /* 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; -/* Create a hash table with at least the given number of INITIAL_SLOTS. */ + /* 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> -void -hash_table <Descriptor, Allocator>::create (size_t size) +template<typename Descriptor, template<typename Type> class Allocator> +hash_table<Descriptor, Allocator>::hash_table (size_t size) : + 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; - htab = Allocator <hash_table_control <value_type> > ::control_alloc (1); - gcc_assert (htab != NULL); - htab->entries = Allocator <value_type*> ::data_alloc (size); - gcc_assert (htab->entries != NULL); - htab->size = size; - htab->size_prime_index = size_prime_index; + m_entries = Allocator <value_type*> ::data_alloc (size); + gcc_assert (m_entries != NULL); + m_size = size; + m_size_prime_index = size_prime_index; } - -/* 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 Descriptor, - template <typename Type> class Allocator> -void -hash_table <Descriptor, Allocator>::dispose () +template<typename Descriptor, template<typename Type> class Allocator> +hash_table<Descriptor, Allocator>::~hash_table () { - size_t size = htab->size; - value_type **entries = htab->entries; + 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]); - for (int i = size - 1; i >= 0; i--) - if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) - Descriptor::remove (entries[i]); - - Allocator <value_type *> ::data_free (entries); - Allocator <hash_table_control <value_type> > ::control_free (htab); - htab = NULL; + 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 @@ -614,14 +516,13 @@ hash_table <Descriptor, 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 Descriptor, - template <typename Type> class Allocator> +template<typename Descriptor, template<typename Type> class Allocator> typename Descriptor::value_type ** -hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) +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; - value_type **slot = htab->entries + index; + 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) @@ -629,14 +530,14 @@ hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) else if (*slot == HTAB_DELETED_ENTRY) abort (); - hash2 = hash_table_mod2 (hash, htab->size_prime_index); + hash2 = hash_table_mod2 (hash, m_size_prime_index); for (;;) { index += hash2; if (index >= size) index -= size; - slot = htab->entries + index; + slot = m_entries + index; if (*slot == HTAB_EMPTY_ENTRY) return slot; else if (*slot == HTAB_DELETED_ENTRY) @@ -644,7 +545,6 @@ hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) } } - /* 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 @@ -652,26 +552,20 @@ hash_table <Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) table entries is changed. If memory allocation fails, this function will abort. */ -template <typename Descriptor, - template <typename Type> class Allocator> + template<typename Descriptor, template<typename Type> class Allocator> void -hash_table <Descriptor, Allocator>::expand () +hash_table<Descriptor, Allocator>::expand () { - value_type **oentries; - value_type **olimit; - value_type **p; - value_type **nentries; - size_t nsize, osize, elts; - unsigned int oindex, nindex; - - oentries = htab->entries; - oindex = htab->size_prime_index; - osize = htab->size; - olimit = oentries + osize; - elts = elements (); + 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); @@ -683,15 +577,15 @@ hash_table <Descriptor, Allocator>::expand () nsize = osize; } - nentries = Allocator <value_type *> ::data_alloc (nsize); + value_type **nentries = Allocator <value_type *> ::data_alloc (nsize); gcc_assert (nentries != NULL); - htab->entries = nentries; - htab->size = nsize; - htab->size_prime_index = nindex; - htab->n_elements -= htab->n_deleted; - htab->n_deleted = 0; + m_entries = nentries; + m_size = nsize; + m_size_prime_index = nindex; + m_n_elements -= m_n_deleted; + m_n_deleted = 0; - p = oentries; + value_type **p = oentries; do { value_type *x = *p; @@ -710,39 +604,80 @@ hash_table <Descriptor, Allocator>::expand () Allocator <value_type *> ::data_free (oentries); } +template<typename Descriptor, template<typename Type> class Allocator> +void +hash_table<Descriptor, Allocator>::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>::clear_slot (value_type **slot) +{ + if (slot < m_entries || slot >= m_entries + size () + || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) + abort (); + + 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> +template<typename Descriptor, template<typename Type> class Allocator> typename Descriptor::value_type * -hash_table <Descriptor, Allocator> +hash_table<Descriptor, Allocator> ::find_with_hash (const compare_type *comparable, hashval_t hash) { - hashval_t index, hash2; - size_t size; - value_type *entry; + m_searches++; + size_t size = m_size; + hashval_t index = hash_table_mod1 (hash, m_size_prime_index); - htab->searches++; - size = htab->size; - index = hash_table_mod1 (hash, htab->size_prime_index); - - entry = htab->entries[index]; + value_type *entry = m_entries[index]; if (entry == HTAB_EMPTY_ENTRY || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) return entry; - hash2 = hash_table_mod2 (hash, htab->size_prime_index); + hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); for (;;) { - htab->collisions++; + m_collisions++; index += hash2; if (index >= size) index -= size; - entry = htab->entries[index]; + entry = m_entries[index]; if (entry == HTAB_EMPTY_ENTRY || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) @@ -750,7 +685,6 @@ hash_table <Descriptor, Allocator> } } - /* 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 @@ -759,56 +693,46 @@ hash_table <Descriptor, Allocator> 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> +template<typename Descriptor, template<typename Type> class Allocator> typename Descriptor::value_type ** -hash_table <Descriptor, Allocator> +hash_table<Descriptor, Allocator> ::find_slot_with_hash (const compare_type *comparable, hashval_t hash, enum insert_option insert) { - value_type **first_deleted_slot; - hashval_t index, hash2; - size_t size; - value_type *entry; - - size = htab->size; - if (insert == INSERT && size * 3 <= htab->n_elements * 4) - { - expand (); - size = htab->size; - } - - index = hash_table_mod1 (hash, htab->size_prime_index); + if (insert == INSERT && m_size * 3 <= m_n_elements * 4) + expand (); - htab->searches++; - first_deleted_slot = NULL; + m_searches++; - entry = htab->entries[index]; + 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 = &htab->entries[index]; + first_deleted_slot = &m_entries[index]; else if (Descriptor::equal (entry, comparable)) - return &htab->entries[index]; + return &m_entries[index]; - hash2 = hash_table_mod2 (hash, htab->size_prime_index); for (;;) { - htab->collisions++; + m_collisions++; index += hash2; if (index >= size) index -= size; - entry = htab->entries[index]; + 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 = &htab->entries[index]; + first_deleted_slot = &m_entries[index]; } else if (Descriptor::equal (entry, comparable)) - return &htab->entries[index]; + return &m_entries[index]; } empty_entry: @@ -817,108 +741,47 @@ hash_table <Descriptor, Allocator> if (first_deleted_slot) { - htab->n_deleted--; + m_n_deleted--; *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); return first_deleted_slot; } - htab->n_elements++; - return &htab->entries[index]; -} - - -/* This function clears all entries in the given hash table. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -void -hash_table <Descriptor, Allocator>::empty () -{ - size_t size = htab->size; - 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) - 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 (htab->entries); - htab->entries = Allocator <value_type *> ::data_alloc (nsize); - htab->size = nsize; - htab->size_prime_index = nindex; - } - else - memset (entries, 0, size * sizeof (value_type *)); - htab->n_deleted = 0; - htab->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>::clear_slot (value_type **slot) -{ - if (slot < htab->entries || slot >= htab->entries + htab->size - || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) - abort (); - - Descriptor::remove (*slot); - - *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); - htab->n_deleted++; + 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> +template<typename Descriptor, template<typename Type> class Allocator> void -hash_table <Descriptor, Allocator> +hash_table<Descriptor, Allocator> ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) { - value_type **slot; - - slot = find_slot_with_hash (comparable, hash, NO_INSERT); + 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); - htab->n_deleted++; + 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, +template<typename Descriptor, + template<typename Type> class Allocator> +template<typename Argument, int (*Callback) (typename Descriptor::value_type **slot, Argument argument)> void -hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument) +hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument) { - value_type **slot; - value_type **limit; - - slot = htab->entries; - limit = slot + htab->size; + value_type **slot = m_entries; + value_type **limit = slot + size (); do { @@ -931,7 +794,6 @@ hash_table <Descriptor, Allocator>::traverse_noresize (Argument argument) while (++slot < limit); } - /* Like traverse_noresize, but does resize the table when it is too empty to improve effectivity of subsequent calls. */ @@ -941,55 +803,20 @@ template <typename Argument, int (*Callback) (typename Descriptor::value_type **slot, Argument argument)> void -hash_table <Descriptor, Allocator>::traverse (Argument argument) +hash_table<Descriptor, Allocator>::traverse (Argument argument) { - size_t size = htab->size; + size_t size = m_size; if (elements () * 8 < size && size > 32) expand (); traverse_noresize <Argument, Callback> (argument); } - -/* Iterator definitions. */ - -/* The default constructor produces the end value. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline -hash_table <Descriptor, Allocator>::iterator::iterator () -: m_slot (NULL), m_limit (NULL) -{ -} - -/* The parameterized constructor produces the begin value. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline -hash_table <Descriptor, Allocator>::iterator::iterator - (value_type **slot, value_type **limit) -: m_slot (slot), m_limit (limit) -{ -} - -/* Obtain the element. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename hash_table <Descriptor, Allocator>::value_type & -hash_table <Descriptor, Allocator>::iterator::operator * () -{ - return **m_slot; -} - /* Slide down the iterator slots until an active entry is found. */ -template <typename Descriptor, - template <typename Type> class Allocator> +template<typename Descriptor, template<typename Type> class Allocator> void -hash_table <Descriptor, Allocator>::iterator::slide () +hash_table<Descriptor, Allocator>::iterator::slide () { for ( ; m_slot < m_limit; ++m_slot ) { @@ -1003,50 +830,15 @@ hash_table <Descriptor, Allocator>::iterator::slide () /* Bump the iterator. */ -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename hash_table <Descriptor, Allocator>::iterator & -hash_table <Descriptor, Allocator>::iterator::operator ++ () +template<typename Descriptor, template<typename Type> class Allocator> +inline typename hash_table<Descriptor, Allocator>::iterator & +hash_table<Descriptor, Allocator>::iterator::operator ++ () { ++m_slot; slide (); return *this; } -/* Compare iterators. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline bool -hash_table <Descriptor, Allocator>::iterator:: - operator != (const iterator &other) const -{ - return m_slot != other.m_slot || m_limit != other.m_limit; -} - -/* Hash table iterator producers. */ - -/* The beginning of a hash table iteration. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename hash_table <Descriptor, Allocator>::iterator -hash_table <Descriptor, Allocator>::begin () -{ - iterator hti (htab->entries, htab->entries + htab->size); - hti.slide (); - return hti; -} - -/* The end of a hash table iteration. */ - -template <typename Descriptor, - template <typename Type> class Allocator> -inline typename hash_table <Descriptor, Allocator>::iterator -hash_table <Descriptor, Allocator>::end () -{ - return iterator (); -} /* Iterate through the elements of hash_table HTAB, using hash_table <....>::iterator ITER, |