CbC/CbC_gcc: gcc/hash-table.h comparison

comparison gcc/hash-table.h @ 145:1830386684a0

gcc-9.2.0

author	anatofuz
date	Thu, 13 Feb 2020 11:34:05 +0900
parents	84e7813d76e9
children

comparison

equal deleted inserted replaced

-:84e7813d76e9
+:1830386684a0
 /* A type-safe hash table template.
-Copyright (C) 2012-2018 Free Software Foundation, Inc.
+Copyright (C) 2012-2020 Free Software Foundation, Inc.
 Contributed by Lawrence Crowl <crowl@google.com>
 This file is part of GCC.
 GCC is free software; you can redistribute it and/or modify it under
 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).
+	 Provided a suitable Descriptor class it may be a user-defined,
+	 non-POD type.
 - A static member function named 'hash' that takes a value_type
 (or 'const value_type &') and returns a hashval_t value.
 - A typedef named 'compare_type' that is used to test when a value
-is found.  This type is the comparison type.  Usually, it will be the
+	 is found.  This type is the comparison type.  Usually, it will be
-same as value_type.  If it is not the same type, you must generally
+	 the same as value_type and may be a user-defined, non-POD type.
-explicitly compute hash values and pass them to the hash table.
+	 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
 and a compare_type, and returns a bool.  Both arguments can be
 const references.
 You can then use 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.
+If a hash table is used only in some rare cases, it is possible
+to construct the hash_table lazily before first use.  This is done
+through:
+hash_table <some_type_hasher, true> some_type_hash_table;
+which will cause whatever methods actually need the allocated entries
+array to allocate it later.
 EASY DESCRIPTORS FOR POINTERS
 There are four descriptors for pointer elements, one for each of
 the removal policies above:
 #include "mem-stats-traits.h"
 #include "hash-traits.h"
 #include "hash-map-traits.h"
 template<typename, typename, typename> class hash_map;
-template<typename, typename> class hash_set;
+template<typename, bool, typename> class hash_set;
 /* The ordinary memory allocator.  */
 /* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
 template <typename Type>
 hashval_t shift;
 };
 extern struct prime_ent const prime_tab[];
+/* Limit number of comparisons when calling hash_table<>::verify.  */
+extern unsigned int hash_table_sanitize_eq_limit;
 /* Functions for computing hash table indexes.  */
 extern unsigned int hash_table_higher_prime_index (unsigned long n)
 ATTRIBUTE_PURE;
+extern ATTRIBUTE_NORETURN ATTRIBUTE_COLD void hashtab_chk_error ();
 /* Return X % Y using multiplicative inverse values INV and SHIFT.
 The multiplicative inverses computed above are for 32-bit types,
 and requires that we be able to compute a highpart multiply.
 Storage is an implementation detail and should not be used outside the
 hash table code.
 */
-template <typename Descriptor,
+template <typename Descriptor, bool Lazy = false,
-	 template<typename Type> class Allocator = xcallocator>
+	  template<typename Type> class Allocator = xcallocator>
 class hash_table
 {
 typedef typename Descriptor::value_type value_type;
 typedef typename Descriptor::compare_type compare_type;
 public:
 explicit hash_table (size_t, bool ggc = false,
+		       bool sanitize_eq_and_hash = true,
 		       bool gather_mem_stats = GATHER_STATISTICS,
 		       mem_alloc_origin origin = HASH_TABLE_ORIGIN
 		       CXX_MEM_STAT_INFO);
 explicit hash_table (const hash_table &, bool ggc = false,
+		       bool sanitize_eq_and_hash = true,
 		       bool gather_mem_stats = GATHER_STATISTICS,
 		       mem_alloc_origin origin = HASH_TABLE_ORIGIN
 		       CXX_MEM_STAT_INFO);
 ~hash_table ();
 /* Create a hash_table in gc memory.  */
 static hash_table *
-create_ggc (size_t n CXX_MEM_STAT_INFO)
+create_ggc (size_t n, bool sanitize_eq_and_hash = true CXX_MEM_STAT_INFO)
 {
 hash_table *table = ggc_alloc<hash_table> ();
-new (table) hash_table (n, true, GATHER_STATISTICS,
+new (table) hash_table (n, true, sanitize_eq_and_hash, GATHER_STATISTICS,
 			    HASH_TABLE_ORIGIN PASS_MEM_STAT);
 return table;
 }
 /* Current size (in entries) of the hash table.  */
 /* 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 this hash table.  */
 void empty () { if (elements ()) empty_slow (); }
+/* Return true when there are no elements in this hash table.  */
+bool is_empty () const { return 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. */
 void clear_slot (value_type *);
 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);
+				   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);
 value_type *m_limit;
 };
 iterator begin () const
 {
+if (Lazy && m_entries == NULL)
+	return iterator ();
 iterator iter (m_entries, m_entries + m_size);
 iter.slide ();
 return iter;
 }
 {
 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0;
 }
 private:
