cds::intrusive::skip_list::random_level_generator< Type > Struct Template Reference

Option specifying random level generator. More...

#include <cds/intrusive/details/skip_list_base.h>

Detailed Description

template<typename Type>
struct cds::intrusive::skip_list::random_level_generator< Type >

Option specifying random level generator.

The random level generator is an important part of skip-list algorithm. The node height in the skip-list have a probabilistic distribution where half of the nodes that have level i pointers also have level i+1 pointers (i = 0..30). The random level generator should provide such distribution.

The Type functor interface is:

struct random_generator {
    static unsigned int const c_nUpperBound = 32;
    random_generator();
    unsigned int operator()();
};

where

• c_nUpperBound - constant that specifies the upper bound of random number generated. The generator produces a number from range [0 .. c_nUpperBound) (upper bound excluded). c_nUpperBound must be no more than 32.
• random_generator() - the constructor of generator object initialises the generator instance (its internal state).
• unsigned int operator()() - the main generating function. Returns random level from range [0 .. c_nUpperBound - 1]

Stateful generators are supported.

Available Type implementations:

• skip_list::xor_shift
• skip_list::turbo

---

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

• cds/intrusive/details/skip_list_base.h