proxygen: folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX

#include <ConcurrentSkipList.h>

Classes
class	Accessor

class	Skipper

Public Types
typedef detail::SkipListNode< T >	NodeType

typedef T	value_type

typedef T	key_type

typedef detail::csl_iterator< value_type, NodeType >	iterator

typedef detail::csl_iterator< const value_type, const NodeType >	const_iterator

Public Member Functions
	ConcurrentSkipList (int height, const NodeAlloc &alloc)

	ConcurrentSkipList (int height)

	~ConcurrentSkipList ()

Static Public Member Functions
static Accessor	create (int height, const NodeAlloc &alloc)

static Accessor	create (int height=1)

static std::shared_ptr< SkipListType >	createInstance (int height, const NodeAlloc &alloc)

static std::shared_ptr< SkipListType >	createInstance (int height=1)

Private Types
typedef std::unique_lock< folly::MicroSpinLock >	ScopedLocker

typedef ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >	SkipListType

Private Member Functions
size_t	size () const

int	height () const

int	maxLayer () const

size_t	incrementSize (int delta)

NodeType *	find (const value_type &data)

bool	lockNodesForChange (int nodeHeight, ScopedLocker guards[MAX_HEIGHT], NodeType preds[MAX_HEIGHT], NodeType succs[MAX_HEIGHT], bool adding=true)

template<typename U >
std::pair< NodeType *, size_t >	addOrGetData (U &&data)

bool	remove (const value_type &data)

const value_type *	first () const

const value_type *	last () const

int	findInsertionPointGetMaxLayer (const value_type &data, NodeType preds[], NodeType succs[], int *max_layer) const

std::pair< NodeType *, int >	findNode (const value_type &data) const

std::pair< NodeType *, int >	findNodeDownRight (const value_type &data) const

std::pair< NodeType *, int >	findNodeRightDown (const value_type &data) const

NodeType *	lower_bound (const value_type &data) const

void	growHeight (int height)

void	recycle (NodeType *node)

Static Private Member Functions
static bool	greater (const value_type &data, const NodeType *node)

static bool	less (const value_type &data, const NodeType *node)

static int	findInsertionPoint (NodeType cur, int cur_layer, const value_type &data, NodeType preds[], NodeType *succs[])

static bool	okToDelete (NodeType *candidate, int layer)

Private Attributes
detail::NodeRecycler< NodeType, NodeAlloc >	recycler_

std::atomic< NodeType * >	head_

std::atomic< size_t >	size_

Detailed Description

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
class folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >

Definition at line 145 of file ConcurrentSkipList.h.

Member Typedef Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef detail::csl_iterator<const value_type, const NodeType> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::const_iterator

Definition at line 161 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef detail::csl_iterator<value_type, NodeType> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::iterator

Definition at line 160 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef T folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::key_type

Definition at line 158 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef detail::SkipListNode<T> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::NodeType

Definition at line 156 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef std::unique_lock<folly::MicroSpinLock> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::ScopedLocker

private

Definition at line 151 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::SkipListType

private

Definition at line 153 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

typedef T folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::value_type

Definition at line 157 of file ConcurrentSkipList.h.

Constructor & Destructor Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::ConcurrentSkipList	(	int	height,
		const NodeAlloc &	alloc
	)

inlineexplicit

Definition at line 166 of file ConcurrentSkipList.h.

       : recycler_(alloc),
         head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
         size_(0) {}

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::ConcurrentSkipList ( int height )

inlineexplicit

Definition at line 171 of file ConcurrentSkipList.h.

       : recycler_(),
         head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
         size_(0) {}

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::~ConcurrentSkipList ( )

inline

Definition at line 201 of file ConcurrentSkipList.h.

