// Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
-// Copyright (C) 2005 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006 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
#define GNU_LIBSTDCXX_TR1_HASHTABLE_
#include <utility> // For std::pair
+#include <memory>
#include <iterator>
#include <cstddef>
#include <cstdlib>
} // namespace Internal
+
//----------------------------------------------------------------------
// Auxiliary types used for all instantiations of hashtable: nodes
// and iterators.
template<typename Value>
struct hash_node<Value, true>
{
- Value m_v;
+ Value m_v;
std::size_t hash_code;
- hash_node* m_next;
+ hash_node* m_next;
};
template<typename Value>
struct hash_node<Value, false>
{
- Value m_v;
- hash_node* m_next;
+ Value m_v;
+ hash_node* m_next;
};
// Local iterators, used to iterate within a bucket but not between
const node_iterator_base<Value, cache>& y)
{ return x.m_cur != y.m_cur; }
- template<typename Value, bool is_const, bool cache>
+ template<typename Value, bool constant_iterators, 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;
+ typedef Value value_type;
+ typedef typename IF<constant_iterators, const Value*, Value*>::type
+ pointer;
+ typedef typename IF<constant_iterators, const Value&, Value&>::type
+ reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
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; }
}
};
+ template<typename Value, bool constant_iterators, bool cache>
+ struct node_const_iterator
+ : public node_iterator_base<Value, cache>
+ {
+ typedef Value value_type;
+ typedef const Value* pointer;
+ typedef const Value& reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ explicit
+ node_const_iterator(hash_node<Value, cache>* p = 0)
+ : node_iterator_base<Value, cache>(p) { }
+
+ node_const_iterator(const node_iterator<Value, constant_iterators,
+ cache>& x)
+ : node_iterator_base<Value, cache>(x.m_cur) { }
+
+ reference
+ operator*() const
+ { return this->m_cur->m_v; }
+
+ pointer
+ operator->() const
+ { return &this->m_cur->m_v; }
+
+ node_const_iterator&
+ operator++()
+ {
+ this->incr();
+ return *this;
+ }
+
+ node_const_iterator
+ operator++(int)
+ {
+ node_const_iterator tmp(*this);
+ this->incr();
+ return tmp;
+ }
+ };
+
template<typename Value, bool cache>
struct hashtable_iterator_base
{
void
m_incr_bucket();
- hash_node<Value, cache>* m_cur_node;
+ hash_node<Value, cache>* m_cur_node;
hash_node<Value, cache>** m_cur_bucket;
};
const hashtable_iterator_base<Value, cache>& y)
{ return x.m_cur_node != y.m_cur_node; }
- template<typename Value, bool is_const, bool cache>
+ template<typename Value, bool constant_iterators, 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;
+ typedef Value value_type;
+ typedef typename IF<constant_iterators, const Value*, Value*>::type
+ pointer;
+ typedef typename IF<constant_iterators, const Value&, Value&>::type
+ reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
hashtable_iterator(hash_node<Value, cache>* p,
hash_node<Value, cache>** 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; }
{
hashtable_iterator tmp(*this);
this->incr();
- return tmp; }
+ return tmp;
+ }
};
+ template<typename Value, bool constant_iterators, bool cache>
+ struct hashtable_const_iterator
+ : public hashtable_iterator_base<Value, cache>
+ {
+ typedef Value value_type;
+ typedef const Value* pointer;
+ typedef const Value& reference;
+ typedef std::ptrdiff_t difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ hashtable_const_iterator(hash_node<Value, cache>* p,
+ hash_node<Value, cache>** b)
+ : hashtable_iterator_base<Value, cache>(p, b) { }
+
+ explicit
+ hashtable_const_iterator(hash_node<Value, cache>** b)
+ : hashtable_iterator_base<Value, cache>(*b, b) { }
+
+ hashtable_const_iterator(const hashtable_iterator<Value,
+ constant_iterators, cache>& x)
+ : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }
+
+ reference
+ operator*() const
+ { return this->m_cur_node->m_v; }
+
+ pointer
+ operator->() const
+ { return &this->m_cur_node->m_v; }
+
+ hashtable_const_iterator&
+ operator++()
+ {
+ this->incr();
+ return *this;
+ }
+
+ hashtable_const_iterator
+ operator++(int)
+ {
+ hashtable_const_iterator tmp(*this);
+ this->incr();
+ return tmp;
+ }
+ };
} // namespace Internal
+
// ----------------------------------------------------------------------
// Many of class template hashtable's template parameters are policy
// classes. These are defaults for the policies.
typedef std::size_t result_type;
result_type
- operator() (first_argument_type r, second_argument_type N) const
+ operator()(first_argument_type r, second_argument_type N) const
{ return r % N; }
};
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;
+ float m_max_load_factor;
+ float m_growth_factor;
mutable std::size_t m_next_resize;
};
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);
+ 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;
}
{
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());
+ 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;
}
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);
+ 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());
+ 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);
} // 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
max_load_factor() const
{
const Hashtable* This = static_cast<const Hashtable*>(this);
- return This->rehash_policy()->max_load_factor();
+ return This->rehash_policy().max_load_factor();
}
void
std::size_t
bucket_index(const Key& k, hash_code_t, std::size_t N) const
- { return m_ranged_hash (k, N); }
+ { 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); }
+ { 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)); }
+ { return m_eq(k, m_extract(n->m_v)); }
+
+ void
+ store_code(hash_node<Value, false>*, hash_code_t) const
+ { }
void
copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
protected:
ExtractKey m_extract;
- Equal m_eq;
- H m_ranged_hash;
+ Equal m_eq;
+ H m_ranged_hash;
};
std::size_t
bucket_index(const Key&, hash_code_t c, std::size_t N) const
- { return m_h2 (c, N); }
+ { 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); }
+ { 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)); }
+ { return m_eq(k, m_extract(n->m_v)); }
+
+ void
+ store_code(hash_node<Value, false>*, hash_code_t) const
+ { }
void
copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
protected:
ExtractKey m_extract;
- Equal m_eq;
- H1 m_h1;
- H2 m_h2;
+ Equal m_eq;
+ H1 m_h1;
+ H2 m_h2;
};
// Specialization: hash function and range-hashing function,
typedef std::size_t hash_code_t;
hash_code_t
- m_hash_code (const Key& k) const
+ 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); }
+ { 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); }
+ { return m_h2(p->hash_code, N); }
bool
compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const
{ return c == n->hash_code && m_eq(k, m_extract(n->m_v)); }
void
+ store_code(hash_node<Value, true>* n, hash_code_t c) const
+ { n->hash_code = c; }
+
+ void
copy_code(hash_node<Value, true>* to,
const hash_node<Value, true>* from) const
{ to->hash_code = from->hash_code; }
protected:
ExtractKey m_extract;
- Equal m_eq;
- H1 m_h1;
- H2 m_h2;
+ Equal m_eq;
+ H1 m_h1;
+ H2 m_h2;
};
} // namespace internal
namespace std
{
-namespace tr1
-{
+_GLIBCXX_BEGIN_NAMESPACE(tr1)
+
//----------------------------------------------------------------------
// Class template hashtable, class definition.
// 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.
+ // constant_iterators: bool. true if iterator and const_iterator are
+ // both constant iterator types. This is true for unordered_set and
+ // unordered_multiset, false for unordered_map and unordered_multimap.
// 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
typename H1, typename H2,
typename H, typename RehashPolicy,
bool cache_hash_code,
- bool mutable_iterators,
+ bool constant_iterators,
bool unique_keys>
class hashtable
: public Internal::rehash_base<RehashPolicy,
hashtable<Key, Value, Allocator, ExtractKey,
Equal, H1, H2, H, RehashPolicy,
- cache_hash_code, mutable_iterators,
+ cache_hash_code, constant_iterators,
unique_keys> >,
public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H,
cache_hash_code>,
public Internal::map_base<Key, Value, ExtractKey, unique_keys,
hashtable<Key, Value, Allocator, ExtractKey,
Equal, H1, H2, H, RehashPolicy,
- cache_hash_code, mutable_iterators,
+ cache_hash_code, constant_iterators,
unique_keys> >
{
public:
- typedef Allocator allocator_type;
- typedef Value value_type;
- typedef Key key_type;
- typedef Equal key_equal;
+ 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 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,
+ typedef Internal::node_iterator<value_type, constant_iterators,
cache_hash_code>
- local_iterator;
- typedef Internal::node_iterator<value_type, false, cache_hash_code>
- const_local_iterator;
+ local_iterator;
+ typedef Internal::node_const_iterator<value_type, constant_iterators,
+ cache_hash_code>
+ const_local_iterator;
- typedef Internal::hashtable_iterator<value_type, !mutable_iterators,
+ typedef Internal::hashtable_iterator<value_type, constant_iterators,
cache_hash_code>
- iterator;
- typedef Internal::hashtable_iterator<value_type, false, cache_hash_code>
- const_iterator;
+ iterator;
+ typedef Internal::hashtable_const_iterator<value_type, constant_iterators,
+ cache_hash_code>
+ const_iterator;
private:
- typedef Internal::hash_node<Value, cache_hash_code> node;
+ typedef Internal::hash_node<Value, cache_hash_code> node;
typedef typename Allocator::template rebind<node>::other
- node_allocator_t;
+ node_allocator_t;
typedef typename Allocator::template rebind<node*>::other
- bucket_allocator_t;
+ 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_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);
template<typename InIter>
hashtable(InIter first, InIter last,
size_type bucket_hint,
- const H1&, const H2&, const H&,
+ const H1&, const H2&, const H&,
const Equal&, const ExtractKey&,
const allocator_type&);
max_size() const
{ return m_node_allocator.max_size(); }
+ public: // Observers
+ key_equal
+ key_eq() const
+ { return this->m_eq; }
+
+ // hash_function, if present, comes from hash_code_base.
+
public: // Bucket operations
size_type
bucket_count() const
bucket_size(size_type n) const
{ return std::distance(begin(n), end(n)); }
- size_type bucket(const key_type& k) const
+ size_type
+ bucket(const key_type& k) const
{
- return this->bucket_index(k, this->m_hash_code, this->m_bucket_count);
+ return this->bucket_index(k, this->m_hash_code(k),
+ this->m_bucket_count);
}
local_iterator
{ return local_iterator(m_buckets[n]); }
local_iterator
- end(size_type n)
+ end(size_type)
{ return local_iterator(0); }
const_local_iterator
{ return const_local_iterator(m_buckets[n]); }
const_local_iterator
- end(size_type n) const
+ end(size_type) const
{ return const_local_iterator(0); }
float
{
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
std::pair<iterator, bool>, iterator>::type
Insert_Return_Type;
+ typedef typename Internal::IF<unique_keys,
+ Internal::extract1st<Insert_Return_Type>,
+ Internal::identity<Insert_Return_Type>
+ >::type
+ Insert_Conv_Type;
+
node*
find_node(node* p, const key_type& k,
typename hashtable::hash_code_t c) const;
iterator
insert(const value_type&, std::tr1::false_type);
+ void
+ erase_node(node*, node**);
+
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
+
+ iterator
+ insert(iterator, const value_type& v)
+ { return iterator(Insert_Conv_Type()(this->insert(v))); }
+
+ const_iterator
insert(const_iterator, const value_type& v)
- { return this->insert(v); }
+ { return const_iterator(Insert_Conv_Type()(this->insert(v))); }
template<typename InIter>
void
insert(InIter first, InIter last);
- void
+ iterator
+ erase(iterator);
+
+ const_iterator
erase(const_iterator);
-
+
size_type
erase(const key_type&);
-
- void
+
+ iterator
+ erase(iterator, iterator);
+
+ const_iterator
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);
+ // Set number of buckets to be appropriate 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);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
m_allocate_node(const value_type& v)
{
node* n = m_node_allocator.allocate(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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
m_deallocate_node(node* n)
{
get_allocator().destroy(&n->m_v);
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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
m_deallocate_nodes(node** array, size_type n)
{
for (size_type i = 0; i < n; ++i)
{
node* tmp = p;
p = p->m_next;
- m_deallocate_node (tmp);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
+ 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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
m_deallocate_buckets(node** p, size_type n)
{
bucket_allocator_t alloc(m_node_allocator);
- alloc.deallocate(p, n+1);
+ 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>::
+ bool c, bool ci, bool u>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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::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),
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>
+ bool c, bool ci, bool u>
template<typename InIter>
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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>(),
+ : 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_bucket_count(0),
m_element_count(0),
m_rehash_policy()
{
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>::
+ bool c, bool ci, bool u>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
hashtable(const hashtable& ht)
: Internal::rehash_base<RP, hashtable>(ht),
Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),
m_element_count(ht.m_element_count),
m_rehash_policy(ht.m_rehash_policy)
{
- m_buckets = m_allocate_buckets (m_bucket_count);
+ m_buckets = m_allocate_buckets(m_bucket_count);
try
{
- for (size_t i = 0; i < ht.m_bucket_count; ++i)
+ for (size_type i = 0; i < ht.m_bucket_count; ++i)
{
node* n = ht.m_buckets[i];
node** tail = m_buckets + i;
}
}
}
- catch (...)
+ catch(...)
{
clear();
- m_deallocate_buckets (m_buckets, m_bucket_count);
+ m_deallocate_buckets(m_buckets, m_bucket_count);
__throw_exception_again;
}
}
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>::
+ bool c, bool ci, bool u>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
operator=(const hashtable& ht)
{
hashtable tmp(ht);
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>::
+ bool c, bool ci, bool u>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
~hashtable()
{
clear();
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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
swap(hashtable& x)
{
// The only base class with member variables is hash_code_base. We
// 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);
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 431. Swapping containers with unequal allocators.
+ std::__alloc_swap<node_allocator_t>::_S_do_it(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);
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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
find(const key_type& k)
{
- typename hashtable::hash_code_t code = this->m_hash_code (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);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
find(const key_type& k) const
{
- typename hashtable::hash_code_t code = this->m_hash_code (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);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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))
+ typename hashtable::hash_code_t code = this->m_hash_code(k);
+ std::size_t n = this->bucket_index(k, code, this->bucket_count());
+ std::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>
+ bool c, bool ci, bool u>
std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
- H2, H, RP, c, m, u>::iterator,
+ H2, H, RP, c, ci, 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>::
+ H2, H, RP, c, ci, u>::iterator>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
equal_range(const key_type& k)
{
- typename hashtable::hash_code_t code = this->m_hash_code (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);
+ 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))
+ for (; p1; p1 = p1->m_next)
+ if (!this->compare(k, code, p1))
break;
iterator first(p, head);
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>
+ bool c, bool ci, bool u>
std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
- H2, H, RP, c, m, u>::const_iterator,
+ H2, H, RP, c, ci, 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>::
+ H2, H, RP, c, ci, u>::const_iterator>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
equal_range(const key_type& k) const
{
- typename hashtable::hash_code_t code = this->m_hash_code (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);
+ 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))
+ for (; p1; p1 = p1->m_next)
+ if (!this->compare(k, code, p1))
break;
const_iterator first(p, head);
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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
find_node(node* p, const key_type& k,
typename hashtable::hash_code_t code) const
{
- for ( ; p ; p = p->m_next)
- if (this->compare (k, code, p))
+ for (; p; p = p->m_next)
+ if (this->compare(k, code, p))
return p;
return false;
}
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>
+ bool c, bool ci, 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>::
+ H2, H, RP, c, ci, u>::iterator, bool>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
+ typename hashtable::hash_code_t code = this->m_hash_code(k);
+ std::size_t 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
+ std::pair<bool, std::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);
+ node* new_node = m_allocate_node(v);
try
{
}
new_node->m_next = m_buckets[n];
+ this->store_code(new_node, code);
m_buckets[n] = new_node;
++m_element_count;
return std::make_pair(iterator(new_node, m_buckets + n), true);
}
- catch (...)
+ catch(...)
{
- m_deallocate_node (new_node);
+ m_deallocate_node(new_node);
__throw_exception_again;
}
}
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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
insert(const value_type& v, std::tr1::false_type)
{
std::pair<bool, std::size_t> do_rehash
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);
+ typename hashtable::hash_code_t code = this->m_hash_code(k);
+ std::size_t n = this->bucket_index(k, code, m_bucket_count);
- node* new_node = m_allocate_node (v);
+ node* new_node = m_allocate_node(v);
node* prev = find_node(m_buckets[n], k, code);
if (prev)
{
new_node->m_next = m_buckets[n];
m_buckets[n] = new_node;
}
+ this->store_code(new_node, code);
++m_element_count;
return iterator(new_node, m_buckets + n);
}
+ // For erase(iterator) and erase(const_iterator).
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>
+ bool c, bool ci, bool u>
+ void
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ erase_node(node* p, node** b)
+ {
+ node* cur = *b;
+ if (cur == p)
+ *b = 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 ci, bool u>
template<typename InIter>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
insert(InIter first, InIter last)
{
- size_type n_elt = Internal::distance_fw (first, last);
+ size_type n_elt = 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);
+ 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ erase(iterator i)
+ {
+ iterator result = i;
+ ++result;
+ erase_node(i.m_cur_node, i.m_cur_bucket);
+ return result;
+ }
+
+ template<typename K, typename V,
+ typename A, typename Ex, typename Eq,
+ typename H1, typename H2, typename H, typename RP,
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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;
+ const_iterator result = i;
+ ++result;
+ erase_node(i.m_cur_node, i.m_cur_bucket);
+ 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>
- 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>::
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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);
+ typename hashtable::hash_code_t code = this->m_hash_code(k);
+ std::size_t n = this->bucket_index(k, code, m_bucket_count);
+ size_type result = 0;
node** slot = m_buckets + n;
- while (*slot && ! this->compare (k, code, *slot))
+ while (*slot && !this->compare(k, code, *slot))
slot = &((*slot)->m_next);
- while (*slot && this->compare (k, code, *slot))
+ while (*slot && this->compare(k, code, *slot))
{
- node* n = *slot;
- *slot = n->m_next;
- m_deallocate_node (n);
+ node* p = *slot;
+ *slot = p->m_next;
+ m_deallocate_node(p);
--m_element_count;
+ ++result;
}
+
+ return result;
}
// ??? 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>::
+ template<typename K, typename V,
+ typename A, typename Ex, typename Eq,
+ typename H1, typename H2, typename H, typename RP,
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ erase(iterator first, iterator last)
+ {
+ while (first != last)
+ first = this->erase(first);
+ return last;
+ }
+
+ template<typename K, typename V,
+ typename A, typename Ex, typename Eq,
+ typename H1, typename H2, typename H, typename RP,
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
erase(const_iterator first, const_iterator last)
{
while (first != last)
- {
- const_iterator next = first;
- ++next;
- this->erase(first);
- first = next;
- }
+ first = this->erase(first);
+ return last;
}
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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, 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 ci, bool u>
+ void
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ rehash(size_type n)
+ {
+ m_rehash(std::max(m_rehash_policy.next_bkt(n),
+ m_rehash_policy.bkt_for_elements(m_element_count
+ + 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>
+ bool c, bool ci, bool u>
void
- hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::
- m_rehash(size_type N)
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ m_rehash(size_type n)
{
- node** new_array = m_allocate_buckets (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);
+ std::size_t 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_bucket_count = n;
m_buckets = new_array;
}
- catch (...)
+ 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(new_array, n);
+ m_deallocate_buckets(new_array, n);
m_deallocate_nodes(m_buckets, m_bucket_count);
m_element_count = 0;
__throw_exception_again;
}
}
-
-}
+
+_GLIBCXX_END_NAMESPACE
} // Namespace std::tr1
#endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */
OSDN Git Service
