From e1355c98e2f9448815c533564fff28fce7b19ea1 Mon Sep 17 00:00:00 2001 From: Tim Blechmann Date: Mon, 28 Apr 2008 23:06:17 +0200 Subject: [PATCH] Initial commit --- boost/lockfree/atomic_int.hpp | 223 ++++++++++++++++++++++++++++++++++++++ boost/lockfree/branch_hints.hpp | 40 +++++++ boost/lockfree/cas.hpp | 212 ++++++++++++++++++++++++++++++++++++ boost/lockfree/fifo.hpp | 234 ++++++++++++++++++++++++++++++++++++++++ boost/lockfree/freelist.hpp | 200 ++++++++++++++++++++++++++++++++++ boost/lockfree/prefix.hpp | 45 ++++++++ boost/lockfree/tagged_ptr.hpp | 184 +++++++++++++++++++++++++++++++ 7 files changed, 1138 insertions(+) create mode 100644 boost/lockfree/atomic_int.hpp create mode 100644 boost/lockfree/branch_hints.hpp create mode 100644 boost/lockfree/cas.hpp create mode 100644 boost/lockfree/fifo.hpp create mode 100644 boost/lockfree/freelist.hpp create mode 100644 boost/lockfree/prefix.hpp create mode 100644 boost/lockfree/tagged_ptr.hpp diff --git a/boost/lockfree/atomic_int.hpp b/boost/lockfree/atomic_int.hpp new file mode 100644 index 0000000..a8b8cdd --- /dev/null +++ b/boost/lockfree/atomic_int.hpp @@ -0,0 +1,223 @@ +// Copyright (C) 2007, 2008 Tim Blechmann & Thomas Grill +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_ATOMIC_INT_HPP +#define BOOST_LOCKFREE_ATOMIC_INT_HPP + +#include + +namespace boost +{ +namespace lockfree +{ + +#if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) && (__GNUC_MINOR__ >= 1)) ) + +template +class atomic_int +{ +public: + explicit atomic_int(T v = 0): + value(v) + {} + + operator T(void) const + { + return __sync_fetch_and_add(&value, 0); + } + + void operator =(T v) + { + value = v; + __sync_synchronize(); + } + + T operator +=(T v) + { + return __sync_add_and_fetch(&value, v); + } + + T operator -=(T v) + { + return __sync_sub_and_fetch(&value, v); + } + + /* prefix operator */ + T operator ++(void) + { + return __sync_add_and_fetch(&value, 1); + } + + /* prefix operator */ + T operator --(void) + { + return __sync_sub_and_fetch(&value, 1); + } + + /* postfix operator */ + T operator ++(int) + { + return __sync_fetch_and_add(&value, 1); + } + + /* postfix operator */ + T operator --(int) + { + return __sync_fetch_and_sub(&value, 1); + } + +private: + mutable T value; +}; + +#elif defined(__GLIBCPP__) || defined(__GLIBCXX__) + +template +class atomic_int +{ +public: + explicit atomic_int(T v = 0): + value(v) + {} + + operator T(void) const + { + return __gnu_cxx::__exchange_and_add(&value, 0); + } + + void operator =(T v) + { + value = v; + } + + T operator +=(T v) + { + return __gnu_cxx::__exchange_and_add(&value, v) + v; + } + + T operator -=(T v) + { + return __gnu_cxx::__exchange_and_add(&value, -v) - v; + } + + /* prefix operator */ + T operator ++(void) + { + return operator+=(1); + } + + /* prefix operator */ + T operator --(void) + { + return operator-=(1); + } + + /* postfix operator */ + T operator ++(int) + { + return __gnu_cxx::__exchange_and_add(&value, 1); + } + + /* postfix operator */ + T operator --(int) + { + return __gnu_cxx::__exchange_and_add(&value, -1); + } + +private: + mutable _Atomic_word value; +}; + +#else /* emulate via CAS */ + +template +class atomic_int +{ +public: + explicit atomic_int(T v = 0) + { + *this = v; + } + + operator T(void) const + { + memory_barrier(); + return value; + } + + void operator =(T v) + { + value = v; + memory_barrier(); + } + + /* prefix operator */ + T operator ++() + { + return *this += 1; + } + + /* prefix operator */ + T operator --() + { + return *this -= 1; + } + + T operator +=(T v) + { + for(;;) + { + T newv = value+v; + if(likely(CAS(&value,value,newv))) + return newv; + } + } + + T operator -=(T v) + { + for(;;) + { + T newv = value-v; + if(likely(CAS(&value,value,newv))) + return newv; + } + } + + /* postfix operator */ + T operator ++(int) + { + for(;;) + { + T oldv = value; + if(likely(CAS(&value,oldv,oldv+1))) + return oldv; + } + } + + /* postfix operator */ + T operator --(int) + { + for(;;) + { + T oldv = value; + if(likely(CAS(&value,oldv,oldv-1))) + return oldv; + } + } + +private: + T value; +}; + + +#endif + +} /* namespace lockfree */ +} /* namespace boost */ + +#endif /* BOOST_LOCKFREE_ATOMIC_INT_HPP */ diff --git a/boost/lockfree/branch_hints.hpp b/boost/lockfree/branch_hints.hpp new file mode 100644 index 0000000..7b5ed24 --- /dev/null +++ b/boost/lockfree/branch_hints.hpp @@ -0,0 +1,40 @@ +// branch hints +// Copyright (C) 2007, 2008 Tim Blechmann +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_BRANCH_HINTS_HPP_INCLUDED +#define BOOST_LOCKFREE_BRANCH_HINTS_HPP_INCLUDED + +namespace boost +{ +namespace lockfree +{ + /** \brief hint for the branch prediction */ + inline bool likely(bool expr) + { +#ifdef __GNUC__ + return __builtin_expect(expr, true); +#else + return expr; +#endif + } + + /** \brief hint for the branch prediction */ + inline bool unlikely(bool expr) + { +#ifdef __GNUC__ + return __builtin_expect(expr, false); +#else + return expr; +#endif + } + +} /* namespace lockfree */ +} /* namespace boost */ + +#endif /* BOOST_LOCKFREE_BRANCH_HINTS_HPP_INCLUDED */ diff --git a/boost/lockfree/cas.hpp b/boost/lockfree/cas.hpp new file mode 100644 index 0000000..0dc85df --- /dev/null +++ b/boost/lockfree/cas.hpp @@ -0,0 +1,212 @@ +// Copyright (C) 2007, 2008 Tim Blechmann & Thomas Grill +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_CAS_HPP_INCLUDED +#define BOOST_LOCKFREE_CAS_HPP_INCLUDED + +#include "prefix.hpp" +#include + +#ifdef __x86_64__ +/* 16 byte aligned for cmpxchg16b! */ +#define DCAS_ALIGNMENT_ATTRIBUTE __attribute__((aligned(16))) +#else +#define DCAS_ALIGNMENT_ATTRIBUTE +#endif + +namespace boost +{ +namespace lockfree +{ + +inline void memory_barrier() +{ +#if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) && (__GNUC_MINOR__ >= 1)) ) + __sync_synchronize(); +#elif defined(_MSC_VER) && (_MSC_VER >= 1300) + _ReadWriteBarrier(); +#elif defined(__APPLE__) + OSMemoryBarrier(); +#elif defined(AO_HAVE_nop_full) + AO_nop_full(); +#else +# warning "no memory barrier implemented for this platform" +#endif +} + +template +inline bool CAS(volatile C * addr,D old,D nw) +{ +#if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) && (__GNUC_MINOR__ >= 1)) ) + return __sync_bool_compare_and_swap(addr, old, nw); +#elif defined(_MSC_VER) + return _InterlockedCompareExchange(addr,old,nw) == old; +#elif defined(_WIN32) + return InterlockedCompareExchange(addr,old,nw) == old; +#elif defined(__APPLE__) + return OSAtomicCompareAndSwap32(old,nw,addr); +#elif defined(AO_HAVE_compare_and_swap_full) + return AO_compare_and_swap_full(reinterpret_cast(addr), + reinterpret_cast(old), + reinterpret_cast(nw)); +#else +#warning ("blocking cas emulation") + + boost::detail::lightweight_mutex guard; + boost::detail::lightweight_mutex::scoped_lock(guard); + + if (*addr == old) + { + *addr = nw; + return true; + } + else + return false; +#endif +} + + +template +inline bool CAS2(volatile C * addr,D old1,E old2,D new1,E new2) +{ +#if defined(__GNUC__) && ((__GNUC__ > 4) || ( (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 2) ) ) && defined(__i386__) && \ + (defined(__i686__) || defined(__pentiumpro__) || defined(__nocona__ ) || \ + defined (__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8)) + + struct packed_c + { + D d; + E e; + }; + + union cu + { + packed_c c; + long long l; + }; + + cu old; + old.c.d = old1; + old.c.e = old2; + + cu nw; + nw.c.d = new1; + nw.c.e = new2; + + return __sync_bool_compare_and_swap_8(reinterpret_cast(addr), + old.l, + nw.l); +#elif defined(_MSC_VER) + bool ok; + __asm { + mov eax,[old1] + mov edx,[old2] + mov ebx,[new1] + mov ecx,[new2] + mov edi,[addr] + lock cmpxchg8b [edi] + setz [ok] + } + return ok; +#elif defined(__GNUC__) && (defined(__i686__) || defined(__pentiumpro__) || defined(__nocona__ )) + char result; +#ifndef __PIC__ + __asm__ __volatile__("lock; cmpxchg8b %0; setz %1" + : "=m"(*addr), "=q"(result) + : "m"(*addr), "d" (old1), "a" (old2), + "c" (new1), "b" (new2) : "memory"); +#else + __asm__ __volatile__("push %%ebx; movl %6,%%ebx; lock; cmpxchg8b %0; setz %1; pop %%ebx" + : "=m"(*addr), "=q"(result) + : "m"(*addr), "d" (old1), "a" (old2), + "c" (new1), "m" (new2) : "memory"); +#endif + return result != 0; +#elif defined(AO_HAVE_double_compare_and_swap_full) + if (sizeof(D) != sizeof(AO_t) || sizeof(E) != sizeof(AO_t)) { + assert(false); + return false; + } + + return AO_compare_double_and_swap_double_full( + reinterpret_cast(addr), + static_cast(old2), + reinterpret_cast(old1), + static_cast(new2), + reinterpret_cast(new1) + ); + +#elif defined(__GNUC__) && defined(__x86_64__) && \ + ( __GCC_HAVE_SYNC_COMPARE_AND_SWAP_16 ) || \ + ( (__GNUC__ > 4) || ( (__GNUC__ >= 4) && (__GNUC_MINOR__ >= 2) ) && defined(__nocona__ )) + + struct packed_c + { + long d; + long e; + }; + + typedef int TItype __attribute__ ((mode (TI))); + + BOOST_STATIC_ASSERT(sizeof(packed_c) == sizeof(TItype)); + + union cu + { + packed_c c; + TItype l; + }; + + cu old; + old.c.d = (long)old1; + old.c.e = (long)old2; + + cu nw; + nw.c.d = (long)new1; + nw.c.e = (long)new2; + + return __sync_bool_compare_and_swap_16(reinterpret_cast(addr), + old.l, + nw.l); + +#elif defined(__GNUC__) && defined(__x86_64__) + /* handcoded asm, will crash on early amd processors */ + char result; + __asm__ __volatile__("lock; cmpxchg16b %0; setz %1" + : "=m"(*addr), "=q"(result) + : "m"(*addr), "d" (old2), "a" (old1), + "c" (new2), "b" (new1) : "memory"); + return result != 0; +#else +#warning ("blocking CAS2 emulation") + struct packed_c + { + D d; + E e; + }; + + volatile packed_c * packed_addr = reinterpret_cast(addr); + + boost::detail::lightweight_mutex guard; + boost::detail::lightweight_mutex::scoped_lock(guard); + + if (packed_addr->d == old1 && + packed_addr->e == old2) + { + packed_addr->d = new1; + packed_addr->e = new2; + return true; + } + else + return false; +#endif +} + +} /* namespace lockfree */ +} /* namespace boost */ + +#endif /* BOOST_LOCKFREE_CAS_HPP_INCLUDED */ diff --git a/boost/lockfree/fifo.hpp b/boost/lockfree/fifo.hpp new file mode 100644 index 0000000..2267fe5 --- /dev/null +++ b/boost/lockfree/fifo.hpp @@ -0,0 +1,234 @@ +// lock-free fifo queue from +// Michael, M. M. and Scott, M. L., +// "simple, fast and practical non-blocking and blocking concurrent queue algorithms" +// +// implementation for c++ +// +// Copyright (C) 2008 Tim Blechmann +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_FIFO_HPP_INCLUDED +#define BOOST_LOCKFREE_FIFO_HPP_INCLUDED + +#include +#include +#include + +#include +#include + + +#include /* std::auto_ptr */ +#include +#include + +namespace boost +{ +namespace lockfree +{ +namespace detail +{ + +template +class fifo +{ + BOOST_CLASS_REQUIRE(T, boost, CopyConstructibleConcept); + BOOST_CLASS_REQUIRE(T, boost, DefaultConstructibleConcept); + + struct node + { + node(T const & v): + data(v), next(NULL) + {} + + node (void): + next(NULL) + {} + + tagged_ptr next; + T data; + }; + + typedef tagged_ptr atomic_node_ptr; + + +public: + fifo(void) + { + node * n = alloc_node(); + head_.set_ptr(n); + tail_.set_ptr(n); + } + + ~fifo(void) + { + assert(empty()); + dealloc_node(head_.get_ptr()); + } + + bool empty(void) const + { + return head_.get_ptr() == tail_.get_ptr(); + } + + void enqueue(T const & t) + { + node * n = alloc_node(t); + + for (;;) + { + atomic_node_ptr tail (tail_); + memory_barrier(); + atomic_node_ptr next (tail->next); + memory_barrier(); + + if (likely(tail == tail_)) + { + if (next.get_ptr() == 0) + { + if ( tail->next.CAS(next, n) ) + { + tail_.CAS(tail, n); + return; + } + } + else + tail_.CAS(tail, next.get_ptr()); + } + } + } + + bool dequeue (T * ret) + { + for (;;) + { + atomic_node_ptr head (head_); + memory_barrier(); + + atomic_node_ptr tail(tail_); + node * next = head->next.get_ptr(); + memory_barrier(); + + if (likely(head == head_)) + { + if (head.get_ptr() == tail.get_ptr()) + { + if (next == 0) + return false; + + tail_.CAS(tail, next); + } + else + { + *ret = next->data; + if (head_.CAS(head, next)) + { + dealloc_node(head.get_ptr()); + + return true; + } + } + } + } + } + +private: + boost::lockfree::caching_freelist pool; + + node * alloc_node(void) + { + node * chunk = pool.allocate(); + new(chunk) node(); + return chunk; + } + + node * alloc_node(T const & t) + { + node * chunk = pool.allocate(); + new(chunk) node(t); + return chunk; + } + + void dealloc_node(node * n) + { + n->~node(); + pool.deallocate(n); + } + + atomic_node_ptr head_; + atomic_node_ptr tail_ __attribute__((aligned(64))); /* force head_ and tail_ to different cache lines! */ +}; + +} /* namespace detail */ + +/** lockfree fifo + * + * - wrapper for detail::fifo + * */ +template +class fifo: + public detail::fifo +{ +}; + + +/** lockfree fifo, template specialization for pointer-types + * + * - wrapper for detail::fifo + * - overload dequeue to support smart pointers + * */ +template +class fifo: + public detail::fifo +{ + typedef detail::fifo fifo_t; + + template + bool dequeue_smart_ptr(smart_ptr & ptr) + { + T * result = 0; + bool success = fifo_t::dequeue(&result); + + if (success) + ptr.reset(result); + return success; + } + +public: + void enqueue(T * t) + { + fifo_t::enqueue(t); + } + + bool dequeue (T ** ret) + { + return fifo_t::dequeue(ret); + } + + bool dequeue (std::auto_ptr & ret) + { + return dequeue_smart_ptr(ret); + } + + bool dequeue (boost::scoped_ptr & ret) + { + BOOST_STATIC_ASSERT(sizeof(boost::scoped_ptr) == sizeof(T*)); + return dequeue(reinterpret_cast(&ret)); + } + + bool dequeue (boost::shared_ptr & ret) + { + return dequeue_smart_ptr(ret); + } +}; + +} /* namespace lockfree */ +} /* namespace boost */ + + +#endif /* BOOST_LOCKFREE_FIFO_HPP_INCLUDED */ diff --git a/boost/lockfree/freelist.hpp b/boost/lockfree/freelist.hpp new file mode 100644 index 0000000..f527d71 --- /dev/null +++ b/boost/lockfree/freelist.hpp @@ -0,0 +1,200 @@ +// lock-free freelist +// +// Copyright (C) 2008 Tim Blechmann +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED +#define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED + +#include +#include + +namespace boost +{ +namespace lockfree +{ + +/** dummy freelist */ +template +struct dummy_freelist +{ + T * allocate (void) + { + return static_cast(operator new(sizeof(T))); + } + + void deallocate (T * n) + { + operator delete(n); + } +}; + + +/** simple freelist implementation */ +template +class freelist: + public dummy_freelist +{ + struct freelist_node + { + tagged_ptr next; + }; + + typedef lockfree::tagged_ptr tagged_ptr; + +public: + freelist(void): + pool_(NULL) + {} + + ~freelist(void) + { + free_memory_pool(); + } + + T * allocate (void) + { + for(;;) + { + tagged_ptr old_pool(pool_); + + if (not old_pool) + return dummy_freelist::allocate(); + + tagged_ptr new_pool (old_pool->next); + + new_pool.set_tag(old_pool.get_tag() + 1); + + if (pool_.CAS(old_pool, new_pool)) + { + --free_list_size; + return reinterpret_cast(old_pool.get_ptr()); + } + } + } + + void deallocate (T * n) + { + if (free_list_size > max_size) + { + dummy_freelist::deallocate(n); + return; + } + + for(;;) + { + tagged_ptr old_pool (pool_); + + freelist_node * fl_node = reinterpret_cast(n); + + fl_node->next.set_ptr(old_pool.get_ptr()); + + tagged_ptr new_pool (fl_node, old_pool.get_tag() + 1); + + if (pool_.CAS(old_pool, new_pool)) + { + --free_list_size; + return; + } + } + } + +private: + void free_memory_pool(void) + { + tagged_ptr current (pool_); + + while (current) + { + freelist_node * n = current.get_ptr(); + current.set(current->next); + operator delete(n); + } + } + + tagged_ptr pool_; + atomic_int free_list_size; +}; + +template +class caching_freelist: + public dummy_freelist +{ + struct freelist_node + { + tagged_ptr next; + }; + + typedef lockfree::tagged_ptr tagged_ptr; + +public: + caching_freelist(void): + pool_(NULL) + {} + + ~caching_freelist(void) + { + free_memory_pool(); + } + + T * allocate (void) + { + for(;;) + { + tagged_ptr old_pool(pool_); + + if (not old_pool) + return dummy_freelist::allocate(); + + tagged_ptr new_pool (old_pool->next); + + new_pool.set_tag(old_pool.get_tag() + 1); + + if (pool_.CAS(old_pool, new_pool)) + return reinterpret_cast(old_pool.get_ptr()); + } + } + + void deallocate (T * n) + { + for(;;) + { + tagged_ptr old_pool (pool_); + + freelist_node * fl_node = reinterpret_cast(n); + + fl_node->next.set_ptr(old_pool.get_ptr()); + + tagged_ptr new_pool (fl_node, old_pool.get_tag() + 1); + + if (pool_.CAS(old_pool, new_pool)) + return; + } + } + +private: + void free_memory_pool(void) + { + tagged_ptr current (pool_); + + while (current) + { + freelist_node * n = current.get_ptr(); + current.set(current->next); + operator delete(n); + } + } + + tagged_ptr pool_; +}; + + +} /* namespace lockfree */ +} /* namespace boost */ + +#endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */ diff --git a/boost/lockfree/prefix.hpp b/boost/lockfree/prefix.hpp new file mode 100644 index 0000000..e428ce6 --- /dev/null +++ b/boost/lockfree/prefix.hpp @@ -0,0 +1,45 @@ +// Copyright (C) 2007, 2008 Tim Blechmann & Thomas Grill +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_PREFIX_HPP_INCLUDED +#define BOOST_LOCKFREE_PREFIX_HPP_INCLUDED + +#include + + +#ifdef _WIN32 + #include +#endif + +#ifdef __APPLE__ + #include + + #if defined(__GLIBCPP__) || defined(__GLIBCXX__) + #include + #endif +#endif + +#if defined(_MSC_VER) +// \note: Must use /Oi option for VC++ to enable intrinsics + extern "C" { + void __cdecl _ReadWriteBarrier(); + LONG __cdecl _InterlockedCompareExchange(LONG volatile* Dest,LONG Exchange, LONG Comp); + } +#endif + + +#ifdef USE_ATOMIC_OPS + #define AO_REQUIRE_CAS + #define AO_USE_PENTIUM4_INSTRS + + extern "C" { + #include "../libatomic_ops/src/atomic_ops.h" + } +#endif + +#endif /* BOOST_LOCKFREE_PREFIX_HPP_INCLUDED */ diff --git a/boost/lockfree/tagged_ptr.hpp b/boost/lockfree/tagged_ptr.hpp new file mode 100644 index 0000000..de4ce42 --- /dev/null +++ b/boost/lockfree/tagged_ptr.hpp @@ -0,0 +1,184 @@ +// tagged pointer, for aba prevention +// +// Copyright (C) 2008 Tim Blechmann +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Disclaimer: Not a Boost library. + +#ifndef BOOST_LOCKFREE_TAGGED_PTR_HPP_INCLUDED +#define BOOST_LOCKFREE_TAGGED_PTR_HPP_INCLUDED + +#include "cas.hpp" +#include "branch_hints.hpp" + +#include + +namespace boost +{ +namespace lockfree +{ + +template +class tagged_ptr +{ + typedef std::size_t tag_t; + +public: + /** uninitialized constructor */ + tagged_ptr(void)//: ptr(0), tag(0) + {} + + /** copy constructor */ + tagged_ptr(tagged_ptr const & p)//: ptr(0), tag(0) + { + set(p); + } + + tagged_ptr(T * p, tag_t t = 0): + ptr(p), tag(t) + {} + + /** atomic set operations */ + /* @{ */ + void operator= (tagged_ptr const & p) + { + atomic_set(p); + } + + void atomic_set(tagged_ptr const & p) + { + for (;;) + { + tagged_ptr old; + old.set(*this); + if(likely(CAS(old, p.ptr, p.tag))) + return; + } + } + + void atomic_set(T * p, tag_t t) + { + for (;;) + { + tagged_ptr old; + old.set(*this); + + if(likely(CAS(old, p, t))) + return; + } + } + /* @} */ + + /** unsafe set operation */ + /* @{ */ + void set(tagged_ptr const & p) + { + ptr = p.ptr; + tag = p.tag; + } + + void set(T * p, tag_t t) + { + ptr = p; + tag = t; + } + /* @} */ + + /** comparing semantics */ + /* @{ */ + bool operator== (tagged_ptr const & p) const + { + return (ptr == p.ptr) && (tag == p.tag); + } + + bool operator!= (tagged_ptr const & p) const + { + return !operator==(p); + } + /* @} */ + + /** pointer access */ + /* @{ */ + T * get_ptr() const + { + return ptr; + } + + void set_ptr(T * p) + { + ptr = p; + } + /* @} */ + + /** tag access */ + /* @{ */ + tag_t get_tag() const + { + return tag; + } + + void set_tag(tag_t t) + { + tag = t; + } + /* @} */ + + /** compare and swap */ + /* @{ */ + bool CAS(tagged_ptr const & oldval, tagged_ptr const & newval) + { + return boost::lockfree::CAS2(this, oldval.ptr, oldval.tag, newval.ptr, newval.tag); + } + + bool CAS(tagged_ptr const & oldval, T * newptr) + { + return boost::lockfree::CAS2(this, oldval.ptr, oldval.tag, newptr, oldval.tag + 1); + } + + bool CAS(tagged_ptr const & oldval, T * newptr, tag_t t) + { + return boost::lockfree::CAS2(this, oldval.ptr, oldval.tag, newptr, t); + } + + bool CAS(const T * oldptr, tag_t oldtag, T * newptr) + { + return boost::lockfree::CAS2(oldptr, oldtag, newptr, oldtag + 1); + } + +/* bool CAS(const T * oldptr, tag_t oldtag, T * newptr, tag_t newtag) */ +/* { */ +/* return lockfree::CAS2(const_cast(this), oldptr, oldtag, newptr, newtag); */ +/* } */ + /* @} */ + + /** smart pointer support */ + /* @{ */ + T & operator*() const + { + return *ptr; + } + + T * operator->() const + { + return ptr; + } + + operator bool(void) const + { + return bool (ptr); + } + /* @} */ + +protected: + T * ptr DCAS_ALIGNMENT_ATTRIBUTE; + tag_t tag; +}; + + +} /* namespace lockfree */ +} /* namespace boost */ + +#endif /* BOOST_LOCKFREE_TAGGED_PTR_HPP_INCLUDED */ -- 2.11.4.GIT