+/* FIXME: Make the class assignable.  See pr90959.  */
+void operator= (hash_table&);
 template<typename T> friend void gt_ggc_mx (hash_table<T> *);
 template<typename T> friend void gt_pch_nx (hash_table<T> *);
 template<typename T> friend void
 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *);
 template<typename T, typename U, typename V> friend void
 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
-template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *,
+template<typename T, typename U>
-							  gt_pointer_operator,
+friend void gt_pch_nx (hash_set<T, false, U> *, gt_pointer_operator, void *);
-							  void *);
 template<typename T> friend void gt_pch_nx (hash_table<T> *,
 					      gt_pointer_operator, void *);
 template<typename T> friend void gt_cleare_cache (hash_table<T> *);
 void empty_slow ();
 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const;
 value_type *find_empty_slot_for_expand (hashval_t);
+void verify (const compare_type &comparable, hashval_t hash);
 bool too_empty_p (unsigned int);
 void expand ();
 static bool is_deleted (value_type &v)
 {
 return Descriptor::is_deleted (v);
 unsigned int m_size_prime_index;
 /* if m_entries is stored in ggc memory.  */
 bool m_ggc;
+/* True if the table should be sanitized for equal and hash functions.  */
+bool m_sanitize_eq_and_hash;
 /* If we should gather memory statistics for the table.  */
+#if GATHER_STATISTICS
 bool m_gather_mem_stats;
+#else
+static const bool m_gather_mem_stats = false;
+#endif
 };
 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include
 mem-stats.h after hash_table declaration.  */
 extern mem_alloc_description<mem_usage>& hash_table_usage (void);
 /* Support function for statistics.  */
 extern void dump_hash_table_loc_statistics (void);
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
-hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool
+	 template<typename Type> class Allocator>
-					       gather_mem_stats,
+hash_table<Descriptor, Lazy, Allocator>::hash_table (size_t size, bool ggc,
-					       mem_alloc_origin origin
+						     bool sanitize_eq_and_hash,
-					       MEM_STAT_DECL) :
+						     bool gather_mem_stats
+						     ATTRIBUTE_UNUSED,
+						     mem_alloc_origin origin
+						     MEM_STAT_DECL) :
 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0),
