proxygen: folly::detail::SkipListNode< T > Class Template Reference

#include <ConcurrentSkipList-inl.h>

Inheritance diagram for folly::detail::SkipListNode< T >:

Classes
struct	DestroyIsNoOp

Public Types
typedef T	value_type

Public Member Functions
SkipListNode *	copyHead (SkipListNode *node)

SkipListNode *	skip (int layer) const

SkipListNode *	next ()

void	setSkip (uint8_t h, SkipListNode *next)

value_type &	data ()

const value_type &	data () const

int	maxLayer () const

int	height () const

std::unique_lock< MicroSpinLock >	acquireGuard ()

bool	fullyLinked () const

bool	markedForRemoval () const

bool	isHeadNode () const

void	setIsHeadNode ()

void	setFullyLinked ()

void	setMarkedForRemoval ()

Static Public Member Functions
template<typename NodeAlloc , typename U , typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>
static SkipListNode *	create (NodeAlloc &alloc, int height, U &&data, bool isHead=false)

template<typename NodeAlloc >
static void	destroy (NodeAlloc &alloc, SkipListNode *node)

Private Types
enum	: uint16_t { IS_HEAD_NODE = 1, MARKED_FOR_REMOVAL = (1 << 1), FULLY_LINKED = (1 << 2) }

Private Member Functions
template<typename U >
	SkipListNode (uint8_t height, U &&data, bool isHead)

	~SkipListNode ()

uint16_t	getFlags () const

void	setFlags (uint16_t flags)

Private Attributes
std::atomic< uint16_t >	flags_

const uint8_t	height_

MicroSpinLock	spinLock_

value_type	data_

std::atomic< SkipListNode * >	skip_ [0]

Detailed Description

template<typename T>
class folly::detail::SkipListNode< T >

Definition at line 46 of file ConcurrentSkipList-inl.h.

Member Typedef Documentation

template<typename T >

typedef T folly::detail::SkipListNode< T >::value_type

Definition at line 54 of file ConcurrentSkipList-inl.h.

Member Enumeration Documentation

template<typename T >

anonymous enum : uint16_t

private

Enumerator
IS_HEAD_NODE
MARKED_FOR_REMOVAL
FULLY_LINKED

Definition at line 47 of file ConcurrentSkipList-inl.h.

        : uint16_t {
     IS_HEAD_NODE = 1,
     MARKED_FOR_REMOVAL = (1 << 1),
     FULLY_LINKED = (1 << 2),
   };

Constructor & Destructor Documentation

template<typename T >

template<typename U >

folly::detail::SkipListNode< T >::SkipListNode	(	uint8_t	height,
		U &&	data,
		bool	isHead
	)

inlineprivate

Definition at line 155 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_, i, folly::MicroSpinLock::init(), folly::detail::SkipListNode< T >::setFlags(), folly::detail::SkipListNode< T >::setIsHeadNode(), folly::detail::SkipListNode< T >::skip_, folly::detail::SkipListNode< T >::spinLock_, and uint8_t.

Referenced by folly::detail::SkipListNode< T >::create(), and folly::detail::SkipListNode< T >::destroy().

       : height_(height), data_(std::forward<U>(data)) {
     spinLock_.init();
     setFlags(0);
     if (isHead) {
       setIsHeadNode();
     }
     // need to explicitly init the dynamic atomic pointer array
     for (uint8_t i = 0; i < height_; ++i) {
       new (&skip_[i]) std::atomic<SkipListNode*>(nullptr);
     }
   }

template<typename T >

folly::detail::SkipListNode< T >::~SkipListNode ( )

inlineprivate

Definition at line 168 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_, i, folly::detail::SkipListNode< T >::skip_, and uint8_t.

Referenced by folly::detail::SkipListNode< T >::destroy().

                   {
     for (uint8_t i = 0; i < height_; ++i) {
       skip_[i].~atomic();
     }
   }

Member Function Documentation

template<typename T >

std::unique_lock<MicroSpinLock> folly::detail::SkipListNode< T >::acquireGuard ( )

inline

Definition at line 128 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::spinLock_.

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

                                                {
     return std::unique_lock<MicroSpinLock>(spinLock_);
   }

template<typename T >

SkipListNode* folly::detail::SkipListNode< T >::copyHead ( SkipListNode< T > * node )

inline

Definition at line 87 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::getFlags(), folly::detail::SkipListNode< T >::height_, i, folly::detail::SkipListNode< T >::setFlags(), folly::detail::SkipListNode< T >::setSkip(), folly::detail::SkipListNode< T >::skip(), and uint8_t.

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

                                              {
     DCHECK(node != nullptr && height_ > node->height_);
     setFlags(node->getFlags());
     for (uint8_t i = 0; i < node->height_; ++i) {
       setSkip(i, node->skip(i));
     }
     return this;
   }

