freelist.hpp

#pragma once
 
#include "../utility/os.hpp"
#include <atomic>
 
namespace tf {


template <typename T, auto MemberPtr>
class AtomicIntrusiveStack {
 
  // NodeType is the pointee (e.g. Node from Node*)
  using NodeType = std::remove_pointer_t<T>;
 
  static_assert(
    std::is_same_v<T, std::remove_reference_t<
      decltype(std::declval<NodeType>().*MemberPtr)
    >>,
    "MemberPtr must point to a field of type T within the node"
  );
 
  // helper: access the intrusive link field of a node
  static T& _link(T node) { return node->*MemberPtr; }
 
  struct TaggedPointer {
    T      ptr;
    size_t tag;
  };
 
  alignas(TF_CACHELINE_SIZE) std::atomic<TaggedPointer> _head;
 
  public:

  AtomicIntrusiveStack() {
    _head.store({nullptr, 0}, std::memory_order_relaxed);
  }

  bool empty() const {
    return _head.load(std::memory_order_relaxed).ptr == nullptr;
  }

  void push(T node) {
 
    TaggedPointer curr = _head.load(std::memory_order_relaxed);
 
    while(true) {
      _link(node) = curr.ptr;
      TaggedPointer next = {node, curr.tag + 1};
 
      if(_head.compare_exchange_weak(curr, next,
                                     std::memory_order_release,
                                     std::memory_order_relaxed)) {
        break;
      }
      // on failure curr is reloaded by compare_exchange_weak
    }
  }

  T pop() {
 
    TaggedPointer curr = _head.load(std::memory_order_acquire);
 
    while(curr.ptr != nullptr) {
      TaggedPointer next = {_link(curr.ptr), curr.tag + 1};
 
      if(_head.compare_exchange_weak(curr, next,
                                     std::memory_order_release,
                                     std::memory_order_acquire)) {
        // This can cause thread sanitizer to report error since this assignment
        // has not guarantee to finish before the return while the other thread
        // may call push that modify curr.ptr causing data race...
        return curr.ptr;
      }
      // on failure curr is reloaded
    }
    return nullptr;
  }
};
 
// ----------------------------------------------------------------------------
// AtomicIntrusiveStack — 64-bit tagged-pointer alternative
//
// Uses the upper 16 bits of a 64-bit uintptr_t as a version tag, avoiding
// the need for 128-bit CAS. Relies on x86-64 canonical address space where
// only the lower 48 bits are used for actual addresses.
//
// Parameterized identically to the 128-bit version above.
// ----------------------------------------------------------------------------
 
/*
template <typename T, auto MemberPtr>
class AtomicIntrusiveStack {
 
  using NodeType = std::remove_pointer_t<T>;
 
  static_assert(
    std::is_same_v<T, std::remove_reference_t<
      decltype(std::declval<NodeType>().*MemberPtr)
    >>,
    "MemberPtr must point to a field of type T within the node"
  );
 
  static T& _link(T node) { return node->*MemberPtr; }
 
  static constexpr uintptr_t ADDR_MASK = (uintptr_t{1} << 48) - 1;
  static constexpr uintptr_t TAG_INC   = (uintptr_t{1} << 48);
 
  T _unpack(uintptr_t val) const {
    return reinterpret_cast<T>(val & ADDR_MASK);
  }
 
  uintptr_t _pack(T ptr, uintptr_t old_val) const {
    uintptr_t next_tag = (old_val & ~ADDR_MASK) + TAG_INC;
    return next_tag | (reinterpret_cast<uintptr_t>(ptr) & ADDR_MASK);
  }
 
  alignas(TF_CACHELINE_SIZE) std::atomic<uintptr_t> _head;
 
public:
 
  AtomicIntrusiveStack() : _head(0) {}
 
  bool empty() const {
    return _unpack(_head.load(std::memory_order_relaxed)) == nullptr;
  }
 
  void push(T node) {
    uintptr_t curr = _head.load(std::memory_order_relaxed);
    while(true) {
      _link(node) = _unpack(curr);
      uintptr_t next = _pack(node, curr);
      if(_head.compare_exchange_weak(curr, next,
                                     std::memory_order_release,
                                     std::memory_order_relaxed)) {
        break;
      }
    }
  }
 
  template <typename I>
  void bulk_push(I first, size_t N) {
    if(N == 0) return;
    for(size_t i = 0; i < N-1; ++i) {
      _link(first[i]) = first[i+1];
    }
    _link(first[N-1]) = nullptr;
    uintptr_t curr = _head.load(std::memory_order_relaxed);
    while(true) {
      _link(first[N-1]) = _unpack(curr);
      uintptr_t next = _pack(first[0], curr);
      if(_head.compare_exchange_weak(curr, next,
                                     std::memory_order_release,
                                     std::memory_order_relaxed)) {
        break;
      }
    }
  }
 
  T pop() {
    uintptr_t curr = _head.load(std::memory_order_acquire);
    while(true) {
      T curr_ptr = _unpack(curr);
      if(curr_ptr == nullptr) return nullptr;
      uintptr_t next = _pack(_link(curr_ptr), curr);
      if(_head.compare_exchange_weak(curr, next,
                                     std::memory_order_release,
                                     std::memory_order_acquire)) {
        _link(curr_ptr) = nullptr;
        return curr_ptr;
      }
    }
  }
};
*/
 
}  // end of namespace tf. ----------------------------------------------------