-m_ggc (ggc), m_gather_mem_stats (gather_mem_stats)
+m_ggc (ggc), m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+#if GATHER_STATISTICS
+, m_gather_mem_stats (gather_mem_stats)
+#endif
 {
 unsigned int size_prime_index;
 size_prime_index = hash_table_higher_prime_index (size);
 size = prime_tab[size_prime_index].prime;
+if (m_gather_mem_stats)
+hash_table_usage ().register_descriptor (this, origin, ggc
+					     FINAL_PASS_MEM_STAT);
+if (Lazy)
+m_entries = NULL;
+else
+m_entries = alloc_entries (size PASS_MEM_STAT);
+m_size = size;
+m_size_prime_index = size_prime_index;
+}
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+hash_table<Descriptor, Lazy, Allocator>::hash_table (const hash_table &h,
+						     bool ggc,
+						     bool sanitize_eq_and_hash,
+						     bool gather_mem_stats
+						     ATTRIBUTE_UNUSED,
+						     mem_alloc_origin origin
+						     MEM_STAT_DECL) :
+m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
+m_searches (0), m_collisions (0), m_ggc (ggc),
+m_sanitize_eq_and_hash (sanitize_eq_and_hash)
+#if GATHER_STATISTICS
+, m_gather_mem_stats (gather_mem_stats)
+#endif
+{
+size_t size = h.m_size;
 if (m_gather_mem_stats)
 hash_table_usage ().register_descriptor (this, origin, ggc
 					  FINAL_PASS_MEM_STAT);
-m_entries = alloc_entries (size PASS_MEM_STAT);
+if (Lazy && h.m_entries == NULL)
-m_size = size;
+m_entries = NULL;
-m_size_prime_index = size_prime_index;
+else
-}
+{
+value_type *nentries = alloc_entries (size PASS_MEM_STAT);
-template<typename Descriptor, template<typename Type> class Allocator>
+for (size_t i = 0; i < size; ++i)
-hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc,
+	{
-					       bool gather_mem_stats,
+	  value_type &entry = h.m_entries[i];
-					       mem_alloc_origin origin
+	  if (is_deleted (entry))
-					       MEM_STAT_DECL) :
+	    mark_deleted (nentries[i]);
-m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted),
+	  else if (!is_empty (entry))
-m_searches (0), m_collisions (0), m_ggc (ggc),
+	    new ((void*) (nentries + i)) value_type (entry);
-m_gather_mem_stats (gather_mem_stats)
+	}
-{
+m_entries = nentries;
-size_t size = h.m_size;
+}
-if (m_gather_mem_stats)
-hash_table_usage ().register_descriptor (this, origin, ggc
-					  FINAL_PASS_MEM_STAT);
-value_type *nentries = alloc_entries (size PASS_MEM_STAT);
-for (size_t i = 0; i < size; ++i)
-{
-value_type &entry = h.m_entries[i];
-if (is_deleted (entry))
-	mark_deleted (nentries[i]);
-else if (!is_empty (entry))
-	nentries[i] = entry;
-}
-m_entries = nentries;
 m_size = size;
 m_size_prime_index = h.m_size_prime_index;
 }
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
-hash_table<Descriptor, Allocator>::~hash_table ()
+	 template<typename Type> class Allocator>
-{
+hash_table<Descriptor, Lazy, 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]))
+if (!Lazy || m_entries)
-Descriptor::remove (m_entries[i]);
+{
+for (size_t i = m_size - 1; i < m_size; i--)
-if (!m_ggc)
+	if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i]))
-Allocator <value_type> ::data_free (m_entries);
+	  Descriptor::remove (m_entries[i]);
-else
-ggc_free (m_entries);
+if (!m_ggc)
+	Allocator <value_type> ::data_free (m_entries);
-if (m_gather_mem_stats)
+else
-hash_table_usage ().release_instance_overhead (this,
+	ggc_free (m_entries);
-						sizeof (value_type) * m_size,
+if (m_gather_mem_stats)
-						true);
+	hash_table_usage ().release_instance_overhead (this,
+						       sizeof (value_type)
+						       * m_size, true);
+}
+else if (m_gather_mem_stats)
+hash_table_usage ().unregister_descriptor (this);
 }
 /* This function returns an array of empty hash table elements.  */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
-inline typename hash_table<Descriptor, Allocator>::value_type *
+	 template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
+inline typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+	   Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const
 {
 value_type *nentries;
 if (m_gather_mem_stats)
 hash_table_usage ().register_instance_overhead (sizeof (value_type) * n, this);
 nentries = Allocator <value_type> ::data_alloc (n);
 else
 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT);
 gcc_assert (nentries != NULL);
