proxygen
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor Class Reference

#include <ConcurrentSkipList.h>

Public Types

typedef T value_type
 
typedef T key_type
 
typedef Treference
 
typedef Tpointer
 
typedef const Tconst_reference
 
typedef const Tconst_pointer
 
typedef size_t size_type
 
typedef Comp key_compare
 
typedef Comp value_compare
 
typedef SkipListType::iterator iterator
 
typedef SkipListType::const_iterator const_iterator
 
typedef SkipListType::Skipper Skipper
 

Public Member Functions

 Accessor (std::shared_ptr< ConcurrentSkipList > skip_list)
 
 Accessor (ConcurrentSkipList *skip_list)
 
 Accessor (const Accessor &accessor)
 
Accessoroperator= (const Accessor &accessor)
 
 ~Accessor ()
 
bool empty () const
 
size_t size () const
 
size_type max_size () const
 
iterator find (const key_type &value)
 
const_iterator find (const key_type &value) const
 
size_type count (const key_type &data) const
 
iterator begin () const
 
iterator end () const
 
const_iterator cbegin () const
 
const_iterator cend () const
 
template<typename U , typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>
std::pair< iterator, bool > insert (U &&data)
 
size_t erase (const key_type &data)
 
iterator lower_bound (const key_type &data) const
 
size_t height () const
 
const key_typefirst () const
 
const key_typelast () const
 
bool pop_back ()
 
std::pair< key_type *, bool > addOrGetData (const key_type &data)
 
SkipListTypeskiplist () const
 
bool contains (const key_type &data) const
 
bool add (const key_type &data)
 
bool remove (const key_type &data)
 

Private Types

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

Private Attributes

SkipListTypesl_
 
std::shared_ptr< SkipListTypeslHolder_
 

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

Definition at line 545 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::const_iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::const_iterator

Definition at line 561 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
typedef const T* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::const_pointer

Definition at line 555 of file ConcurrentSkipList.h.

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
typedef const T& folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::const_reference

Definition at line 554 of file ConcurrentSkipList.h.

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

Definition at line 560 of file ConcurrentSkipList.h.

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

Definition at line 557 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 >::Accessor::key_type

Definition at line 551 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 >::Accessor::NodeType
private

Definition at line 546 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 >::Accessor::pointer

Definition at line 553 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 >::Accessor::reference

Definition at line 552 of file ConcurrentSkipList.h.

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

Definition at line 556 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 >::Accessor::SkipListType
private

Definition at line 547 of file ConcurrentSkipList.h.

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

Definition at line 562 of file ConcurrentSkipList.h.

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

Definition at line 558 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 >::Accessor::value_type

Definition at line 550 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 >::Accessor::Accessor ( std::shared_ptr< ConcurrentSkipList skip_list)
inlineexplicit

Definition at line 564 of file ConcurrentSkipList.h.

565  : slHolder_(std::move(skip_list)) {
566  sl_ = slHolder_.get();
567  DCHECK(sl_ != nullptr);
568  sl_->recycler_.addRef();
569  }
std::shared_ptr< SkipListType > slHolder_
constexpr detail::Map< Move > move
Definition: Base-inl.h:2567
detail::NodeRecycler< NodeType, NodeAlloc > recycler_
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::Accessor ( ConcurrentSkipList skip_list)
inlineexplicit

Definition at line 573 of file ConcurrentSkipList.h.

573  : sl_(skip_list) {
574  DCHECK(sl_ != nullptr);
575  sl_->recycler_.addRef();
576  }
detail::NodeRecycler< NodeType, NodeAlloc > recycler_
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::Accessor ( const Accessor accessor)
inline

Definition at line 578 of file ConcurrentSkipList.h.

579  : sl_(accessor.sl_), slHolder_(accessor.slHolder_) {
580  sl_->recycler_.addRef();
581  }
std::shared_ptr< SkipListType > slHolder_
detail::NodeRecycler< NodeType, NodeAlloc > recycler_
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::~Accessor ( )
inline

Definition at line 593 of file ConcurrentSkipList.h.

593  {
594  sl_->recycler_.releaseRef();
595  }
detail::NodeRecycler< NodeType, NodeAlloc > recycler_

Member Function Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::add ( const key_type data)
inline

Definition at line 698 of file ConcurrentSkipList.h.

698  {
699  return sl_->addOrGetData(data).second;
700  }
std::pair< NodeType *, size_t > addOrGetData(U &&data)
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
std::pair<key_type*, bool> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::addOrGetData ( const key_type data)
inline

Definition at line 682 of file ConcurrentSkipList.h.

682  {
683  auto ret = sl_->addOrGetData(data);
684  return std::make_pair(&ret.first->data(), ret.second);
685  }
std::pair< NodeType *, size_t > addOrGetData(U &&data)
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::begin ( ) const
inline

Definition at line 620 of file ConcurrentSkipList.h.

References folly::detail::SkipListNode< T >::next().

