folly::HazptrSWMRSet< T, Atom > Class Template Reference

#include <HazptrSWMRSet.h>

Classes
struct	Node
struct	Reclaimer

Public Member Functions
	HazptrSWMRSet ()
	~HazptrSWMRSet ()
bool	add (T v)
bool	remove (const T &v)
bool	contains (const T &val) const

Private Member Functions
void	locate_lower_bound (const T &v, Atom< Node * > *&prev) const

Private Attributes
Atom< Node * >	head_ {nullptr}

Detailed Description

template<typename T, template< typename > class Atom = std::atomic>
class folly::HazptrSWMRSet< T, Atom >

Set implemented as an ordered singly-linked list.

A single writer thread may add or remove elements. Multiple reader threads may search the set concurrently with each other and with the writer's operations.

Definition at line 31 of file HazptrSWMRSet.h.

Constructor & Destructor Documentation

template<typename T, template< typename > class Atom = std::atomic>

folly::HazptrSWMRSet< T, Atom >::HazptrSWMRSet ( )

inline

Definition at line 49 of file HazptrSWMRSet.h.

: head_(nullptr) {}

template<typename T, template< typename > class Atom = std::atomic>

folly::HazptrSWMRSet< T, Atom >::~HazptrSWMRSet ( )

inline

Definition at line 51 of file HazptrSWMRSet.h.

References folly::HazptrSWMRSet< T, Atom >::head_, and cpp.ast::next().

                   {
    auto p = head_.load();
    while (p) {
      auto next = p->next_.load();
      delete p;
      p = next;
    }
  }

Member Function Documentation

template<typename T, template< typename > class Atom = std::atomic>

bool folly::HazptrSWMRSet< T, Atom >::add ( T  v )

inline

Definition at line 60 of file HazptrSWMRSet.h.

References folly::HazptrSWMRSet< T, Atom >::head_, folly::HazptrSWMRSet< T, Atom >::locate_lower_bound(), and folly::gen::move.

Referenced by swmr_test().

                {
    auto prev = &head_;
    locate_lower_bound(v, prev);
    auto curr = prev->load(std::memory_order_relaxed);
    if (curr && curr->elem_ == v) {
      return false;
    }
    prev->store(new Node(std::move(v), curr));
    return true;
  }

template<typename T, template< typename > class Atom = std::atomic>

bool folly::HazptrSWMRSet< T, Atom >::contains ( const T &  val ) const

inline

Definition at line 88 of file HazptrSWMRSet.h.

References folly::HazptrSWMRSet< T, Atom >::head_, cpp.ast::next(), folly::f14::swap(), and folly::hazptr_holder< Atom >::try_protect().

Referenced by swmr_test().

                                    {
    /* Two hazard pointers for hand-over-hand traversal. */
    hazptr_local<2, Atom> hptr;
    hazptr_holder<Atom>* hptr_prev = &hptr[0];
    hazptr_holder<Atom>* hptr_curr = &hptr[1];
    while (true) {
      auto prev = &head_;
      auto curr = prev->load(std::memory_order_acquire);
      while (true) {
        if (!curr) {
          return false;
        }
        if (!hptr_curr->try_protect(curr, *prev)) {
          break;
        }
        auto next = curr->next_.load(std::memory_order_acquire);
        if (prev->load(std::memory_order_acquire) != curr) {
          break;
        }
        if (curr->elem_ == val) {
          return true;
        } else if (!(curr->elem_ < val)) {
          return false; // because the list is sorted
        }
        prev = &(curr->next_);
        curr = next;
        std::swap(hptr_curr, hptr_prev);
      }
    }
  }

template<typename T, template< typename > class Atom = std::atomic>

void folly::HazptrSWMRSet< T, Atom >::locate_lower_bound ( const T &  v, Atom< Node * > *&  prev  ) const

inlineprivate

Definition at line 121 of file HazptrSWMRSet.h.

Referenced by folly::HazptrSWMRSet< T, Atom >::add(), and folly::HazptrSWMRSet< T, Atom >::remove().

                                                                {
    auto curr = prev->load(std::memory_order_relaxed);
    while (curr) {
      if (curr->elem_ >= v) {
        break;
      }
      prev = &(curr->next_);
      curr = curr->next_.load(std::memory_order_relaxed);
    }
    return;
  }

template<typename T, template< typename > class Atom = std::atomic>

bool folly::HazptrSWMRSet< T, Atom >::remove ( const T &  v )

inline

Definition at line 71 of file HazptrSWMRSet.h.

References folly::HazptrSWMRSet< T, Atom >::head_, folly::HazptrSWMRSet< T, Atom >::locate_lower_bound(), and folly::HazptrSWMRSet< T, Atom >::Node::next_.

Referenced by swmr_test().

                          {
    auto prev = &head_;
    locate_lower_bound(v, prev);
    auto curr = prev->load(std::memory_order_relaxed);
    if (!curr || curr->elem_ != v) {
      return false;
    }
    Node* curr_next = curr->next_.load();
    // Patch up the actual list...
    prev->store(curr_next, std::memory_order_release);
    // ...and only then null out the removed node.
    curr->next_.store(nullptr, std::memory_order_release);
    curr->retire();
    return true;
  }

Member Data Documentation

template<typename T, template< typename > class Atom = std::atomic>

Atom<Node*> folly::HazptrSWMRSet< T, Atom >::head_ {nullptr}

private

Definition at line 46 of file HazptrSWMRSet.h.

Referenced by folly::HazptrSWMRSet< T, Atom >::add(), folly::HazptrSWMRSet< T, Atom >::contains(), folly::HazptrSWMRSet< T, Atom >::remove(), and folly::HazptrSWMRSet< T, Atom >::~HazptrSWMRSet().

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/synchronization/example/HazptrSWMRSet.h