diff options
Diffstat (limited to 'libstdc++-v3/include/tr1/hashtable')
-rw-r--r-- | libstdc++-v3/include/tr1/hashtable | 971 |
1 files changed, 48 insertions, 923 deletions
diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable index d5041f75db8..9a682db1228 100644 --- a/libstdc++-v3/include/tr1/hashtable +++ b/libstdc++-v3/include/tr1/hashtable @@ -38,8 +38,6 @@ // the differences between those four classes and partly to // accommodate policy choices that go beyond what TR1 calls for. -// ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable. - // Class template hashtable attempts to encapsulate all reasonable // variation among hash tables that use chaining. It does not handle // open addressing. @@ -48,8 +46,8 @@ // M. Austern, "A Proposal to Add Hash Tables to the Standard // Library (revision 4)," WG21 Document N1456=03-0039, 2003. // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. -// A. Tavori and V. Dreizin, "Generic Associative Containers", 2004. -// ??? Full citation? +// A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. +// http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html #ifndef _TR1_HASHTABLE #define _TR1_HASHTABLE 1 @@ -62,882 +60,12 @@ #include <cmath> #include <bits/functexcept.h> #include <tr1/type_traits> // For true_type and false_type - -//---------------------------------------------------------------------- -// General utilities - -namespace Internal -{ - template<bool Flag, typename IfTrue, typename IfFalse> - struct IF; - - template<typename IfTrue, typename IfFalse> - struct IF<true, IfTrue, IfFalse> - { typedef IfTrue type; }; - - template <typename IfTrue, typename IfFalse> - struct IF<false, IfTrue, IfFalse> - { typedef IfFalse type; }; - - // Helper function: return distance(first, last) for forward - // iterators, or 0 for input iterators. - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last, std::input_iterator_tag) - { return 0; } - - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last, std::forward_iterator_tag) - { return std::distance(first, last); } - - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last) - { - typedef typename std::iterator_traits<Iterator>::iterator_category tag; - return distance_fw(first, last, tag()); - } - -} // namespace Internal - - -//---------------------------------------------------------------------- -// Auxiliary types used for all instantiations of hashtable: nodes -// and iterators. - -// Nodes, used to wrap elements stored in the hash table. A policy -// template parameter of class template hashtable controls whether -// nodes also store a hash code. In some cases (e.g. strings) this may -// be a performance win. - -namespace Internal -{ - template<typename Value, bool cache_hash_code> - struct hash_node; - - template<typename Value> - struct hash_node<Value, true> - { - Value m_v; - std::size_t hash_code; - hash_node* m_next; - }; - - template<typename Value> - struct hash_node<Value, false> - { - Value m_v; - hash_node* m_next; - }; - - // Local iterators, used to iterate within a bucket but not between - // buckets. - - template<typename Value, bool cache> - struct node_iterator_base - { - node_iterator_base(hash_node<Value, cache>* p) - : m_cur(p) { } - - void - incr() - { m_cur = m_cur->m_next; } - - hash_node<Value, cache>* m_cur; - }; - - template<typename Value, bool cache> - inline bool - operator==(const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) - { return x.m_cur == y.m_cur; } - - template<typename Value, bool cache> - inline bool - operator!=(const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) - { return x.m_cur != y.m_cur; } - - template<typename Value, bool constant_iterators, bool cache> - struct node_iterator - : public node_iterator_base<Value, cache> - { - typedef Value value_type; - typedef typename IF<constant_iterators, const Value*, Value*>::type - pointer; - typedef typename IF<constant_iterators, const Value&, Value&>::type - reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - node_iterator() - : node_iterator_base<Value, cache>(0) { } - - explicit - node_iterator(hash_node<Value, cache>* p) - : node_iterator_base<Value, cache>(p) { } - - reference - operator*() const - { return this->m_cur->m_v; } - - pointer - operator->() const - { return &this->m_cur->m_v; } - - node_iterator& - operator++() - { - this->incr(); - return *this; - } - - node_iterator - operator++(int) - { - node_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool constant_iterators, bool cache> - struct node_const_iterator - : public node_iterator_base<Value, cache> - { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - node_const_iterator() - : node_iterator_base<Value, cache>(0) { } - - explicit - node_const_iterator(hash_node<Value, cache>* p) - : node_iterator_base<Value, cache>(p) { } - - node_const_iterator(const node_iterator<Value, constant_iterators, - cache>& x) - : node_iterator_base<Value, cache>(x.m_cur) { } - - reference - operator*() const - { return this->m_cur->m_v; } - - pointer - operator->() const - { return &this->m_cur->m_v; } - - node_const_iterator& - operator++() - { - this->incr(); - return *this; - } - - node_const_iterator - operator++(int) - { - node_const_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool cache> - struct hashtable_iterator_base - { - hashtable_iterator_base(hash_node<Value, cache>* node, - hash_node<Value, cache>** bucket) - : m_cur_node(node), m_cur_bucket(bucket) { } - - void - incr() - { - m_cur_node = m_cur_node->m_next; - if (!m_cur_node) - m_incr_bucket(); - } - - void - m_incr_bucket(); - - hash_node<Value, cache>* m_cur_node; - hash_node<Value, cache>** m_cur_bucket; - }; - - // Global iterators, used for arbitrary iteration within a hash - // table. Larger and more expensive than local iterators. - template<typename Value, bool cache> - void - hashtable_iterator_base<Value, cache>:: - m_incr_bucket() - { - ++m_cur_bucket; - - // This loop requires the bucket array to have a non-null sentinel. - while (!*m_cur_bucket) - ++m_cur_bucket; - m_cur_node = *m_cur_bucket; - } - - template<typename Value, bool cache> - inline bool - operator==(const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) - { return x.m_cur_node == y.m_cur_node; } - - template<typename Value, bool cache> - inline bool - operator!=(const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) - { return x.m_cur_node != y.m_cur_node; } - - template<typename Value, bool constant_iterators, bool cache> - struct hashtable_iterator - : public hashtable_iterator_base<Value, cache> - { - typedef Value value_type; - typedef typename IF<constant_iterators, const Value*, Value*>::type - pointer; - typedef typename IF<constant_iterators, const Value&, Value&>::type - reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - hashtable_iterator() - : hashtable_iterator_base<Value, cache>(0, 0) { } - - hashtable_iterator(hash_node<Value, cache>* p, - hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(p, b) { } - - explicit - hashtable_iterator(hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(*b, b) { } - - reference - operator*() const - { return this->m_cur_node->m_v; } - - pointer - operator->() const - { return &this->m_cur_node->m_v; } - - hashtable_iterator& - operator++() - { - this->incr(); - return *this; - } - - hashtable_iterator - operator++(int) - { - hashtable_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool constant_iterators, bool cache> - struct hashtable_const_iterator - : public hashtable_iterator_base<Value, cache> - { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - hashtable_const_iterator() - : hashtable_iterator_base<Value, cache>(0, 0) { } - - hashtable_const_iterator(hash_node<Value, cache>* p, - hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(p, b) { } - - explicit - hashtable_const_iterator(hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(*b, b) { } - - hashtable_const_iterator(const hashtable_iterator<Value, - constant_iterators, cache>& x) - : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { } - - reference - operator*() const - { return this->m_cur_node->m_v; } - - pointer - operator->() const - { return &this->m_cur_node->m_v; } - - hashtable_const_iterator& - operator++() - { - this->incr(); - return *this; - } - - hashtable_const_iterator - operator++(int) - { - hashtable_const_iterator tmp(*this); - this->incr(); - return tmp; - } - }; -} // namespace Internal - - -// ---------------------------------------------------------------------- -// Many of class template hashtable's template parameters are policy -// classes. These are defaults for the policies. - -namespace Internal -{ - // The two key extraction policies used by the *set and *map variants. - template<typename T> - struct identity - { - const T& - operator()(const T& t) const - { return t; } - }; - - template<typename Pair> - struct extract1st - { - const typename Pair::first_type& - operator()(const Pair& p) const - { return p.first; } - }; - - // Default range hashing function: use division to fold a large number - // into the range [0, N). - struct mod_range_hashing - { - typedef std::size_t first_argument_type; - typedef std::size_t second_argument_type; - typedef std::size_t result_type; - - result_type - operator()(first_argument_type r, second_argument_type N) const - { return r % N; } - }; - - // Default ranged hash function H. In principle it should be a - // function object composed from objects of type H1 and H2 such that - // h(k, N) = h2(h1(k), N), but that would mean making extra copies of - // h1 and h2. So instead we'll just use a tag to tell class template - // hashtable to do that composition. - struct default_ranged_hash { }; - - // Default value for rehash policy. Bucket size is (usually) the - // smallest prime that keeps the load factor small enough. - struct prime_rehash_policy - { - prime_rehash_policy(float z = 1.0); - - float - max_load_factor() const; - - // Return a bucket size no smaller than n. - std::size_t - next_bkt(std::size_t n) const; - - // Return a bucket count appropriate for n elements - std::size_t - bkt_for_elements(std::size_t n) const; - - // n_bkt is current bucket count, n_elt is current element count, - // and n_ins is number of elements to be inserted. Do we need to - // increase bucket count? If so, return make_pair(true, n), where n - // is the new bucket count. If not, return make_pair(false, 0). - std::pair<bool, std::size_t> - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; - - float m_max_load_factor; - float m_growth_factor; - mutable std::size_t m_next_resize; - }; - - // XXX This is a hack. prime_rehash_policy's member functions, and - // certainly the list of primes, should be defined in a .cc file. - // We're temporarily putting them in a header because we don't have a - // place to put TR1 .cc files yet. There's no good reason for any of - // prime_rehash_policy's member functions to be inline, and there's - // certainly no good reason for X<> to exist at all. - - struct lt - { - template<typename X, typename Y> - bool - operator()(X x, Y y) - { return x < y; } - }; - - template<int ulongsize = sizeof(unsigned long)> - struct X - { - static const int n_primes = ulongsize != 8 ? 256 : 256 + 48; - static const unsigned long primes[256 + 48 + 1]; - }; - - template<int ulongsize> - const int X<ulongsize>::n_primes; - - template<int ulongsize> - const unsigned long X<ulongsize>::primes[256 + 48 + 1] = - { - 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, - 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, - 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, - 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, - 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, - 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, - 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, - 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, - 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, - 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, - 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, - 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, - 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, - 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, - 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, - 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, - 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, - 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, - 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, - 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, - 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, - 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, - 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, - 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, - 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, - 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, - 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, - 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, - 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, - 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, - 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, - 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, - 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, - 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, - 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, - 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, - 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, - 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, - 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, - 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, - 4294967291ul, - // Sentinel, so we don't have to test the result of lower_bound, - // or, on 64-bit machines, rest of the table. - ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, - (unsigned long)8589934583ull, - (unsigned long)12884901857ull, (unsigned long)17179869143ull, - (unsigned long)25769803693ull, (unsigned long)34359738337ull, - (unsigned long)51539607367ull, (unsigned long)68719476731ull, - (unsigned long)103079215087ull, (unsigned long)137438953447ull, - (unsigned long)206158430123ull, (unsigned long)274877906899ull, - (unsigned long)412316860387ull, (unsigned long)549755813881ull, - (unsigned long)824633720731ull, (unsigned long)1099511627689ull, - (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, - (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, - (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, - (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, - (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, - (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, - (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, - (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, - (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, - (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, - (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, - (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, - (unsigned long)144115188075855859ull, - (unsigned long)288230376151711717ull, - (unsigned long)576460752303423433ull, - (unsigned long)1152921504606846883ull, - (unsigned long)2305843009213693951ull, - (unsigned long)4611686018427387847ull, - (unsigned long)9223372036854775783ull, - (unsigned long)18446744073709551557ull, - (unsigned long)18446744073709551557ull - }; - - inline - prime_rehash_policy:: - prime_rehash_policy(float z) - : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0) - { } - - inline float - prime_rehash_policy:: - max_load_factor() const - { return m_max_load_factor; } - - // Return a prime no smaller than n. - inline std::size_t - prime_rehash_policy:: - next_bkt(std::size_t n) const - { - const unsigned long* const last = X<>::primes + X<>::n_primes; - const unsigned long* p = std::lower_bound(X<>::primes, last, n); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; - } - - // Return the smallest prime p such that alpha p >= n, where alpha - // is the load factor. - inline std::size_t - prime_rehash_policy:: - bkt_for_elements(std::size_t n) const - { - const unsigned long* const last = X<>::primes + X<>::n_primes; - const float min_bkts = n / m_max_load_factor; - const unsigned long* p = std::lower_bound(X<>::primes, last, - min_bkts, lt()); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; - } - - // Finds the smallest prime p such that alpha p > n_elt + n_ins. - // If p > n_bkt, return make_pair(true, p); otherwise return - // make_pair(false, 0). In principle this isn't very different from - // bkt_for_elements. - - // The only tricky part is that we're caching the element count at - // which we need to rehash, so we don't have to do a floating-point - // multiply for every insertion. - - inline std::pair<bool, std::size_t> - prime_rehash_policy:: - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const - { - if (n_elt + n_ins > m_next_resize) - { - float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor; - if (min_bkts > n_bkt) - { - min_bkts = std::max(min_bkts, m_growth_factor * n_bkt); - const unsigned long* const last = X<>::primes + X<>::n_primes; - const unsigned long* p = std::lower_bound(X<>::primes, last, - min_bkts, lt()); - m_next_resize = - static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return std::make_pair(true, *p); - } - else - { - m_next_resize = - static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor)); - return std::make_pair(false, 0); - } - } - else - return std::make_pair(false, 0); - } - -} // namespace Internal - - -//---------------------------------------------------------------------- -// Base classes for std::tr1::hashtable. We define these base classes -// because in some cases we want to do different things depending on -// the value of a policy class. In some cases the policy class affects -// which member functions and nested typedefs are defined; we handle that -// by specializing base class templates. Several of the base class templates -// need to access other members of class template hashtable, so we use -// the "curiously recurring template pattern" for them. - -namespace Internal -{ - // class template map_base. If the hashtable has a value type of the - // form pair<T1, T2> and a key extraction policy that returns the - // first part of the pair, the hashtable gets a mapped_type typedef. - // If it satisfies those criteria and also has unique keys, then it - // also gets an operator[]. - - template<typename K, typename V, typename Ex, bool unique, typename Hashtable> - struct map_base { }; - - template<typename K, typename Pair, typename Hashtable> - struct map_base<K, Pair, extract1st<Pair>, false, Hashtable> - { - typedef typename Pair::second_type mapped_type; - }; - - template<typename K, typename Pair, typename Hashtable> - struct map_base<K, Pair, extract1st<Pair>, true, Hashtable> - { - typedef typename Pair::second_type mapped_type; - - mapped_type& - operator[](const K& k); - }; - - template<typename K, typename Pair, typename Hashtable> - typename map_base<K, Pair, extract1st<Pair>, true, Hashtable>::mapped_type& - map_base<K, Pair, extract1st<Pair>, true, Hashtable>:: - operator[](const K& k) - { - Hashtable* h = static_cast<Hashtable*>(this); - typename Hashtable::hash_code_t code = h->m_hash_code(k); - std::size_t n = h->bucket_index(k, code, h->bucket_count()); - - typename Hashtable::node* p = h->m_find_node(h->m_buckets[n], k, code); - if (!p) - return h->m_insert_bucket(std::make_pair(k, mapped_type()), - n, code)->second; - return (p->m_v).second; - } - - // class template rehash_base. Give hashtable the max_load_factor - // functions iff the rehash policy is prime_rehash_policy. - template<typename RehashPolicy, typename Hashtable> - struct rehash_base { }; - - template<typename Hashtable> - struct rehash_base<prime_rehash_policy, Hashtable> - { - float - max_load_factor() const - { - const Hashtable* This = static_cast<const Hashtable*>(this); - return This->rehash_policy().max_load_factor(); - } - - void - max_load_factor(float z) - { - Hashtable* This = static_cast<Hashtable*>(this); - This->rehash_policy(prime_rehash_policy(z)); - } - }; - - // Class template hash_code_base. Encapsulates two policy issues that - // aren't quite orthogonal. - // (1) the difference between using a ranged hash function and using - // the combination of a hash function and a range-hashing function. - // In the former case we don't have such things as hash codes, so - // we have a dummy type as placeholder. - // (2) Whether or not we cache hash codes. Caching hash codes is - // meaningless if we have a ranged hash function. - // We also put the key extraction and equality comparison function - // objects here, for convenience. - - // Primary template: unused except as a hook for specializations. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H, - bool cache_hash_code> - struct hash_code_base; - - // Specialization: ranged hash function, no caching hash codes. H1 - // and H2 are provided but ignored. We define a dummy hash code type. - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false> - { - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1&, const H2&, const H& h) - : m_extract(ex), m_eq(eq), m_ranged_hash(h) { } - - typedef void* hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return 0; } - - std::size_t - bucket_index(const Key& k, hash_code_t, std::size_t N) const - { return m_ranged_hash(k, N); } - - std::size_t - bucket_index(const hash_node<Value, false>* p, std::size_t N) const - { return m_ranged_hash(m_extract(p->m_v), N); } - - bool - compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, false>*, hash_code_t) const - { } - - void - copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const - { } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_ranged_hash, x.m_ranged_hash); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H m_ranged_hash; - }; - - - // No specialization for ranged hash function while caching hash codes. - // That combination is meaningless, and trying to do it is an error. - - - // Specialization: ranged hash function, cache hash codes. This - // combination is meaningless, so we provide only a declaration - // and no definition. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>; - - - // Specialization: hash function and range-hashing function, no - // caching of hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, - default_ranged_hash, false> - { - typedef H1 hasher; - - hasher - hash_function() const - { return m_h1; } - - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return m_h1(k); } - - std::size_t - bucket_index(const Key&, hash_code_t c, std::size_t N) const - { return m_h2(c, N); } - - std::size_t - bucket_index(const hash_node<Value, false>* p, std::size_t N) const - { return m_h2(m_h1(m_extract(p->m_v)), N); } - - bool - compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, false>*, hash_code_t) const - { } - - void - copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const - { } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_h1, x.m_h1); - std::swap(m_h2, x.m_h2); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; - }; - - // Specialization: hash function and range-hashing function, - // caching hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, - default_ranged_hash, true> - { - typedef H1 hasher; - - hasher - hash_function() const - { return m_h1; } - - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return m_h1(k); } - - std::size_t - bucket_index(const Key&, hash_code_t c, std::size_t N) const - { return m_h2(c, N); } - - std::size_t - bucket_index(const hash_node<Value, true>* p, std::size_t N) const - { return m_h2(p->hash_code, N); } - - bool - compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const - { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, true>* n, hash_code_t c) const - { n->hash_code = c; } - - void - copy_code(hash_node<Value, true>* to, - const hash_node<Value, true>* from) const - { to->hash_code = from->hash_code; } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_h1, x.m_h1); - std::swap(m_h2, x.m_h2); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; - }; - -} // namespace internal +#include <tr1/hashtable_policy.h> namespace std { _GLIBCXX_BEGIN_NAMESPACE(tr1) - //---------------------------------------------------------------------- // Class template hashtable, class definition. // Meaning of class template hashtable's template parameters @@ -994,27 +122,26 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // true for unordered_set and unordered_map, false for unordered_multiset // and unordered_multimap. - template<typename Key, typename Value, - typename Allocator, + template<typename Key, typename Value, typename Allocator, typename ExtractKey, typename Equal, - typename H1, typename H2, - typename H, typename RehashPolicy, + typename H1, typename H2, typename H, + typename RehashPolicy, bool cache_hash_code, bool constant_iterators, bool unique_keys> class hashtable - : public Internal::rehash_base<RehashPolicy, - hashtable<Key, Value, Allocator, ExtractKey, - Equal, H1, H2, H, RehashPolicy, - cache_hash_code, constant_iterators, - unique_keys> >, - public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, - cache_hash_code>, - public Internal::map_base<Key, Value, ExtractKey, unique_keys, - hashtable<Key, Value, Allocator, ExtractKey, - Equal, H1, H2, H, RehashPolicy, - cache_hash_code, constant_iterators, - unique_keys> > + : public detail::rehash_base<RehashPolicy, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, constant_iterators, + unique_keys> >, + public detail::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, + cache_hash_code>, + public detail::map_base<Key, Value, ExtractKey, unique_keys, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, constant_iterators, + unique_keys> > { public: typedef Allocator allocator_type; @@ -1028,31 +155,30 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) typedef typename Allocator::reference reference; typedef typename Allocator::const_reference const_reference; - typedef Internal::node_iterator<value_type, constant_iterators, + typedef detail::node_iterator<value_type, constant_iterators, cache_hash_code> local_iterator; - typedef Internal::node_const_iterator<value_type, constant_iterators, + typedef detail::node_const_iterator<value_type, constant_iterators, cache_hash_code> const_local_iterator; - typedef Internal::hashtable_iterator<value_type, constant_iterators, + typedef detail::hashtable_iterator<value_type, constant_iterators, cache_hash_code> iterator; - typedef Internal::hashtable_const_iterator<value_type, constant_iterators, + typedef detail::hashtable_const_iterator<value_type, constant_iterators, cache_hash_code> const_iterator; template<typename K, typename Pair, typename Hashtable> - friend struct Internal::map_base; + friend struct detail::map_base; private: - typedef Internal::hash_node<Value, cache_hash_code> node; + typedef detail::hash_node<Value, cache_hash_code> node; typedef typename Allocator::template rebind<node>::other node_allocator_t; typedef typename Allocator::template rebind<node*>::other bucket_allocator_t; - private: node_allocator_t m_node_allocator; node** m_buckets; size_type m_bucket_count; @@ -1074,7 +200,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void m_deallocate_buckets(node**, size_type n); - public: // Constructor, destructor, assignment, swap + public: + // Constructor, destructor, assignment, swap hashtable(size_type bucket_hint, const H1&, const H2&, const H&, const Equal&, const ExtractKey&, @@ -1096,7 +223,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void swap(hashtable&); - public: // Basic container operations + // Basic container operations iterator begin() { @@ -1139,14 +266,14 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) max_size() const { return m_node_allocator.max_size(); } - public: // Observers + // Observers key_equal key_eq() const { return this->m_eq; } // hash_function, if present, comes from hash_code_base. - public: // Bucket operations + // Bucket operations size_type bucket_count() const { return m_bucket_count; } @@ -1199,7 +326,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void rehash_policy(const RehashPolicy&); - public: // lookup + // Lookup. iterator find(const key_type& k); @@ -1220,13 +347,13 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // have partial specialization of member templates; it would be // better to just specialize insert on unique_keys. There may be a // cleaner workaround. - typedef typename Internal::IF<unique_keys, + typedef typename detail::IF<unique_keys, std::pair<iterator, bool>, iterator>::type Insert_Return_Type; - typedef typename Internal::IF<unique_keys, - Internal::extract1st<Insert_Return_Type>, - Internal::identity<Insert_Return_Type> + typedef typename detail::IF<unique_keys, + detail::extract1st<Insert_Return_Type>, + detail::identity<Insert_Return_Type> >::type Insert_Conv_Type; @@ -1247,7 +374,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void m_erase_node(node*, node**); - public: // Insert and erase + public: + // Insert and erase Insert_Return_Type insert(const value_type& v) { return m_insert(v, std::tr1::integral_constant<bool, unique_keys>()); } @@ -1282,7 +410,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void clear(); - public: // Set number of buckets to be appropriate for container of n element. void rehash(size_type n); @@ -1292,9 +419,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) }; - //---------------------------------------------------------------------- // Definitions of class template hashtable's out-of-line member functions. - template<typename K, typename V, typename A, typename Ex, typename Eq, typename H1, typename H2, typename H, typename RP, @@ -1389,9 +514,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const H1& h1, const H2& h2, const H& h, const Eq& eq, const Ex& exk, const allocator_type& a) - : Internal::rehash_base<RP, hashtable>(), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), - Internal::map_base<K, V, Ex, u, hashtable>(), + : detail::rehash_base<RP, hashtable>(), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), + detail::map_base<K, V, Ex, u, hashtable>(), m_node_allocator(a), m_bucket_count(0), m_element_count(0), @@ -1412,10 +537,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const H1& h1, const H2& h2, const H& h, const Eq& eq, const Ex& exk, const allocator_type& a) - : Internal::rehash_base<RP, hashtable>(), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, + : detail::rehash_base<RP, hashtable>(), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), - Internal::map_base<K, V, Ex, u, hashtable>(), + detail::map_base<K, V, Ex, u, hashtable>(), m_node_allocator(a), m_bucket_count(0), m_element_count(0), @@ -1423,7 +548,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) { m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), m_rehash_policy. - bkt_for_elements(Internal:: + bkt_for_elements(detail:: distance_fw(f, l))); m_buckets = m_allocate_buckets(m_bucket_count); try @@ -1445,9 +570,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) bool c, bool ci, bool u> hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>:: hashtable(const hashtable& ht) - : Internal::rehash_base<RP, hashtable>(ht), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht), - Internal::map_base<K, V, Ex, u, hashtable>(ht), + : detail::rehash_base<RP, hashtable>(ht), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht), + detail::map_base<K, V, Ex, u, hashtable>(ht), m_node_allocator(ht.get_allocator()), m_bucket_count(ht.m_bucket_count), m_element_count(ht.m_element_count), @@ -1512,7 +637,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // The only base class with member variables is hash_code_base. We // define hash_code_base::m_swap because different specializations // have different members. - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 431. Swapping containers with unequal allocators. @@ -1799,7 +924,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>:: insert(InIter first, InIter last) { - size_type n_elt = Internal::distance_fw(first, last); + size_type n_elt = detail::distance_fw(first, last); std::pair<bool, std::size_t> do_rehash = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt); if (do_rehash.first) |