References current, folly::detail::SkipListNode< T >::destroy(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_, and value.

                         {
     if /* constexpr */ (NodeType::template DestroyIsNoOp<NodeAlloc>::value) {
       // Avoid traversing the list if using arena allocator.
       return;
     }
     for (NodeType* current = head_.load(std::memory_order_relaxed); current;) {
       NodeType* tmp = current->skip(0);
       NodeType::destroy(recycler_.alloc(), current);
       current = tmp;
     }
   }

Member Function Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

template<typename U >

std::pair<NodeType*, size_t> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData ( U && data )

inlineprivate

Definition at line 314 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::create(), folly::data(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPointGetMaxLayer(), folly::detail::SkipListNode< T >::fullyLinked(), folly::detail::SkipListRandomHeight::getHeight(), folly::detail::SkipListRandomHeight::getSizeLimit(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::growHeight(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::incrementSize(), folly::detail::SkipListRandomHeight::instance(), k, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lockNodesForChange(), folly::detail::SkipListNode< T >::markedForRemoval(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_, folly::detail::SkipListNode< T >::setFullyLinked(), folly::detail::SkipListNode< T >::setSkip(), and UNLIKELY.

                                                     {
     NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
     NodeType* newNode;
     size_t newSize;
     while (true) {
       int max_layer = 0;
       int layer = findInsertionPointGetMaxLayer(data, preds, succs, &max_layer);
 
       if (layer >= 0) {
         NodeType* nodeFound = succs[layer];
         DCHECK(nodeFound != nullptr);
         if (nodeFound->markedForRemoval()) {
           continue; // if it's getting deleted retry finding node.
         }
         // wait until fully linked.
         while (UNLIKELY(!nodeFound->fullyLinked())) {
         }
         return std::make_pair(nodeFound, 0);
       }
 
       // need to capped at the original height -- the real height may have grown
       int nodeHeight =
           detail::SkipListRandomHeight::instance()->getHeight(max_layer + 1);
 
       ScopedLocker guards[MAX_HEIGHT];
       if (!lockNodesForChange(nodeHeight, guards, preds, succs)) {
         continue; // give up the locks and retry until all valid
       }
 
       // locks acquired and all valid, need to modify the links under the locks.
       newNode = NodeType::create(
           recycler_.alloc(), nodeHeight, std::forward<U>(data));
       for (int k = 0; k < nodeHeight; ++k) {
         newNode->setSkip(k, succs[k]);
         preds[k]->setSkip(k, newNode);
       }
 
       newNode->setFullyLinked();
       newSize = incrementSize(1);
       break;
     }
 
     int hgt = height();
     size_t sizeLimit =
         detail::SkipListRandomHeight::instance()->getSizeLimit(hgt);
 
     if (hgt < MAX_HEIGHT && newSize > sizeLimit) {
       growHeight(hgt + 1);
     }
     CHECK_GT(newSize, 0);
     return std::make_pair(newNode, newSize);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static Accessor folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::create	(	int	height,
		const NodeAlloc &	alloc
	)

inlinestatic

Definition at line 177 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::createInstance().

                                                              {
     return Accessor(createInstance(height, alloc));
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static Accessor folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::create ( int height = 1 )

inlinestatic

Definition at line 181 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::createInstance(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height().

                                          {
     return Accessor(createInstance(height));
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static std::shared_ptr<SkipListType> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::createInstance	(	int	height,
		const NodeAlloc &	alloc
	)

inlinestatic

Definition at line 186 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::create().

                               {
     return std::make_shared<ConcurrentSkipList>(height, alloc);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static std::shared_ptr<SkipListType> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::createInstance ( int height = 1 )

inlinestatic

Definition at line 192 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height().

                                                                     {
     return std::make_shared<ConcurrentSkipList>(height);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

NodeType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::find ( const value_type & data )

inlineprivate

Definition at line 268 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNode().

                                          {
     auto ret = findNode(data);
     if (ret.second && !ret.first->markedForRemoval()) {
       return ret.first;
     }
     return nullptr;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPoint	(	NodeType *	cur,
		int	cur_layer,
		const value_type &	data,
		NodeType *	preds[],
		NodeType *	succs[]
	)

inlinestaticprivate

Definition at line 222 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::greater(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::less(), and folly::detail::SkipListNode< T >::skip().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPointGetMaxLayer(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::to().

                          {
     int foundLayer = -1;
     NodeType* pred = cur;
     NodeType* foundNode = nullptr;
     for (int layer = cur_layer; layer >= 0; --layer) {
       NodeType* node = pred->skip(layer);
       while (greater(data, node)) {
         pred = node;
         node = node->skip(layer);
       }
       if (foundLayer == -1 && !less(data, node)) { // the two keys equal
         foundLayer = layer;
         foundNode = node;
       }
       preds[layer] = pred;
 
       // if found, succs[0..foundLayer] need to point to the cached foundNode,
       // as foundNode might be deleted at the same time thus pred->skip() can
       // return nullptr or another node.
       succs[layer] = foundNode ? foundNode : node;
     }
     return foundLayer;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPointGetMaxLayer	(	const value_type &	data,
		NodeType *	preds[],
		NodeType *	succs[],
		int *	max_layer
	)		const

inlineprivate

Definition at line 436 of file ConcurrentSkipList.h.

References folly::data(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPoint(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::maxLayer().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                             {
     *max_layer = maxLayer();
     return findInsertionPoint(
         head_.load(std::memory_order_consume), *max_layer, data, preds, succs);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

std::pair<NodeType*, int> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNode ( const value_type & data ) const

inlineprivate

Definition at line 451 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::find(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lower_bound().

                                                                  {
     return findNodeDownRight(data);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

std::pair<NodeType*, int> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight ( const value_type & data ) const

inlineprivate

Definition at line 458 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::greater(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, folly::detail::SkipListNode< T >::height(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::less(), and folly::detail::SkipListNode< T >::skip().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNode().

                                                                           {
     NodeType* pred = head_.load(std::memory_order_consume);
     int ht = pred->height();
     NodeType* node = nullptr;
 
     bool found = false;
     while (!found) {
       // stepping down
       for (; ht > 0 && less(data, node = pred->skip(ht - 1)); --ht) {
       }
       if (ht == 0) {
         return std::make_pair(node, 0); // not found
       }
       // node <= data now, but we need to fix up ht
       --ht;
 
       // stepping right
       while (greater(data, node)) {
         pred = node;
         node = node->skip(ht);
       }
       found = !less(data, node);
     }
     return std::make_pair(node, found);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

std::pair<NodeType*, int> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeRightDown ( const value_type & data ) const

inlineprivate

Definition at line 486 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::greater(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::less(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::maxLayer(), folly::detail::SkipListNode< T >::skip(), and folly::pushmi::top.

                                                                           {
     NodeType* pred = head_.load(std::memory_order_consume);
     NodeType* node = nullptr;
     auto top = maxLayer();
     int found = 0;
     for (int layer = top; !found && layer >= 0; --layer) {
       node = pred->skip(layer);
       while (greater(data, node)) {
         pred = node;
         node = node->skip(layer);
       }
       found = !less(data, node);
     }
     return std::make_pair(node, found);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

const value_type* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::first ( ) const

inlineprivate

Definition at line 409 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_.

                                   {
     auto node = head_.load(std::memory_order_consume)->skip(0);
     return node ? &node->data() : nullptr;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::greater	(	const value_type &	data,
		const NodeType *	node
	)

inlinestaticprivate

Definition at line 214 of file ConcurrentSkipList.h.

References folly::data(), and folly::detail::SkipListNode< T >::data().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPoint(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeRightDown(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::to().

                                                                     {
     return node && Comp()(node->data(), data);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

void folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::growHeight ( int height )

inlineprivate

Definition at line 510 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::acquireGuard(), folly::detail::SkipListNode< T >::copyHead(), folly::detail::SkipListNode< T >::create(), folly::detail::SkipListNode< T >::destroy(), g(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, folly::detail::SkipListNode< T >::height(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycle(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_, and folly::detail::SkipListNode< T >::setMarkedForRemoval().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData().

                               {
     NodeType* oldHead = head_.load(std::memory_order_consume);
     if (oldHead->height() >= height) { // someone else already did this
       return;
     }
 
     NodeType* newHead =
         NodeType::create(recycler_.alloc(), height, value_type(), true);
 
     { // need to guard the head node in case others are adding/removing
       // nodes linked to the head.
       ScopedLocker g = oldHead->acquireGuard();
       newHead->copyHead(oldHead);
       NodeType* expected = oldHead;
       if (!head_.compare_exchange_strong(
               expected, newHead, std::memory_order_release)) {
         // if someone has already done the swap, just return.
         NodeType::destroy(recycler_.alloc(), newHead);
         return;
       }
       oldHead->setMarkedForRemoval();
     }
     recycle(oldHead);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height ( ) const

inlineprivate

Definition at line 255 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_.

                      {
     return head_.load(std::memory_order_consume)->height();
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

size_t folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::incrementSize ( int delta )

inlineprivate

Definition at line 263 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::size_.

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                                   {
     return size_.fetch_add(delta, std::memory_order_relaxed) + delta;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

const value_type* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::last ( ) const

inlineprivate

Definition at line 414 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::data(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::maxLayer(), and folly::detail::SkipListNode< T >::skip().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::pop_back().

                                  {
     NodeType* pred = head_.load(std::memory_order_consume);
     NodeType* node = nullptr;
     for (int layer = maxLayer(); layer >= 0; --layer) {
       do {
         node = pred->skip(layer);
         if (node) {
           pred = node;
         }
       } while (node != nullptr);
     }
     return pred == head_.load(std::memory_order_relaxed) ? nullptr
                                                          : &pred->data();
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::less	(	const value_type &	data,
		const NodeType *	node
	)

inlinestaticprivate

Definition at line 218 of file ConcurrentSkipList.h.

References folly::data(), and folly::detail::SkipListNode< T >::data().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPoint(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeRightDown().

                                                                  {
     return (node == nullptr) || Comp()(data, node->data());
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lockNodesForChange	(	int	nodeHeight,
		ScopedLocker	guards[MAX_HEIGHT],
		NodeType *	preds[MAX_HEIGHT],
		NodeType *	succs[MAX_HEIGHT],
		bool	adding = `true`
	)

inlineprivate

Definition at line 279 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::acquireGuard(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height(), folly::detail::SkipListNode< T >::markedForRemoval(), and folly::detail::SkipListNode< T >::skip().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                           {
     NodeType *pred, *succ, *prevPred = nullptr;
     bool valid = true;
     for (int layer = 0; valid && layer < nodeHeight; ++layer) {
       pred = preds[layer];
       DCHECK(pred != nullptr) << "layer=" << layer << " height=" << height()
                               << " nodeheight=" << nodeHeight;
       succ = succs[layer];
       if (pred != prevPred) {
         guards[layer] = pred->acquireGuard();
         prevPred = pred;
       }
       valid = !pred->markedForRemoval() &&
           pred->skip(layer) == succ; // check again after locking
 
       if (adding) { // when adding a node, the succ shouldn't be going away
         valid = valid && (succ == nullptr || !succ->markedForRemoval());
       }
     }
 
     return valid;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

NodeType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lower_bound ( const value_type & data ) const

inlineprivate

Definition at line 502 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNode().

                                                       {
     auto node = findNode(data).first;
     while (node != nullptr && node->markedForRemoval()) {
       node = node->skip(0);
     }
     return node;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::maxLayer ( ) const

inlineprivate

Definition at line 259 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::height().

                        {
     return height() - 1;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

static bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::okToDelete	(	NodeType *	candidate,
		int	layer
	)

inlinestaticprivate

Definition at line 429 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::fullyLinked(), folly::detail::SkipListNode< T >::markedForRemoval(), and folly::detail::SkipListNode< T >::maxLayer().

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                                                          {
     DCHECK(candidate != nullptr);
     return candidate->fullyLinked() && candidate->maxLayer() == layer &&
         !candidate->markedForRemoval();
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

void folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycle ( NodeType * node )

inlineprivate

Definition at line 535 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_.

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::growHeight(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                                {
     recycler_.add(node);
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove ( const value_type & data )

inlineprivate

Definition at line 367 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::acquireGuard(), folly::data(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPointGetMaxLayer(), folly::detail::SkipListNode< T >::height(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::incrementSize(), k, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lockNodesForChange(), folly::detail::SkipListNode< T >::markedForRemoval(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::okToDelete(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycle(), folly::detail::SkipListNode< T >::setMarkedForRemoval(), folly::detail::SkipListNode< T >::setSkip(), and folly::detail::SkipListNode< T >::skip().

                                       {
     NodeType* nodeToDelete = nullptr;
     ScopedLocker nodeGuard;
     bool isMarked = false;
     int nodeHeight = 0;
     NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
 
     while (true) {
       int max_layer = 0;
       int layer = findInsertionPointGetMaxLayer(data, preds, succs, &max_layer);
       if (!isMarked && (layer < 0 || !okToDelete(succs[layer], layer))) {
         return false;
       }
 
       if (!isMarked) {
         nodeToDelete = succs[layer];
         nodeHeight = nodeToDelete->height();
         nodeGuard = nodeToDelete->acquireGuard();
         if (nodeToDelete->markedForRemoval()) {
           return false;
         }
         nodeToDelete->setMarkedForRemoval();
         isMarked = true;
       }
 
       // acquire pred locks from bottom layer up
       ScopedLocker guards[MAX_HEIGHT];
       if (!lockNodesForChange(nodeHeight, guards, preds, succs, false)) {
         continue; // this will unlock all the locks
       }
 
       for (int k = nodeHeight - 1; k >= 0; --k) {
         preds[k]->setSkip(k, nodeToDelete->skip(k));
       }
 
       incrementSize(-1);
       break;
     }
     recycle(nodeToDelete);
     return true;
   }

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

size_t folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::size ( ) const

inlineprivate

Definition at line 251 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::size_.

                       {
     return size_.load(std::memory_order_relaxed);
   }

Member Data Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

std::atomic<NodeType*> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::head_

private

Definition at line 540 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

detail::NodeRecycler<NodeType, NodeAlloc> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_

private

Definition at line 539 of file ConcurrentSkipList.h.

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::growHeight(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::operator=(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycle(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::~ConcurrentSkipList().

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>

std::atomic<size_t> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::size_

private

Definition at line 541 of file ConcurrentSkipList.h.

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::incrementSize(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::size().

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

proxygen/folly/folly/ConcurrentSkipList.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24> class folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
class folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >