9 #ifndef ADOBE_CLOSED_HASH_HPP
10 #define ADOBE_CLOSED_HASH_HPP
22 #include <boost/compressed_pair.hpp>
23 #include <boost/functional/hash.hpp>
24 #include <boost/iterator/iterator_adaptor.hpp>
25 #include <boost/iterator/iterator_facade.hpp>
26 #include <boost/static_assert.hpp>
27 #include <boost/type_traits/has_nothrow_constructor.hpp>
28 #include <boost/type_traits/remove_reference.hpp>
29 #include <boost/operators.hpp>
30 #include <boost/next_prior.hpp>
42 #include <adobe/implementation/swap.hpp>
50 namespace implementation {
54 template <
typename T,
typename V>
55 class closed_hash_iterator :
public boost::iterator_facade<closed_hash_iterator<T, V>, V,
56 std::bidirectional_iterator_tag>
58 typedef boost::iterator_facade<closed_hash_iterator<T, V>, V,
59 std::bidirectional_iterator_tag> inherited_t;
61 typedef typename T::node_t node_t;
63 typedef typename inherited_t::reference reference;
64 typedef typename inherited_t::difference_type difference_type;
65 typedef typename inherited_t::value_type value_type;
67 closed_hash_iterator() : node_m(0) { }
70 closed_hash_iterator(
const closed_hash_iterator<T, O>& x) : node_m(x.node_m) { }
82 reference dereference()
const {
return node_m->value_m; }
83 void increment() { node_m = node_m->next(); }
84 void decrement() { node_m = node_m->prior(); }
87 bool equal(
const closed_hash_iterator<T, O>& y)
const {
return node_m == y.node_m; }
89 std::size_t state()
const {
return node_m->state(); }
90 void set_state(std::size_t x) {
return node_m->set_state(x); }
92 explicit closed_hash_iterator(node_t* node) : node_m(node) { }
95 typename T::key_equal, typename T::allocator_type>;
96 friend class boost::iterator_core_access;
97 friend struct unsafe::set_next_fn<closed_hash_iterator>;
108 template <
typename T,
typename V>
109 struct set_next_fn<implementation::closed_hash_iterator<T, V> >
111 typedef typename implementation::closed_hash_iterator<T, V> iterator;
113 void operator()(iterator x, iterator y)
const
121 #ifndef ADOBE_NO_DOCUMENTATION
123 namespace version_1 {
152 template<
typename T,
153 typename KeyTransform,
157 class closed_hash_set : boost::equality_comparable<closed_hash_set<T, KeyTransform, Hash, Pred, A>,
158 closed_hash_set<T, KeyTransform, Hash, Pred, A>,
159 empty_base<closed_hash_set<T, KeyTransform, Hash, Pred, A> > >
164 typedef typename boost::remove_reference<typename key_transform::result_type>::type
181 typedef implementation::closed_hash_iterator<closed_hash_set, value_type>
iterator;
182 typedef implementation::closed_hash_iterator<closed_hash_set, const value_type>
const_iterator;
195 template <
typename U>
196 struct list_node_base
198 list_node_base() { next_m =
static_cast<U*
>(
this); prior_m =
static_cast<U*
>(
this); }
200 U* address() {
return static_cast<U*
>(
this); }
201 const U* address()
const {
return static_cast<const U*
>(
this); }
203 operator U& () {
return *
static_cast<U*
>(
this); }
204 operator const U& ()
const {
return *
static_cast<const U*
>(
this); }
206 friend inline void set_next(U& x, U& y)
207 { x.next_m =
reinterpret_cast<U*
>(
uintptr_t(&y) |
uintptr_t(x.state())); y.prior_m = &x; }
209 friend inline void set_next_raw(U& x, U& y)
210 { x.next_m = &y; y.prior_m = &x; }
212 std::size_t state()
const {
return std::size_t(
uintptr_t(next_m) &
uintptr_t(0x03UL)); }
213 void set_state(std::size_t x)
219 U* next()
const {
return reinterpret_cast<U*
>(
reinterpret_cast<uintptr_t>(next_m) & ~
uintptr_t(0x03UL)); }
220 U* prior()
const {
return prior_m; }
227 struct node_t : list_node_base<node_t>
232 typedef list_node_base<node_t> node_base_t;
251 sizeof(std::size_t))));
257 const allocator_type& allocator()
const {
return header_m.get().alloc_free_tail_m.first(); }
258 node_base_t& free_tail() {
return header_m.get().alloc_free_tail_m.second(); }
259 const node_base_t& free_tail()
const {
return header_m.get().alloc_free_tail_m.second(); }
260 node_base_t& used_tail() {
return header_m.get().used_tail_m; }
261 const node_base_t& used_tail()
const {
return header_m.get().used_tail_m; }
262 std::size_t& capacity() {
return header_m.get().capacity_m; }
263 const std::size_t& capacity()
const {
return header_m.get().capacity_m; }
264 std::size_t&
size() {
return header_m.get().size_m; }
265 const std::size_t&
size()
const {
return header_m.get().size_m; }
268 typedef node_t* node_ptr;
270 typedef boost::compressed_pair< hasher,
271 boost::compressed_pair< key_equal,
272 boost::compressed_pair< key_transform,
280 typedef header_t* header_pointer;
282 const header_pointer& header()
const {
return data_m.second().second().second(); }
283 header_pointer& header() {
return data_m.second().second().second(); }
302 data_m.second().first() = eq;
303 data_m.second().second().first() = kf;
307 template <
typename I>
310 template <
typename I>
318 data_m.second().first() = eq;
319 data_m.second().second().first() = kf;
338 template <
typename I>
339 closed_hash_set(I f, I l, move_ctor) { header() = 0; move_insert(f, l); }
351 if (n <= capacity())
return;
356 closed_hash_set tmp(n, hash_function(), key_eq(), key_function(), get_allocator());
380 iterator next(boost::next(location));
383 if ((location.state() == std::size_t(state_home)) && (next != end())
384 && (next.state() == std::size_t(state_misplaced)))
386 swap(*next, *location);
402 if (node == end())
return 0;
409 for(
iterator first(begin()), last(end()); first != last; first =
erase(first)) ;
419 if (empty())
return end();
423 if (node.state() != std::size_t(state_home))
return end();
425 return find(node, key);
443 {
return std::size_t(
find(key) != end()); }
445 template <
typename I>
446 void insert(I first, I last)
447 {
while (first != last) {
insert(*first); ++first; } }
449 template <
typename I>
450 void move_insert(I first, I last)
451 {
while (first != last) { insert(
adobe::move(*first)); ++first; } }
461 if (capacity() ==
size()) reserve(
size() ? 2 *
size() : 3);
463 iterator node = bucket(key_function()(x));
465 switch (node.state())
470 if (found != end()) {
481 case state_misplaced:
484 insert_raw(free,
adobe::move(*node), state_misplaced);
498 header()->size() += 1;
511 for(
iterator first(begin()), last(end()); first != last; ++first)
destroy(&*first);
512 raw_allocator alloc(get_allocator());
513 alloc.deallocate(reinterpret_cast<char*>(header()), 0);
524 if (x.
size() != y.
size())
return false;
528 if (iter == y.
end() || !(*first == *iter))
return false;
534 typedef typename allocator_type::template rebind<char>::other raw_allocator;
537 void allocate(
const allocator_type& a, size_type n)
541 static const std::size_t prime_table[] = { 3UL, 7UL, 17UL, 37UL, 79UL, 163UL, 331UL, 673UL,
542 1361UL, 2729UL, 5471UL, 10949UL, 21911UL, 43853UL, 87719UL, 175447UL, 350899UL,
543 701819UL, 1403641UL, 2807303UL, 5614657UL, 11229331UL, 22458671UL, 44917381UL,
544 89834777UL, 179669557UL, 359339171UL, 718678369UL, 1437356741UL, 2874713497UL,
548 assert(!header() &&
"WARNING (sparent@adobe.com) : About to write over allocated header.");
550 if (n == 0 && a == allocator_type())
return;
554 raw_allocator alloc(a);
556 header() =
reinterpret_cast<header_t*
>(alloc.allocate(
sizeof(header_t) -
sizeof(node_t)
557 +
sizeof(node_t) * n));
558 header()->capacity() = n;
559 header()->size() = 0;
564 node_t* prior = header()->free_tail().address();
565 for (node_ptr first(&header()->storage_m[0]), last(&header()->storage_m[0]+ n);
566 first != last; ++first)
568 set_next_raw(*prior, *first);
572 set_next_raw(*prior, header()->free_tail());
576 iterator bucket(
const key_type& key)
578 std::size_t slot(hash_function()(key) % capacity());
579 return iterator(&header()->storage_m[0] + slot);
582 iterator
find(iterator node,
const key_type& key)
586 if (key_eq()(key, key_function()(*node)))
return node;
588 }
while ((node != end()) && (node.state() != std::size_t(state_home)));
594 static void insert_raw(iterator location, value_type x, std::size_t state)
597 location.set_state(state);
602 void erase_raw(iterator location)
605 location.set_state(state_free);
609 iterator begin_free() {
return iterator(header() ? header()->free_tail().next() : 0); }
610 iterator end_free() {
return iterator(header() ? header()->free_tail().address() : 0); }
633 template<
typename Key,
639 get_element<0, pair<Key, T> >,
654 template <
typename I>
658 template <
typename I>
665 {
swap(x, *
this);
return *
this; }
668 {
swap(static_cast<set_type&>(x), static_cast<set_type&>(y)); }
672 {
return static_cast<const set_type&
>(x) == static_cast<const set_type&>(y); }
680 {
return !(x == y); }
682 #ifndef ADOBE_CLOSED_HASH_MAP_INDEX
683 #define ADOBE_CLOSED_HASH_MAP_INDEX 1
686 #if ADOBE_CLOSED_HASH_MAP_INDEX
703 #ifndef ADOBE_NO_DOCUMENTATION
723 adobe::version_1::closed_hash_set<T0, T1, T2, T3, T4 >);
725 adobe::version_1::closed_hash_map<T0, T1, T2, T3, T4 >);
731 template<
typename T,
732 typename KeyTransform,
737 : boost::mpl::true_ { };
739 template<
typename Key,
745 : boost::mpl::true_ { };