From 69f0fb0f7dcd8467f998df91e67f7c1cf44aa1b1 Mon Sep 17 00:00:00 2001 From: austern Date: Fri, 18 Feb 2005 07:50:08 +0000 Subject: [PATCH] * include/tr1/functional (hash): New function object. * include/tr1/hashtable: New file. * include/tr1/unordered_set: New file. * include/tr1/unordered_map: New file. * include/Makefile.am: Add three new TR1 headers. * include/Makefile.in: Likewise. * testsuite/tr1/6_containers/unordered/insert/array_syntax.cc: New test. * testsuite/tr1/6_containers/unordered/insert/map_single.cc: New test. * testsuite/tr1/6_containers/unordered/insert/multimap_single.cc: New test. * testsuite/tr1/6_containers/unordered/insert/multiset_single.cc: New test. * testsuite/tr1/6_containers/unordered/insert/set_single.cc: New test. * testsuite/tr1/6_containers/unordered/instantiate/hash.cc: New test. * testsuite/tr1/6_containers/unordered/instantiate/map.cc: New test. * testsuite/tr1/6_containers/unordered/instantiate/multimap.cc: New test. * testsuite/tr1/6_containers/unordered/instantiate/multiset.cc: New test. * testsuite/tr1/6_containers/unordered/instantiate/set.cc: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@95219 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 19 + libstdc++-v3/include/Makefile.am | 5 +- libstdc++-v3/include/Makefile.in | 6 +- libstdc++-v3/include/tr1/functional | 72 +- libstdc++-v3/include/tr1/hashtable | 1422 ++++++++++++++++++++ libstdc++-v3/include/tr1/unordered_map | 157 +++ libstdc++-v3/include/tr1/unordered_set | 151 +++ .../6_containers/unordered/insert/array_syntax.cc | 61 + .../6_containers/unordered/insert/map_single.cc | 74 + .../unordered/insert/multimap_single.cc | 78 ++ .../unordered/insert/multiset_single.cc | 69 + .../6_containers/unordered/insert/set_single.cc | 67 + .../tr1/6_containers/unordered/instantiate/hash.cc | 51 + .../tr1/6_containers/unordered/instantiate/map.cc | 37 + .../6_containers/unordered/instantiate/multimap.cc | 37 + .../6_containers/unordered/instantiate/multiset.cc | 34 + .../tr1/6_containers/unordered/instantiate/set.cc | 34 + 17 files changed, 2369 insertions(+), 5 deletions(-) create mode 100644 libstdc++-v3/include/tr1/hashtable create mode 100644 libstdc++-v3/include/tr1/unordered_map create mode 100644 libstdc++-v3/include/tr1/unordered_set create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/array_syntax.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/map_single.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multimap_single.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multiset_single.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/set_single.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/hash.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/map.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multimap.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multiset.cc create mode 100644 libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/set.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 93021e7aefa..0ddd1a52fa6 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,22 @@ +2005-02-17 Matt Austern + + * include/tr1/functional (hash): New function object. + * include/tr1/hashtable: New file. + * include/tr1/unordered_set: New file. + * include/tr1/unordered_map: New file. + * include/Makefile.am: Add three new TR1 headers. + * include/Makefile.in: Likewise. + * testsuite/tr1/6_containers/unordered/insert/array_syntax.cc: New test. + * testsuite/tr1/6_containers/unordered/insert/map_single.cc: New test. + * testsuite/tr1/6_containers/unordered/insert/multimap_single.cc: New test. + * testsuite/tr1/6_containers/unordered/insert/multiset_single.cc: New test. + * testsuite/tr1/6_containers/unordered/insert/set_single.cc: New test. + * testsuite/tr1/6_containers/unordered/instantiate/hash.cc: New test. + * testsuite/tr1/6_containers/unordered/instantiate/map.cc: New test. + * testsuite/tr1/6_containers/unordered/instantiate/multimap.cc: New test. + * testsuite/tr1/6_containers/unordered/instantiate/multiset.cc: New test. + * testsuite/tr1/6_containers/unordered/instantiate/set.cc: New test. + 2005-02-16 Paolo Carlini * testsuite/23_containers/set/modifiers/16728.cc: diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 3fa1dd65e77..d7d61b9157f 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -232,7 +232,10 @@ tr1_headers = \ ${tr1_srcdir}/tuple \ ${tr1_srcdir}/utility \ ${tr1_srcdir}/type_traits \ - ${tr1_srcdir}/type_traits_fwd.h + ${tr1_srcdir}/type_traits_fwd.h \ + ${tr1_srcdir}/hashtable \ + ${tr1_srcdir}/unordered_set \ + ${tr1_srcdir}/unordered_map # This is the common subset of files that all three "C" header models use. diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index d56d35aab7f..e73c81ddc47 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -448,8 +448,10 @@ tr1_headers = \ ${tr1_srcdir}/tuple \ ${tr1_srcdir}/utility \ ${tr1_srcdir}/type_traits \ - ${tr1_srcdir}/type_traits_fwd.h - + ${tr1_srcdir}/type_traits_fwd.h \ + ${tr1_srcdir}/hashtable \ + ${tr1_srcdir}/unordered_set \ + ${tr1_srcdir}/unordered_map # This is the common subset of files that all three "C" header models use. c_base_srcdir = $(C_INCLUDE_DIR) diff --git a/libstdc++-v3/include/tr1/functional b/libstdc++-v3/include/tr1/functional index 1e897e2b3c7..d53c99a9a5d 100644 --- a/libstdc++-v3/include/tr1/functional +++ b/libstdc++-v3/include/tr1/functional @@ -1,6 +1,6 @@ // TR1 functional header -*- C++ -*- -// Copyright (C) 2004 Free Software Foundation, Inc. +// Copyright (C) 2004, 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 @@ -26,6 +26,7 @@ #define _TR1_FUNCTIONAL 1 #include "../functional" +#include // for std::tr1::hash namespace std { @@ -78,8 +79,75 @@ namespace tr1 template reference_wrapper cref(reference_wrapper<_Tp> __t) { return cref(__t.get()); } + + +// Definition of default hash function std::tr1::hash<>. The types for +// which std::tr1::hash is defined is in clause 6.3.3. of the PDTR. + + template struct hash; + + #define tr1_hashtable_define_trivial_hash(T) \ + template <> struct hash { \ + std::size_t operator()(T val) { return static_cast(val); } \ + } \ + + tr1_hashtable_define_trivial_hash(bool); + tr1_hashtable_define_trivial_hash(char); + tr1_hashtable_define_trivial_hash(signed char); + tr1_hashtable_define_trivial_hash(unsigned char); + tr1_hashtable_define_trivial_hash(wchar_t); + tr1_hashtable_define_trivial_hash(short); + tr1_hashtable_define_trivial_hash(int); + tr1_hashtable_define_trivial_hash(long); + tr1_hashtable_define_trivial_hash(unsigned short); + tr1_hashtable_define_trivial_hash(unsigned int); + tr1_hashtable_define_trivial_hash(unsigned long); + + tr1_hashtable_define_trivial_hash(float); + tr1_hashtable_define_trivial_hash(double); + tr1_hashtable_define_trivial_hash(long double); + + #undef tr1_hashtable_define_trivial_hash + + template + struct hash { + std::size_t operator()(T* p) const { + return reinterpret_cast(p); + } + }; + + // ??? We can probably find a better hash function than this (i.e. one + // that vectorizes better and that produces a more uniform distribution). + + // XXX String hash probably shouldn't be an inline member function, + // since it's nontrivial. Once we have the framework for TR1 .cc + // files, this should go in one. + + template <> + struct hash + { + std::size_t operator()(const std::string& s) const + { + std::size_t result = 0; + for (std::string::const_iterator i = s.begin(); i != s.end(); ++i) + result = (result * 131) + *i; + return result; + } + }; + + template <> + struct hash + { + std::size_t operator()(const std::wstring& s) const + { + std::size_t result = 0; + for (std::wstring::const_iterator i = s.begin(); i != s.end(); ++i) + result = (result * 131) + *i; + return result; + } + }; + } } #endif - diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable new file mode 100644 index 00000000000..fb53f70d269 --- /dev/null +++ b/libstdc++-v3/include/tr1/hashtable @@ -0,0 +1,1422 @@ +// 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. + +/** @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 // For std::pair +#include +#include +#include +#include +#include // For true_type and false_type + +//---------------------------------------------------------------------- +// General utilities + +namespace Internal { +template struct IF; + +template +struct IF { typedef IfTrue type; }; + +template +struct IF { typedef IfFalse type; }; + +// Helper function: return distance(first, last) for forward +// iterators, or 0 for input iterators. + +template +inline typename std::iterator_traits::difference_type +distance_fw (Iterator first, Iterator last, std::input_iterator_tag) +{ + return 0; +} + +template +inline typename std::iterator_traits::difference_type +distance_fw (Iterator first, Iterator last, std::forward_iterator_tag) +{ + return std::distance(first, last); +} + +template +inline typename std::iterator_traits::difference_type +distance_fw (Iterator first, Iterator last) +{ + typedef typename std::iterator_traits::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 struct hash_node; + +template +struct hash_node { + Value m_v; + std::size_t hash_code; + hash_node* m_next; +}; + +template +struct hash_node { + Value m_v; + hash_node* m_next; +}; + +// Local iterators, used to iterate within a bucket but not between +// buckets. + +template +struct node_iterator_base { + node_iterator_base(hash_node* p) : m_cur(p) { } + void incr() { m_cur = m_cur->m_next; } + + hash_node* m_cur; +}; + +template +inline bool operator== (const node_iterator_base& x, + const node_iterator_base& y) +{ + return x.m_cur == y.m_cur; +} + +template +inline bool operator!= (const node_iterator_base& x, + const node_iterator_base& y) +{ + return x.m_cur != y.m_cur; +} + +template +struct node_iterator : public node_iterator_base { + typedef Value value_type; + typedef typename IF::type pointer; + typedef typename IF::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + explicit node_iterator (hash_node* p = 0) + : node_iterator_base(p) { } + node_iterator (const node_iterator& x) + : node_iterator_base(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 +struct hashtable_iterator_base { + hashtable_iterator_base(hash_node* node, + hash_node** 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* m_cur_node; + hash_node** m_cur_bucket; +}; + + +// Global iterators, used for arbitrary iteration within a hash +// table. Larger and more expensive than local iterators. + +template +void hashtable_iterator_base::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 +inline bool operator== (const hashtable_iterator_base& x, + const hashtable_iterator_base& y) +{ + return x.m_cur_node == y.m_cur_node; +} + +template +inline bool operator!= (const hashtable_iterator_base& x, + const hashtable_iterator_base& y) +{ + return x.m_cur_node != y.m_cur_node; +} + +template +struct hashtable_iterator : public hashtable_iterator_base +{ + typedef Value value_type; + typedef typename IF::type pointer; + typedef typename IF::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + hashtable_iterator (hash_node* p, hash_node** b) + : hashtable_iterator_base(p, b) { } + hashtable_iterator (hash_node** b) + : hashtable_iterator_base(*b, b) { } + hashtable_iterator (const hashtable_iterator& x) + : hashtable_iterator_base(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 +struct identity { + T operator()(const T& t) const { return t; } +}; + +template +struct extract1st { + typename Pair::first_type operator()(const Pair& p) { 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 + 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 bool operator()(X x, Y y) { return x < y; } +}; + +template +struct X { + static const int n_primes = 256; + static const unsigned long primes[n_primes + 1]; +}; + +template +const int X::n_primes; + +template +const unsigned long X::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::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::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 +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::ceil(*p * m_max_load_factor)); + return std::make_pair(true, *p); + } + else { + m_next_resize = static_cast(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 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 +struct map_base { }; + +template +struct map_base, false, Hashtable> +{ + typedef typename Pair::second_type mapped_type; +}; + +template +struct map_base, true, Hashtable> +{ + typedef typename Pair::second_type mapped_type; + mapped_type& operator[](const K& k) { + Hashtable* h = static_cast(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 +struct rehash_base { }; + +template +struct rehash_base +{ + float max_load_factor() const { + const Hashtable* This = static_cast(this); + return This->rehash_policy()->max_load_factor(); + } + + void max_load_factor(float z) { + Hashtable* This = static_cast(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 +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 +struct hash_code_base +{ +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) { 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* p, std::size_t N) { + return m_ranged_hash (m_extract (p->m_v), N); + } + + bool compare (const Key& k, hash_code_t, hash_node* n) + { return m_eq (k, m_extract(n->m_v)); } + + void copy_code (hash_node*, const hash_node*) { } + + 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 +struct hash_code_base ; + + +// 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 +struct hash_code_base +{ + 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) { 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* p, std::size_t N) { + return m_h2 (m_h1 (m_extract (p->m_v)), N); + } + + bool compare (const Key& k, hash_code_t, hash_node* n) + { return m_eq (k, m_extract(n->m_v)); } + + void copy_code (hash_node*, const hash_node*) { } + + 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 +struct hash_code_base +{ + 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) { 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* p, std::size_t N) { + return m_h2 (p->hash_code, N); + } + + bool compare (const Key& k, hash_code_t c, hash_node* n) + { return c == n->hash_code && m_eq (k, m_extract(n->m_v)); } + + void copy_code (hash_node* to, const hash_node* from) + { 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:::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, ). + +// ??? 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 +class hashtable + : public Internal::rehash_base >, + public Internal::hash_code_base, + public Internal::map_base > +{ +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 + local_iterator; + typedef Internal::node_iterator + const_local_iterator; + + typedef Internal::hashtable_iterator + iterator; + typedef Internal::hashtable_iterator + const_iterator; + +private: + typedef Internal::hash_node node; + typedef typename Allocator::template rebind::other node_allocator_t; + typedef typename Allocator::template rebind::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 + 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(size()) / static_cast(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 equal_range(const key_type& k); + std::pair 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, iterator>::type + Insert_Return_Type; + + node* find_node (node* p, const key_type& k, typename hashtable::hash_code_t c); + + std::pair 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()); } + Insert_Return_Type insert (const_iterator, const value_type& v) + { return this->insert(v); } + + template 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 hashtable::node* +hashtable::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 +void +hashtable::m_deallocate_node (node* n) +{ + get_allocator().destroy(&n->m_v); + m_node_allocator.deallocate(n, 1); +} + +template +void +hashtable +::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 hashtable::node** +hashtable::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(0x1000); + return p; +} + +template +void +hashtable +::m_deallocate_buckets (node** p, size_type n) +{ + bucket_allocator_t alloc(m_node_allocator); + alloc.deallocate(p, n+1); +} + +template +hashtable +::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 (), + Internal::hash_code_base (exk, eq, h1, h2, h), + Internal::map_base (), + 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 +template +hashtable +::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 (), + Internal::hash_code_base (exk, eq, h1, h2, h), + Internal::map_base (), + 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 +hashtable +::hashtable(const hashtable& ht) + : Internal::rehash_base (ht), + Internal::hash_code_base (ht), + Internal::map_base (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 +hashtable& +hashtable::operator= (const hashtable& ht) +{ + hashtable tmp(ht); + this->swap(tmp); + return *this; +} + +template +hashtable::~hashtable() +{ + clear(); + m_deallocate_buckets(m_buckets, m_bucket_count); +} + +template +void hashtable::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::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 +void +hashtable::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 hashtable::iterator +hashtable::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 hashtable::const_iterator +hashtable::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 hashtable::size_type +hashtable::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 +std::pair::iterator, + typename hashtable::iterator> +hashtable::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) + p1->m_incr_bucket(); + return std::make_pair(first, last); + } + else + return std::make_pair (this->end(), this->end()); +} + +template +std::pair::const_iterator, + typename hashtable::const_iterator> +hashtable::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) + p1->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 hashtable::node* +hashtable +::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 +std::pair::iterator, bool> +hashtable +::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 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 hashtable::iterator +hashtable +::insert (const value_type& v, std::tr1::false_type) +{ + std::pair 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 +template +void +hashtable::insert(InIter first, InIter last) +{ + size_type n_elt = Internal::distance_fw (first, last); + std::pair 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 +void hashtable::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 hashtable::size_type +hashtable::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 +void hashtable +::erase(const_iterator first, const_iterator last) +{ + while (first != last) { + const_iterator next = first; + ++next; + this->erase(first); + first = next; + } +} + +template +void hashtable::clear() +{ + m_deallocate_nodes (m_buckets, m_bucket_count); + m_element_count = 0; +} + +template +void +hashtable::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_ */ + diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map new file mode 100644 index 00000000000..8a724ebfad3 --- /dev/null +++ b/libstdc++-v3/include/tr1/unordered_map @@ -0,0 +1,157 @@ +// TR1 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. + +/** @file + * This is a TR1 C++ Library header. + */ + +#ifndef GNU_LIBSTDCXX_TR1_UNORDERED_MAP_ +#define GNU_LIBSTDCXX_TR1_UNORDERED_MAP_ + +#include +#include +#include +#include +#include + +namespace std { namespace tr1 { + +// XXX When we get typedef templates these class definitions will be unnecessary. + +template , + class Pred = std::equal_to, + class Alloc = std::allocator >, + bool cache_hash_code = false> +class unordered_map + : public hashtable , + Alloc, + Internal::extract1st >, Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, true> +{ + typedef hashtable , + Alloc, + Internal::extract1st >, Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, true> + Base; + +public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit unordered_map(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::extract1st >(), + a) + { } + + template + unordered_map(InputIterator f, InputIterator l, + size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, + n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::extract1st >(), + a) + { } +}; + +template , + class Pred = std::equal_to, + class Alloc = std::allocator >, + bool cache_hash_code = false> +class unordered_multimap + : public hashtable , + Alloc, + Internal::extract1st >, Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, false> +{ + typedef hashtable , + Alloc, + Internal::extract1st >, Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, false> + Base; + +public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit unordered_multimap(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::extract1st >(), + a) + { } + + + template + unordered_multimap(InputIterator f, InputIterator l, + typename Base::size_type n = 0, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, + n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::extract1st >(), + a) + { } +}; + +template +inline void swap (unordered_map& x, + unordered_map& y) +{ + x.swap(y); +} + +template +inline void swap (unordered_multimap& x, + unordered_multimap& y) +{ + x.swap(y); +} + +} } + +#endif /* GNU_LIBSTDCXX_TR1_UNORDERED_MAP_ */ diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set new file mode 100644 index 00000000000..554141cbad5 --- /dev/null +++ b/libstdc++-v3/include/tr1/unordered_set @@ -0,0 +1,151 @@ +// TR1 unordered_set -*- 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. + +/** @file + * This is a TR1 C++ Library header. + */ + +#ifndef GNU_LIBSTDCXX_TR1_UNORDERED_SET_ +#define GNU_LIBSTDCXX_TR1_UNORDERED_SET_ + +#include +#include +#include + +namespace std { namespace tr1 { + +// XXX When we get typedef templates these class definitions will be unnecessary. + +template , + class Pred = std::equal_to, + class Alloc = std::allocator, + bool cache_hash_code = false> +class unordered_set + : public hashtable , Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, true> +{ + typedef hashtable , Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, true> + Base; + +public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit unordered_set(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::identity(), + a) + { } + + template + unordered_set(InputIterator f, InputIterator l, + size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, + n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::identity(), + a) + { } +}; + +template , + class Pred = std::equal_to, + class Alloc = std::allocator, + bool cache_hash_code = false> +class unordered_multiset + : public hashtable , Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, false> +{ + typedef hashtable , Pred, + Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, false> + Base; + +public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit unordered_multiset(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::identity(), + a) + { } + + + template + unordered_multiset(InputIterator f, InputIterator l, + typename Base::size_type n = 0, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, + n, + hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), + eql, Internal::identity(), + a) + { } +}; + +template +inline void swap (unordered_set& x, + unordered_set& y) +{ + x.swap(y); +} + +template +inline void swap (unordered_multiset& x, + unordered_multiset& y) +{ + x.swap(y); +} + +} } + +#endif /* GNU_LIBSTDCXX_TR1_UNORDERED_SET_ */ diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/array_syntax.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/array_syntax.cc new file mode 100644 index 00000000000..308e5178c7b --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/array_syntax.cc @@ -0,0 +1,61 @@ +// { dg-do run } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.4 unordered_map +// Array version of insert + +#include +#include +#include +#include "testsuite_hooks.h" + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::tr1::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + m["red"] = 17; + VERIFY(m.size() == 1); + VERIFY(m.begin()->first == "red"); + VERIFY(m.begin()->second == 17); + VERIFY(m["red"] == 17); + + m["blue"] == 9; + VERIFY(m.size() == 2); + VERIFY(m["blue"] == 9); + + m["red"] = 5; + VERIFY(m.size() == 2); + VERIFY(m["red"] == 5); + VERIFY(m["blue"] == 9); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/map_single.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/map_single.cc new file mode 100644 index 00000000000..0cb60dfb1cd --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/map_single.cc @@ -0,0 +1,74 @@ +// { dg-do run } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.4 unordered_map +// Single-element insert + +#include +#include +#include +#include "testsuite_hooks.h" + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::tr1::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + std::pair p = m.insert(Pair("abcde", 3)); + VERIFY(p.second); + VERIFY(m.size() == 1); + VERIFY(std::distance(m.begin(), m.end()) == 1); + VERIFY(p.first == m.begin()); + VERIFY(p.first->first == "abcde"); + VERIFY(p.first->second == 3); +} + +void test02() +{ + typedef std::tr1::unordered_map Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + std::pair p1 = m.insert(Pair("abcde", 3)); + std::pair p2 = m.insert(Pair("abcde", 7)); + + VERIFY(p1.second); + VERIFY(!p2.second); + VERIFY(m.size() == 1); + VERIFY(p1.first == p2.first); + VERIFY(p1.first->first == "abcde"); + VERIFY(p2.first->second == 3); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multimap_single.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multimap_single.cc new file mode 100644 index 00000000000..bfd4056bb9e --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multimap_single.cc @@ -0,0 +1,78 @@ +// { dg-do run } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.6 unordered_multimap +// Single-element insert + +#include +#include +#include +#include "testsuite_hooks.h" + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::tr1::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + Map::iterator i = m.insert(Pair("abcde", 3)); + VERIFY(m.size() == 1); + VERIFY(std::distance(m.begin(), m.end()) == 1); + VERIFY(i == m.begin()); + VERIFY(i->first == "abcde"); + VERIFY(i->second == 3); +} + +void test02() +{ + typedef std::tr1::unordered_multimap Map; + typedef std::pair Pair; + + Map m; + VERIFY(m.empty()); + + m.insert(Pair("abcde", 3)); + m.insert(Pair("abcde", 7)); + + VERIFY(m.size() == 2); + VERIFY(std::distance(m.begin(), m.end()) == 2); + + Map::iterator i1 = m.begin(); + Map::iterator i2 = i1; + ++i2; + + VERIFY(i1->first == "abcde"); + VERIFY(i2->first == "abcde"); + VERIFY((i1->second == 3 && i2->second == 7) || + (i1->second == 7 && i2->second == 3)); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multiset_single.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multiset_single.cc new file mode 100644 index 00000000000..a02c12acf18 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/multiset_single.cc @@ -0,0 +1,69 @@ +// { dg-do run } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.5 unordered_multiset +// Single-element insert + +#include +#include +#include +#include "testsuite_hooks.h" + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::tr1::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + Set::iterator i = s.insert("abcde"); + VERIFY(s.size() == 1); + VERIFY(std::distance(s.begin(), s.end()) == 1); + VERIFY(i == s.begin()); + VERIFY(*i == "abcde"); +} + +void test02() +{ + typedef std::tr1::unordered_multiset Set; + Set s; + VERIFY(s.empty()); + + s.insert("abcde"); + Set::iterator i = s.insert("abcde"); + VERIFY(s.size() == 2); + VERIFY(std::distance(s.begin(), s.end()) == 2); + VERIFY(*i == "abcde"); + + Set::iterator i2 = s.begin(); + ++i2; + VERIFY(i == s.begin() || i == i2); + VERIFY(*(s.begin()) == "abcde" && *i2 == "abcde"); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/set_single.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/set_single.cc new file mode 100644 index 00000000000..203185af097 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/insert/set_single.cc @@ -0,0 +1,67 @@ +// { dg-do run } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.3 unordered_set +// Single-element insert + +#include +#include +#include +#include "testsuite_hooks.h" + +bool test __attribute__((unused)) = true; + +void test01() +{ + typedef std::tr1::unordered_set Set; + Set s; + VERIFY(s.empty()); + + std::pair p = s.insert("abcde"); + VERIFY(p.second); + VERIFY(s.size() == 1); + VERIFY(std::distance(s.begin(), s.end()) == 1); + VERIFY(p.first == s.begin()); + VERIFY(*p.first == "abcde"); +} + +void test02() +{ + typedef std::tr1::unordered_set Set; + Set s; + VERIFY(s.empty()); + + std::pair p1 = s.insert("abcde"); + std::pair p2 = s.insert("abcde"); + VERIFY(p1.second); + VERIFY(!p2.second); + VERIFY(s.size() == 1); + VERIFY(p1.first == p2.first); + VERIFY(*p1.first == "abcde"); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/hash.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/hash.cc new file mode 100644 index 00000000000..05838c5bd15 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/hash.cc @@ -0,0 +1,51 @@ +// { dg-do compile } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.3 class template hash + +#include +#include + +int main() +{ + using namespace std::tr1; + + // Verify that we can instantiate hash for every required type. + + hash hb; + hash hc; + hash hsc; + hash huc; + hash hw; + hash hs; + hash hi; + hash hl; + hash hus; + hash hui; + hash hul; + hash hf; + hash hd; + hash hld; + hash hp; + hash hstr; + hash hwstr; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/map.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/map.cc new file mode 100644 index 00000000000..88fe2b08628 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/map.cc @@ -0,0 +1,37 @@ +// { dg-do compile } + +// 2005-2-17 Matt Austern +// +// Copyright (C) 2004 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. + +// 6.3.4.4 unordered_map + +#include +#include + +int main() +{ + using namespace std; + using namespace std::tr1; + + unordered_map m1; + unordered_map, equal_to, + allocator >, true> s2; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multimap.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multimap.cc new file mode 100644 index 00000000000..8132a318fae --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multimap.cc @@ -0,0 +1,37 @@ +// { dg-do compile } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.6 unordered_multimap + +#include +#include + +int main() +{ + using namespace std; + using namespace std::tr1; + + unordered_multimap m1; + unordered_multimap, equal_to, + allocator >, true> s2; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multiset.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multiset.cc new file mode 100644 index 00000000000..902adafcdc3 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/multiset.cc @@ -0,0 +1,34 @@ +// { dg-do compile } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.5 unordered_multiset + +#include + +int main() +{ + using namespace std; + using namespace std::tr1; + + unordered_multiset s1; + unordered_multiset, equal_to, allocator, true> s2; +} diff --git a/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/set.cc b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/set.cc new file mode 100644 index 00000000000..52f3cb45140 --- /dev/null +++ b/libstdc++-v3/testsuite/tr1/6_containers/unordered/instantiate/set.cc @@ -0,0 +1,34 @@ +// { dg-do compile } + +// 2005-2-17 Matt Austern +// +// 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. + +// 6.3.4.3 unordered_set + +#include + +int main() +{ + using namespace std; + using namespace std::tr1; + + unordered_set s1; + unordered_set, equal_to, allocator, true> s2; +} -- 2.11.0