-for (size_t i = 0; i < n; i++)
+if (!Descriptor::empty_zero_p)
-mark_empty (nentries[i]);
+for (size_t i = 0; i < n; i++)
+mark_empty (nentries[i]);
 return nentries;
 }
 /* Similar to find_slot, but without several unwanted side effects:
 - 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>
+template<typename Descriptor, bool Lazy,
-typename hash_table<Descriptor, Allocator>::value_type *
+	 template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash)
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy,
+	   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;
 value_type *slot = m_entries + index;
 hashval_t hash2;
 }
 }
 /* Return true if the current table is excessively big for ELTS elements.  */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
 inline bool
-hash_table<Descriptor, Allocator>::too_empty_p (unsigned int elts)
+hash_table<Descriptor, Lazy, Allocator>::too_empty_p (unsigned int elts)
 {
 return elts * 8 < m_size && m_size > 32;
 }
 /* The following function changes size of memory allocated for the
 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>
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::expand ()
+hash_table<Descriptor, Lazy, Allocator>::expand ()
 {
 value_type *oentries = m_entries;
 unsigned int oindex = m_size_prime_index;
 size_t osize = size ();
 value_type *olimit = oentries + osize;
 value_type &x = *p;
 if (!is_empty (x) && !is_deleted (x))
 {
 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
+	  new ((void*) q) value_type (x);
-*q = x;
 }
 p++;
 }
 while (p < olimit);
 ggc_free (oentries);
 }
 /* Implements empty() in cases where it isn't a no-op.  */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::empty_slow ()
+hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
 {
 size_t size = m_size;
 size_t nsize = size;
 value_type *entries = m_entries;
-int i;
+for (size_t i = size - 1; i < size; i--)
-for (i = size - 1; i >= 0; i--)
 if (!is_empty (entries[i]) && !is_deleted (entries[i]))
 Descriptor::remove (entries[i]);
 /* Instead of clearing megabyte, downsize the table.  */
 if (size > 1024*1024 / sizeof (value_type))
 else if (too_empty_p (m_n_elements))
 nsize = m_n_elements * 2;
 if (nsize != size)
 {
-int nindex = hash_table_higher_prime_index (nsize);
+unsigned int nindex = hash_table_higher_prime_index (nsize);
-int nsize = prime_tab[nindex].prime;
+nsize = prime_tab[nindex].prime;
 if (!m_ggc)
 	Allocator <value_type> ::data_free (m_entries);
 else
 	ggc_free (m_entries);
 m_entries = alloc_entries (nsize);
 m_size = nsize;
 m_size_prime_index = nindex;
 }
+else if (Descriptor::empty_zero_p)
+memset ((void *) entries, 0, size * sizeof (value_type));
 else
-{
+for (size_t i = 0; i < size; i++)
-#ifndef BROKEN_VALUE_INITIALIZATION
+mark_empty (entries[i]);
-for ( ; size; ++entries, --size)
-	*entries = value_type ();
-#else
-memset (entries, 0, size * sizeof (value_type));
-#endif
-}
 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>
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::clear_slot (value_type *slot)
+hash_table<Descriptor, Lazy, Allocator>::clear_slot (value_type *slot)
 {
 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
 		         || is_empty (*slot) || is_deleted (*slot)));
 Descriptor::remove (*slot);
 /* 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, bool Lazy,
-typename hash_table<Descriptor, Allocator>::value_type &
+	 template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type &
+hash_table<Descriptor, Lazy, Allocator>
 ::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);
+if (Lazy && m_entries == NULL)
+m_entries = alloc_entries (size);
 value_type *entry = &m_entries[index];
 if (is_empty (*entry)
 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
 return *entry;
 index -= size;
 entry = &m_entries[index];
 if (is_empty (*entry)
 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable)))
-return *entry;
+	{
+#if CHECKING_P
+	  if (m_sanitize_eq_and_hash)
+	    verify (comparable, hash);
+#endif
+	  return *entry;
+	}
 }
 }
 /* This function searches for a hash table slot containing an entry
 equal to the given COMPARABLE element and starting with the given
 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>
+template<typename Descriptor, bool Lazy,
-typename hash_table<Descriptor, Allocator>::value_type *
+	 template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>
+typename hash_table<Descriptor, Lazy, Allocator>::value_type *
+hash_table<Descriptor, Lazy, Allocator>
 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash,
 		       enum insert_option insert)
 {
+if (Lazy && m_entries == NULL)
+{
+if (insert == INSERT)
+	m_entries = alloc_entries (m_size);
+else
+	return NULL;
+}
 if (insert == INSERT && m_size * 3 <= m_n_elements * 4)
 expand ();
+#if CHECKING_P
+if (m_sanitize_eq_and_hash)
+verify (comparable, hash);
+#endif
 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;
 m_n_elements++;
 return &m_entries[index];
 }
+/* Verify that all existing elements in th hash table which are
+equal to COMPARABLE have an equal HASH value provided as argument.  */
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
+void
+hash_table<Descriptor, Lazy, Allocator>
+::verify (const compare_type &comparable, hashval_t hash)
+{
+for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++)
+{
+value_type *entry = &m_entries[i];
+if (!is_empty (*entry) && !is_deleted (*entry)
+	  && hash != Descriptor::hash (*entry)
+	  && Descriptor::equal (*entry, comparable))
+	hashtab_chk_error ();
+}
+}
 /* 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, bool Lazy,
+	 template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>
+hash_table<Descriptor, Lazy, Allocator>
 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
 {
 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
-if (is_empty (*slot))
+if (slot == NULL)
 return;
 Descriptor::remove (*slot);
 mark_deleted (*slot);
 /* 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 Descriptor, bool Lazy,
 	  template<typename Type> class Allocator>
 template<typename Argument,
-	  int (*Callback)
+	 int (*Callback)
-(typename hash_table<Descriptor, Allocator>::value_type *slot,
+	 (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
-Argument argument)>
+	 Argument argument)>
 void
-hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument)
+hash_table<Descriptor, Lazy, Allocator>::traverse_noresize (Argument argument)
 {
+if (Lazy && m_entries == NULL)
+return;
 value_type *slot = m_entries;
 value_type *limit = slot + size ();
 do
 {
 }
 /* Like traverse_noresize, but does resize the table when it is too empty
 to improve effectivity of subsequent calls.  */
