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 #pragma once
20 
21 #include <boost/lockfree/detail/tagged_ptr.hpp>
22 #include <atomic>
23 
24 namespace nova {
25 
26 /**
27  * simple freelist implementation without any memory allocation features
28  * */
29 class freelist {
30     struct freelist_node {
31         boost::lockfree::detail::tagged_ptr<freelist_node> next;
32     };
33 
34     typedef boost::lockfree::detail::tagged_ptr<freelist_node> tagged_ptr;
35 
36 public:
freelist(void)37     freelist(void): pool_(tagged_ptr(nullptr)) {}
38 
39     freelist(freelist const& rhs) = delete;
40     freelist& operator=(freelist const& rhs) = delete;
41 
pop(void)42     void* pop(void) {
43         for (;;) {
44             tagged_ptr old_pool = pool_.load(std::memory_order_consume);
45 
46             if (!old_pool.get_ptr())
47                 return nullptr;
48 
49             freelist_node* new_pool_ptr = old_pool->next.get_ptr();
50             tagged_ptr new_pool(new_pool_ptr, old_pool.get_tag() + 1);
51 
52             if (pool_.compare_exchange_weak(old_pool, new_pool)) {
53                 void* ptr = old_pool.get_ptr();
54                 return reinterpret_cast<void*>(ptr);
55             }
56         }
57     }
58 
push(void * n)59     void push(void* n) {
60         void* node = n;
61         for (;;) {
62             tagged_ptr old_pool = pool_.load(std::memory_order_consume);
63 
64             freelist_node* new_pool_ptr = reinterpret_cast<freelist_node*>(node);
65             tagged_ptr new_pool(new_pool_ptr, old_pool.get_tag() + 1);
66 
67             new_pool->next.set_ptr(old_pool.get_ptr());
68 
69             if (pool_.compare_exchange_weak(old_pool, new_pool))
70                 return;
71         }
72     }
73 
74 private:
75     std::atomic<tagged_ptr> pool_;
76 };
77 
78 
79 } /* namespace nova */
80