1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Thread safety 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// ------------- 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Writes require external synchronization, most likely a mutex. 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Reads require a guarantee that the SkipList will not be destroyed 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// while the read is in progress. Apart from that, reads progress 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// without any internal locking or synchronization. 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Invariants: 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// (1) Allocated nodes are never deleted until the SkipList is 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// destroyed. This is trivially guaranteed by the code since we 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// never delete any skip list nodes. 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// (2) The contents of a Node except for the next/prev pointers are 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// immutable after the Node has been linked into the SkipList. 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Only Insert() modifies the list, and it is careful to initialize 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// a node and use release-stores to publish the nodes in one or 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// more lists. 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// ... prev vs. next pointer ordering ... 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <assert.h> 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <stdlib.h> 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "port/port.h" 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/arena.h" 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/random.h" 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Arena; 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass SkipList { 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org struct Node; 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Create a new SkipList object that will use "cmp" for comparing keys, 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // and will allocate memory using "*arena". Objects allocated in the arena 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // must remain allocated for the lifetime of the skiplist object. 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit SkipList(Comparator cmp, Arena* arena); 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Insert key into the list. 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: nothing that compares equal to key is currently in the list. 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Insert(const Key& key); 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Returns true iff an entry that compares equal to key is in the list. 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool Contains(const Key& key) const; 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Iteration over the contents of a skip list 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org class Iterator { 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Initialize an iterator over the specified list. 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // The returned iterator is not valid. 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit Iterator(const SkipList* list); 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Returns true iff the iterator is positioned at a valid node. 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool Valid() const; 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Returns the key at the current position. 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: Valid() 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Key& key() const; 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Advances to the next position. 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: Valid() 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Next(); 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Advances to the previous position. 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: Valid() 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Prev(); 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Advance to the first entry with a key >= target 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Seek(const Key& target); 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Position at the first entry in list. 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Final state of iterator is Valid() iff list is not empty. 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void SeekToFirst(); 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Position at the last entry in list. 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Final state of iterator is Valid() iff list is not empty. 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void SeekToLast(); 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const SkipList* list_; 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* node_; 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Intentionally copyable 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org }; 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org enum { kMaxHeight = 12 }; 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Immutable after construction 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Comparator const compare_; 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Arena* const arena_; // Arena used for allocations of nodes 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* const head_; 102179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Modified only by Insert(). Read racily by readers, but stale 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // values are ok. 105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org port::AtomicPointer max_height_; // Height of the entire list 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org inline int GetMaxHeight() const { 108bf10812927b9a05a7b671eb32504eaa5972725d7sanjay@google.com return static_cast<int>( 109bf10812927b9a05a7b671eb32504eaa5972725d7sanjay@google.com reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load())); 110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Read/written only by Insert(). 113179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Random rnd_; 114179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 115179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* NewNode(const Key& key, int height); 116179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int RandomHeight(); 117179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); } 118179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 119179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return true if key is greater than the data stored in "n" 120179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool KeyIsAfterNode(const Key& key, Node* n) const; 121179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 122179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return the earliest node that comes at or after key. 123179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return NULL if there is no such node. 124179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 125179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // If prev is non-NULL, fills prev[level] with pointer to previous 126179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // node at "level" for every level in [0..max_height_-1]. 127179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* FindGreaterOrEqual(const Key& key, Node** prev) const; 128179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 129179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return the latest node with a key < key. 130179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return head_ if there is no such node. 131179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* FindLessThan(const Key& key) const; 132179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return the last node in the list. 134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return head_ if list is empty. 135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* FindLast() const; 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No copying allowed 138179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org SkipList(const SkipList&); 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void operator=(const SkipList&); 140179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Implementation details follow 143179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstruct SkipList<Key,Comparator>::Node { 145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org explicit Node(const Key& k) : key(k) { } 146179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 147179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Key const key; 148179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 149179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Accessors/mutators for links. Wrapped in methods so we can 150179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // add the appropriate barriers as necessary. 151179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* Next(int n) { 152179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(n >= 0); 153179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Use an 'acquire load' so that we observe a fully initialized 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // version of the returned Node. 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return reinterpret_cast<Node*>(next_[n].Acquire_Load()); 156179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 157179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void SetNext(int n, Node* x) { 158179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(n >= 0); 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Use a 'release store' so that anybody who reads through this 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // pointer observes a fully initialized version of the inserted node. 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org next_[n].Release_Store(x); 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No-barrier variants that can be safely used in a few locations. 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* NoBarrier_Next(int n) { 166179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(n >= 0); 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return reinterpret_cast<Node*>(next_[n].NoBarrier_Load()); 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 169179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void NoBarrier_SetNext(int n, Node* x) { 170179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(n >= 0); 171179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org next_[n].NoBarrier_Store(x); 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Array of length equal to the node height. next_[0] is lowest level link. 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org port::AtomicPointer next_[1]; 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtypename SkipList<Key,Comparator>::Node* 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgSkipList<Key,Comparator>::NewNode(const Key& key, int height) { 182179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char* mem = arena_->AllocateAligned( 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1)); 184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return new (mem) Node(key); 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) { 189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org list_ = list; 190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = NULL; 191179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline bool SkipList<Key,Comparator>::Iterator::Valid() const { 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return node_ != NULL; 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 198179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 199179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline const Key& SkipList<Key,Comparator>::Iterator::key() const { 200179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 201179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return node_->key; 202179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 203179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 204179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 205179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline void SkipList<Key,Comparator>::Iterator::Next() { 206179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 207179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = node_->Next(0); 208179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 209179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 211179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline void SkipList<Key,Comparator>::Iterator::Prev() { 212179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Instead of using explicit "prev" links, we just search for the 213179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // last node that falls before key. 214179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 215179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = list_->FindLessThan(node_->key); 216179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (node_ == list_->head_) { 217179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = NULL; 218179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 219179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 220179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 221179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 222179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) { 223179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = list_->FindGreaterOrEqual(target, NULL); 224179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 225179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 226179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 227179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline void SkipList<Key,Comparator>::Iterator::SeekToFirst() { 228179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = list_->head_->Next(0); 229179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 230179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 231179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 232179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orginline void SkipList<Key,Comparator>::Iterator::SeekToLast() { 233179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = list_->FindLast(); 234179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (node_ == list_->head_) { 235179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org node_ = NULL; 236179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 237179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 238179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 239179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 240179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint SkipList<Key,Comparator>::RandomHeight() { 241179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Increase height with probability 1 in kBranching 242179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org static const unsigned int kBranching = 4; 243179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int height = 1; 244179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) { 245179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org height++; 246179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 247179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(height > 0); 248179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(height <= kMaxHeight); 249179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return height; 250179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 251179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 252179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 253179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgbool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const { 254179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // NULL n is considered infinite 255179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return (n != NULL) && (compare_(n->key, key) < 0); 256179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 257179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 258179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 259179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtypename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev) 260179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const { 261179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* x = head_; 262179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int level = GetMaxHeight() - 1; 263179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (true) { 264179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* next = x->Next(level); 265179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (KeyIsAfterNode(key, next)) { 266179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Keep searching in this list 267179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org x = next; 268179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 269179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (prev != NULL) prev[level] = x; 270179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level == 0) { 271179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return next; 272179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 273179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Switch to next list 274179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level--; 275179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 276179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 277179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 278179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 279179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 280179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 281179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtypename SkipList<Key,Comparator>::Node* 282179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgSkipList<Key,Comparator>::FindLessThan(const Key& key) const { 283179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* x = head_; 284179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int level = GetMaxHeight() - 1; 285179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (true) { 286179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(x == head_ || compare_(x->key, key) < 0); 287179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* next = x->Next(level); 288179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (next == NULL || compare_(next->key, key) >= 0) { 289179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level == 0) { 290179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return x; 291179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 292179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Switch to next list 293179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level--; 294179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 295179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 296179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org x = next; 297179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 298179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 299179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 300179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 301179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 302179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtypename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast() 303179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const { 304179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* x = head_; 305179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int level = GetMaxHeight() - 1; 306179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (true) { 307179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* next = x->Next(level); 308179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (next == NULL) { 309179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level == 0) { 310179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return x; 311179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 312179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Switch to next list 313179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level--; 314179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 315179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 316179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org x = next; 317179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 318179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 319179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 320179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 321179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 322179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgSkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena) 323179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : compare_(cmp), 324179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org arena_(arena), 325179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org head_(NewNode(0 /* any key will do */, kMaxHeight)), 326179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org max_height_(reinterpret_cast<void*>(1)), 327179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rnd_(0xdeadbeef) { 328179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < kMaxHeight; i++) { 329179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org head_->SetNext(i, NULL); 330179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 331179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 332179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 333179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 334179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid SkipList<Key,Comparator>::Insert(const Key& key) { 335179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual() 336179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // here since Insert() is externally synchronized. 337179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* prev[kMaxHeight]; 338179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* x = FindGreaterOrEqual(key, prev); 339179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 340179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Our data structure does not allow duplicate insertion 341179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(x == NULL || !Equal(key, x->key)); 342179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 343179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int height = RandomHeight(); 344179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (height > GetMaxHeight()) { 345179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = GetMaxHeight(); i < height; i++) { 346179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org prev[i] = head_; 347179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 348179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org //fprintf(stderr, "Change height from %d to %d\n", max_height_, height); 349179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 350179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // It is ok to mutate max_height_ without any synchronization 351179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // with concurrent readers. A concurrent reader that observes 352179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // the new value of max_height_ will see either the old value of 353179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // new level pointers from head_ (NULL), or a new value set in 354179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // the loop below. In the former case the reader will 355179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // immediately drop to the next level since NULL sorts after all 356179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // keys. In the latter case the reader will use the new node. 357179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org max_height_.NoBarrier_Store(reinterpret_cast<void*>(height)); 358179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 359179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 360179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org x = NewNode(key, height); 361179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < height; i++) { 362179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // NoBarrier_SetNext() suffices since we will add a barrier when 363179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // we publish a pointer to "x" in prev[i]. 364179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); 365179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org prev[i]->SetNext(i, x); 366179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 367179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 368179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 369179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgtemplate<typename Key, class Comparator> 370179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgbool SkipList<Key,Comparator>::Contains(const Key& key) const { 371179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Node* x = FindGreaterOrEqual(key, NULL); 372179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (x != NULL && Equal(key, x->key)) { 373179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return true; 374179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 375179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return false; 376179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 377179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 378179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 37945b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 380