-template <typename Descriptor,
+template <typename Descriptor, bool Lazy,
 	  template <typename Type> class Allocator>
 template <typename Argument,
 	  int (*Callback)
-(typename hash_table<Descriptor, Allocator>::value_type *slot,
+	  (typename hash_table<Descriptor, Lazy, Allocator>::value_type *slot,
-Argument argument)>
+	  Argument argument)>
 void
-hash_table<Descriptor, Allocator>::traverse (Argument argument)
+hash_table<Descriptor, Lazy, Allocator>::traverse (Argument argument)
 {
-if (too_empty_p (elements ()))
+if (too_empty_p (elements ()) && (!Lazy || m_entries))
 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>
+template<typename Descriptor, bool Lazy,
+	 template<typename Type> class Allocator>
 void
-hash_table<Descriptor, Allocator>::iterator::slide ()
+hash_table<Descriptor, Lazy, Allocator>::iterator::slide ()
 {
 for ( ; m_slot < m_limit; ++m_slot )
 {
 value_type &x = *m_slot;
 if (!is_empty (x) && !is_deleted (x))
 m_limit = NULL;
 }
 /* Bump the iterator.  */
-template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, bool Lazy,
-inline typename hash_table<Descriptor, Allocator>::iterator &
+	 template<typename Type> class Allocator>
-hash_table<Descriptor, Allocator>::iterator::operator ++ ()
+inline typename hash_table<Descriptor, Lazy, Allocator>::iterator &
+hash_table<Descriptor, Lazy, Allocator>::iterator::operator ++ ()
 {
 ++m_slot;
 slide ();
 return *this;
 }

Mercurial > hg > CbC > CbC_gcc

comparison gcc/hash-table.h @ 145:1830386684a0