summaryrefslogtreecommitdiff
path: root/boost/intrusive/detail/hashtable_node.hpp
blob: ac6ab81948c0d572a09f45f53f1148308c5078ad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2007-2009
//
// 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)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
#define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP

#include <boost/intrusive/detail/config_begin.hpp>
#include <iterator>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/intrusive/pointer_traits.hpp>
#include <boost/intrusive/circular_list_algorithms.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/utilities.hpp>
//#include <boost/intrusive/detail/slist_node.hpp> //remove-me
#include <boost/intrusive/pointer_traits.hpp>
#include <cstddef>
#include <boost/pointer_cast.hpp>
#include <boost/move/move.hpp>


namespace boost {
namespace intrusive {
namespace detail {

template<int Dummy = 0>
struct prime_list_holder
{
   static const std::size_t prime_list[];
   static const std::size_t prime_list_size;
};

template<int Dummy>
const std::size_t prime_list_holder<Dummy>::prime_list[] = {
   3ul, 7ul, 11ul, 17ul, 29ul, 
   53ul, 97ul, 193ul, 389ul, 769ul,
   1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
   49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
   1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
   50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
   1610612741ul, 3221225473ul, 4294967291ul };

template<int Dummy>
const std::size_t prime_list_holder<Dummy>::prime_list_size
   = sizeof(prime_list)/sizeof(std::size_t);

template <class Slist>
struct bucket_impl : public Slist
{
   typedef Slist slist_type;
   bucket_impl()
   {}

   bucket_impl(const bucket_impl &)
   {}

   ~bucket_impl()
   {
      //This bucket is still being used!
      BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
   }

   bucket_impl &operator=(const bucket_impl&)
   {
      //This bucket is still in use!
      BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
      //Slist::clear();
      return *this;
   }
};

template<class Slist>
struct bucket_traits_impl
{
   private:
   BOOST_COPYABLE_AND_MOVABLE(bucket_traits_impl)

   public:
   /// @cond

   typedef typename pointer_traits
      <typename Slist::pointer>::template rebind_pointer
         < bucket_impl<Slist> >::type                                bucket_ptr;
   typedef typename Slist::size_type size_type;
   /// @endcond

   bucket_traits_impl(bucket_ptr buckets, size_type len)
      :  buckets_(buckets), buckets_len_(len)
   {}

   bucket_traits_impl(const bucket_traits_impl &x)
      : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
   {}


   bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x)
      : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
   {  x.buckets_ = bucket_ptr();   x.buckets_len_ = 0;  }

   bucket_traits_impl& operator=(BOOST_RV_REF(bucket_traits_impl) x)
   {
      buckets_ = x.buckets_; buckets_len_ = x.buckets_len_;
      x.buckets_ = bucket_ptr();   x.buckets_len_ = 0; return *this;
   }

   bucket_traits_impl& operator=(BOOST_COPY_ASSIGN_REF(bucket_traits_impl) x)
   {
      buckets_ = x.buckets_;  buckets_len_ = x.buckets_len_; return *this;
   }

   const bucket_ptr &bucket_begin() const
   {  return buckets_;  }

   size_type  bucket_count() const
   {  return buckets_len_;  }

   private:
   bucket_ptr  buckets_;
   size_type   buckets_len_;
};

template<class Container, bool IsConst>
class hashtable_iterator
   :  public std::iterator
         < std::forward_iterator_tag
         , typename Container::value_type
         , typename pointer_traits<typename Container::value_type*>::difference_type
         , typename detail::add_const_if_c
                     <typename Container::value_type, IsConst>::type *
         , typename detail::add_const_if_c
                     <typename Container::value_type, IsConst>::type &
         >
{
   typedef typename Container::real_value_traits                  real_value_traits;
   typedef typename Container::siterator                          siterator;
   typedef typename Container::const_siterator                    const_siterator;
   typedef typename Container::bucket_type                        bucket_type;

   typedef typename pointer_traits
      <typename Container::pointer>::template rebind_pointer
         < const Container >::type                                const_cont_ptr;
   typedef typename Container::size_type                          size_type;

   static typename Container::node_ptr downcast_bucket(typename bucket_type::node_ptr p)
   {
      return pointer_traits<typename Container::node_ptr>::
         pointer_to(static_cast<typename Container::node&>(*p));
   }

   public:
   typedef typename Container::value_type    value_type;
   typedef  typename detail::add_const_if_c
                     <typename Container::value_type, IsConst>::type *pointer;
   typedef typename detail::add_const_if_c
                     <typename Container::value_type, IsConst>::type &reference;

   hashtable_iterator ()
   {}

   explicit hashtable_iterator(siterator ptr, const Container *cont)
      :  slist_it_ (ptr),   cont_ (cont ? pointer_traits<const_cont_ptr>::pointer_to(*cont) : const_cont_ptr() )
   {}

   hashtable_iterator(const hashtable_iterator<Container, false> &other)
      :  slist_it_(other.slist_it()), cont_(other.get_container())
   {}

   const siterator &slist_it() const
   { return slist_it_; }

   hashtable_iterator<Container, false> unconst() const
   {  return hashtable_iterator<Container, false>(this->slist_it(), this->get_container());   }

   public:
   hashtable_iterator& operator++() 
   {  this->increment();   return *this;   }
   
   hashtable_iterator operator++(int)
   {
      hashtable_iterator result (*this);
      this->increment();
      return result;
   }

   friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
   { return i.slist_it_ == i2.slist_it_; }

   friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
   { return !(i == i2); }

   reference operator*() const
   { return *this->operator ->(); }

   pointer operator->() const
   {
      return boost::intrusive::detail::to_raw_pointer(this->get_real_value_traits()->to_value_ptr
         (downcast_bucket(slist_it_.pointed_node())));
   }

   const const_cont_ptr &get_container() const
   {  return cont_;  }

   const real_value_traits *get_real_value_traits() const
   {  return &this->get_container()->get_real_value_traits();  }

   private:
   void increment()
   {
      const Container *cont =  boost::intrusive::detail::to_raw_pointer(cont_);
      bucket_type* buckets = boost::intrusive::detail::to_raw_pointer(cont->bucket_pointer());
      size_type   buckets_len    = cont->bucket_count();

      ++slist_it_;
      if(buckets[0].cend().pointed_node()    <= slist_it_.pointed_node() && 
         slist_it_.pointed_node()<= buckets[buckets_len].cend().pointed_node()      ){
         //Now get the bucket_impl from the iterator
         const bucket_type &b = static_cast<const bucket_type&>
            (bucket_type::slist_type::container_from_end_iterator(slist_it_));

         //Now just calculate the index b has in the bucket array
         size_type n_bucket = static_cast<size_type>(&b - &buckets[0]);
         do{
            if (++n_bucket == buckets_len){
               slist_it_ = (&buckets[0] + buckets_len)->end();
               break;
            }
            slist_it_ = buckets[n_bucket].begin();
         }
         while (slist_it_ == buckets[n_bucket].end());
      }
   }

   siterator      slist_it_;
   const_cont_ptr cont_;
};

}  //namespace detail {
}  //namespace intrusive {
}  //namespace boost {

#endif