leveldb::SkipList< Key, Comparator > Class Template Reference

#include <skiplist.h>

Collaboration diagram for leveldb::SkipList< Key, Comparator >:

Classes
class	Iterator
struct	Node

Public Member Functions
	SkipList (Comparator cmp, Arena *arena)
void	Insert (const Key &key)
bool	Contains (const Key &key) const

Private Types
enum	{ kMaxHeight = 12 }

Private Member Functions
int	GetMaxHeight () const
Node *	NewNode (const Key &key, int height)
int	RandomHeight ()
bool	Equal (const Key &a, const Key &b) const
bool	KeyIsAfterNode (const Key &key, Node *n) const
Node *	FindGreaterOrEqual (const Key &key, Node **prev) const
Node *	FindLessThan (const Key &key) const
Node *	FindLast () const
	SkipList (const SkipList &)
void	operator= (const SkipList &)

Private Attributes
Comparator const	compare_
Arena *const	arena_
Node *const	head_
port::AtomicPointer	max_height_
Random	rnd_

Detailed Description

template<typename Key, class Comparator>
class leveldb::SkipList< Key, Comparator >

Definition at line 38 of file skiplist.h.

Member Enumeration Documentation

template<typename Key, class Comparator>

anonymous enum

private

Enumerator
kMaxHeight

Definition at line 95 of file skiplist.h.

Constructor & Destructor Documentation

template<typename Key , class Comparator>

leveldb::SkipList< Key, Comparator >::SkipList ( Comparator  cmp, Arena *  arena  )

explicit

Definition at line 322 of file skiplist.h.

template<typename Key, class Comparator>

leveldb::SkipList< Key, Comparator >::SkipList ( const SkipList< Key, Comparator > &  )

private

Member Function Documentation

template<typename Key, class Comparator >

bool leveldb::SkipList< Key, Comparator >::Contains

(

const Key &

key

)

const

Definition at line 370 of file skiplist.h.

template<typename Key, class Comparator>

bool leveldb::SkipList< Key, Comparator >::Equal ( const Key &  a, const Key &  b  ) const

inlineprivate

Definition at line 117 of file skiplist.h.

template<typename Key, class Comparator >

SkipList< Key, Comparator >::Node * leveldb::SkipList< Key, Comparator >::FindGreaterOrEqual ( const Key &  key, Node **  prev  ) const

private

Definition at line 259 of file skiplist.h.

template<typename Key , class Comparator >

SkipList< Key, Comparator >::Node * leveldb::SkipList< Key, Comparator >::FindLast ( ) const

private

Definition at line 302 of file skiplist.h.

template<typename Key, class Comparator >

SkipList< Key, Comparator >::Node * leveldb::SkipList< Key, Comparator >::FindLessThan ( const Key &  key ) const

private

Definition at line 282 of file skiplist.h.

template<typename Key, class Comparator>

int leveldb::SkipList< Key, Comparator >::GetMaxHeight ( ) const

inlineprivate

Definition at line 107 of file skiplist.h.

template<typename Key, class Comparator >

void leveldb::SkipList< Key, Comparator >::Insert

(

const Key &

key

)

Definition at line 334 of file skiplist.h.

template<typename Key, class Comparator >

bool leveldb::SkipList< Key, Comparator >::KeyIsAfterNode ( const Key &  key, Node *  n  ) const

private

Definition at line 253 of file skiplist.h.

template<typename Key, class Comparator >

SkipList< Key, Comparator >::Node * leveldb::SkipList< Key, Comparator >::NewNode ( const Key &  key, int  height  )

private

Definition at line 181 of file skiplist.h.

template<typename Key, class Comparator>

void leveldb::SkipList< Key, Comparator >::operator= ( const SkipList< Key, Comparator > &  )

private

template<typename Key , class Comparator >

int leveldb::SkipList< Key, Comparator >::RandomHeight ( )

private

Definition at line 240 of file skiplist.h.

Member Data Documentation

template<typename Key, class Comparator>

Arena* const leveldb::SkipList< Key, Comparator >::arena_

private

Definition at line 99 of file skiplist.h.

template<typename Key, class Comparator>

Comparator const leveldb::SkipList< Key, Comparator >::compare_

private

Definition at line 98 of file skiplist.h.

template<typename Key, class Comparator>

Node* const leveldb::SkipList< Key, Comparator >::head_

private

Definition at line 101 of file skiplist.h.

template<typename Key, class Comparator>

port::AtomicPointer leveldb::SkipList< Key, Comparator >::max_height_

private

Definition at line 105 of file skiplist.h.

template<typename Key, class Comparator>

Random leveldb::SkipList< Key, Comparator >::rnd_

private

Definition at line 113 of file skiplist.h.

---

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

• src/leveldb/db/skiplist.h