template<typename T >

template<typename NodeAlloc , typename U , typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>

static SkipListNode* folly::detail::SkipListNode< T >::create	(	NodeAlloc &	alloc,
		int	height,
		U &&	data,
		bool	isHead = `false`
	)

inlinestatic

Definition at line 62 of file ConcurrentSkipList-inl.h.

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

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

                                                                       {
     DCHECK(height >= 1 && height < 64) << height;
 
     size_t size =
         sizeof(SkipListNode) + height * sizeof(std::atomic<SkipListNode*>);
     auto storage = std::allocator_traits<NodeAlloc>::allocate(alloc, size);
     // do placement new
     return new (storage)
         SkipListNode(uint8_t(height), std::forward<U>(data), isHead);
   }

template<typename T >

value_type& folly::detail::SkipListNode< T >::data ( )

inline

Definition at line 115 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::data_.

Referenced by folly::detail::SkipListNode< T >::create(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::greater(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::last(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::less().

                      {
     return data_;
   }

template<typename T >

const value_type& folly::detail::SkipListNode< T >::data ( ) const

inline

Definition at line 118 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::data_.

                                  {
     return data_;
   }

template<typename T >

template<typename NodeAlloc >

static void folly::detail::SkipListNode< T >::destroy	(	NodeAlloc &	alloc,
		SkipListNode< T > *	node
	)

inlinestatic

Definition at line 74 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_, folly::size(), folly::detail::SkipListNode< T >::SkipListNode(), and folly::detail::SkipListNode< T >::~SkipListNode().

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

                                                             {
     size_t size = sizeof(SkipListNode) +
         node->height_ * sizeof(std::atomic<SkipListNode*>);
     node->~SkipListNode();
     std::allocator_traits<NodeAlloc>::deallocate(alloc, node, size);
   }

template<typename T >

bool folly::detail::SkipListNode< T >::fullyLinked ( ) const

inline

Definition at line 132 of file ConcurrentSkipList-inl.h.

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

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

                            {
     return getFlags() & FULLY_LINKED;
   }

template<typename T >

uint16_t folly::detail::SkipListNode< T >::getFlags ( ) const

inlineprivate

Definition at line 174 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::flags_.

Referenced by folly::detail::SkipListNode< T >::copyHead(), folly::detail::SkipListNode< T >::fullyLinked(), folly::detail::SkipListNode< T >::isHeadNode(), folly::detail::SkipListNode< T >::markedForRemoval(), folly::detail::SkipListNode< T >::setFullyLinked(), folly::detail::SkipListNode< T >::setIsHeadNode(), and folly::detail::SkipListNode< T >::setMarkedForRemoval().

                             {
     return flags_.load(std::memory_order_consume);
   }

template<typename T >

int folly::detail::SkipListNode< T >::height ( ) const

inline

Definition at line 124 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_.

Referenced by folly::detail::SkipListNode< T >::create(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight(), folly::detail::SkipListRandomHeight::getSizeLimit(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::growHeight(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::init(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                      {
     return height_;
   }

template<typename T >

bool folly::detail::SkipListNode< T >::isHeadNode ( ) const

inline

Definition at line 138 of file ConcurrentSkipList-inl.h.

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

                           {
     return getFlags() & IS_HEAD_NODE;
   }

template<typename T >

bool folly::detail::SkipListNode< T >::markedForRemoval ( ) const

inline

Definition at line 135 of file ConcurrentSkipList-inl.h.

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

Referenced by folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lockNodesForChange(), folly::detail::SkipListNode< T >::next(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::okToDelete(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                                 {
     return getFlags() & MARKED_FOR_REMOVAL;
   }

template<typename T >

int folly::detail::SkipListNode< T >::maxLayer ( ) const

inline

Definition at line 121 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_.

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

                        {
     return height_ - 1;
   }

template<typename T >

SkipListNode* folly::detail::SkipListNode< T >::next ( )

inline

Definition at line 102 of file ConcurrentSkipList-inl.h.

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

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

                        {
     SkipListNode* node;
     for (node = skip(0); (node != nullptr && node->markedForRemoval());
          node = node->skip(0)) {
     }
     return node;
   }

template<typename T >

void folly::detail::SkipListNode< T >::setFlags ( uint16_t flags )

inlineprivate

Definition at line 177 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::flags_.

Referenced by folly::detail::SkipListNode< T >::copyHead(), folly::detail::SkipListNode< T >::setFullyLinked(), folly::detail::SkipListNode< T >::setIsHeadNode(), folly::detail::SkipListNode< T >::setMarkedForRemoval(), and folly::detail::SkipListNode< T >::SkipListNode().

                                 {
     flags_.store(flags, std::memory_order_release);
   }

template<typename T >

void folly::detail::SkipListNode< T >::setFullyLinked ( )

inline

Definition at line 145 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::FULLY_LINKED, folly::detail::SkipListNode< T >::getFlags(), folly::detail::SkipListNode< T >::setFlags(), and uint16_t.

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

                         {
     setFlags(uint16_t(getFlags() | FULLY_LINKED));
   }

template<typename T >

void folly::detail::SkipListNode< T >::setIsHeadNode ( )

inline

Definition at line 142 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::getFlags(), folly::detail::SkipListNode< T >::IS_HEAD_NODE, folly::detail::SkipListNode< T >::setFlags(), and uint16_t.

Referenced by folly::detail::SkipListNode< T >::SkipListNode().

                        {
     setFlags(uint16_t(getFlags() | IS_HEAD_NODE));
   }

template<typename T >

void folly::detail::SkipListNode< T >::setMarkedForRemoval ( )

inline

Definition at line 148 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::getFlags(), folly::detail::SkipListNode< T >::MARKED_FOR_REMOVAL, folly::detail::SkipListNode< T >::setFlags(), and uint16_t.

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

                              {
     setFlags(uint16_t(getFlags() | MARKED_FOR_REMOVAL));
   }

template<typename T >

void folly::detail::SkipListNode< T >::setSkip	(	uint8_t	h,
		SkipListNode< T > *	next
	)

inline

Definition at line 110 of file ConcurrentSkipList-inl.h.

References h, folly::detail::SkipListNode< T >::height_, and folly::detail::SkipListNode< T >::skip_.

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

                                               {
     DCHECK_LT(h, height_);
     skip_[h].store(next, std::memory_order_release);
   }

template<typename T >

SkipListNode* folly::detail::SkipListNode< T >::skip ( int layer ) const

inline

Definition at line 96 of file ConcurrentSkipList-inl.h.

References folly::detail::SkipListNode< T >::height_, and folly::detail::SkipListNode< T >::skip_.

Referenced by folly::detail::SkipListNode< T >::copyHead(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findInsertionPoint(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeDownRight(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::findNodeRightDown(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::init(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::last(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::lockNodesForChange(), folly::detail::SkipListNode< T >::next(), and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove().

                                              {
     DCHECK_LT(layer, height_);
     return skip_[layer].load(std::memory_order_consume);
   }

Member Data Documentation

template<typename T >

value_type folly::detail::SkipListNode< T >::data_

private

Definition at line 189 of file ConcurrentSkipList-inl.h.

Referenced by folly::detail::SkipListNode< T >::data().

template<typename T >

std::atomic<uint16_t> folly::detail::SkipListNode< T >::flags_

private

Definition at line 185 of file ConcurrentSkipList-inl.h.

Referenced by folly::detail::SkipListNode< T >::getFlags(), and folly::detail::SkipListNode< T >::setFlags().

template<typename T >

const uint8_t folly::detail::SkipListNode< T >::height_

private

Definition at line 186 of file ConcurrentSkipList-inl.h.

Referenced by folly::detail::SkipListNode< T >::copyHead(), folly::detail::SkipListNode< T >::destroy(), folly::detail::SkipListNode< T >::height(), folly::detail::SkipListNode< T >::maxLayer(), folly::detail::SkipListNode< T >::setSkip(), folly::detail::SkipListNode< T >::skip(), folly::detail::SkipListNode< T >::SkipListNode(), and folly::detail::SkipListNode< T >::~SkipListNode().

template<typename T >

std::atomic<SkipListNode*> folly::detail::SkipListNode< T >::skip_[0]

private

Definition at line 191 of file ConcurrentSkipList-inl.h.

Referenced by folly::detail::SkipListNode< T >::setSkip(), folly::detail::SkipListNode< T >::skip(), folly::detail::SkipListNode< T >::SkipListNode(), and folly::detail::SkipListNode< T >::~SkipListNode().

template<typename T >

MicroSpinLock folly::detail::SkipListNode< T >::spinLock_

private

Definition at line 187 of file ConcurrentSkipList-inl.h.

Referenced by folly::detail::SkipListNode< T >::acquireGuard(), and folly::detail::SkipListNode< T >::SkipListNode().

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

proxygen/folly/folly/ConcurrentSkipList-inl.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename T> class folly::detail::SkipListNode< T >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class folly::detail::SkipListNode< T >