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