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 41 of file skiplist.h.

Member Enumeration Documentation

anonymous enum

template<typename Key, class Comparator>

anonymous enum

private

Enumerator
kMaxHeight

Definition at line 98 of file skiplist.h.

{ kMaxHeight = 12 };

Constructor & Destructor Documentation

SkipList() [1/2]

template<typename Key , class Comparator>

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

explicit

Definition at line 325 of file skiplist.h.

    : compare_(cmp),
      arena_(arena),
      head_(NewNode(0 /* any key will do */, kMaxHeight)),
      max_height_(reinterpret_cast<void*>(1)),
      rnd_(0xdeadbeef) {
  for (int i = 0; i < kMaxHeight; i++) {
    head_->SetNext(i, NULL);
  }
}

Here is the caller graph for this function:

SkipList() [2/2]

template<typename Key, class Comparator>

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

private

Member Function Documentation

Contains()

template<typename Key, class Comparator >

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

(

const Key &

key

)

const

Definition at line 373 of file skiplist.h.

                                                            {
  Node* x = FindGreaterOrEqual(key, NULL);
  if (x != NULL && Equal(key, x->key)) {
    return true;
  } else {
    return false;
  }
}

Here is the caller graph for this function:

Equal()

template<typename Key, class Comparator>

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

inlineprivate

Definition at line 120 of file skiplist.h.

{ return (compare_(a, b) == 0); }

FindGreaterOrEqual()

template<typename Key, class Comparator >

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

private

Definition at line 262 of file skiplist.h.

          {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != NULL) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}

Here is the caller graph for this function:

FindLast()

template<typename Key , class Comparator >

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

private

Definition at line 305 of file skiplist.h.

          {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (next == NULL) {
      if (level == 0) {
        return x;
      } else {
        // Switch to next list
        level--;
      }
    } else {
      x = next;
    }
  }
}

Here is the caller graph for this function:

FindLessThan()

template<typename Key, class Comparator >

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

private

Definition at line 285 of file skiplist.h.

                                                           {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    assert(x == head_ || compare_(x->key, key) < 0);
    Node* next = x->Next(level);
    if (next == NULL || compare_(next->key, key) >= 0) {
      if (level == 0) {
        return x;
      } else {
        // Switch to next list
        level--;
      }
    } else {
      x = next;
    }
  }
}

Here is the caller graph for this function:

GetMaxHeight()

template<typename Key, class Comparator>

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

inlineprivate

Definition at line 110 of file skiplist.h.

                                  {
    return static_cast<int>(
        reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));
  }

Here is the caller graph for this function:

Insert()

template<typename Key, class Comparator >

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

(

const Key &

key

)

Definition at line 337 of file skiplist.h.

                                                    {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  assert(x == NULL || !Equal(key, x->key));

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);

    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (NULL), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since NULL sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
  }

  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

Here is the caller graph for this function:

KeyIsAfterNode()

template<typename Key, class Comparator >

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

private

Definition at line 256 of file skiplist.h.

                                                                           {
  // NULL n is considered infinite
  return (n != NULL) && (compare_(n->key, key) < 0);
}

Here is the caller graph for this function:

NewNode()

template<typename Key, class Comparator >

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

private

Definition at line 184 of file skiplist.h.

                                                            {
  char* mem = arena_->AllocateAligned(
      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
  return new (mem) Node(key);
}

operator=()

template<typename Key, class Comparator>

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

private

Here is the caller graph for this function:

RandomHeight()

template<typename Key , class Comparator >

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

private

Definition at line 243 of file skiplist.h.

                                           {
  // Increase height with probability 1 in kBranching
  static const unsigned int kBranching = 4;
  int height = 1;
  while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxHeight);
  return height;
}

Member Data Documentation

arena_

template<typename Key, class Comparator>

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

private

Definition at line 102 of file skiplist.h.

compare_

template<typename Key, class Comparator>

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

private

Definition at line 101 of file skiplist.h.

head_

template<typename Key, class Comparator>

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

private

Definition at line 104 of file skiplist.h.

max_height_

template<typename Key, class Comparator>

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

private

Definition at line 108 of file skiplist.h.

rnd_

template<typename Key, class Comparator>

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

private

Definition at line 116 of file skiplist.h.

---

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

• db/skiplist.h