620  {
621  NodeType* head = sl_->head_.load(std::memory_order_consume);
622  return iterator(head->next());
623  }
detail::SkipListNode< T > NodeType
std::atomic< NodeType * > head_
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
const_iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::cbegin ( ) const
inline

Definition at line 627 of file ConcurrentSkipList.h.

References folly::test::begin().

627  {
628  return begin();
629  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
const_iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::cend ( ) const
inline

Definition at line 630 of file ConcurrentSkipList.h.

References folly::test::end(), type, and value.

630  {
631  return end();
632  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::contains ( const key_type data) const
inline

Definition at line 695 of file ConcurrentSkipList.h.

695  {
696  return sl_->find(data);
697  }
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
NodeType * find(const value_type &data)
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
size_type folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::count ( const key_type data) const
inline

Definition at line 616 of file ConcurrentSkipList.h.

References folly::gen::contains().

616  {
617  return contains(data);
618  }
bool contains(const key_type &data) const
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::empty ( ) const
inline

Definition at line 597 of file ConcurrentSkipList.h.

597  {
598  return sl_->size() == 0;
599  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::end ( ) const
inline

Definition at line 624 of file ConcurrentSkipList.h.

624  {
625  return iterator(nullptr);
626  }
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 >::Accessor::erase ( const key_type data)
inline

Definition at line 642 of file ConcurrentSkipList.h.

References folly::data().

642  {
643  return remove(data);
644  }
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::find ( const key_type value)
inline

Definition at line 610 of file ConcurrentSkipList.h.

610  {
611  return iterator(sl_->find(value));
612  }
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
NodeType * find(const value_type &data)
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
const_iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::find ( const key_type value) const
inline

Definition at line 613 of file ConcurrentSkipList.h.

613  {
614  return iterator(sl_->find(value));
615  }
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
NodeType * find(const value_type &data)
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
const key_type* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::first ( ) const
inline

Definition at line 665 of file ConcurrentSkipList.h.

665  {
666  return sl_->first();
667  }
const value_type * first() const
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 >::Accessor::height ( ) const
inline

Definition at line 650 of file ConcurrentSkipList.h.

650  {
651  return sl_->height();
652  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
template<typename U , typename = typename std::enable_if<std::is_convertible<U, T>::value>::type>
std::pair<iterator, bool> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::insert ( U &&  data)
inline

Definition at line 638 of file ConcurrentSkipList.h.

References folly::data().

638  {
639  auto ret = sl_->addOrGetData(std::forward<U>(data));
640  return std::make_pair(iterator(ret.first), ret.second);
641  }
std::pair< NodeType *, size_t > addOrGetData(U &&data)
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
const key_type* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::last ( ) const
inline

Definition at line 668 of file ConcurrentSkipList.h.

668  {
669  return sl_->last();
670  }
const value_type * last() const
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
iterator folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::lower_bound ( const key_type data) const
inline

Definition at line 646 of file ConcurrentSkipList.h.

646  {
647  return iterator(sl_->lower_bound(data));
648  }
NodeType * lower_bound(const value_type &data) const
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
size_type folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::max_size ( ) const
inline

Definition at line 603 of file ConcurrentSkipList.h.

References max.

603  {
605  }
LogLevel max
Definition: LogLevel.cpp:31
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
Accessor& folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::operator= ( const Accessor accessor)
inline

Definition at line 583 of file ConcurrentSkipList.h.

References folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::recycler_, folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::sl_, and folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::slHolder_.

583  {
584  if (this != &accessor) {
585  slHolder_ = accessor.slHolder_;
586  sl_->recycler_.releaseRef();
587  sl_ = accessor.sl_;
588  sl_->recycler_.addRef();
589  }
590  return *this;
591  }
std::shared_ptr< SkipListType > slHolder_
detail::NodeRecycler< NodeType, NodeAlloc > recycler_
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
bool folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::pop_back ( )
inline

Definition at line 677 of file ConcurrentSkipList.h.

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

677  {
678  auto last = sl_->last();
679  return last ? sl_->remove(*last) : false;
680  }
const value_type * last() const
bool remove(const value_type &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 >::Accessor::remove ( const key_type data)
inline

Definition at line 701 of file ConcurrentSkipList.h.

References folly::data().

701  {
702  return sl_->remove(data);
703  }
bool remove(const value_type &data)
constexpr auto data(C &c) -> decltype(c.data())
Definition: Access.h:71
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 >::Accessor::size ( ) const
inline

Definition at line 600 of file ConcurrentSkipList.h.

600  {
601  return sl_->size();
602  }
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
SkipListType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::skiplist ( ) const
inline

Definition at line 687 of file ConcurrentSkipList.h.

687  {
688  return sl_;
689  }

Member Data Documentation

template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
SkipListType* folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::sl_
private
template<typename T, typename Comp = std::less<T>, typename NodeAlloc = SysAllocator<void>, int MAX_HEIGHT = 24>
std::shared_ptr<SkipListType> folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::Accessor::slHolder_
private

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