folly::detail::SkipListRandomHeight Class Reference

#include <ConcurrentSkipList-inl.h>

Public Member Functions
int	getHeight (int maxHeight) const
size_t	getSizeLimit (int height) const

Static Public Member Functions
static SkipListRandomHeight *	instance ()

Private Types
enum	{ kMaxHeight = 64 }

Private Member Functions
	SkipListRandomHeight ()
void	initLookupTable ()

Static Private Member Functions
static double	randomProb ()

Private Attributes
double	lookupTable_ [kMaxHeight]
size_t	sizeLimitTable_ [kMaxHeight]

Detailed Description

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

Member Enumeration Documentation

anonymous enum

private

Enumerator
kMaxHeight

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

{ kMaxHeight = 64 };

Constructor & Destructor Documentation

folly::detail::SkipListRandomHeight::SkipListRandomHeight ( )

inlineprivate

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

                         {
    initLookupTable();
  }

Member Function Documentation

int folly::detail::SkipListRandomHeight::getHeight ( int  maxHeight ) const

inline

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

References i.

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

                                     {
    DCHECK_LE(maxHeight, kMaxHeight) << "max height too big!";
    double p = randomProb();
    for (int i = 0; i < maxHeight; ++i) {
      if (p < lookupTable_[i]) {
        return i + 1;
      }
    }
    return maxHeight;
  }

size_t folly::detail::SkipListRandomHeight::getSizeLimit ( int  height ) const

inline

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

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

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

                                        {
    DCHECK_LT(height, kMaxHeight);
    return sizeLimitTable_[height];
  }

void folly::detail::SkipListRandomHeight::initLookupTable ( )

inlineprivate

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

References i, and max.

                         {
    // set skip prob = 1/E
    static const double kProbInv = exp(1);
    static const double kProb = 1.0 / kProbInv;
    static const size_t kMaxSizeLimit = std::numeric_limits<size_t>::max();

    double sizeLimit = 1;
    double p = lookupTable_[0] = (1 - kProb);
    sizeLimitTable_[0] = 1;
    for (int i = 1; i < kMaxHeight - 1; ++i) {
      p *= kProb;
      sizeLimit *= kProbInv;
      lookupTable_[i] = lookupTable_[i - 1] + p;
      sizeLimitTable_[i] = sizeLimit > kMaxSizeLimit
          ? kMaxSizeLimit
          : static_cast<size_t>(sizeLimit);
    }
    lookupTable_[kMaxHeight - 1] = 1;
    sizeLimitTable_[kMaxHeight - 1] = kMaxSizeLimit;
  }

static SkipListRandomHeight* folly::detail::SkipListRandomHeight::instance ( )

inlinestatic

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

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

                                          {
    static SkipListRandomHeight instance_;
    return &instance_;
  }

static double folly::detail::SkipListRandomHeight::randomProb ( )

inlinestaticprivate

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

                             {
    static ThreadLocal<boost::lagged_fibonacci2281> rng_;
    return (*rng_)();
  }

Member Data Documentation

double folly::detail::SkipListRandomHeight::lookupTable_[kMaxHeight]

private

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

size_t folly::detail::SkipListRandomHeight::sizeLimitTable_[kMaxHeight]

private

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

---

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

• proxygen/folly/folly/ConcurrentSkipList-inl.h