diff options
Diffstat (limited to 'libstdc++-v3/include/tr1/hashtable')
| -rw-r--r-- | libstdc++-v3/include/tr1/hashtable | 1431 |
1 files changed, 1431 insertions, 0 deletions
diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable new file mode 100644 index 00000000000..c015e9edf69 --- /dev/null +++ b/libstdc++-v3/include/tr1/hashtable @@ -0,0 +1,1431 @@ +// Internal header for TR1 unordered_set and unordered_map -*- C++ -*- + +// Copyright (C) 2005 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/** @file + * This is a TR1 C++ Library header. + */ + +// This header file defines std::tr1::hashtable, which is used to +// implement std::tr1::unordered_set, std::tr1::unordered_map, +// std::tr1::unordered_multiset, and std::tr1::unordered_multimap. +// hashtable has many template parameters, partly to accommodate +// 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. + +// References: +// 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? + +#ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_ +#define GNU_LIBSTDCXX_TR1_HASHTABLE_ + +#include <utility> // For std::pair +#include <iterator> +#include <cstddef> +#include <cstdlib> +#include <cmath> +#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 is_const, bool cache> +struct node_iterator : public node_iterator_base<Value, cache> { + typedef Value value_type; + typedef typename IF<is_const, const Value*, Value*>::type pointer; + typedef typename IF<is_const, const Value&, Value&>::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + explicit node_iterator (hash_node<Value, cache>* p = 0) + : node_iterator_base<Value, cache>(p) { } + node_iterator (const node_iterator<Value, true, 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_iterator& operator++() { this->incr(); return *this; } + node_iterator operator++(int) + { node_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 is_const, bool cache> +struct hashtable_iterator : public hashtable_iterator_base<Value, cache> +{ + typedef Value value_type; + typedef typename IF<is_const, const Value*, Value*>::type pointer; + typedef typename IF<is_const, const Value&, Value&>::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + hashtable_iterator (hash_node<Value, cache>* p, hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(p, b) { } + hashtable_iterator (hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(*b, b) { } + hashtable_iterator (const hashtable_iterator<Value, true, 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_iterator& operator++() { this->incr(); return *this; } + hashtable_iterator operator++(int) + { hashtable_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 { + T operator()(const T& t) const { return t; } +}; + +template <typename Pair> +struct extract1st { + 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 dummy> +struct X { + static const int n_primes = 256; + static const unsigned long primes[n_primes + 1]; +}; + +template <int dummy> +const int X<dummy>::n_primes; + +template <int dummy> +const unsigned long X<dummy>::primes[n_primes + 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, + 4294967291ul // sentinel so we don't have to test result of lower_bound + }; + +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<0>::primes + X<0>::n_primes; + const unsigned long* p = std::lower_bound (X<0>::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<0>::primes + X<0>::n_primes; + const float min_bkts = n / m_max_load_factor; + const unsigned long* p = std::lower_bound (X<0>::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<0>::primes + X<0>::n_primes; + const unsigned long* p = std::lower_bound (X<0>::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) { + Hashtable* h = static_cast<Hashtable*>(this); + typename Hashtable::iterator it = h->insert(std::make_pair(k, mapped_type())).first; + return it->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 copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { } + + void m_swap(hash_code_base& x) { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_ranged_hash.m_swap(x); + } + +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 copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { } + + void m_swap(hash_code_base& x) { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_h1.m_swap(x); + m_h2.m_swap(x); + } + +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 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) { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_h1.m_swap(x); + m_h2.m_swap(x); + } + +protected: + ExtractKey m_extract; + Equal m_eq; + H1 m_h1; + H2 m_h2; +}; + +} // namespace internal + +namespace std { namespace tr1 { + +//---------------------------------------------------------------------- +// Class template hashtable, class definition. + +// Meaning of class template hashtable's template parameters + +// Key and Value: arbitrary CopyConstructible types. + +// Allocator: an allocator type ([lib.allocator.requirements]) whose +// value type is Value. + +// ExtractKey: function object that takes a object of type Value +// and returns a value of type Key. + +// Equal: function object that takes two objects of type k and returns +// a bool-like value that is true if the two objects are considered equal. + +// H1: the hash function. A unary function object with argument type +// Key and result type size_t. Return values should be distributed +// over the entire range [0, numeric_limits<size_t>:::max()]. + +// H2: the range-hashing function (in the terminology of Tavori and +// Dreizin). A binary function object whose argument types and result +// type are all size_t. Given arguments r and N, the return value is +// in the range [0, N). + +// H: the ranged hash function (Tavori and Dreizin). A binary function +// whose argument types are Key and size_t and whose result type is +// size_t. Given arguments k and N, the return value is in the range +// [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other +// than the default, H1 and H2 are ignored. + +// RehashPolicy: Policy class with three members, all of which govern +// the bucket count. n_bkt(n) returns a bucket count no smaller +// than n. bkt_for_elements(n) returns a bucket count appropriate +// for an element count of n. need_rehash(n_bkt, n_elt, n_ins) +// determines whether, if the current bucket count is n_bkt and the +// current element count is n_elt, we need to increase the bucket +// count. If so, returns make_pair(true, n), where n is the new +// bucket count. If not, returns make_pair(false, <anything>). + +// ??? Right now it is hard-wired that the number of buckets never +// shrinks. Should we allow RehashPolicy to change that? + +// cache_hash_code: bool. true if we store the value of the hash +// function along with the value. This is a time-space tradeoff. +// Storing it may improve lookup speed by reducing the number of times +// we need to call the Equal function. + +// mutable_iterators: bool. true if hashtable::iterator is a mutable +// iterator, false if iterator and const_iterator are both const +// iterators. This is true for unordered_map and unordered_multimap, +// false for unordered_set and unordered_multiset. + +// unique_keys: bool. true if the return value of hashtable::count(k) +// is always at most one, false if it may be an arbitrary number. This +// true for unordered_set and unordered_map, false for unordered_multiset +// and unordered_multimap. + +template <typename Key, typename Value, + typename Allocator, + typename ExtractKey, typename Equal, + typename H1, typename H2, + typename H, typename RehashPolicy, + bool cache_hash_code, + bool mutable_iterators, + bool unique_keys> +class hashtable + : public Internal::rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_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, mutable_iterators, unique_keys> > +{ +public: + typedef Allocator allocator_type; + typedef Value value_type; + typedef Key key_type; + typedef Equal key_equal; + // mapped_type, if present, comes from map_base. + // hasher, if present, comes from hash_code_base. + typedef typename Allocator::difference_type difference_type; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::reference reference; + typedef typename Allocator::const_reference const_reference; + + typedef Internal::node_iterator<value_type, !mutable_iterators, cache_hash_code> + local_iterator; + typedef Internal::node_iterator<value_type, false, cache_hash_code> + const_local_iterator; + + typedef Internal::hashtable_iterator<value_type, !mutable_iterators, cache_hash_code> + iterator; + typedef Internal::hashtable_iterator<value_type, false, cache_hash_code> + const_iterator; + +private: + typedef Internal::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; + size_type m_element_count; + RehashPolicy m_rehash_policy; + + node* m_allocate_node (const value_type& v); + void m_deallocate_node (node* n); + void m_deallocate_nodes (node**, size_type); + + node** m_allocate_buckets (size_type n); + void m_deallocate_buckets (node**, size_type n); + +public: // Constructor, destructor, assignment, swap + hashtable(size_type bucket_hint, + const H1&, const H2&, const H&, + const Equal&, const ExtractKey&, + const allocator_type&); + + template <typename InIter> + hashtable(InIter first, InIter last, + size_type bucket_hint, + const H1&, const H2&, const H&, + const Equal&, const ExtractKey&, + const allocator_type&); + + hashtable(const hashtable&); + hashtable& operator=(const hashtable&); + ~hashtable(); + + void swap(hashtable&); + +public: // Basic container operations + iterator begin() { + iterator i(m_buckets); + if (!i.m_cur_node) + i.m_incr_bucket(); + return i; + } + + const_iterator begin() const { + const_iterator i(m_buckets); + if (!i.m_cur_node) + i.m_incr_bucket(); + return i; + } + + iterator end() + { return iterator(m_buckets + m_bucket_count); } + const_iterator end() const + { return const_iterator(m_buckets + m_bucket_count); } + + size_type size() const { return m_element_count; } + bool empty() const { return size() == 0; } + + allocator_type get_allocator() const { return m_node_allocator; } + size_type max_size() const { return m_node_allocator.max_size(); } + +public: // Bucket operations + size_type bucket_count() const + { return m_bucket_count; } + size_type max_bucket_count() const + { return max_size(); } + size_type bucket_size (size_type n) const + { return std::distance(begin(n), end(n)); } + size_type bucket (const key_type& k) const + { return this->bucket_index (k, this->m_hash_code, this->m_bucket_count); } + + local_iterator begin(size_type n) + { return local_iterator(m_buckets[n]); } + local_iterator end(size_type n) + { return local_iterator(0); } + const_local_iterator begin(size_type n) const + { return const_local_iterator(m_buckets[n]); } + const_local_iterator end(size_type n) const + { return const_local_iterator(0); } + + float load_factor() const + { return static_cast<float>(size()) / static_cast<float>(bucket_count()); } + // max_load_factor, if present, comes from rehash_base. + + // Generalization of max_load_factor. Extension, not found in TR1. Only + // useful if RehashPolicy is something other than the default. + const RehashPolicy& rehash_policy() const { return m_rehash_policy; } + void rehash_policy (const RehashPolicy&); + +public: // lookup + iterator find(const key_type&); + const_iterator find(const key_type& k) const; + size_type count(const key_type& k) const; + std::pair<iterator, iterator> equal_range(const key_type& k); + std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const; + +private: // Insert and erase helper functions + // ??? This dispatching is a workaround for the fact that we don't + // 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, std::pair<iterator, bool>, iterator>::type + Insert_Return_Type; + + node* find_node (node* p, const key_type& k, typename hashtable::hash_code_t c); + + std::pair<iterator, bool> insert (const value_type&, std::tr1::true_type); + iterator insert (const value_type&, std::tr1::false_type); + +public: // Insert and erase + Insert_Return_Type insert (const value_type& v) + { return this->insert (v, std::tr1::integral_constant<bool, unique_keys>()); } + Insert_Return_Type insert (const_iterator, const value_type& v) + { return this->insert(v); } + + template <typename InIter> void insert(InIter first, InIter last); + + void erase(const_iterator); + size_type erase(const key_type&); + void erase(const_iterator, const_iterator); + void clear(); + +public: + // Set number of buckets to be apropriate for container of n element. + void rehash (size_type n); + +private: + // Unconditionally change size of bucket array to n. + void m_rehash (size_type n); +}; + +//---------------------------------------------------------------------- +// 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, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node* +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_node (const value_type& v) +{ + node* n = m_node_allocator.allocate(1); + try { + get_allocator().construct(&n->m_v, v); + n->m_next = 0; + return n; + } + catch(...) { + m_node_allocator.deallocate(n, 1); + throw; + } +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_deallocate_node (node* n) +{ + get_allocator().destroy(&n->m_v); + m_node_allocator.deallocate(n, 1); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::m_deallocate_nodes (node** array, size_type n) +{ + for (size_type i = 0; i < n; ++i) { + node* p = array[i]; + while (p) { + node* tmp = p; + p = p->m_next; + m_deallocate_node (tmp); + } + array[i] = 0; + } +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node** +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_buckets (size_type n) +{ + bucket_allocator_t alloc(m_node_allocator); + + // We allocate one extra bucket to hold a sentinel, an arbitrary + // non-null pointer. Iterator increment relies on this. + node** p = alloc.allocate(n+1); + std::fill(p, p+n, (node*) 0); + p[n] = reinterpret_cast<node*>(0x1000); + return p; +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::m_deallocate_buckets (node** p, size_type n) +{ + bucket_allocator_t alloc(m_node_allocator); + alloc.deallocate(p, n+1); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::hashtable(size_type bucket_hint, + 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> (), + m_node_allocator(a), + m_bucket_count (0), + m_element_count (0), + m_rehash_policy () +{ + m_bucket_count = m_rehash_policy.next_bkt(bucket_hint); + m_buckets = m_allocate_buckets (m_bucket_count); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +template <typename InIter> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::hashtable(InIter f, InIter l, + size_type bucket_hint, + 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> (), + m_node_allocator(a), + m_bucket_count (0), + m_element_count (0), + m_rehash_policy () +{ + m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), + m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l))); + m_buckets = m_allocate_buckets (m_bucket_count); + try { + for (; f != l; ++f) + this->insert (*f); + } + catch(...) { + clear(); + m_deallocate_buckets (m_buckets, m_bucket_count); + throw; + } +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,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), + m_node_allocator(ht.get_allocator()), + m_bucket_count (ht.m_bucket_count), + m_element_count (ht.m_element_count), + m_rehash_policy (ht.m_rehash_policy) +{ + m_buckets = m_allocate_buckets (m_bucket_count); + try { + for (size_t i = 0; i < ht.m_bucket_count; ++i) { + node* n = ht.m_buckets[i]; + node** tail = m_buckets + i; + while (n) { + *tail = m_allocate_node (n); + (*tail).copy_code_from (n); + tail = &((*tail)->m_next); + n = n->m_next; + } + } + } + catch (...) { + clear(); + m_deallocate_buckets (m_buckets, m_bucket_count); + throw; + } +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>& +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::operator= (const hashtable& ht) +{ + hashtable tmp(ht); + this->swap(tmp); + return *this; +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::~hashtable() +{ + clear(); + m_deallocate_buckets(m_buckets, m_bucket_count); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::swap (hashtable& x) +{ + // 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); + + // open LWG issue 431 + // std::swap(m_node_allocator, x.m_node_allocator); + std::swap (m_rehash_policy, x.m_rehash_policy); + std::swap (m_buckets, x.m_buckets); + std::swap (m_bucket_count, x.m_bucket_count); + std::swap (m_element_count, x.m_element_count); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::rehash_policy (const RP& pol) +{ + m_rehash_policy = pol; + size_type n_bkt = pol.bkt_for_elements(m_element_count); + if (n_bkt > m_bucket_count) + m_rehash (n_bkt); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + node* p = find_node (m_buckets[n], k, code); + return p ? iterator(p, m_buckets + n) : this->end(); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) const +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + node* p = find_node (m_buckets[n], k, code); + return p ? const_iterator(p, m_buckets + n) : this->end(); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::count (const key_type& k) const +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + size_t result = 0; + for (node* p = m_buckets[n]; p ; p = p->m_next) + if (this->compare (k, code, p)) + ++result; + return result; +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, + typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + node** head = m_buckets + n; + node* p = find_node (*head, k, code); + + if (p) { + node* p1 = p->m_next; + for (; p1 ; p1 = p1->m_next) + if (!this->compare (k, code, p1)) + break; + iterator first(p, head); + iterator last(p1, head); + if (!p1) + last.m_incr_bucket(); + return std::make_pair(first, last); + } + else + return std::make_pair (this->end(), this->end()); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator, + typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) const +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + node** head = m_buckets + n; + node* p = find_node (*head, k, code); + + if (p) { + node* p1 = p->m_next; + for (; p1 ; p1 = p1->m_next) + if (!this->compare (k, code, p1)) + break; + const_iterator first(p, head); + const_iterator last(p1, head); + if (!p1) + last.m_incr_bucket(); + return std::make_pair(first, last); + } + else + return std::make_pair (this->end(), this->end()); +} + +// Find the node whose key compares equal to k, beginning the search +// at p (usually the head of a bucket). Return nil if no node is found. +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node* +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::find_node (node* p, const key_type& k, typename hashtable::hash_code_t code) +{ + for ( ; p ; p = p->m_next) + if (this->compare (k, code, p)) + return p; + return false; +} + +// Insert v if no element with its key is already present. +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, bool> +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::insert (const value_type& v, std::tr1::true_type) +{ + const key_type& k = this->m_extract(v); + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index (k, code, m_bucket_count); + + if (node* p = find_node (m_buckets[n], k, code)) + return std::make_pair(iterator(p, m_buckets + n), false); + + std::pair<bool, size_t> do_rehash + = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + + // Allocate the new node before doing the rehash so that we don't + // do a rehash if the allocation throws. + node* new_node = m_allocate_node (v); + + try { + if (do_rehash.first) { + n = this->bucket_index (k, code, do_rehash.second); + m_rehash(do_rehash.second); + } + + new_node->m_next = m_buckets[n]; + m_buckets[n] = new_node; + ++m_element_count; + return std::make_pair(iterator (new_node, m_buckets + n), true); + } + catch (...) { + m_deallocate_node (new_node); + throw; + } +} + +// Insert v unconditionally. +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::insert (const value_type& v, std::tr1::false_type) +{ + std::pair<bool, std::size_t> do_rehash + = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + if (do_rehash.first) + m_rehash(do_rehash.second); + + const key_type& k = this->m_extract(v); + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index (k, code, m_bucket_count); + + node* new_node = m_allocate_node (v); + node* prev = find_node (m_buckets[n], k, code); + if (prev) { + new_node->m_next = prev->m_next; + prev->m_next = new_node; + } + else { + new_node->m_next = m_buckets[n]; + m_buckets[n] = new_node; + } + + ++m_element_count; + return iterator (new_node, m_buckets + n); +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +template <typename InIter> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::insert(InIter first, InIter last) +{ + size_type n_elt = Internal::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) + m_rehash(do_rehash.second); + + for (; first != last; ++first) + this->insert (*first); +} + +// XXX We're following the TR in giving this a return type of void, +// but that ought to change. The return type should be const_iterator, +// and it should return the iterator following the one we've erased. +// That would simplify range erase. +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase (const_iterator i) +{ + node* p = i.m_cur_node; + node* cur = *i.m_cur_bucket; + if (cur == p) + *i.m_cur_bucket = cur->m_next; + else { + node* next = cur->m_next; + while (next != p) { + cur = next; + next = cur->m_next; + } + cur->m_next = next->m_next; + } + + m_deallocate_node (p); + --m_element_count; +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase(const key_type& k) +{ + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index (k, code, m_bucket_count); + + node** slot = m_buckets + n; + while (*slot && ! this->compare (k, code, *slot)) + slot = &((*slot)->m_next); + + while (*slot && this->compare (k, code, *slot)) { + node* n = *slot; + *slot = n->m_next; + m_deallocate_node (n); + --m_element_count; + } +} + +// ??? This could be optimized by taking advantage of the bucket +// structure, but it's not clear that it's worth doing. It probably +// wouldn't even be an optimization unless the load factor is large. +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> +::erase(const_iterator first, const_iterator last) +{ + while (first != last) { + const_iterator next = first; + ++next; + this->erase(first); + first = next; + } +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::clear() +{ + m_deallocate_nodes (m_buckets, m_bucket_count); + m_element_count = 0; +} + +template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> +void +hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_rehash (size_type N) +{ + node** new_array = m_allocate_buckets (N); + try { + for (size_type i = 0; i < m_bucket_count; ++i) + while (node* p = m_buckets[i]) { + size_type new_index = this->bucket_index (p, N); + m_buckets[i] = p->m_next; + p->m_next = new_array[new_index]; + new_array[new_index] = p; + } + m_deallocate_buckets (m_buckets, m_bucket_count); + m_bucket_count = N; + m_buckets = new_array; + } + catch (...) { + // A failure here means that a hash function threw an exception. + // We can't restore the previous state without calling the hash + // function again, so the only sensible recovery is to delete + // everything. + m_deallocate_nodes (new_array, N); + m_deallocate_buckets (new_array, N); + m_deallocate_nodes (m_buckets, m_bucket_count); + m_element_count = 0; + throw; + } +} + +} } // Namespace std::tr1 + +#endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */ + |