server/supernova/utilities/freelist.hpp

   1 //  nova freelist class
   2 //  Copyright (C) 2009 Tim Blechmann
   3 //
   4 //  This program is free software; you can redistribute it and/or modify
   5 //  it under the terms of the GNU General Public License as published by
   6 //  the Free Software Foundation; either version 2 of the License, or
   7 //  (at your option) any later version.
   8 //
   9 //  This program is distributed in the hope that it will be useful,
  10 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 //  GNU General Public License for more details.
  13 //
  14 //  You should have received a copy of the GNU General Public License
  15 //  along with this program; see the file COPYING.  If not, write to
  16 //  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17 //  Boston, MA 02111-1307, USA.
  18
  19 #ifndef UTILITIES_FREELIST_HPP
  20 #define UTILITIES_FREELIST_HPP
  21
  22 #include <boost/lockfree/detail/tagged_ptr.hpp>
  23 #include <boost/atomic.hpp>
  24 #include <boost/noncopyable.hpp>
  25
  26
  27 namespace nova
  28 {
  29
  30 /**
  31  * simple freelist implementation without any memory allocation features
  32  * */
  33 class freelist
  34 {
  35     struct freelist_node
  36     {
  37         boost::lockfree::detail::tagged_ptr<freelist_node> next;
  38     };
  39
  40     typedef boost::lockfree::detail::tagged_ptr<freelist_node> tagged_ptr;
  41
  42 public:
  43     freelist(void):
  44         pool_(tagged_ptr(NULL))
  45     {}
  46
  47     void * pop (void)
  48     {
  49         for(;;)
  50         {
  51             tagged_ptr old_pool = pool_.load(boost::memory_order_consume);
  52
  53             if (!old_pool.get_ptr())
  54                 return 0;
  55
  56             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
  57             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
  58
  59             if (pool_.compare_exchange_weak(old_pool, new_pool)) {
  60                 void * ptr = old_pool.get_ptr();
  61                 return reinterpret_cast<void*>(ptr);
  62             }
  63         }
  64     }
  65
  66     void push (void * n)
  67     {
  68         void * node = n;
  69         for(;;)
  70         {
  71             tagged_ptr old_pool = pool_.load(boost::memory_order_consume);
  72
  73             freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
  74             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
  75
  76             new_pool->next.set_ptr(old_pool.get_ptr());
  77
  78             if (pool_.compare_exchange_weak(old_pool, new_pool))
  79                 return;
  80         }
  81     }
  82
  83 private:
  84     boost::atomic<tagged_ptr> pool_;
  85 };
  86
  87
  88 } /* namespace nova */
  89
  90 #endif /* UTILITIES_FREELIST_HPP */