Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: // (C) Copyright Ion Gaztanaga  2007-2013
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/intrusive for documentation.
Chris@16: //
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
Chris@16: #define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP
Chris@16: 
Chris@16: #include <boost/intrusive/detail/config_begin.hpp>
Chris@16: #include <iterator>
Chris@16: #include <boost/intrusive/detail/assert.hpp>
Chris@16: #include <boost/intrusive/pointer_traits.hpp>
Chris@16: #include <boost/intrusive/circular_list_algorithms.hpp>
Chris@16: #include <boost/intrusive/detail/mpl.hpp>
Chris@16: #include <boost/intrusive/detail/utilities.hpp>
Chris@16: #include <boost/intrusive/slist.hpp> //remove-me
Chris@16: #include <boost/intrusive/pointer_traits.hpp>
Chris@16: #include <boost/intrusive/trivial_value_traits.hpp>
Chris@16: #include <cstddef>
Chris@16: #include <boost/type_traits/make_unsigned.hpp>
Chris@16: #include <boost/pointer_cast.hpp>
Chris@16: #include <boost/move/core.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace intrusive {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template<int Dummy = 0>
Chris@16: struct prime_list_holder
Chris@16: {
Chris@16:    static const std::size_t prime_list[];
Chris@16:    static const std::size_t prime_list_size;
Chris@16: };
Chris@16: 
Chris@16: template<int Dummy>
Chris@16: const std::size_t prime_list_holder<Dummy>::prime_list[] = {
Chris@16:    3ul, 7ul, 11ul, 17ul, 29ul,
Chris@16:    53ul, 97ul, 193ul, 389ul, 769ul,
Chris@16:    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
Chris@16:    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
Chris@16:    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
Chris@16:    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
Chris@16:    1610612741ul, 3221225473ul, 4294967291ul };
Chris@16: 
Chris@16: template<int Dummy>
Chris@16: const std::size_t prime_list_holder<Dummy>::prime_list_size
Chris@16:    = sizeof(prime_list)/sizeof(std::size_t);
Chris@16: 
Chris@16: template <class Slist>
Chris@16: struct bucket_impl : public Slist
Chris@16: {
Chris@16:    typedef Slist slist_type;
Chris@16:    bucket_impl()
Chris@16:    {}
Chris@16: 
Chris@16:    bucket_impl(const bucket_impl &)
Chris@16:    {}
Chris@16: 
Chris@16:    ~bucket_impl()
Chris@16:    {
Chris@16:       //This bucket is still being used!
Chris@16:       BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
Chris@16:    }
Chris@16: 
Chris@16:    bucket_impl &operator=(const bucket_impl&)
Chris@16:    {
Chris@16:       //This bucket is still in use!
Chris@16:       BOOST_INTRUSIVE_INVARIANT_ASSERT(Slist::empty());
Chris@16:       //Slist::clear();
Chris@16:       return *this;
Chris@16:    }
Chris@16: };
Chris@16: 
Chris@16: template<class Slist>
Chris@16: struct bucket_traits_impl
Chris@16: {
Chris@16:    private:
Chris@16:    BOOST_COPYABLE_AND_MOVABLE(bucket_traits_impl)
Chris@16: 
Chris@16:    public:
Chris@16:    /// @cond
Chris@16: 
Chris@16:    typedef typename pointer_traits
Chris@16:       <typename Slist::pointer>::template rebind_pointer
Chris@16:          < bucket_impl<Slist> >::type                                bucket_ptr;
Chris@16:    typedef Slist slist;
Chris@16:    typedef typename Slist::size_type size_type;
Chris@16:    /// @endcond
Chris@16: 
Chris@16:    bucket_traits_impl(bucket_ptr buckets, size_type len)
Chris@16:       :  buckets_(buckets), buckets_len_(len)
Chris@16:    {}
Chris@16: 
Chris@16:    bucket_traits_impl(const bucket_traits_impl &x)
Chris@16:       : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
Chris@16:    {}
Chris@16: 
Chris@16:    bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x)
Chris@16:       : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
Chris@16:    {  x.buckets_ = bucket_ptr();   x.buckets_len_ = 0;  }
Chris@16: 
Chris@16:    bucket_traits_impl& operator=(BOOST_RV_REF(bucket_traits_impl) x)
Chris@16:    {
Chris@16:       buckets_ = x.buckets_; buckets_len_ = x.buckets_len_;
Chris@16:       x.buckets_ = bucket_ptr();   x.buckets_len_ = 0; return *this;
Chris@16:    }
Chris@16: 
Chris@16:    bucket_traits_impl& operator=(BOOST_COPY_ASSIGN_REF(bucket_traits_impl) x)
Chris@16:    {
Chris@16:       buckets_ = x.buckets_;  buckets_len_ = x.buckets_len_; return *this;
Chris@16:    }
Chris@16: 
Chris@16:    const bucket_ptr &bucket_begin() const
Chris@16:    {  return buckets_;  }
Chris@16: 
Chris@16:    size_type  bucket_count() const
Chris@16:    {  return buckets_len_;  }
Chris@16: 
Chris@16:    private:
Chris@16:    bucket_ptr  buckets_;
Chris@16:    size_type   buckets_len_;
Chris@16: };
Chris@16: 
Chris@16: template <class NodeTraits>
Chris@16: struct hash_reduced_slist_node_traits
Chris@16: {
Chris@16:    template <class U> static detail::one test(...);
Chris@16:    template <class U> static detail::two test(typename U::reduced_slist_node_traits* = 0);
Chris@16:    static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::two);
Chris@16: };
Chris@16: 
Chris@16: template <class NodeTraits>
Chris@16: struct apply_reduced_slist_node_traits
Chris@16: {
Chris@16:    typedef typename NodeTraits::reduced_slist_node_traits type;
Chris@16: };
Chris@16: 
Chris@16: template <class NodeTraits>
Chris@16: struct reduced_slist_node_traits
Chris@16: {
Chris@16:    typedef typename detail::eval_if_c
Chris@16:       < hash_reduced_slist_node_traits<NodeTraits>::value
Chris@16:       , apply_reduced_slist_node_traits<NodeTraits>
Chris@16:       , detail::identity<NodeTraits>
Chris@16:       >::type type;
Chris@16: };
Chris@16: 
Chris@16: template<class NodeTraits>
Chris@16: struct get_slist_impl
Chris@16: {
Chris@16:    typedef trivial_value_traits<NodeTraits, normal_link> trivial_traits;
Chris@16: 
Chris@16:    //Reducing symbol length
Chris@16:    struct type : make_slist
Chris@16:       < typename NodeTraits::node
Chris@16:       , boost::intrusive::value_traits<trivial_traits>
Chris@16:       , boost::intrusive::constant_time_size<false>
Chris@16: 	  , boost::intrusive::size_type<typename boost::make_unsigned
Chris@16:          <typename pointer_traits<typename NodeTraits::node_ptr>::difference_type>::type >
Chris@16:       >::type
Chris@16:    {};
Chris@16: };
Chris@16: 
Chris@16: }  //namespace detail {
Chris@16: 
Chris@16: template<class BucketValueTraits, bool IsConst>
Chris@16: class hashtable_iterator
Chris@16:    :  public std::iterator
Chris@16:          < std::forward_iterator_tag
Chris@16:          , typename BucketValueTraits::real_value_traits::value_type
Chris@16:          , typename pointer_traits<typename BucketValueTraits::real_value_traits::value_type*>::difference_type
Chris@16:          , typename detail::add_const_if_c
Chris@16:                      <typename BucketValueTraits::real_value_traits::value_type, IsConst>::type *
Chris@16:          , typename detail::add_const_if_c
Chris@16:                      <typename BucketValueTraits::real_value_traits::value_type, IsConst>::type &
Chris@16:          >
Chris@16: {
Chris@16:    typedef typename BucketValueTraits::real_value_traits          real_value_traits;
Chris@16:    typedef typename BucketValueTraits::real_bucket_traits         real_bucket_traits;
Chris@16:    typedef typename real_value_traits::node_traits                node_traits;
Chris@16:    typedef typename detail::get_slist_impl
Chris@16:       <typename detail::reduced_slist_node_traits
Chris@16:          <typename real_value_traits::node_traits>::type
Chris@16:       >::type                                                     slist_impl;
Chris@16:    typedef typename slist_impl::iterator                          siterator;
Chris@16:    typedef typename slist_impl::const_iterator                    const_siterator;
Chris@16:    typedef detail::bucket_impl<slist_impl>                        bucket_type;
Chris@16: 
Chris@16:    typedef typename pointer_traits
Chris@16:       <typename real_value_traits::pointer>::template rebind_pointer
Chris@16:          < const BucketValueTraits >::type                        const_bucketvaltraits_ptr;
Chris@16:    typedef typename slist_impl::size_type                         size_type;
Chris@16: 
Chris@16: 
Chris@16:    static typename node_traits::node_ptr downcast_bucket(typename bucket_type::node_ptr p)
Chris@16:    {
Chris@16:       return pointer_traits<typename node_traits::node_ptr>::
Chris@16:          pointer_to(static_cast<typename node_traits::node&>(*p));
Chris@16:    }
Chris@16: 
Chris@16:    public:
Chris@16:    typedef typename real_value_traits::value_type    value_type;
Chris@16:    typedef typename detail::add_const_if_c<value_type, IsConst>::type *pointer;
Chris@16:    typedef typename detail::add_const_if_c<value_type, IsConst>::type &reference;
Chris@16: 
Chris@16:    hashtable_iterator ()
Chris@16:    {}
Chris@16: 
Chris@16:    explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont)
Chris@16:       :  slist_it_ (ptr),   traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() )
Chris@16:    {}
Chris@16: 
Chris@16:    hashtable_iterator(const hashtable_iterator<BucketValueTraits, false> &other)
Chris@16:       :  slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits())
Chris@16:    {}
Chris@16: 
Chris@16:    const siterator &slist_it() const
Chris@16:    { return slist_it_; }
Chris@16: 
Chris@16:    hashtable_iterator<BucketValueTraits, false> unconst() const
Chris@16:    {  return hashtable_iterator<BucketValueTraits, false>(this->slist_it(), this->get_bucket_value_traits());   }
Chris@16: 
Chris@16:    public:
Chris@16:    hashtable_iterator& operator++()
Chris@16:    {  this->increment();   return *this;   }
Chris@16: 
Chris@16:    hashtable_iterator operator++(int)
Chris@16:    {
Chris@16:       hashtable_iterator result (*this);
Chris@16:       this->increment();
Chris@16:       return result;
Chris@16:    }
Chris@16: 
Chris@16:    friend bool operator== (const hashtable_iterator& i, const hashtable_iterator& i2)
Chris@16:    { return i.slist_it_ == i2.slist_it_; }
Chris@16: 
Chris@16:    friend bool operator!= (const hashtable_iterator& i, const hashtable_iterator& i2)
Chris@16:    { return !(i == i2); }
Chris@16: 
Chris@16:    reference operator*() const
Chris@16:    { return *this->operator ->(); }
Chris@16: 
Chris@16:    pointer operator->() const
Chris@16:    {
Chris@16:       return boost::intrusive::detail::to_raw_pointer(this->priv_real_value_traits().to_value_ptr
Chris@16:          (downcast_bucket(slist_it_.pointed_node())));
Chris@16:    }
Chris@16: 
Chris@16:    const const_bucketvaltraits_ptr &get_bucket_value_traits() const
Chris@16:    {  return traitsptr_;  }
Chris@16: 
Chris@16:    const real_value_traits &priv_real_value_traits() const
Chris@16:    {  return traitsptr_->priv_real_value_traits();  }
Chris@16: 
Chris@16:    const real_bucket_traits &priv_real_bucket_traits() const
Chris@16:    {  return traitsptr_->priv_real_bucket_traits();  }
Chris@16: 
Chris@16:    private:
Chris@16:    void increment()
Chris@16:    {
Chris@16:       const real_bucket_traits &rbuck_traits = this->priv_real_bucket_traits();
Chris@16:       bucket_type* const buckets = boost::intrusive::detail::to_raw_pointer(rbuck_traits.bucket_begin());
Chris@16:       const size_type buckets_len = rbuck_traits.bucket_count();
Chris@16: 
Chris@16:       ++slist_it_;
Chris@16:       const typename slist_impl::node_ptr n = slist_it_.pointed_node();
Chris@16:       const siterator first_bucket_bbegin = buckets->end();
Chris@16:       if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].cend().pointed_node()){
Chris@16:          //If one-past the node is inside the bucket then look for the next non-empty bucket
Chris@16:          //1. get the bucket_impl from the iterator
Chris@16:          const bucket_type &b = static_cast<const bucket_type&>
Chris@16:             (bucket_type::slist_type::container_from_end_iterator(slist_it_));
Chris@16: 
Chris@16:          //2. Now just calculate the index b has in the bucket array
Chris@16:          size_type n_bucket = static_cast<size_type>(&b - buckets);
Chris@16: 
Chris@16:          //3. Iterate until a non-empty bucket is found
Chris@16:          do{
Chris@16:             if (++n_bucket >= buckets_len){  //bucket overflow, return end() iterator
Chris@16:                slist_it_ = buckets->before_begin();
Chris@16:                return;
Chris@16:             }
Chris@16:          }
Chris@16:          while (buckets[n_bucket].empty());
Chris@16:          slist_it_ = buckets[n_bucket].begin();
Chris@16:       }
Chris@16:       else{
Chris@16:          //++slist_it_ yield to a valid object
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    siterator                  slist_it_;
Chris@16:    const_bucketvaltraits_ptr  traitsptr_;
Chris@16: };
Chris@16: 
Chris@16: }  //namespace intrusive {
Chris@16: }  //namespace boost {
Chris@16: 
Chris@16: #endif