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 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
178 friend class implementation::closed_hash_iterator<
closed_hash_set, value_type>;
179 friend class implementation::closed_hash_iterator<
closed_hash_set, const value_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;
250 || (
sizeof(
compact_header_t) == (
sizeof(allocator_type) + 2 *
sizeof(node_base_t) + 2 *
251 sizeof(std::size_t))));
256 allocator_type& allocator() {
return header_m.
get().alloc_free_tail_m.first(); }
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(); }
293 allocate(allocator_type(), n);
297 const key_transform& kf = key_transform(),
298 const allocator_type& a = allocator_type())
302 data_m.second().first() = eq;
303 data_m.second().second().first() = kf;
307 template <
typename I>
310 template <
typename I>
312 const key_equal& eq = key_equal(),
313 const key_transform& kf = key_transform(),
314 const allocator_type& a = allocator_type())
318 data_m.second().first() = eq;
319 data_m.second().second().first() = kf;
333 {
return header() ? header()->allocator() : allocator_type(); }
338 template <
typename I>
339 closed_hash_set(I f, I l, move_ctor) { header() = 0; move_insert(f, l); }
344 size_type
size()
const {
return header() ? header()->size() : 0; }
345 size_type
max_size()
const {
return size_type(-1) /
sizeof(node_t); }
347 size_type
capacity()
const {
return header() ? header()->capacity() : 0; }
351 if (n <= capacity())
return;
353 if (!header()) allocate(allocator_type(), n);
356 closed_hash_set tmp(n, hash_function(), key_eq(), key_function(), get_allocator());
362 key_transform
key_function()
const {
return data_m.second().second().first(); }
364 key_equal
key_eq()
const {
return data_m.second().first(); }
366 iterator
begin() {
return iterator(header() ? header()->used_tail().next() : 0); }
367 iterator
end() {
return iterator(header() ? header()->used_tail().address() : 0); }
369 const_iterator
begin()
const {
return iterator(header() ? header()->used_tail().next() : 0); }
370 const_iterator
end()
const {
return iterator(header() ? const_cast<node_t*>(header()->used_tail().address()) : 0); }
372 reverse_iterator
rbegin() {
return reverse_iterator(end()); }
373 reverse_iterator
rend() {
return reverse_iterator(begin()); }
375 const_reverse_iterator
rbegin()
const {
return const_reverse_iterator(end()); }
376 const_reverse_iterator
rend()
const {
return const_reverse_iterator(begin()); }
380 iterator next(boost::next(location));
381 iterator result = next;
383 if ((location.state() == std::size_t(state_home)) && (next != end())
384 && (next.state() == std::size_t(state_misplaced)))
386 swap(*next, *location);
401 iterator node(
find(key));
402 if (node == end())
return 0;
409 for(iterator first(begin()), last(end()); first != last; first =
erase(first)) ;
419 if (empty())
return end();
421 iterator node(bucket(key));
423 if (node.state() != std::size_t(state_home))
return end();
425 return find(node, key);
430 const_iterator result =
find(key);
437 iterator result =
find(key);
443 {
return std::size_t(
find(key) != end()); }
445 template <
typename I>
447 {
while (first != last) { insert(*first); ++first; } }
449 template <
typename I>
451 {
while (first != last) { insert(
adobe::move(*first)); ++first; } }
459 std::pair<iterator, bool>
insert(value_type x)
461 if (capacity() ==
size()) reserve(
size() ? 2 *
size() : 3);
463 iterator node = bucket(key_function()(x));
465 switch (node.state())
469 iterator found =
find(node, key_function()(x));
470 if (found != end()) {
475 iterator free(begin_free());
481 case state_misplaced:
483 iterator free(begin_free());
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;
525 for (const_iterator first(x.
begin()), last(x.
end()); first != last; ++first)
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);
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 691 if (i == this->end())
return insert(
adobe::make_pair(x, mapped_type())).first->second;
703 #ifndef ADOBE_NO_DOCUMENTATION 731 template<
typename T,
732 typename KeyTransform,
737 : boost::mpl::true_ { };
739 template<
typename Key,
745 : boost::mpl::true_ { };
std::reverse_iterator< iterator > reverse_iterator
closed_hash_map & operator=(closed_hash_map x)
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
void skip_node(I location)
closed_hash_map(const closed_hash_map &x)
std::pair< iterator, iterator > equal_range(const key_type &key)
reverse_iterator rbegin()
closed_hash_set(size_type n, const hasher &hf, const key_equal &eq=key_equal(), const key_transform &kf=key_transform(), const allocator_type &a=allocator_type())
size_type capacity() const
friend bool operator==(const closed_hash_map &x, const closed_hash_map &y)
const_reverse_iterator rend() const
friend bool operator==(const closed_hash_set &x, const closed_hash_set &y)
move_from is used for move_ctors.
allocator_type get_allocator() const
void swap(adobe::lex_stream_t &, adobe::lex_stream_t &)
A hash based associative container.
I lower_bound(I f, I l, const T &x)
BOOST_STATIC_ASSERT(sizeof(closed_hash_set< int >)==sizeof(void *))
iterator erase(iterator location)
std::size_t count(const key_type &key) const
version_1::closed_hash_set closed_hash_set
const_iterator end() const
friend void swap(closed_hash_map &x, closed_hash_map &y)
const_iterator begin() const
iterator find(const key_type &key)
std::ptrdiff_t difference_type
ADOBE_NAME_TYPE_1("closed_hash_set:version_1:adobe", adobe::version_1::closed_hash_set< T0, adobe::identity< const T0 >, boost::hash< T0 >, std::equal_to< T0 >, adobe::capture_allocator< T0 > >)
key_transform key_function() const
closed_hash_set & operator=(closed_hash_set x)
const value_type * const_pointer
void splice_node_range(I location, I first, I last)
void reserve(size_type n)
size_type max_size() const
friend void swap(closed_hash_set &x, closed_hash_set &y)
closed_hash_map(I f, I l)
A hash based associative container.
friend bool operator!=(const closed_hash_map &x, const closed_hash_map &y)
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
implementation::closed_hash_iterator< closed_hash_set, value_type > iterator
closed_hash_set(I f, I l)
std::pair< iterator, bool > insert(value_type x)
closed_hash_set(move_from< closed_hash_set > x)
closed_hash_set(I f, I l, size_type n, const hasher &hf=hasher(), const key_equal &eq=key_equal(), const key_transform &kf=key_transform(), const allocator_type &a=allocator_type())
void move_insert(I first, I last)
void swap(circular_queue< T > &, circular_queue< T > &)
iterator insert(iterator, value_type x)
const_iterator find(const key_type &key) const
KeyTransform key_transform
ADOBE_NAME_TYPE_5("closed_hash_set:version_1:adobe", adobe::version_1::closed_hash_set< T0, T1, T2, T3, T4 >)
boost::remove_reference< typename key_transform::result_type >::type key_type
T::iterator erase(T &x, typename T::iterator f, typename T::iterator l)
closed_hash_map(move_from< closed_hash_map > x)
boost::range_iterator< InputRange >::type find(InputRange &range, const T &value)
find implementation
void insert(I first, I last)
closed_hash_set(const closed_hash_set &x)
closed_hash_set(size_type n)
const_reverse_iterator rbegin() const
version_1::closed_hash_map closed_hash_map
ADOBE_NAME_TYPE_2("closed_hash_map:version_1:adobe", adobe::version_1::closed_hash_map< T0, T1, boost::hash< T0 >, std::equal_to< T0 >, adobe::capture_allocator< adobe::pair< T0, T1 > > >)
const value_type & const_reference
implementation::closed_hash_iterator< closed_hash_set, const value_type > const_iterator
std::size_t erase(const key_type &key)
std::reverse_iterator< const_iterator > const_reverse_iterator
boost::range_size< Selection >::type size(const Selection &x)
pair< T1, T2 > make_pair(T1 x, T2 y)
hasher hash_function() const
mapped_type & operator[](const Key &x)
T & remove_const(const T &x)