chromium/third_party/leveldatabase/src/db/skiplist.h

// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#ifndef STORAGE_LEVELDB_DB_SKIPLIST_H_
#define STORAGE_LEVELDB_DB_SKIPLIST_H_

// Thread safety
// -------------
//
// Writes require external synchronization, most likely a mutex.
// Reads require a guarantee that the SkipList will not be destroyed
// while the read is in progress.  Apart from that, reads progress
// without any internal locking or synchronization.
//
// Invariants:
//
// (1) Allocated nodes are never deleted until the SkipList is
// destroyed.  This is trivially guaranteed by the code since we
// never delete any skip list nodes.
//
// (2) The contents of a Node except for the next/prev pointers are
// immutable after the Node has been linked into the SkipList.
// Only Insert() modifies the list, and it is careful to initialize
// a node and use release-stores to publish the nodes in one or
// more lists.
//
// ... prev vs. next pointer ordering ...

#include <atomic>
#include <cassert>
#include <cstdlib>

#include "util/arena.h"
#include "util/random.h"

namespace leveldb {

template <typename Key, class Comparator>
class SkipList { … };

// Implementation details follow
template <typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node { … };

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
    const Key& key, int height) { … }

template <typename Key, class Comparator>
inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) { … }

template <typename Key, class Comparator>
inline bool SkipList<Key, Comparator>::Iterator::Valid() const { … }

template <typename Key, class Comparator>
inline const Key& SkipList<Key, Comparator>::Iterator::key() const { … }

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Next() { … }

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Prev() { … }

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) { … }

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() { … }

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::SeekToLast() { … }

template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() { … }

template <typename Key, class Comparator>
bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const { … }

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
                                              Node** prev) const { … }

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindLessThan(const Key& key) const { … }

template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindLast()
    const { … }

template <typename Key, class Comparator>
SkipList<Key, Comparator>::SkipList(Comparator cmp, Arena* arena)
    : … { … }

template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) { … }

template <typename Key, class Comparator>
bool SkipList<Key, Comparator>::Contains(const Key& key) const { … }

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_DB_SKIPLIST_H_