proxygen
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper Class Reference

#include <ConcurrentSkipList.h>

Public Types

typedef T value_type
 
typedef T & reference
 
typedef T * pointer
 
typedef ptrdiff_t difference_type
 

Public Member Functions

 Skipper (const std::shared_ptr< SkipListType > &skipList)
 
 Skipper (const Accessor &accessor)
 
void init ()
 
Skipper & operator++ ()
 
bool good () const
 
int maxLayer () const
 
int curHeight () const
 
const value_type & data () const
 
value_type & operator* () const
 
value_type * operator-> ()
 
bool to (const value_type &data)
 

Private Types

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

Private Member Functions

NodeType * head () const
 

Private Attributes

Accessor accessor_
 
int headHeight_
 
NodeType * succs_ [MAX_HEIGHT]
 
NodeType * preds_ [MAX_HEIGHT]
 
uint8_t hints_ [MAX_HEIGHT]
 

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 >::Skipper

Definition at line 760 of file ConcurrentSkipList.h.

Member Typedef Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
typedef SkipListType::Accessor folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::Accessor
private

Definition at line 763 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
typedef ptrdiff_t folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::difference_type

Definition at line 769 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 >::Skipper::NodeType
private

Definition at line 761 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 >::Skipper::pointer

Definition at line 768 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 >::Skipper::reference

Definition at line 767 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 >::Skipper::SkipListType
private

Definition at line 762 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 >::Skipper::value_type

Definition at line 766 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 >::Skipper::Skipper ( const std::shared_ptr< SkipListType > &  skipList)
inline

Definition at line 771 of file ConcurrentSkipList.h.

References folly::init().

771  : accessor_(skipList) {
772  init();
773  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::Skipper ( const Accessor &  accessor)
inline

Definition at line 775 of file ConcurrentSkipList.h.

References folly::init().

775  : accessor_(accessor) {
776  init();
777  }

Member Function Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::curHeight ( ) const
inline

Definition at line 814 of file ConcurrentSkipList.h.

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

814  {
815  // need to cap the height to the cached head height, as the current node
816  // might be some newly inserted node and also during the time period the
817  // head height may have grown.
818  return succs_[0] ? std::min(headHeight_, succs_[0]->height()) : 0;
819  }
min
LogLevel min
Definition: LogLevel.cpp:30
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 >::Skipper::data ( ) const
inline

Definition at line 821 of file ConcurrentSkipList.h.

821  {
822  DCHECK(succs_[0] != nullptr);
823  return succs_[0]->data();
824  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::good ( ) const
inline

Definition at line 806 of file ConcurrentSkipList.h.

806  {
807  return succs_[0] != nullptr;
808  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
NodeType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::head ( ) const
inlineprivate

Definition at line 867 of file ConcurrentSkipList.h.

867  {
868  return accessor_.skiplist()->head_.load(std::memory_order_consume);
869  }
folly::ConcurrentSkipList::head_
std::atomic< NodeType * > head_
Definition: ConcurrentSkipList.h:540
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
void folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::init ( )
inline

Definition at line 779 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::height(), i, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::maxLayer(), folly::detail::SkipListNode< T >::skip(), and uint8_t.

779  {
780  // need to cache the head node
781  NodeType* head_node = head();
782  headHeight_ = head_node->height();
783  for (int i = 0; i < headHeight_; ++i) {
784  preds_[i] = head_node;
785  succs_[i] = head_node->skip(i);
786  }
787  int max_layer = maxLayer();
788  for (int i = 0; i < max_layer; ++i) {
789  hints_[i] = uint8_t(i + 1);
790  }
791  hints_[max_layer] = max_layer;
792  }
i
i
Definition: gtest_output_test_golden_lin.txt:83
folly::ConcurrentSkipList::Skipper::NodeType
detail::SkipListNode< T > NodeType
Definition: ConcurrentSkipList.h:761
folly::detail::SkipListNode::skip
SkipListNode * skip(int layer) const
Definition: ConcurrentSkipList-inl.h:96
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
int folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::maxLayer ( ) const
inline

Definition at line 810 of file ConcurrentSkipList.h.

810  {
811  return headHeight_ - 1;
812  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
value_type& folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::operator* ( ) const
inline

Definition at line 826 of file ConcurrentSkipList.h.

826  {
827  DCHECK(succs_[0] != nullptr);
828  return succs_[0]->data();
829  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
Skipper& folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::operator++ ( )
inline

Definition at line 795 of file ConcurrentSkipList.h.

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

795  {
796  preds_[0] = succs_[0];
797  succs_[0] = preds_[0]->skip(0);
798  int height = curHeight();
799  for (int i = 1; i < height && preds_[0] == succs_[i]; ++i) {
800  preds_[i] = succs_[i];
801  succs_[i] = preds_[i]->skip(i);
802  }
803  return *this;
804  }
i
i
Definition: gtest_output_test_golden_lin.txt:83
folly::detail::SkipListNode::skip
SkipListNode * skip(int layer) const
Definition: ConcurrentSkipList-inl.h:96
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
value_type* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::operator-> ( )
inline

Definition at line 831 of file ConcurrentSkipList.h.

831  {
832  DCHECK(succs_[0] != nullptr);
833  return &succs_[0]->data();
834  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::to ( const value_type &  data)
inline

Definition at line 842 of file ConcurrentSkipList.h.

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

842  {
843  int layer = curHeight() - 1;
844  if (layer < 0) {
845  return false; // reaches the end of the list
846  }
847 
848  int lyr = hints_[layer];
849  int max_layer = maxLayer();
850  while (SkipListType::greater(data, succs_[lyr]) && lyr < max_layer) {
851  ++lyr;
852  }
853  hints_[layer] = lyr; // update the hint
854 
855  int foundLayer = SkipListType::findInsertionPoint(
856  preds_[lyr], lyr, data, preds_, succs_);
857  if (foundLayer < 0) {
858  return false;
859  }
860 
861  DCHECK(succs_[0] != nullptr)
862  << "lyr=" << lyr << "; max_layer=" << max_layer;
863  return !succs_[0]->markedForRemoval();
864  }
folly::ConcurrentSkipList::findInsertionPoint
static int findInsertionPoint(NodeType *cur, int cur_layer, const value_type &data, NodeType *preds[], NodeType *succs[])
Definition: ConcurrentSkipList.h:222
folly::ConcurrentSkipList::Skipper::data
const value_type & data() const
Definition: ConcurrentSkipList.h:821
folly::ConcurrentSkipList::greater
static bool greater(const value_type &data, const NodeType *node)
Definition: ConcurrentSkipList.h:214

Member Data Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
Accessor folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::accessor_
private

Definition at line 871 of file ConcurrentSkipList.h.

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

Definition at line 872 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
uint8_t folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::hints_[MAX_HEIGHT]
private

Definition at line 874 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
NodeType * folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::preds_[MAX_HEIGHT]
private

Definition at line 873 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
NodeType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Skipper::succs_[MAX_HEIGHT]
private

Definition at line 873 of file ConcurrentSkipList.h.

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