ceph/src/boost/libs/intrusive/test/bounded_pointer.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Matei David 2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOUNDED_POINTER_HPP
  14 #define BOUNDED_POINTER_HPP
  15
  16 #include <iostream>
  17 #include <cstdlib>
  18 #include <cassert>
  19 #include <boost/container/vector.hpp>
  20 #include <boost/intrusive/detail/mpl.hpp>
  21 #include <boost/intrusive/pointer_traits.hpp>
  22 #include <boost/core/no_exceptions_support.hpp>
  23 #include <boost/move/adl_move_swap.hpp>
  24
  25 template < typename T >
  26 class bounded_pointer;
  27
  28 template < typename T >
  29 class bounded_reference;
  30
  31 template < typename T >
  32 class bounded_allocator;
  33
  34
  35 template < typename T >
  36 class bounded_pointer
  37 {
  38    private:
  39    void unspecified_bool_type_func() const {}
  40    typedef void (bounded_pointer::*unspecified_bool_type)() const;
  41
  42    public:
  43    typedef typename boost::intrusive::detail::remove_const< T >::type mut_val_t;
  44    typedef const mut_val_t const_val_t;
  45
  46    typedef bounded_reference<T>  reference;
  47
  48    static const unsigned char max_offset = (unsigned char)-1;
  49
  50    bounded_pointer() : m_offset(max_offset) {}
  51
  52    bounded_pointer(const bounded_pointer& other)
  53       : m_offset(other.m_offset)
  54    {}
  55
  56    template<class T2>
  57    bounded_pointer( const bounded_pointer<T2> &other
  58                   , typename boost::intrusive::detail::enable_if_convertible<T2*, T*>::type* = 0)
  59       :  m_offset(other.m_offset)
  60    {}
  61
  62    bounded_pointer& operator = (const bounded_pointer& other)
  63    { m_offset = other.m_offset; return *this; }
  64
  65    template <class T2>
  66    typename boost::intrusive::detail::enable_if_convertible<T2*, T*, bounded_pointer&>::type
  67       operator= (const bounded_pointer<T2> & other)
  68    {  m_offset = other.m_offset;  return *this;  }
  69
  70    const bounded_pointer< typename boost::intrusive::detail::remove_const< T >::type >& unconst() const
  71    { return *reinterpret_cast< const bounded_pointer< typename boost::intrusive::detail::remove_const< T >::type >* >(this); }
  72
  73    bounded_pointer< typename boost::intrusive::detail::remove_const< T >::type >& unconst()
  74    { return *reinterpret_cast< bounded_pointer< typename boost::intrusive::detail::remove_const< T >::type >* >(this); }
  75
  76    static mut_val_t* base()
  77    {
  78       assert(bounded_allocator< mut_val_t >::inited());
  79       return &bounded_allocator< mut_val_t >::m_base[0];
  80    }
  81
  82    static bounded_pointer pointer_to(bounded_reference< T > r) { return &r; }
  83
  84    template<class U>
  85    static bounded_pointer const_cast_from(const bounded_pointer<U> &uptr)
  86    {  return uptr.unconst();  }
  87
  88    operator unspecified_bool_type() const
  89    {
  90       return m_offset != max_offset? &bounded_pointer::unspecified_bool_type_func : 0;
  91    }
  92
  93    T* raw() const
  94    { return base() + m_offset; }
  95
  96    bounded_reference< T > operator * () const
  97    { return bounded_reference< T >(*this); }
  98
  99    T* operator -> () const
 100       { return raw(); }
 101
 102    bounded_pointer& operator ++ ()
 103    { ++m_offset; return *this; }
 104
 105    bounded_pointer operator ++ (int)
 106    { bounded_pointer res(*this); ++(*this); return res; }
 107
 108    friend bool operator == (const bounded_pointer& lhs, const bounded_pointer& rhs)
 109    { return lhs.m_offset == rhs.m_offset;   }
 110
 111    friend bool operator != (const bounded_pointer& lhs, const bounded_pointer& rhs)
 112    { return lhs.m_offset != rhs.m_offset;   }
 113
 114    friend bool operator < (const bounded_pointer& lhs, const bounded_pointer& rhs)
 115    { return lhs.m_offset < rhs.m_offset;   }
 116
 117    friend bool operator <= (const bounded_pointer& lhs, const bounded_pointer& rhs)
 118    { return lhs.m_offset <= rhs.m_offset;   }
 119
 120    friend bool operator >= (const bounded_pointer& lhs, const bounded_pointer& rhs)
 121    { return lhs.m_offset >= rhs.m_offset;   }
 122
 123    friend bool operator > (const bounded_pointer& lhs, const bounded_pointer& rhs)
 124    { return lhs.m_offset > rhs.m_offset;   }
 125
 126    friend std::ostream& operator << (std::ostream& os, const bounded_pointer& ptr)
 127    {
 128       os << static_cast< int >(ptr.m_offset);
 129       return os;
 130    }
 131    private:
 132
 133    template <typename> friend class bounded_pointer;
 134    friend class bounded_reference< T >;
 135    friend class bounded_allocator< T >;
 136
 137    unsigned char m_offset;
 138 }; // class bounded_pointer
 139
 140 template < typename T >
 141 class bounded_reference
 142 {
 143    public:
 144    typedef typename boost::intrusive::detail::remove_const< T >::type mut_val_t;
 145    typedef const mut_val_t const_val_t;
 146    typedef bounded_pointer< T > pointer;
 147    static const unsigned char max_offset = pointer::max_offset;
 148
 149
 150    bounded_reference()
 151       : m_offset(max_offset)
 152    {}
 153
 154    bounded_reference(const bounded_reference& other)
 155       : m_offset(other.m_offset)
 156    {}
 157
 158    T& raw() const
 159    { assert(m_offset != max_offset); return *(bounded_pointer< T >::base() + m_offset); }
 160
 161    operator T& () const
 162    { assert(m_offset != max_offset); return raw(); }
 163
 164    bounded_pointer< T > operator & () const
 165    { assert(m_offset != max_offset); bounded_pointer< T > res; res.m_offset = m_offset; return res; }
 166
 167    bounded_reference& operator = (const T& rhs)
 168    { assert(m_offset != max_offset); raw() = rhs; return *this; }
 169
 170    bounded_reference& operator = (const bounded_reference& rhs)
 171    { assert(m_offset != max_offset); raw() = rhs.raw(); return *this; }
 172
 173    template<class T2>
 174    bounded_reference( const bounded_reference<T2> &other
 175                     , typename boost::intrusive::detail::enable_if_convertible<T2*, T*>::type* = 0)
 176       :  m_offset(other.m_offset)
 177    {}
 178
 179    template <class T2>
 180    typename boost::intrusive::detail::enable_if_convertible<T2*, T*, bounded_reference&>::type
 181       operator= (const bounded_reference<T2> & other)
 182    {  m_offset = other.m_offset;  return *this;  }
 183
 184    friend std::ostream& operator << (std::ostream& os, const bounded_reference< T >& ref)
 185    {
 186       os << "[bptr=" << static_cast< int >(ref.m_offset) << ",deref=" << ref.raw() << "]";
 187       return os;
 188    }
 189
 190    // the copy asop is shallow; we need swap overload to shuffle a vector of references
 191    friend void swap(bounded_reference& lhs, bounded_reference& rhs)
 192    {  ::boost::adl_move_swap(lhs.m_offset, rhs.m_offset); }
 193
 194    private:
 195    template <typename> friend class bounded_reference;
 196    friend class bounded_pointer< T >;
 197    bounded_reference(bounded_pointer< T > bptr) : m_offset(bptr.m_offset) { assert(m_offset != max_offset); }
 198
 199    unsigned char m_offset;
 200 }; // class bounded_reference
 201
 202 template < typename T >
 203 class bounded_allocator
 204 {
 205    public:
 206    typedef T value_type;
 207    typedef bounded_pointer< T > pointer;
 208
 209    static const unsigned char max_offset = pointer::max_offset;
 210
 211    pointer allocate(size_t n)
 212    {
 213       assert(inited());
 214       assert(n == 1);(void)n;
 215       pointer p;
 216       unsigned char i;
 217       for (i = 0; i < max_offset && m_in_use[i]; ++i);
 218       assert(i < max_offset);
 219       p.m_offset = i;
 220       m_in_use[p.m_offset] = true;
 221       ++m_in_use_count;
 222       return p;
 223    }
 224
 225    void deallocate(pointer p, size_t n)
 226    {
 227       assert(inited());
 228       assert(n == 1);(void)n;
 229       assert(m_in_use[p.m_offset]);
 230       m_in_use[p.m_offset] = false;
 231       --m_in_use_count;
 232    }
 233
 234    // static methods
 235    static void init()
 236    {
 237       assert(m_in_use.empty());
 238       m_in_use = boost::container::vector< bool >(max_offset, false);
 239       // allocate non-constructed storage
 240       m_base = static_cast< T* >(::operator new [] (max_offset * sizeof(T)));
 241    }
 242
 243    static bool inited()
 244    {
 245       return m_in_use.size() == max_offset;
 246    }
 247
 248    static bool is_clear()
 249    {
 250       assert(inited());
 251       for (unsigned char i = 0; i < max_offset; ++i)
 252       {
 253          if (m_in_use[i])
 254          {
 255                return false;
 256          }
 257       }
 258       return true;
 259    }
 260
 261    static void destroy()
 262    {
 263       // deallocate storage without destructors
 264       ::operator delete [] (m_base);
 265       m_in_use.clear();
 266    }
 267
 268    private:
 269    friend class bounded_pointer< T >;
 270    friend class bounded_pointer< const T >;
 271    static T* m_base;
 272    static boost::container::vector< bool > m_in_use;
 273    static std::size_t m_in_use_count;
 274 }; // class bounded_allocator
 275
 276 template <class BoundedAllocator>
 277 class bounded_allocator_scope
 278 {
 279    public:
 280    bounded_allocator_scope()
 281    {  BoundedAllocator::init();  }
 282
 283    ~bounded_allocator_scope()
 284    {
 285       assert(BoundedAllocator::is_clear());
 286       BoundedAllocator::destroy();
 287    }
 288 };
 289
 290 template < typename T >
 291 T* bounded_allocator< T >::m_base = 0;
 292
 293 template < typename T >
 294 boost::container::vector< bool > bounded_allocator< T >::m_in_use;
 295
 296 template < typename T >
 297 std::size_t bounded_allocator< T >::m_in_use_count;
 298
 299 template < typename T >
 300 class bounded_reference_cont
 301     : private boost::container::vector< bounded_reference< T > >
 302 {
 303    private:
 304    typedef T val_type;
 305    typedef boost::container::vector< bounded_reference< T > > Base;
 306    typedef bounded_allocator< T > allocator_type;
 307    typedef bounded_pointer< T > pointer;
 308
 309    public:
 310    typedef typename Base::value_type value_type;
 311    typedef typename Base::iterator iterator;
 312    typedef typename Base::const_iterator const_iterator;
 313    typedef typename Base::reference reference;
 314    typedef typename Base::const_reference const_reference;
 315    typedef typename Base::reverse_iterator reverse_iterator;
 316    typedef typename Base::const_reverse_iterator const_reverse_iterator;
 317
 318    using Base::begin;
 319    using Base::rbegin;
 320    using Base::end;
 321    using Base::rend;
 322    using Base::front;
 323    using Base::back;
 324    using Base::size;
 325    using Base::operator[];
 326    using Base::push_back;
 327
 328    explicit bounded_reference_cont(size_t n = 0)
 329       : Base(), m_allocator()
 330    {
 331       for (size_t i = 0; i < n; ++i){
 332          pointer p = m_allocator.allocate(1);
 333          BOOST_TRY{
 334             new (p.raw()) val_type();
 335          }
 336          BOOST_CATCH(...){
 337             m_allocator.deallocate(p, 1);
 338             BOOST_RETHROW
 339          }
 340          BOOST_CATCH_END
 341          Base::push_back(*p);
 342       }
 343    }
 344
 345    bounded_reference_cont(const bounded_reference_cont& other)
 346       : Base(), m_allocator(other.m_allocator)
 347    {  *this = other;  }
 348
 349    template < typename InputIterator >
 350    bounded_reference_cont(InputIterator it_start, InputIterator it_end)
 351       : Base(), m_allocator()
 352    {
 353       for (InputIterator it = it_start; it != it_end; ++it){
 354          pointer p = m_allocator.allocate(1);
 355          new (p.raw()) val_type(*it);
 356          Base::push_back(*p);
 357       }
 358    }
 359
 360    template <typename InputIterator>
 361    void assign(InputIterator it_start, InputIterator it_end)
 362    {
 363       this->clear();
 364       for (InputIterator it = it_start; it != it_end;){
 365          pointer p = m_allocator.allocate(1);
 366          new (p.raw()) val_type(*it++);
 367          Base::push_back(*p);
 368       }
 369    }
 370
 371    ~bounded_reference_cont()
 372    {  clear();  }
 373
 374    void clear()
 375    {
 376       while (!Base::empty()){
 377          pointer p = &Base::back();
 378          p->~val_type();
 379          m_allocator.deallocate(p, 1);
 380          Base::pop_back();
 381       }
 382    }
 383
 384    bounded_reference_cont& operator = (const bounded_reference_cont& other)
 385    {
 386       if (&other != this){
 387          clear();
 388          for (typename Base::const_iterator it = other.begin(); it != other.end(); ++it){
 389                pointer p = m_allocator.allocate(1);
 390                new (p.raw()) val_type(*it);
 391                Base::push_back(*p);
 392          }
 393       }
 394       return *this;
 395    }
 396
 397    private:
 398    allocator_type m_allocator;
 399 }; // class bounded_reference_cont
 400
 401 template < typename T >
 402 class bounded_pointer_holder
 403 {
 404    public:
 405    typedef T value_type;
 406    typedef bounded_pointer< value_type > pointer;
 407    typedef bounded_pointer< const value_type > const_pointer;
 408    typedef bounded_allocator< value_type > allocator_type;
 409
 410    bounded_pointer_holder() : _ptr(allocator_type().allocate(1))
 411    {  new (_ptr.raw()) value_type();   }
 412
 413    ~bounded_pointer_holder()
 414    {
 415       _ptr->~value_type();
 416       allocator_type().deallocate(_ptr, 1);
 417    }
 418
 419    const_pointer get_node () const
 420    { return _ptr; }
 421
 422    pointer get_node ()
 423    { return _ptr; }
 424
 425    private:
 426    const pointer _ptr;
 427 }; // class bounded_pointer_holder
 428
 429 #endif