// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. | |
// Copyright (C) 2005-2009 Daniel James | |
// Distributed under the Boost Software License, Version 1.0. (See accompanying | |
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
// This contains the basic data structure, apart from the actual values. There's | |
// no construction or deconstruction here. So this only depends on the pointer | |
// type. | |
#ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED | |
#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED | |
#include <boost/config.hpp> | |
#include <boost/iterator.hpp> | |
#include <boost/compressed_pair.hpp> | |
#include <boost/type_traits/aligned_storage.hpp> | |
#include <boost/type_traits/alignment_of.hpp> | |
#include <boost/unordered/detail/allocator_helpers.hpp> | |
#include <algorithm> | |
// This header defines most of the classes used to implement the unordered | |
// containers. It doesn't include the insert methods as they require a lot | |
// of preprocessor metaprogramming - they are in unique.hpp and equivalent.hpp. | |
// Template parameters: | |
// | |
// H = Hash Function | |
// P = Predicate | |
// A = Value Allocator | |
// G = Bucket group policy, 'grouped' or 'ungrouped' | |
// E = Key Extractor | |
#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) | |
# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) | |
// STLport doesn't have std::forward. | |
# else | |
# define BOOST_UNORDERED_STD_FORWARD | |
# endif | |
#endif | |
#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT) | |
#define BOOST_UNORDERED_EMPLACE_LIMIT 10 | |
#endif | |
#if !defined(BOOST_UNORDERED_STD_FORWARD) | |
#include <boost/preprocessor/repetition/enum_params.hpp> | |
#include <boost/preprocessor/repetition/enum_binary_params.hpp> | |
#include <boost/preprocessor/repetition/repeat_from_to.hpp> | |
#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ | |
BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg) | |
#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ | |
BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg) | |
#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ | |
BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg) | |
#endif | |
namespace boost { namespace unordered_detail { | |
static const float minimum_max_load_factor = 1e-3f; | |
static const std::size_t default_bucket_count = 11; | |
struct move_tag {}; | |
template <class T> class hash_unique_table; | |
template <class T> class hash_equivalent_table; | |
template <class Alloc, class Grouped> | |
class hash_node_constructor; | |
template <class ValueType> | |
struct set_extractor; | |
template <class Key, class ValueType> | |
struct map_extractor; | |
struct no_key; | |
// Explicitly call a destructor | |
#if defined(BOOST_MSVC) | |
#pragma warning(push) | |
#pragma warning(disable:4100) // unreferenced formal parameter | |
#endif | |
template <class T> | |
inline void destroy(T* x) { | |
x->~T(); | |
} | |
#if defined(BOOST_MSVC) | |
#pragma warning(pop) | |
#endif | |
//////////////////////////////////////////////////////////////////////////// | |
// | |
// This section implements buckets and nodes. Here's a rough | |
// inheritance diagram, to show how they pull together. | |
// | |
// For unordered_set/unordered_map: | |
// | |
// hash_bucket<A> | |
// | | |
// ungrouped_node_base<A> value_base<A::value_type> | |
// | | | |
// +--------------+-------------+ | |
// | | |
// hash_node<A, ungrouped> | |
// | |
// For unordered_multiset/unordered_multimap: | |
// | |
// hash_bucket<A> | |
// | | |
// grouped_node_base<A> value_base<A::value_type> | |
// | | | |
// +--------------+-------------+ | |
// | | |
// hash_node<A, grouped> | |
// hash_bucket | |
// | |
// hash_bucket is used for both the buckets and as a base class for | |
// nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point | |
// to either a bucket or a node. This is used later to implement a | |
// sentinel at the end of the bucket array. | |
template <class A> | |
class hash_bucket | |
{ | |
hash_bucket& operator=(hash_bucket const&); | |
public: | |
typedef hash_bucket<A> bucket; | |
typedef BOOST_DEDUCED_TYPENAME | |
boost::unordered_detail::rebind_wrap<A, bucket>::type | |
bucket_allocator; | |
typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr; | |
typedef bucket_ptr node_ptr; | |
node_ptr next_; | |
hash_bucket() : next_() {} | |
}; | |
// In containers with equivalent keys (unordered_multimap and | |
// unordered_multiset) equivalent nodes are grouped together, in | |
// containers with unique keys (unordered_map and unordered_set) | |
// individual nodes are treated as groups of one. The following two | |
// classes implement the data structure. | |
// This is used for containers with unique keys. There are no groups | |
// so it doesn't add any extra members, and just treats individual | |
// nodes as groups of one. | |
template <class A> | |
struct ungrouped_node_base : hash_bucket<A> { | |
typedef hash_bucket<A> bucket; | |
typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; | |
ungrouped_node_base() : bucket() {} | |
static inline node_ptr& next_group(node_ptr ptr); | |
static inline std::size_t group_count(node_ptr ptr); | |
static inline void add_to_bucket(node_ptr n, bucket& b); | |
static inline void add_after_node(node_ptr n, node_ptr position); | |
static void unlink_node(bucket& b, node_ptr n); | |
static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); | |
static void unlink_nodes(bucket& b, node_ptr end); | |
}; | |
// This is used for containers with equivalent keys. It implements a | |
// circular list running in the opposite direction to the linked | |
// list through the nodes. | |
template <class A> | |
struct grouped_node_base : hash_bucket<A> | |
{ | |
typedef hash_bucket<A> bucket; | |
typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; | |
node_ptr group_prev_; | |
grouped_node_base() : bucket(), group_prev_() {} | |
static inline node_ptr& next_group(node_ptr ptr); | |
static inline node_ptr first_in_group(node_ptr n); | |
static inline std::size_t group_count(node_ptr ptr); | |
static inline void add_to_bucket(node_ptr n, bucket& b); | |
static inline void add_after_node(node_ptr n, node_ptr position); | |
static void unlink_node(bucket& b, node_ptr n); | |
static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); | |
static void unlink_nodes(bucket& b, node_ptr end); | |
private: | |
static inline node_ptr split_group(node_ptr split); | |
static inline grouped_node_base& get(node_ptr ptr) { | |
return static_cast<grouped_node_base&>(*ptr); | |
} | |
}; | |
// These two classes implement an easy way to pass around the node | |
// group policy classes without the messy template parameters. | |
// Whenever you see the template parameter 'G' it's one of these. | |
struct ungrouped | |
{ | |
template <class A> | |
struct base { | |
typedef ungrouped_node_base<A> type; | |
}; | |
}; | |
struct grouped | |
{ | |
template <class A> | |
struct base { | |
typedef grouped_node_base<A> type; | |
}; | |
}; | |
// The space used to store values in a node. | |
template <class ValueType> | |
struct value_base | |
{ | |
typedef ValueType value_type; | |
BOOST_DEDUCED_TYPENAME boost::aligned_storage< | |
sizeof(value_type), | |
::boost::alignment_of<value_type>::value>::type data_; | |
void* address() { | |
return this; | |
} | |
value_type& value() { | |
return *(ValueType*) this; | |
} | |
value_type* value_ptr() { | |
return (ValueType*) this; | |
} | |
private: | |
value_base& operator=(value_base const&); | |
}; | |
// Node | |
template <class A, class G> | |
class hash_node : | |
public G::BOOST_NESTED_TEMPLATE base<A>::type, | |
public value_base<BOOST_DEDUCED_TYPENAME A::value_type> | |
{ | |
public: | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr; | |
static value_type& get_value(node_ptr p) { | |
return static_cast<hash_node&>(*p).value(); | |
} | |
static value_type* get_value_ptr(node_ptr p) { | |
return static_cast<hash_node&>(*p).value_ptr(); | |
} | |
private: | |
hash_node& operator=(hash_node const&); | |
}; | |
//////////////////////////////////////////////////////////////////////////// | |
// | |
// Iterator Base | |
// | |
// This is the iterator used internally, the external iterators are | |
// provided by lightweight wrappers (hash_iterator and | |
// hast_const_iterator) which provide the full iterator interface. | |
template <class A, class G> | |
class hash_iterator_base | |
{ | |
public: | |
typedef A value_allocator; | |
typedef hash_bucket<A> bucket; | |
typedef hash_node<A, G> node; | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; | |
bucket_ptr bucket_; | |
node_ptr node_; | |
hash_iterator_base() : bucket_(), node_() {} | |
explicit hash_iterator_base(bucket_ptr b) | |
: bucket_(b), | |
node_(b ? b->next_ : node_ptr()) {} | |
hash_iterator_base(bucket_ptr b, node_ptr n) | |
: bucket_(b), | |
node_(n) {} | |
bool operator==(hash_iterator_base const& x) const { | |
return node_ == x.node_; } | |
bool operator!=(hash_iterator_base const& x) const { | |
return node_ != x.node_; } | |
value_type& operator*() const { | |
return node::get_value(node_); | |
} | |
void increment_bucket(node_ptr n) { | |
while(!n) { | |
++bucket_; | |
n = bucket_->next_; | |
} | |
node_ = bucket_ == n ? node_ptr() : n; | |
} | |
void increment() { | |
increment_bucket(node_->next_); | |
} | |
}; | |
//////////////////////////////////////////////////////////////////////////// | |
// | |
// Now the main data structure: | |
// | |
// hash_buckets<A, G> hash_buffered_functions<H, P> | |
// | | | |
// +-------------+--------------+ | |
// | | |
// hash_table<T> | |
// | |
// T is a class which contains typedefs for all the types we need. | |
// hash_buckets | |
// | |
// This is responsible for allocating and deallocating buckets and nodes. | |
// | |
// Notes: | |
// 1. For the sake exception safety the consturctors don't allocate | |
// anything. | |
// 2. It's the callers responsibility to allocate the buckets before calling | |
// any of the methods (other than getters and setters). | |
template <class A, class G> | |
class hash_buckets | |
{ | |
hash_buckets(hash_buckets const&); | |
hash_buckets& operator=(hash_buckets const&); | |
public: | |
// Types | |
typedef A value_allocator; | |
typedef hash_bucket<A> bucket; | |
typedef hash_iterator_base<A, G> iterator_base; | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
typedef BOOST_DEDUCED_TYPENAME iterator_base::node node; | |
typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator | |
bucket_allocator; | |
typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; | |
typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type | |
node_allocator; | |
typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr; | |
// Members | |
bucket_ptr buckets_; | |
std::size_t bucket_count_; | |
boost::compressed_pair<bucket_allocator, node_allocator> allocators_; | |
// Data access | |
bucket_allocator const& bucket_alloc() const { | |
return allocators_.first(); } | |
node_allocator const& node_alloc() const { | |
return allocators_.second(); } | |
bucket_allocator& bucket_alloc() { | |
return allocators_.first(); } | |
node_allocator& node_alloc() { | |
return allocators_.second(); } | |
std::size_t max_bucket_count() const; | |
// Constructors | |
hash_buckets(node_allocator const& a, std::size_t n); | |
void create_buckets(); | |
~hash_buckets(); | |
// no throw | |
void swap(hash_buckets& other); | |
void move(hash_buckets& other); | |
// For the remaining functions, buckets_ must not be null. | |
bucket_ptr get_bucket(std::size_t n) const; | |
bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const; | |
std::size_t bucket_size(std::size_t index) const; | |
node_ptr bucket_begin(std::size_t n) const; | |
// Alloc/Dealloc | |
void delete_node(node_ptr); | |
// | |
void delete_buckets(); | |
void clear_bucket(bucket_ptr); | |
std::size_t delete_nodes(node_ptr begin, node_ptr end); | |
std::size_t delete_to_bucket_end(node_ptr begin); | |
}; | |
// Assigning and swapping the equality and hash function objects | |
// needs strong exception safety. To implement that normally we'd | |
// require one of them to be known to not throw and the other to | |
// guarantee strong exception safety. Unfortunately they both only | |
// have basic exception safety. So to acheive strong exception | |
// safety we have storage space for two copies, and assign the new | |
// copies to the unused space. Then switch to using that to use | |
// them. This is implemented in 'set_hash_functions' which | |
// atomically assigns the new function objects in a strongly | |
// exception safe manner. | |
template <class H, class P> class set_hash_functions; | |
template <class H, class P> | |
class hash_buffered_functions | |
{ | |
friend class set_hash_functions<H, P>; | |
hash_buffered_functions& operator=(hash_buffered_functions const&); | |
typedef boost::compressed_pair<H, P> function_pair; | |
typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage< | |
sizeof(function_pair), | |
::boost::alignment_of<function_pair>::value>::type aligned_function; | |
bool current_; // The currently active functions. | |
aligned_function funcs_[2]; | |
function_pair const& current() const { | |
return *static_cast<function_pair const*>( | |
static_cast<void const*>(&funcs_[current_])); | |
} | |
void construct(bool which, H const& hf, P const& eq) | |
{ | |
new((void*) &funcs_[which]) function_pair(hf, eq); | |
} | |
void construct(bool which, function_pair const& f) | |
{ | |
new((void*) &funcs_[which]) function_pair(f); | |
} | |
void destroy(bool which) | |
{ | |
boost::unordered_detail::destroy((function_pair*)(&funcs_[which])); | |
} | |
public: | |
hash_buffered_functions(H const& hf, P const& eq) | |
: current_(false) | |
{ | |
construct(current_, hf, eq); | |
} | |
hash_buffered_functions(hash_buffered_functions const& bf) | |
: current_(false) | |
{ | |
construct(current_, bf.current()); | |
} | |
~hash_buffered_functions() { | |
destroy(current_); | |
} | |
H const& hash_function() const { | |
return current().first(); | |
} | |
P const& key_eq() const { | |
return current().second(); | |
} | |
}; | |
template <class H, class P> | |
class set_hash_functions | |
{ | |
set_hash_functions(set_hash_functions const&); | |
set_hash_functions& operator=(set_hash_functions const&); | |
typedef hash_buffered_functions<H, P> buffered_functions; | |
buffered_functions& buffered_functions_; | |
bool tmp_functions_; | |
public: | |
set_hash_functions(buffered_functions& f, H const& h, P const& p) | |
: buffered_functions_(f), | |
tmp_functions_(!f.current_) | |
{ | |
f.construct(tmp_functions_, h, p); | |
} | |
set_hash_functions(buffered_functions& f, | |
buffered_functions const& other) | |
: buffered_functions_(f), | |
tmp_functions_(!f.current_) | |
{ | |
f.construct(tmp_functions_, other.current()); | |
} | |
~set_hash_functions() | |
{ | |
buffered_functions_.destroy(tmp_functions_); | |
} | |
void commit() | |
{ | |
buffered_functions_.current_ = tmp_functions_; | |
tmp_functions_ = !tmp_functions_; | |
} | |
}; | |
// This implements almost all of the required functionality, apart | |
// from some things that are specific to containers with unique and | |
// equivalent keys which is implemented in hash_unique_table and | |
// hash_equivalent_table. See unique.hpp and equivalent.hpp for | |
// their declaration and implementation. | |
template <class T> | |
class hash_table : public T::buckets, public T::buffered_functions | |
{ | |
hash_table(hash_table const&); | |
public: | |
typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; | |
typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; | |
typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; | |
typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; | |
typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; | |
typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base; | |
typedef BOOST_DEDUCED_TYPENAME T::buckets buckets; | |
typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; | |
typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; | |
typedef BOOST_DEDUCED_TYPENAME T::node node; | |
typedef BOOST_DEDUCED_TYPENAME T::bucket bucket; | |
typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; | |
typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; | |
typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator; | |
typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair; | |
// Members | |
std::size_t size_; | |
float mlf_; | |
// Cached data - invalid if !this->buckets_ | |
bucket_ptr cached_begin_bucket_; | |
std::size_t max_load_; | |
// Helper methods | |
key_type const& get_key(value_type const& v) const { | |
return extractor::extract(v); | |
} | |
key_type const& get_key_from_ptr(node_ptr n) const { | |
return extractor::extract(node::get_value(n)); | |
} | |
bool equal(key_type const& k, value_type const& v) const; | |
template <class Key, class Pred> | |
node_ptr find_iterator(bucket_ptr bucket, Key const& k, | |
Pred const&) const; | |
node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const; | |
node_ptr find_iterator(key_type const& k) const; | |
node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const; | |
// Load methods | |
std::size_t max_size() const; | |
std::size_t bucket_index(key_type const& k) const; | |
void max_load_factor(float z); | |
std::size_t min_buckets_for_size(std::size_t n) const; | |
std::size_t calculate_max_load(); | |
// Constructors | |
hash_table(std::size_t n, hasher const& hf, key_equal const& eq, | |
node_allocator const& a); | |
hash_table(hash_table const& x, node_allocator const& a); | |
hash_table(hash_table& x, move_tag m); | |
hash_table(hash_table& x, node_allocator const& a, move_tag m); | |
~hash_table() {} | |
hash_table& operator=(hash_table const&); | |
// Iterators | |
iterator_base begin() const { | |
return this->size_ ? | |
iterator_base(this->cached_begin_bucket_) : | |
iterator_base(); | |
} | |
iterator_base end() const { | |
return iterator_base(); | |
} | |
// Swap & Move | |
void swap(hash_table& x); | |
void fast_swap(hash_table& other); | |
void slow_swap(hash_table& other); | |
void partial_swap(hash_table& other); | |
void move(hash_table& x); | |
// Reserve and rehash | |
void create_for_insert(std::size_t n); | |
bool reserve_for_insert(std::size_t n); | |
void rehash(std::size_t n); | |
void rehash_impl(std::size_t n); | |
// Move/copy buckets | |
void move_buckets_to(buckets& dst); | |
void copy_buckets_to(buckets& dst) const; | |
// Misc. key methods | |
std::size_t count(key_type const& k) const; | |
iterator_base find(key_type const& k) const; | |
template <class Key, class Hash, class Pred> | |
iterator_base find(Key const& k, Hash const& h, Pred const& eq) const; | |
value_type& at(key_type const& k) const; | |
iterator_pair equal_range(key_type const& k) const; | |
// Erase | |
// | |
// no throw | |
void clear(); | |
std::size_t erase_key(key_type const& k); | |
iterator_base erase_return_iterator(iterator_base r); | |
void erase(iterator_base r); | |
std::size_t erase_group(node_ptr* it, bucket_ptr bucket); | |
iterator_base erase_range(iterator_base r1, iterator_base r2); | |
// recompute_begin_bucket | |
void init_buckets(); | |
// After an erase cached_begin_bucket_ might be left pointing to | |
// an empty bucket, so this is called to update it | |
// | |
// no throw | |
void recompute_begin_bucket(bucket_ptr b); | |
// This is called when a range has been erased | |
// | |
// no throw | |
void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2); | |
// no throw | |
float load_factor() const; | |
iterator_base emplace_empty_impl_with_node( | |
node_constructor&, std::size_t); | |
}; | |
/////////////////////////////////////////////////////////////////// | |
// | |
// Iterators | |
// iterator_access is used to access the internal iterator without | |
// making it publicly available. | |
class iterator_access | |
{ | |
public: | |
template <class Iterator> | |
static BOOST_DEDUCED_TYPENAME Iterator::base const& | |
get(Iterator const& it) | |
{ | |
return it.base_; | |
} | |
}; | |
template <class A, class G> class hash_iterator; | |
template <class A, class G> class hash_const_iterator; | |
template <class A, class G> class hash_local_iterator; | |
template <class A, class G> class hash_const_local_iterator; | |
// Local Iterators | |
// | |
// all no throw | |
template <class A, class G> | |
class hash_local_iterator | |
: public boost::iterator < | |
std::forward_iterator_tag, | |
BOOST_DEDUCED_TYPENAME A::value_type, | |
std::ptrdiff_t, | |
BOOST_DEDUCED_TYPENAME A::pointer, | |
BOOST_DEDUCED_TYPENAME A::reference> | |
{ | |
public: | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
private: | |
typedef hash_buckets<A, G> buckets; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node node; | |
typedef hash_const_local_iterator<A, G> const_local_iterator; | |
friend class hash_const_local_iterator<A, G>; | |
node_ptr ptr_; | |
public: | |
hash_local_iterator() : ptr_() {} | |
explicit hash_local_iterator(node_ptr x) : ptr_(x) {} | |
BOOST_DEDUCED_TYPENAME A::reference operator*() const { | |
return node::get_value(ptr_); | |
} | |
value_type* operator->() const { | |
return node::get_value_ptr(ptr_); | |
} | |
hash_local_iterator& operator++() { | |
ptr_ = ptr_->next_; return *this; | |
} | |
hash_local_iterator operator++(int) { | |
hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; } | |
bool operator==(hash_local_iterator x) const { | |
return ptr_ == x.ptr_; | |
} | |
bool operator==(const_local_iterator x) const { | |
return ptr_ == x.ptr_; | |
} | |
bool operator!=(hash_local_iterator x) const { | |
return ptr_ != x.ptr_; | |
} | |
bool operator!=(const_local_iterator x) const { | |
return ptr_ != x.ptr_; | |
} | |
}; | |
template <class A, class G> | |
class hash_const_local_iterator | |
: public boost::iterator < | |
std::forward_iterator_tag, | |
BOOST_DEDUCED_TYPENAME A::value_type, | |
std::ptrdiff_t, | |
BOOST_DEDUCED_TYPENAME A::const_pointer, | |
BOOST_DEDUCED_TYPENAME A::const_reference > | |
{ | |
public: | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
private: | |
typedef hash_buckets<A, G> buckets; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node node; | |
typedef hash_local_iterator<A, G> local_iterator; | |
friend class hash_local_iterator<A, G>; | |
ptr ptr_; | |
public: | |
hash_const_local_iterator() : ptr_() {} | |
explicit hash_const_local_iterator(ptr x) : ptr_(x) {} | |
hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {} | |
BOOST_DEDUCED_TYPENAME A::const_reference | |
operator*() const { | |
return node::get_value(ptr_); | |
} | |
value_type const* operator->() const { | |
return node::get_value_ptr(ptr_); | |
} | |
hash_const_local_iterator& operator++() { | |
ptr_ = ptr_->next_; return *this; | |
} | |
hash_const_local_iterator operator++(int) { | |
hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; | |
} | |
bool operator==(local_iterator x) const { | |
return ptr_ == x.ptr_; | |
} | |
bool operator==(hash_const_local_iterator x) const { | |
return ptr_ == x.ptr_; | |
} | |
bool operator!=(local_iterator x) const { | |
return ptr_ != x.ptr_; | |
} | |
bool operator!=(hash_const_local_iterator x) const { | |
return ptr_ != x.ptr_; | |
} | |
}; | |
// Iterators | |
// | |
// all no throw | |
template <class A, class G> | |
class hash_iterator | |
: public boost::iterator < | |
std::forward_iterator_tag, | |
BOOST_DEDUCED_TYPENAME A::value_type, | |
std::ptrdiff_t, | |
BOOST_DEDUCED_TYPENAME A::pointer, | |
BOOST_DEDUCED_TYPENAME A::reference > | |
{ | |
public: | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
private: | |
typedef hash_buckets<A, G> buckets; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node node; | |
typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; | |
typedef hash_const_iterator<A, G> const_iterator; | |
friend class hash_const_iterator<A, G>; | |
base base_; | |
public: | |
hash_iterator() : base_() {} | |
explicit hash_iterator(base const& x) : base_(x) {} | |
BOOST_DEDUCED_TYPENAME A::reference operator*() const { | |
return *base_; | |
} | |
value_type* operator->() const { | |
return &*base_; | |
} | |
hash_iterator& operator++() { | |
base_.increment(); return *this; | |
} | |
hash_iterator operator++(int) { | |
hash_iterator tmp(base_); base_.increment(); return tmp; | |
} | |
bool operator==(hash_iterator const& x) const { | |
return base_ == x.base_; | |
} | |
bool operator==(const_iterator const& x) const { | |
return base_ == x.base_; | |
} | |
bool operator!=(hash_iterator const& x) const { | |
return base_ != x.base_; | |
} | |
bool operator!=(const_iterator const& x) const { | |
return base_ != x.base_; | |
} | |
}; | |
template <class A, class G> | |
class hash_const_iterator | |
: public boost::iterator < | |
std::forward_iterator_tag, | |
BOOST_DEDUCED_TYPENAME A::value_type, | |
std::ptrdiff_t, | |
BOOST_DEDUCED_TYPENAME A::const_pointer, | |
BOOST_DEDUCED_TYPENAME A::const_reference > | |
{ | |
public: | |
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; | |
private: | |
typedef hash_buckets<A, G> buckets; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node node; | |
typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; | |
typedef hash_iterator<A, G> iterator; | |
friend class hash_iterator<A, G>; | |
friend class iterator_access; | |
base base_; | |
public: | |
hash_const_iterator() : base_() {} | |
explicit hash_const_iterator(base const& x) : base_(x) {} | |
hash_const_iterator(iterator const& x) : base_(x.base_) {} | |
BOOST_DEDUCED_TYPENAME A::const_reference operator*() const { | |
return *base_; | |
} | |
value_type const* operator->() const { | |
return &*base_; | |
} | |
hash_const_iterator& operator++() { | |
base_.increment(); return *this; | |
} | |
hash_const_iterator operator++(int) { | |
hash_const_iterator tmp(base_); base_.increment(); return tmp; | |
} | |
bool operator==(iterator const& x) const { | |
return base_ == x.base_; | |
} | |
bool operator==(hash_const_iterator const& x) const { | |
return base_ == x.base_; | |
} | |
bool operator!=(iterator const& x) const { | |
return base_ != x.base_; | |
} | |
bool operator!=(hash_const_iterator const& x) const { | |
return base_ != x.base_; | |
} | |
}; | |
//////////////////////////////////////////////////////////////////////////// | |
// | |
// types | |
// | |
// This is used to convieniently pass around a container's typedefs | |
// without having 7 template parameters. | |
template <class K, class V, class H, class P, class A, class E, class G> | |
struct types | |
{ | |
public: | |
typedef K key_type; | |
typedef V value_type; | |
typedef H hasher; | |
typedef P key_equal; | |
typedef A value_allocator; | |
typedef E extractor; | |
typedef G group_type; | |
typedef hash_node_constructor<value_allocator, group_type> | |
node_constructor; | |
typedef hash_buckets<value_allocator, group_type> buckets; | |
typedef hash_buffered_functions<hasher, key_equal> buffered_functions; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node node; | |
typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; | |
typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr; | |
typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base; | |
typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator; | |
typedef std::pair<iterator_base, iterator_base> iterator_pair; | |
}; | |
}} | |
#endif |