# common/include/boost/lockfree/detail/tagged_ptr_ptrcompression.hpp

    00001 //  tagged pointer, for aba prevention
    00002 //
    00003 //  Copyright (C) 2008, 2009 Tim Blechmann, based on code by Cory Nelson
    00004 //
    00005 //  Distributed under the Boost Software License, Version 1.0. (See
    00006 //  accompanying file LICENSE_1_0.txt or copy at
    00007 //  http://www.boost.org/LICENSE_1_0.txt)
    00008
    00009 //  Disclaimer: Not a Boost library.
    00010
    00011 #ifndef BOOST_LOCKFREE_TAGGED_PTR_PTRCOMPRESSION_HPP_INCLUDED
    00012 #define BOOST_LOCKFREE_TAGGED_PTR_PTRCOMPRESSION_HPP_INCLUDED
    00013
    00014 #include <boost/lockfree/detail/cas.hpp>
    00015 #include <boost/lockfree/detail/branch_hints.hpp>
    00016
    00017 #include <cstddef>              /* for std::size_t */
    00018
    00019 #include <boost/cstdint.hpp>
    00020
    00021 namespace boost
    00022 {
    00023 namespace lockfree
    00024 {
    00025
    00026 #if defined (__x86_64__) || defined (_M_X64)
    00027
    00028 template <class T>
    00029 class BOOST_LOCKFREE_DCAS_ALIGNMENT tagged_ptr
    00030 {
    00031     typedef boost::uint64_t compressed_ptr_t;
    00032     typedef boost::uint16_t tag_t;
    00033
    00034 private:
    00035     union cast_unit
    00036     {
    00037         compressed_ptr_t value;
    00038         tag_t tag[4];
    00039     };
    00040
    00041     static const int tag_index = 3;
    00042     static const compressed_ptr_t ptr_mask = 0xffffffffffff; //(1L<<48L)-1;
    00043
    00044     static T* extract_ptr(compressed_ptr_t const & i)
    00045     {
    00046         return (T*)(i & ptr_mask);
    00047     }
    00048
    00049     static tag_t extract_tag(compressed_ptr_t const & i)
    00050     {
    00051         cast_unit cu;
    00052         cu.value = i;
    00053         return cu.tag[tag_index];
    00054     }
    00055
    00056     static compressed_ptr_t pack_ptr(T * ptr, int tag)
    00057     {
    00058         cast_unit ret;
    00059         ret.value = compressed_ptr_t(ptr);
    00060         ret.tag[tag_index] = tag;
    00061         return ret.value;
    00062     }
    00063
    00064 public:
    00065     static const bool is_lockfree = boost::lockfree::atomic_cas<compressed_ptr_t>::is_lockfree;
    00066
    00068     tagged_ptr(void)//: ptr(0), tag(0)
    00069     {}
    00070
    00072     tagged_ptr(tagged_ptr const & p)//: ptr(0), tag(0)
    00073     {
    00074         set(p);
    00075     }
    00076
    00077     explicit tagged_ptr(T * p, tag_t t = 0):
    00078         ptr(pack_ptr(p, t))
    00079     {}
    00080
    00082     /* @{ */
    00083     void operator= (tagged_ptr const & p)
    00084     {
    00085         atomic_set(p);
    00086     }
    00087
    00088     void atomic_set(tagged_ptr const & p)
    00089     {
    00090         set(p);
    00091     }
    00092
    00093     void atomic_set(T * p, tag_t t)
    00094     {
    00095         ptr = pack_ptr(p, t);
    00096     }
    00097     /* @} */
    00098
    00100     /* @{ */
    00101     void set(tagged_ptr const & p)
    00102     {
    00103         ptr = p.ptr;
    00104     }
    00105
    00106     void set(T * p, tag_t t)
    00107     {
    00108         ptr = pack_ptr(p, t);
    00109     }
    00110     /* @} */
    00111
    00113     /* @{ */
    00114     bool operator== (tagged_ptr const & p) const
    00115     {
    00116         return (ptr == p.ptr);
    00117     }
    00118
    00119     bool operator!= (tagged_ptr const & p) const
    00120     {
    00121         return !operator==(p);
    00122     }
    00123     /* @} */
    00124
    00126     /* @{ */
    00127     T * get_ptr() const
    00128     {
    00129         return extract_ptr(ptr);
    00130     }
    00131
    00132     void set_ptr(T * p)
    00133     {
    00134         tag_t tag = get_tag();
    00135         ptr = pack_ptr(p, tag);
    00136     }
    00137     /* @} */
    00138
    00140     /* @{ */
    00141     tag_t get_tag() const
    00142     {
    00143         return extract_tag(ptr);
    00144     }
    00145
    00146     void set_tag(tag_t t)
    00147     {
    00148         T * p = get_ptr();
    00149         ptr = pack_ptr(p, t);
    00150     }
    00151     /* @} */
    00152
    00154     /* @{ */
    00155 private:
    00156     bool cas(compressed_ptr_t const & oldval, compressed_ptr_t const & newval)
    00157     {
    00158         return boost::lockfree::atomic_cas<compressed_ptr_t>::cas(&(this->ptr), oldval, newval);
    00159     }
    00160
    00161 public:
    00162     bool cas(tagged_ptr const & oldval, T * newptr)
    00163     {
    00164         compressed_ptr_t new_compressed_ptr = pack_ptr(newptr, extract_tag(oldval.ptr)+1);
    00165         return cas(oldval.ptr, new_compressed_ptr);
    00166     }
    00167
    00168     bool cas(tagged_ptr const & oldval, T * newptr, tag_t t)
    00169     {
    00170         compressed_ptr_t new_compressed_ptr = pack_ptr(newptr, t);
    00171         return boost::lockfree::atomic_cas<compressed_ptr_t>::cas(&(this->ptr), oldval.ptr, new_compressed_ptr);
    00172     }
    00173     /* @} */
    00174
    00176     /* @{ */
    00177     T & operator*() const
    00178     {
    00179         return *get_ptr();
    00180     }
    00181
    00182     T * operator->() const
    00183     {
    00184         return get_ptr();
    00185     }
    00186
    00187     operator bool(void) const
    00188     {
    00189         return get_ptr() != 0;
    00190     }
    00191     /* @} */
    00192
    00193 protected:
    00194     compressed_ptr_t ptr;
    00195 };
    00196 #else
    00197 #error unsupported platform
    00198 #endif
    00199
    00200 } /* namespace lockfree */
    00201 } /* namespace boost */
    00202
    00203 #endif /* BOOST_LOCKFREE_TAGGED_PTR_PTRCOMPRESSION_HPP_INCLUDED */