|
Go to the documentation of this file.
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
731 template< typename T,
732 typename KeyTransform,
737 : boost::mpl::true_ { };
739 template< typename Key,
745 : boost::mpl::true_ { };
|