external_libraries/boost-lockfree/boost/lockfree/detail/freelist.hpp

   1 //  lock-free freelist
   2 //
   3 //  Copyright (C) 2008, 2009, 2011 Tim Blechmann
   4 //
   5 //  Distributed under the Boost Software License, Version 1.0. (See
   6 //  accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  10 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  11
  12 #include <memory>
  13
  14 #include <boost/array.hpp>
  15 #include <boost/config.hpp>
  16 #include <boost/noncopyable.hpp>
  17 #include <boost/static_assert.hpp>
  18
  19 #include <boost/lockfree/detail/atomic.hpp>
  20 #include <boost/lockfree/detail/parameter.hpp>
  21 #include <boost/lockfree/detail/tagged_ptr.hpp>
  22
  23 namespace boost    {
  24 namespace lockfree {
  25 namespace detail   {
  26
  27 template <typename T,
  28           typename Alloc = std::allocator<T>
  29          >
  30 class freelist_stack:
  31     Alloc
  32 {
  33     struct freelist_node
  34     {
  35         tagged_ptr<freelist_node> next;
  36     };
  37
  38     typedef tagged_ptr<freelist_node> tagged_node_ptr;
  39
  40 public:
  41     typedef tagged_ptr<T> tagged_node_handle;
  42
  43     template <typename Allocator>
  44     freelist_stack (Allocator const & alloc, std::size_t n = 0):
  45         Alloc(alloc),
  46         pool_(tagged_node_ptr(NULL))
  47     {
  48         for (std::size_t i = 0; i != n; ++i) {
  49             T * node = Alloc::allocate(1);
  50 #ifdef BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
  51             destruct<false>(node);
  52 #else
  53             deallocate<false>(node);
  54 #endif
  55         }
  56     }
  57
  58     template <bool ThreadSafe>
  59     void reserve (std::size_t count)
  60     {
  61         for (std::size_t i = 0; i != count; ++i) {
  62             T * node = Alloc::allocate(1);
  63             deallocate<ThreadSafe>(node);
  64         }
  65     }
  66
  67     template <bool ThreadSafe, bool Bounded>
  68     T * construct (void)
  69     {
  70         T * node = allocate<ThreadSafe, Bounded>();
  71         if (node)
  72             new(node) T();
  73         return node;
  74     }
  75
  76     template <bool ThreadSafe, bool Bounded, typename ArgumentType>
  77     T * construct (ArgumentType const & arg)
  78     {
  79         T * node = allocate<ThreadSafe, Bounded>();
  80         if (node)
  81             new(node) T(arg);
  82         return node;
  83     }
  84
  85     template <bool ThreadSafe, bool Bounded, typename ArgumentType1, typename ArgumentType2>
  86     T * construct (ArgumentType1 const & arg1, ArgumentType2 const & arg2)
  87     {
  88         T * node = allocate<ThreadSafe, Bounded>();
  89         if (node)
  90             new(node) T(arg1, arg2);
  91         return node;
  92     }
  93
  94     template <bool ThreadSafe>
  95     void destruct (tagged_node_handle tagged_ptr)
  96     {
  97         T * n = tagged_ptr.get_ptr();
  98         n->~T();
  99         deallocate<ThreadSafe>(n);
 100     }
 101
 102     template <bool ThreadSafe>
 103     void destruct (T * n)
 104     {
 105         n->~T();
 106         deallocate<ThreadSafe>(n);
 107     }
 108
 109     ~freelist_stack(void)
 110     {
 111         tagged_node_ptr current (pool_);
 112
 113         while (current) {
 114             freelist_node * current_ptr = current.get_ptr();
 115             if (current_ptr)
 116                 current = current_ptr->next;
 117             Alloc::deallocate((T*)current_ptr, 1);
 118         }
 119     }
 120
 121     bool is_lock_free(void) const
 122     {
 123         return pool_.is_lock_free();
 124     }
 125
 126     T * get_handle(T * pointer) const
 127     {
 128         return pointer;
 129     }
 130
 131     T * get_handle(tagged_node_handle const & handle) const
 132     {
 133         return get_pointer(handle);
 134     }
 135
 136     T * get_pointer(tagged_node_handle const & tptr) const
 137     {
 138         return tptr.get_ptr();
 139     }
 140
 141     T * get_pointer(T * pointer) const
 142     {
 143         return pointer;
 144     }
 145
 146     T * null_handle(void) const
 147     {
 148         return NULL;
 149     }
 150
 151 private:
 152     template <bool ThreadSafe, bool Bounded>
 153     T * allocate (void)
 154     {
 155         if (ThreadSafe)
 156             return allocate_impl<Bounded>();
 157         else
 158             return allocate_impl_unsafe<Bounded>();
 159     }
 160
 161     template <bool Bounded>
 162     T * allocate_impl (void)
 163     {
 164         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
 165
 166         for(;;) {
 167             if (!old_pool.get_ptr()) {
 168                 if (!Bounded)
 169                     return Alloc::allocate(1);
 170                 else
 171                     return 0;
 172             }
 173
 174             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
 175             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 176
 177             if (pool_.compare_exchange_weak(old_pool, new_pool)) {
 178                 void * ptr = old_pool.get_ptr();
 179                 return reinterpret_cast<T*>(ptr);
 180             }
 181         }
 182     }
 183
 184     template <bool Bounded>
 185     T * allocate_impl_unsafe (void)
 186     {
 187         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
 188
 189         if (!old_pool.get_ptr()) {
 190             if (!Bounded)
 191                 return Alloc::allocate(1);
 192             else
 193                 return 0;
 194         }
 195
 196         freelist_node * new_pool_ptr = old_pool->next.get_ptr();
 197         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 198
 199         pool_.store(new_pool, memory_order_relaxed);
 200         void * ptr = old_pool.get_ptr();
 201         return reinterpret_cast<T*>(ptr);
 202     }
 203
 204     template <bool ThreadSafe>
 205     void deallocate (T * n)
 206     {
 207         if (ThreadSafe)
 208             deallocate_impl(n);
 209         else
 210             deallocate_impl_unsafe(n);
 211     }
 212
 213     void deallocate_impl (T * n)
 214     {
 215         void * node = n;
 216         tagged_node_ptr old_pool = pool_.load(memory_order_consume);
 217         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 218
 219         for(;;) {
 220             tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
 221             new_pool->next.set_ptr(old_pool.get_ptr());
 222
 223             if (pool_.compare_exchange_weak(old_pool, new_pool))
 224                 return;
 225         }
 226     }
 227
 228     void deallocate_impl_unsafe (T * n)
 229     {
 230         void * node = n;
 231         tagged_node_ptr old_pool = pool_.load(memory_order_relaxed);
 232         freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 233
 234         tagged_node_ptr new_pool (new_pool_ptr, old_pool.get_tag());
 235         new_pool->next.set_ptr(old_pool.get_ptr());
 236
 237         pool_.store(new_pool, memory_order_relaxed);
 238     }
 239
 240     atomic<tagged_node_ptr> pool_;
 241 };
 242
 243 class tagged_index
 244 {
 245 public:
 246     typedef boost::uint16_t tag_t;
 247     typedef boost::uint16_t index_t;
 248
 249     /** uninitialized constructor */
 250     tagged_index(void) BOOST_NOEXCEPT //: index(0), tag(0)
 251     {}
 252
 253     /** copy constructor */
 254 #ifdef BOOST_NO_DEFAULTED_FUNCTIONS
 255     tagged_index(tagged_index const & rhs):
 256         index(rhs.index), tag(rhs.tag)
 257     {}
 258 #else
 259     tagged_index(tagged_index const & rhs) = default;
 260 #endif
 261
 262     explicit tagged_index(index_t i, tag_t t = 0):
 263         index(i), tag(t)
 264     {}
 265
 266     /** index access */
 267     /* @{ */
 268     index_t get_index() const
 269     {
 270         return index;
 271     }
 272
 273     void set_index(index_t i)
 274     {
 275         index = i;
 276     }
 277     /* @} */
 278
 279     /** tag access */
 280     /* @{ */
 281     tag_t get_tag() const
 282     {
 283         return tag;
 284     }
 285
 286     void set_tag(tag_t t)
 287     {
 288         tag = t;
 289     }
 290     /* @} */
 291
 292     bool operator==(tagged_index const & rhs) const
 293     {
 294         return (index == rhs.index) && (tag == rhs.tag);
 295     }
 296
 297 protected:
 298     index_t index;
 299     tag_t tag;
 300 };
 301
 302 template <typename T,
 303           std::size_t size>
 304 struct compiletime_sized_freelist_storage
 305 {
 306     // array-based freelists only support a 16bit address space.
 307     BOOST_STATIC_ASSERT(size < 65536);
 308
 309     boost::array<char, size * sizeof(T)> data;
 310
 311     // unused ... only for API purposes
 312     template <typename Allocator>
 313     compiletime_sized_freelist_storage(Allocator const & alloc, std::size_t count)
 314     {}
 315
 316     T * nodes(void) const
 317     {
 318         return reinterpret_cast<T*>(const_cast<char*>(data.data()));
 319     }
 320
 321     std::size_t node_count(void) const
 322     {
 323         return size;
 324     }
 325 };
 326
 327 template <typename T,
 328           typename Alloc = std::allocator<T> >
 329 struct runtime_sized_freelist_storage:
 330     Alloc
 331 {
 332     T * nodes_;
 333     std::size_t node_count_;
 334
 335     template <typename Allocator>
 336     runtime_sized_freelist_storage(Allocator const & alloc, std::size_t count):
 337         Alloc(alloc), node_count_(count)
 338     {
 339         if (count > 65535)
 340             boost::throw_exception(std::runtime_error("boost.lockfree: freelist size is limited to a maximum of 65535 objects"));
 341         nodes_ = Alloc::allocate(count);
 342     }
 343
 344     ~runtime_sized_freelist_storage(void)
 345     {
 346         Alloc::deallocate(nodes_, node_count_);
 347     }
 348
 349     T * nodes(void) const
 350     {
 351         return nodes_;
 352     }
 353
 354     std::size_t node_count(void) const
 355     {
 356         return node_count_;
 357     }
 358 };
 359
 360
 361 template <typename T,
 362           typename NodeStorage = runtime_sized_freelist_storage<T>
 363          >
 364 class fixed_size_freelist:
 365     NodeStorage
 366 {
 367     struct freelist_node
 368     {
 369         tagged_index next;
 370     };
 371
 372     typedef tagged_index::index_t index_t;
 373
 374     void initialize(void)
 375     {
 376         T * nodes = NodeStorage::nodes();
 377         for (std::size_t i = 0; i != NodeStorage::node_count(); ++i) {
 378             tagged_index * next_index = reinterpret_cast<tagged_index*>(nodes + i);
 379             next_index->set_index(null_handle());
 380
 381 #ifdef BOOST_LOCKFREE_FREELIST_INIT_RUNS_DTOR
 382             destruct<false>(nodes + i);
 383 #else
 384             deallocate<false>(i);
 385 #endif
 386         }
 387     }
 388
 389 public:
 390     typedef tagged_index tagged_node_handle;
 391
 392     template <typename Allocator>
 393     fixed_size_freelist (Allocator const & alloc, std::size_t count):
 394         NodeStorage(alloc, count), pool_(tagged_index(count, 0))
 395     {
 396         initialize();
 397     }
 398
 399     fixed_size_freelist (void):
 400         pool_(tagged_index(NodeStorage::node_count(), 0))
 401     {
 402         initialize();
 403     }
 404
 405     template <bool ThreadSafe, bool Bounded>
 406     T * construct (void)
 407     {
 408         index_t node_index = allocate<ThreadSafe>();
 409         if (node_index == null_handle())
 410             return NULL;
 411
 412         T * node = NodeStorage::nodes() + node_index;
 413         new(node) T();
 414         return node;
 415     }
 416
 417     template <bool ThreadSafe, bool Bounded, typename ArgumentType>
 418     T * construct (ArgumentType const & arg)
 419     {
 420         index_t node_index = allocate<ThreadSafe>();
 421         if (node_index == null_handle())
 422             return NULL;
 423
 424         T * node = NodeStorage::nodes() + node_index;
 425         new(node) T(arg);
 426         return node;
 427     }
 428
 429     template <bool ThreadSafe, bool Bounded, typename ArgumentType1, typename ArgumentType2>
 430     T * construct (ArgumentType1 const & arg1, ArgumentType2 const & arg2)
 431     {
 432         index_t node_index = allocate<ThreadSafe>();
 433         if (node_index == null_handle())
 434             return NULL;
 435
 436         T * node = NodeStorage::nodes() + node_index;
 437         new(node) T(arg1, arg2);
 438         return node;
 439     }
 440
 441     template <bool ThreadSafe>
 442     void destruct (tagged_node_handle tagged_index)
 443     {
 444         index_t index = tagged_index.get_index();
 445         T * n = NodeStorage::nodes() + index;
 446         n->~T();
 447         deallocate<ThreadSafe>(index);
 448     }
 449
 450     template <bool ThreadSafe>
 451     void destruct (T * n)
 452     {
 453         n->~T();
 454         deallocate<ThreadSafe>(n - NodeStorage::nodes());
 455     }
 456
 457     bool is_lock_free(void) const
 458     {
 459         return pool_.is_lock_free();
 460     }
 461
 462     index_t null_handle(void) const
 463     {
 464         return NodeStorage::node_count();
 465     }
 466
 467     index_t get_handle(T * pointer) const
 468     {
 469         if (pointer == NULL)
 470             return null_handle();
 471         else
 472             return pointer - NodeStorage::nodes();
 473     }
 474
 475     index_t get_handle(tagged_node_handle const & handle) const
 476     {
 477         return handle.get_index();
 478     }
 479
 480     T * get_pointer(tagged_node_handle const & tptr) const
 481     {
 482         return get_pointer(tptr.get_index());
 483     }
 484
 485     T * get_pointer(index_t index) const
 486     {
 487         if (index == null_handle())
 488             return 0;
 489         else
 490             return NodeStorage::nodes() + index;
 491     }
 492
 493     T * get_pointer(T * ptr) const
 494     {
 495         return ptr;
 496     }
 497
 498 private:
 499     template <bool ThreadSafe>
 500     index_t allocate (void)
 501     {
 502         if (ThreadSafe)
 503             return allocate_impl();
 504         else
 505             return allocate_impl_unsafe();
 506     }
 507
 508     index_t allocate_impl (void)
 509     {
 510         tagged_index old_pool = pool_.load(memory_order_consume);
 511
 512         for(;;) {
 513             index_t index = old_pool.get_index();
 514             if (index == null_handle())
 515                 return index;
 516
 517             T * old_node = NodeStorage::nodes() + index;
 518             tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
 519
 520             tagged_index new_pool(next_index->get_index(), old_pool.get_tag() + 1);
 521
 522             if (pool_.compare_exchange_weak(old_pool, new_pool))
 523                 return old_pool.get_index();
 524         }
 525     }
 526
 527     index_t allocate_impl_unsafe (void)
 528     {
 529         tagged_index old_pool = pool_.load(memory_order_consume);
 530
 531         index_t index = old_pool.get_index();
 532         if (index == null_handle())
 533             return index;
 534
 535         T * old_node = NodeStorage::nodes() + index;
 536         tagged_index * next_index = reinterpret_cast<tagged_index*>(old_node);
 537
 538         tagged_index new_pool(next_index->get_index(), old_pool.get_tag() + 1);
 539
 540         pool_.store(new_pool, memory_order_relaxed);
 541         return old_pool.get_index();
 542     }
 543
 544     template <bool ThreadSafe>
 545     void deallocate (index_t index)
 546     {
 547         if (ThreadSafe)
 548             deallocate_impl(index);
 549         else
 550             deallocate_impl_unsafe(index);
 551     }
 552
 553     void deallocate_impl (index_t index)
 554     {
 555         freelist_node * new_pool_node = reinterpret_cast<freelist_node*>(NodeStorage::nodes() + index);
 556         tagged_index old_pool = pool_.load(memory_order_consume);
 557
 558         for(;;) {
 559             tagged_index new_pool (index, old_pool.get_tag());
 560             new_pool_node->next.set_index(old_pool.get_index());
 561
 562             if (pool_.compare_exchange_weak(old_pool, new_pool))
 563                 return;
 564         }
 565     }
 566
 567     void deallocate_impl_unsafe (index_t index)
 568     {
 569         freelist_node * new_pool_node = reinterpret_cast<freelist_node*>(NodeStorage::nodes() + index);
 570         tagged_index old_pool = pool_.load(memory_order_consume);
 571
 572         tagged_index new_pool (index, old_pool.get_tag());
 573         new_pool_node->next.set_index(old_pool.get_index());
 574
 575         pool_.store(new_pool);
 576     }
 577
 578     atomic<tagged_index> pool_;
 579 };
 580
 581 template <typename T,
 582           typename Alloc,
 583           bool IsCompileTimeSized,
 584           bool IsFixedSize,
 585           std::size_t Capacity
 586           >
 587 struct select_freelist
 588 {
 589     typedef typename mpl::if_c<IsCompileTimeSized,
 590                                compiletime_sized_freelist_storage<T, Capacity>,
 591                                runtime_sized_freelist_storage<T, Alloc>
 592                               >::type fixed_sized_storage_type;
 593
 594     typedef typename mpl::if_c<IsCompileTimeSized || IsFixedSize,
 595                                fixed_size_freelist<T, fixed_sized_storage_type>,
 596                                freelist_stack<T, Alloc>
 597                               >::type type;
 598 };
 599
 600 template <typename T, bool IsNodeBased>
 601 struct select_tagged_handle
 602 {
 603     typedef typename mpl::if_c<IsNodeBased,
 604                                tagged_ptr<T>,
 605                                tagged_index
 606                               >::type tagged_handle_type;
 607
 608     typedef typename mpl::if_c<IsNodeBased,
 609                                T*,
 610                                typename tagged_index::index_t
 611                               >::type handle_type;
 612 };
 613
 614
 615 } /* namespace detail */
 616 } /* namespace lockfree */
 617 } /* namespace boost */
 618
 619 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */