/Users/deen/code/yugabyte-db/src/yb/rocksdb/db/skiplist.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | |
24 | | // Thread safety |
25 | | // ------------- |
26 | | // |
27 | | // Writes require external synchronization, most likely a mutex. |
28 | | // Reads require a guarantee that the SkipList will not be destroyed |
29 | | // while the read is in progress. Apart from that, reads progress |
30 | | // without any internal locking or synchronization. |
31 | | // |
32 | | // Invariants: |
33 | | // |
34 | | // (1) Allocated nodes are never deleted until the SkipList is |
35 | | // destroyed. This is trivially guaranteed by the code since we |
36 | | // never delete any skip list nodes. |
37 | | // |
38 | | // (2) The contents of a Node except for the next/prev pointers are |
39 | | // immutable after the Node has been linked into the SkipList. |
40 | | // Only Insert() modifies the list, and it is careful to initialize |
41 | | // a node and use release-stores to publish the nodes in one or |
42 | | // more lists. |
43 | | // |
44 | | // ... prev vs. next pointer ordering ... |
45 | | // |
46 | | |
47 | | #ifndef YB_ROCKSDB_DB_SKIPLIST_H |
48 | | #define YB_ROCKSDB_DB_SKIPLIST_H |
49 | | |
50 | | #pragma once |
51 | | |
52 | | #include <atomic> |
53 | | |
54 | | #include <glog/logging.h> |
55 | | |
56 | | #include "yb/rocksdb/util/allocator.h" |
57 | | #include "yb/rocksdb/util/random.h" |
58 | | |
59 | | namespace rocksdb { |
60 | | |
61 | | // Base skip list implementation shares common logic for SkipList and SingleWriterInlineSkipList. |
62 | | // Since concurrent writes are not allowed many operations could be simplified. |
63 | | // See InlineSkipList for an implementation that supports concurrent writes. |
64 | | template<class Key, class Comparator, class NodeType> |
65 | | class SkipListBase { |
66 | | private: |
67 | | typedef NodeType Node; |
68 | | |
69 | | public: |
70 | | // Create a new SkipList object that will use "cmp" for comparing keys, |
71 | | // and will allocate memory using "*allocator". Objects allocated in the |
72 | | // allocator must remain allocated for the lifetime of the skiplist object. |
73 | | explicit SkipListBase(Comparator cmp, Allocator* allocator, |
74 | | int32_t max_height = 12, int32_t branching_factor = 4); |
75 | | |
76 | | // No copying allowed |
77 | | SkipListBase(const SkipListBase&) = delete; |
78 | | void operator=(const SkipListBase&) = delete; |
79 | | |
80 | | // Returns true iff an entry that compares equal to key is in the list. |
81 | | bool Contains(Key key) const; |
82 | | |
83 | | bool Erase(Key key, Comparator cmp); |
84 | | |
85 | | // Return estimated number of entries smaller than `key`. |
86 | | uint64_t EstimateCount(Key key) const; |
87 | | |
88 | | // Iteration over the contents of a skip list |
89 | | class Iterator { |
90 | | public: |
91 | | // Initialize an iterator over the specified list. |
92 | | // The returned iterator is not valid. |
93 | | explicit Iterator(const SkipListBase* list); |
94 | | |
95 | | // Change the underlying skiplist used for this iterator |
96 | | // This enables us not changing the iterator without deallocating |
97 | | // an old one and then allocating a new one |
98 | | void SetList(const SkipListBase* list); |
99 | | |
100 | | // Returns true iff the iterator is positioned at a valid node. |
101 | | bool Valid() const; |
102 | | |
103 | | // Returns the key at the current position. |
104 | | // REQUIRES: Valid() |
105 | | Key key() const; |
106 | | |
107 | | // Advances to the next position. |
108 | | // REQUIRES: Valid() |
109 | | void Next(); |
110 | | |
111 | | // Advances to the previous position. |
112 | | // REQUIRES: Valid() |
113 | | void Prev(); |
114 | | |
115 | | // Advance to the first entry with a key >= target |
116 | | void Seek(Key target); |
117 | | |
118 | | // Position at the first entry in list. |
119 | | // Final state of iterator is Valid() iff list is not empty. |
120 | | void SeekToFirst(); |
121 | | |
122 | | // Position at the last entry in list. |
123 | | // Final state of iterator is Valid() iff list is not empty. |
124 | | void SeekToLast(); |
125 | | |
126 | | private: |
127 | | const SkipListBase* list_; |
128 | | Node* node_; |
129 | | // Intentionally copyable |
130 | | }; |
131 | | |
132 | | protected: |
133 | | // We do insert in 3 phases: |
134 | | // 1) Prepare key insertion |
135 | | // 2) Allocate and initialize node |
136 | | // 3) Complete newly allocated node |
137 | | // (1) and (3) are generic phases, while (2) is implementation specific. |
138 | | // REQUIRES: nothing that compares equal to key is currently in the list. |
139 | | void PrepareInsert(Key key); |
140 | | void CompleteInsert(NodeType* node, int height); |
141 | | |
142 | | int RandomHeight(); |
143 | | |
144 | | Allocator* const allocator_; // Allocator used for allocations of nodes |
145 | | |
146 | | private: |
147 | | const uint16_t kMaxHeight_; |
148 | | const uint16_t kBranching_; |
149 | | const uint32_t kScaledInverseBranching_; |
150 | | |
151 | | // Immutable after construction |
152 | | Comparator const compare_; |
153 | | |
154 | | Node* const head_; |
155 | | |
156 | | // Modified only by Insert(). Read racily by readers, but stale |
157 | | // values are ok. |
158 | | std::atomic<int> max_height_; // Height of the entire list |
159 | | |
160 | | // Used for optimizing sequential insert patterns. Tricky. prev_[i] for |
161 | | // i up to max_height_ is the predecessor of prev_[0] and prev_height_ |
162 | | // is the height of prev_[0]. prev_[0] can only be equal to head before |
163 | | // insertion, in which case max_height_ and prev_height_ are 1. |
164 | | Node** prev_; |
165 | | int32_t prev_height_; |
166 | | |
167 | | // Whether prev_ is valid, prev_ is invalidated during erase. |
168 | | bool prev_valid_ = true; |
169 | | |
170 | 280M | int GetMaxHeight() const { |
171 | 280M | return max_height_.load(std::memory_order_relaxed); |
172 | 280M | } Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE12GetMaxHeightEv _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE12GetMaxHeightEv Line | Count | Source | 170 | 11.4M | int GetMaxHeight() const { | 171 | 11.4M | return max_height_.load(std::memory_order_relaxed); | 172 | 11.4M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE12GetMaxHeightEv Line | Count | Source | 170 | 2.85M | int GetMaxHeight() const { | 171 | 2.85M | return max_height_.load(std::memory_order_relaxed); | 172 | 2.85M | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE12GetMaxHeightEv Line | Count | Source | 170 | 255M | int GetMaxHeight() const { | 171 | 255M | return max_height_.load(std::memory_order_relaxed); | 172 | 255M | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE12GetMaxHeightEv Line | Count | Source | 170 | 10.0M | int GetMaxHeight() const { | 171 | 10.0M | return max_height_.load(std::memory_order_relaxed); | 172 | 10.0M | } |
|
173 | | |
174 | 79.8M | bool Equal(Key a, Key b) const { return (compare_(a, b) == 0); } Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE5EqualES2_S2_ _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE5EqualES2_S2_ Line | Count | Source | 174 | 3.81M | bool Equal(Key a, Key b) const { return (compare_(a, b) == 0); } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE5EqualES4_S4_ Line | Count | Source | 174 | 1.04M | bool Equal(Key a, Key b) const { return (compare_(a, b) == 0); } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE5EqualES2_S2_ Line | Count | Source | 174 | 74.9M | bool Equal(Key a, Key b) const { return (compare_(a, b) == 0); } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE5EqualES4_S4_ Line | Count | Source | 174 | 281 | bool Equal(Key a, Key b) const { return (compare_(a, b) == 0); } |
|
175 | | |
176 | | // Return true if key is greater than the data stored in "n" |
177 | | bool KeyIsAfterNode(Key key, Node* n) const; |
178 | | |
179 | | // Returns the earliest node with a key >= key. |
180 | | // Return nullptr if there is no such node. |
181 | | Node* FindGreaterOrEqual(Key key) const; |
182 | | |
183 | | // Return the latest node with a key < key. |
184 | | // Return head_ if there is no such node. |
185 | | // Fills prev[level] with pointer to previous node at "level" for every |
186 | | // level in [0..max_height_-1], if prev is non-null. |
187 | | Node* FindLessThan(Key key, Node** prev = nullptr) const; |
188 | | |
189 | | // Return the last node in the list. |
190 | | // Return head_ if list is empty. |
191 | | Node* FindLast() const; |
192 | | }; |
193 | | |
194 | | // Implementation details follow |
195 | | template<typename Key> |
196 | | struct SkipListNode { |
197 | 14.2M | explicit SkipListNode(const Key& k) : key(k) { } _ZN7rocksdb12SkipListNodeIyEC2ERKy Line | Count | Source | 197 | 5.08M | explicit SkipListNode(const Key& k) : key(k) { } |
_ZN7rocksdb12SkipListNodeIPKcEC2ERKS2_ Line | Count | Source | 197 | 1.09M | explicit SkipListNode(const Key& k) : key(k) { } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEEC2ERKS2_ Line | Count | Source | 197 | 8.10M | explicit SkipListNode(const Key& k) : key(k) { } |
|
198 | | |
199 | | Key const key; |
200 | | |
201 | | // Accessors/mutators for links. Wrapped in methods so we can |
202 | | // add the appropriate barriers as necessary. |
203 | 170M | SkipListNode* Next(int n) { |
204 | 170M | DCHECK_GE(n, 0); |
205 | | // Use an 'acquire load' so that we observe a fully initialized |
206 | | // version of the returned Node. |
207 | 170M | return next_[n].load(std::memory_order_acquire); |
208 | 170M | } _ZN7rocksdb12SkipListNodeIyE4NextEi Line | Count | Source | 203 | 96.2M | SkipListNode* Next(int n) { | 204 | 96.2M | DCHECK_GE(n, 0); | 205 | | // Use an 'acquire load' so that we observe a fully initialized | 206 | | // version of the returned Node. | 207 | 96.2M | return next_[n].load(std::memory_order_acquire); | 208 | 96.2M | } |
_ZN7rocksdb12SkipListNodeIPKcE4NextEi Line | Count | Source | 203 | 54.6M | SkipListNode* Next(int n) { | 204 | 54.6M | DCHECK_GE(n, 0); | 205 | | // Use an 'acquire load' so that we observe a fully initialized | 206 | | // version of the returned Node. | 207 | 54.6M | return next_[n].load(std::memory_order_acquire); | 208 | 54.6M | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE4NextEi Line | Count | Source | 203 | 19.7M | SkipListNode* Next(int n) { | 204 | 19.7M | DCHECK_GE(n, 0); | 205 | | // Use an 'acquire load' so that we observe a fully initialized | 206 | | // version of the returned Node. | 207 | 19.7M | return next_[n].load(std::memory_order_acquire); | 208 | 19.7M | } |
|
209 | | |
210 | 27.2M | void SetNext(int n, SkipListNode* x) { |
211 | 27.2M | DCHECK_GE(n, 0); |
212 | | // Use a 'release store' so that anybody who reads through this |
213 | | // pointer observes a fully initialized version of the inserted node. |
214 | 27.2M | next_[n].store(x, std::memory_order_release); |
215 | 27.2M | } _ZN7rocksdb12SkipListNodeIyE7SetNextEiPS1_ Line | Count | Source | 210 | 6.92M | void SetNext(int n, SkipListNode* x) { | 211 | 6.92M | DCHECK_GE(n, 0); | 212 | | // Use a 'release store' so that anybody who reads through this | 213 | | // pointer observes a fully initialized version of the inserted node. | 214 | 6.92M | next_[n].store(x, std::memory_order_release); | 215 | 6.92M | } |
_ZN7rocksdb12SkipListNodeIPKcE7SetNextEiPS3_ Line | Count | Source | 210 | 1.64M | void SetNext(int n, SkipListNode* x) { | 211 | 1.64M | DCHECK_GE(n, 0); | 212 | | // Use a 'release store' so that anybody who reads through this | 213 | | // pointer observes a fully initialized version of the inserted node. | 214 | 1.64M | next_[n].store(x, std::memory_order_release); | 215 | 1.64M | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE7SetNextEiPS3_ Line | Count | Source | 210 | 18.6M | void SetNext(int n, SkipListNode* x) { | 211 | 18.6M | DCHECK_GE(n, 0); | 212 | | // Use a 'release store' so that anybody who reads through this | 213 | | // pointer observes a fully initialized version of the inserted node. | 214 | 18.6M | next_[n].store(x, std::memory_order_release); | 215 | 18.6M | } |
|
216 | | |
217 | | // No-barrier variants that can be safely used in a few locations. |
218 | 31.6M | SkipListNode* NoBarrier_Next(int n) { |
219 | 31.6M | DCHECK_GE(n, 0); |
220 | 31.6M | return next_[n].load(std::memory_order_relaxed); |
221 | 31.6M | } _ZN7rocksdb12SkipListNodeIyE14NoBarrier_NextEi Line | Count | Source | 218 | 12.1M | SkipListNode* NoBarrier_Next(int n) { | 219 | 12.1M | DCHECK_GE(n, 0); | 220 | 12.1M | return next_[n].load(std::memory_order_relaxed); | 221 | 12.1M | } |
_ZN7rocksdb12SkipListNodeIPKcE14NoBarrier_NextEi Line | Count | Source | 218 | 2.40M | SkipListNode* NoBarrier_Next(int n) { | 219 | 2.40M | DCHECK_GE(n, 0); | 220 | 2.40M | return next_[n].load(std::memory_order_relaxed); | 221 | 2.40M | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE14NoBarrier_NextEi Line | Count | Source | 218 | 17.1M | SkipListNode* NoBarrier_Next(int n) { | 219 | 17.1M | DCHECK_GE(n, 0); | 220 | 17.1M | return next_[n].load(std::memory_order_relaxed); | 221 | 17.1M | } |
|
222 | | |
223 | 17.9M | void NoBarrier_SetNext(int n, SkipListNode* x) { |
224 | 17.9M | DCHECK_GE(n, 0); |
225 | 17.9M | next_[n].store(x, std::memory_order_relaxed); |
226 | 17.9M | } _ZN7rocksdb12SkipListNodeIyE17NoBarrier_SetNextEiPS1_ Line | Count | Source | 223 | 6.77M | void NoBarrier_SetNext(int n, SkipListNode* x) { | 224 | 6.77M | DCHECK_GE(n, 0); | 225 | 6.77M | next_[n].store(x, std::memory_order_relaxed); | 226 | 6.77M | } |
_ZN7rocksdb12SkipListNodeIPKcE17NoBarrier_SetNextEiPS3_ Line | Count | Source | 223 | 1.37M | void NoBarrier_SetNext(int n, SkipListNode* x) { | 224 | 1.37M | DCHECK_GE(n, 0); | 225 | 1.37M | next_[n].store(x, std::memory_order_relaxed); | 226 | 1.37M | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE17NoBarrier_SetNextEiPS3_ Line | Count | Source | 223 | 9.80M | void NoBarrier_SetNext(int n, SkipListNode* x) { | 224 | 9.80M | DCHECK_GE(n, 0); | 225 | 9.80M | next_[n].store(x, std::memory_order_relaxed); | 226 | 9.80M | } |
|
227 | | |
228 | 14.2M | static SkipListNode<Key>* Create(Allocator* allocator, const Key& key, int height) { |
229 | 14.2M | char* mem = allocator->AllocateAligned( |
230 | 14.2M | sizeof(SkipListNode<Key>) + sizeof(std::atomic<SkipListNode<Key>*>) * (height - 1)); |
231 | 14.2M | return new (mem) SkipListNode<Key>(key); |
232 | 14.2M | } _ZN7rocksdb12SkipListNodeIyE6CreateEPNS_9AllocatorERKyi Line | Count | Source | 228 | 5.08M | static SkipListNode<Key>* Create(Allocator* allocator, const Key& key, int height) { | 229 | 5.08M | char* mem = allocator->AllocateAligned( | 230 | 5.08M | sizeof(SkipListNode<Key>) + sizeof(std::atomic<SkipListNode<Key>*>) * (height - 1)); | 231 | 5.08M | return new (mem) SkipListNode<Key>(key); | 232 | 5.08M | } |
_ZN7rocksdb12SkipListNodeIPKcE6CreateEPNS_9AllocatorERKS2_i Line | Count | Source | 228 | 1.09M | static SkipListNode<Key>* Create(Allocator* allocator, const Key& key, int height) { | 229 | 1.09M | char* mem = allocator->AllocateAligned( | 230 | 1.09M | sizeof(SkipListNode<Key>) + sizeof(std::atomic<SkipListNode<Key>*>) * (height - 1)); | 231 | 1.09M | return new (mem) SkipListNode<Key>(key); | 232 | 1.09M | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE6CreateEPNS_9AllocatorERKS2_i Line | Count | Source | 228 | 8.10M | static SkipListNode<Key>* Create(Allocator* allocator, const Key& key, int height) { | 229 | 8.10M | char* mem = allocator->AllocateAligned( | 230 | 8.10M | sizeof(SkipListNode<Key>) + sizeof(std::atomic<SkipListNode<Key>*>) * (height - 1)); | 231 | 8.10M | return new (mem) SkipListNode<Key>(key); | 232 | 8.10M | } |
|
233 | | |
234 | 814k | static SkipListNode<Key>* CreateHead(Allocator* allocator, int height) { |
235 | 814k | return Create(allocator, Key() /* any key will do */, height); |
236 | 814k | } _ZN7rocksdb12SkipListNodeIyE10CreateHeadEPNS_9AllocatorEi Line | Count | Source | 234 | 5.20k | static SkipListNode<Key>* CreateHead(Allocator* allocator, int height) { | 235 | 5.20k | return Create(allocator, Key() /* any key will do */, height); | 236 | 5.20k | } |
_ZN7rocksdb12SkipListNodeIPKcE10CreateHeadEPNS_9AllocatorEi Line | Count | Source | 234 | 64.7k | static SkipListNode<Key>* CreateHead(Allocator* allocator, int height) { | 235 | 64.7k | return Create(allocator, Key() /* any key will do */, height); | 236 | 64.7k | } |
_ZN7rocksdb12SkipListNodeIPNS_20WriteBatchIndexEntryEE10CreateHeadEPNS_9AllocatorEi Line | Count | Source | 234 | 744k | static SkipListNode<Key>* CreateHead(Allocator* allocator, int height) { | 235 | 744k | return Create(allocator, Key() /* any key will do */, height); | 236 | 744k | } |
|
237 | | |
238 | | private: |
239 | | // Array of length equal to the node height. next_[0] is lowest level link. |
240 | | std::atomic<SkipListNode*> next_[1]; |
241 | | }; |
242 | | |
243 | | // Generic skip list implementation - allows any key comparable with specified comparator. |
244 | | // Please note thread safety at top of this file. |
245 | | template<typename Key, class Comparator> |
246 | | class SkipList : public SkipListBase<const Key&, Comparator, SkipListNode<Key>> { |
247 | | private: |
248 | | typedef SkipListNode<Key> Node; |
249 | | typedef SkipListBase<const Key&, Comparator, SkipListNode<Key>> Base; |
250 | | |
251 | | public: |
252 | | template<class... Args> |
253 | | explicit SkipList(Args&&... args) |
254 | 814k | : Base(std::forward<Args>(args)...) { |
255 | 814k | } _ZN7rocksdb8SkipListIyNS_14TestComparatorEEC2IJS1_PNS_5ArenaEEEEDpOT_ Line | Count | Source | 254 | 5.00k | : Base(std::forward<Args>(args)...) { | 255 | 5.00k | } |
_ZN7rocksdb8SkipListIyNS_14TestComparatorEEC2IJRS1_PNS_5ArenaEEEEDpOT_ Line | Count | Source | 254 | 202 | : Base(std::forward<Args>(args)...) { | 255 | 202 | } |
_ZN7rocksdb8SkipListIPKcRKNS_11MemTableRep13KeyComparatorEEC2IJS6_RPNS_17MemTableAllocatorEEEEDpOT_ Line | Count | Source | 254 | 52 | : Base(std::forward<Args>(args)...) { | 255 | 52 | } |
_ZN7rocksdb8SkipListIPKcRKNS_11MemTableRep13KeyComparatorEEC2IJS6_RPNS_5ArenaEEEEDpOT_ Line | Count | Source | 254 | 1.30k | : Base(std::forward<Args>(args)...) { | 255 | 1.30k | } |
_ZN7rocksdb8SkipListIPKcRKNS_11MemTableRep13KeyComparatorEEC2IJS6_RKPNS_17MemTableAllocatorERKiSE_EEEDpOT_ Line | Count | Source | 254 | 63.3k | : Base(std::forward<Args>(args)...) { | 255 | 63.3k | } |
_ZN7rocksdb8SkipListIPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorEEC2IJRS3_PNS_5ArenaEEEEDpOT_ Line | Count | Source | 254 | 744k | : Base(std::forward<Args>(args)...) { | 255 | 744k | } |
|
256 | | |
257 | 13.4M | void Insert(const Key& key) { |
258 | 13.4M | Base::PrepareInsert(key); |
259 | 13.4M | int height = Base::RandomHeight(); |
260 | 13.4M | Node* x = Node::Create(Base::allocator_, key, height); |
261 | 13.4M | Base::CompleteInsert(x, height); |
262 | 13.4M | } _ZN7rocksdb8SkipListIyNS_14TestComparatorEE6InsertERKy Line | Count | Source | 257 | 5.08M | void Insert(const Key& key) { | 258 | 5.08M | Base::PrepareInsert(key); | 259 | 5.08M | int height = Base::RandomHeight(); | 260 | 5.08M | Node* x = Node::Create(Base::allocator_, key, height); | 261 | 5.08M | Base::CompleteInsert(x, height); | 262 | 5.08M | } |
_ZN7rocksdb8SkipListIPKcRKNS_11MemTableRep13KeyComparatorEE6InsertERKS2_ Line | Count | Source | 257 | 1.03M | void Insert(const Key& key) { | 258 | 1.03M | Base::PrepareInsert(key); | 259 | 1.03M | int height = Base::RandomHeight(); | 260 | 1.03M | Node* x = Node::Create(Base::allocator_, key, height); | 261 | 1.03M | Base::CompleteInsert(x, height); | 262 | 1.03M | } |
_ZN7rocksdb8SkipListIPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorEE6InsertERKS2_ Line | Count | Source | 257 | 7.36M | void Insert(const Key& key) { | 258 | 7.36M | Base::PrepareInsert(key); | 259 | 7.36M | int height = Base::RandomHeight(); | 260 | 7.36M | Node* x = Node::Create(Base::allocator_, key, height); | 261 | 7.36M | Base::CompleteInsert(x, height); | 262 | 7.36M | } |
|
263 | | |
264 | | private: |
265 | | Node* NewNode(const Key& key, int height); |
266 | | }; |
267 | | |
268 | | template<typename Key, class Comparator> |
269 | | typename SkipList<Key, Comparator>::Node* |
270 | | SkipList<Key, Comparator>::NewNode(const Key& key, int height) { |
271 | | return Node::Create(Base::allocator_, key, height); |
272 | | } |
273 | | |
274 | | template<class Key, class Comparator, class NodeType> |
275 | | SkipListBase<Key, Comparator, NodeType>::Iterator::Iterator( |
276 | 17.7M | const SkipListBase* list) { |
277 | 17.7M | SetList(list); |
278 | 17.7M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE8IteratorC2EPKS5_ _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8IteratorC2EPKS6_ Line | Count | Source | 276 | 1.24M | const SkipListBase* list) { | 277 | 1.24M | SetList(list); | 278 | 1.24M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8IteratorC2EPKSB_ Line | Count | Source | 276 | 565k | const SkipListBase* list) { | 277 | 565k | SetList(list); | 278 | 565k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8IteratorC2EPKS8_ Line | Count | Source | 276 | 15.4M | const SkipListBase* list) { | 277 | 15.4M | SetList(list); | 278 | 15.4M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8IteratorC2EPKSA_ Line | Count | Source | 276 | 501k | const SkipListBase* list) { | 277 | 501k | SetList(list); | 278 | 501k | } |
|
279 | | |
280 | | template<class Key, class Comparator, class NodeType> |
281 | 17.8M | void SkipListBase<Key, Comparator, NodeType>::Iterator::SetList(const SkipListBase* list) { |
282 | 17.8M | list_ = list; |
283 | 17.8M | node_ = nullptr; |
284 | 17.8M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator7SetListEPKS5_ _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator7SetListEPKS6_ Line | Count | Source | 281 | 1.24M | void SkipListBase<Key, Comparator, NodeType>::Iterator::SetList(const SkipListBase* list) { | 282 | 1.24M | list_ = list; | 283 | 1.24M | node_ = nullptr; | 284 | 1.24M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator7SetListEPKSB_ Line | Count | Source | 281 | 665k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SetList(const SkipListBase* list) { | 282 | 665k | list_ = list; | 283 | 665k | node_ = nullptr; | 284 | 665k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator7SetListEPKS8_ Line | Count | Source | 281 | 15.4M | void SkipListBase<Key, Comparator, NodeType>::Iterator::SetList(const SkipListBase* list) { | 282 | 15.4M | list_ = list; | 283 | 15.4M | node_ = nullptr; | 284 | 15.4M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator7SetListEPKSA_ Line | Count | Source | 281 | 501k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SetList(const SkipListBase* list) { | 282 | 501k | list_ = list; | 283 | 501k | node_ = nullptr; | 284 | 501k | } |
|
285 | | |
286 | | template<class Key, class Comparator, class NodeType> |
287 | 1.98G | bool SkipListBase<Key, Comparator, NodeType>::Iterator::Valid() const { |
288 | 1.98G | return node_ != nullptr; |
289 | 1.98G | } _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator5ValidEv Line | Count | Source | 287 | 64.3M | bool SkipListBase<Key, Comparator, NodeType>::Iterator::Valid() const { | 288 | 64.3M | return node_ != nullptr; | 289 | 64.3M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator5ValidEv Line | Count | Source | 287 | 5.22M | bool SkipListBase<Key, Comparator, NodeType>::Iterator::Valid() const { | 288 | 5.22M | return node_ != nullptr; | 289 | 5.22M | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator5ValidEv Line | Count | Source | 287 | 1.91G | bool SkipListBase<Key, Comparator, NodeType>::Iterator::Valid() const { | 288 | 1.91G | return node_ != nullptr; | 289 | 1.91G | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator5ValidEv Line | Count | Source | 287 | 10.1M | bool SkipListBase<Key, Comparator, NodeType>::Iterator::Valid() const { | 288 | 10.1M | return node_ != nullptr; | 289 | 10.1M | } |
|
290 | | |
291 | | template<class Key, class Comparator, class NodeType> |
292 | 993M | Key SkipListBase<Key, Comparator, NodeType>::Iterator::key() const { |
293 | 993M | DCHECK(Valid()); |
294 | 993M | return node_->key; |
295 | 993M | } _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator3keyEv Line | Count | Source | 292 | 18.1M | Key SkipListBase<Key, Comparator, NodeType>::Iterator::key() const { | 293 | 18.1M | DCHECK(Valid()); | 294 | 18.1M | return node_->key; | 295 | 18.1M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator3keyEv Line | Count | Source | 292 | 1.73M | Key SkipListBase<Key, Comparator, NodeType>::Iterator::key() const { | 293 | 1.73M | DCHECK(Valid()); | 294 | 1.73M | return node_->key; | 295 | 1.73M | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator3keyEv Line | Count | Source | 292 | 967M | Key SkipListBase<Key, Comparator, NodeType>::Iterator::key() const { | 293 | 967M | DCHECK(Valid()); | 294 | 967M | return node_->key; | 295 | 967M | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator3keyEv Line | Count | Source | 292 | 5.74M | Key SkipListBase<Key, Comparator, NodeType>::Iterator::key() const { | 293 | 5.74M | DCHECK(Valid()); | 294 | 5.74M | return node_->key; | 295 | 5.74M | } |
|
296 | | |
297 | | template<class Key, class Comparator, class NodeType> |
298 | 450M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Next() { |
299 | 450M | DCHECK(Valid()); |
300 | 450M | node_ = node_->Next(0); |
301 | 450M | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator4NextEv Line | Count | Source | 298 | 10.3M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Next() { | 299 | 10.3M | DCHECK(Valid()); | 300 | 10.3M | node_ = node_->Next(0); | 301 | 10.3M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator4NextEv Line | Count | Source | 298 | 824k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Next() { | 299 | 824k | DCHECK(Valid()); | 300 | 824k | node_ = node_->Next(0); | 301 | 824k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator4NextEv Line | Count | Source | 298 | 438M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Next() { | 299 | 438M | DCHECK(Valid()); | 300 | 438M | node_ = node_->Next(0); | 301 | 438M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator4NextEv Line | Count | Source | 298 | 500k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Next() { | 299 | 500k | DCHECK(Valid()); | 300 | 500k | node_ = node_->Next(0); | 301 | 500k | } |
|
302 | | |
303 | | template<class Key, class Comparator, class NodeType> |
304 | 655k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Prev() { |
305 | | // Instead of using explicit "prev" links, we just search for the |
306 | | // last node that falls before key. |
307 | 655k | DCHECK(Valid()); |
308 | 655k | node_ = list_->FindLessThan(node_->key); |
309 | 655k | if (node_ == list_->head_) { |
310 | 307k | node_ = nullptr; |
311 | 307k | } |
312 | 655k | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator4PrevEv Line | Count | Source | 304 | 1.64k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Prev() { | 305 | | // Instead of using explicit "prev" links, we just search for the | 306 | | // last node that falls before key. | 307 | 1.64k | DCHECK(Valid()); | 308 | 1.64k | node_ = list_->FindLessThan(node_->key); | 309 | 1.64k | if (node_ == list_->head_) { | 310 | 1 | node_ = nullptr; | 311 | 1 | } | 312 | 1.64k | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator4PrevEv Line | Count | Source | 304 | 7 | void SkipListBase<Key, Comparator, NodeType>::Iterator::Prev() { | 305 | | // Instead of using explicit "prev" links, we just search for the | 306 | | // last node that falls before key. | 307 | 7 | DCHECK(Valid()); | 308 | 7 | node_ = list_->FindLessThan(node_->key); | 309 | 7 | if (node_ == list_->head_) { | 310 | 1 | node_ = nullptr; | 311 | 1 | } | 312 | 7 | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator4PrevEv Line | Count | Source | 304 | 349k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Prev() { | 305 | | // Instead of using explicit "prev" links, we just search for the | 306 | | // last node that falls before key. | 307 | 349k | DCHECK(Valid()); | 308 | 349k | node_ = list_->FindLessThan(node_->key); | 309 | 349k | if (node_ == list_->head_) { | 310 | 303k | node_ = nullptr; | 311 | 303k | } | 312 | 349k | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator4PrevEv Line | Count | Source | 304 | 304k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Prev() { | 305 | | // Instead of using explicit "prev" links, we just search for the | 306 | | // last node that falls before key. | 307 | 304k | DCHECK(Valid()); | 308 | 304k | node_ = list_->FindLessThan(node_->key); | 309 | 304k | if (node_ == list_->head_) { | 310 | 3.78k | node_ = nullptr; | 311 | 3.78k | } | 312 | 304k | } |
|
313 | | |
314 | | template<class Key, class Comparator, class NodeType> |
315 | 70.7M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Seek(Key target) { |
316 | 70.7M | node_ = list_->FindGreaterOrEqual(target); |
317 | 70.7M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator4SeekES2_ _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator4SeekES2_ Line | Count | Source | 315 | 2.55M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Seek(Key target) { | 316 | 2.55M | node_ = list_->FindGreaterOrEqual(target); | 317 | 2.55M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator4SeekES4_ Line | Count | Source | 315 | 663k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Seek(Key target) { | 316 | 663k | node_ = list_->FindGreaterOrEqual(target); | 317 | 663k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator4SeekES2_ Line | Count | Source | 315 | 66.7M | void SkipListBase<Key, Comparator, NodeType>::Iterator::Seek(Key target) { | 316 | 66.7M | node_ = list_->FindGreaterOrEqual(target); | 317 | 66.7M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator4SeekES4_ Line | Count | Source | 315 | 756k | void SkipListBase<Key, Comparator, NodeType>::Iterator::Seek(Key target) { | 316 | 756k | node_ = list_->FindGreaterOrEqual(target); | 317 | 756k | } |
|
318 | | |
319 | | template<class Key, class Comparator, class NodeType> |
320 | 187k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToFirst() { |
321 | 187k | node_ = list_->head_->Next(0); |
322 | 187k | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator11SeekToFirstEv Line | Count | Source | 320 | 116k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToFirst() { | 321 | 116k | node_ = list_->head_->Next(0); | 322 | 116k | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator11SeekToFirstEv Line | Count | Source | 320 | 1.37k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToFirst() { | 321 | 1.37k | node_ = list_->head_->Next(0); | 322 | 1.37k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator11SeekToFirstEv Line | Count | Source | 320 | 69.9k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToFirst() { | 321 | 69.9k | node_ = list_->head_->Next(0); | 322 | 69.9k | } |
|
323 | | |
324 | | template<class Key, class Comparator, class NodeType> |
325 | 453k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToLast() { |
326 | 453k | node_ = list_->FindLast(); |
327 | 453k | if (node_ == list_->head_) { |
328 | 136k | node_ = nullptr; |
329 | 136k | } |
330 | 453k | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8Iterator10SeekToLastEv Line | Count | Source | 325 | 3 | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToLast() { | 326 | 3 | node_ = list_->FindLast(); | 327 | 3 | if (node_ == list_->head_) { | 328 | 1 | node_ = nullptr; | 329 | 1 | } | 330 | 3 | } |
Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8Iterator10SeekToLastEv _ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8Iterator10SeekToLastEv Line | Count | Source | 325 | 451k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToLast() { | 326 | 451k | node_ = list_->FindLast(); | 327 | 451k | if (node_ == list_->head_) { | 328 | 136k | node_ = nullptr; | 329 | 136k | } | 330 | 451k | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8Iterator10SeekToLastEv Line | Count | Source | 325 | 1.41k | void SkipListBase<Key, Comparator, NodeType>::Iterator::SeekToLast() { | 326 | 1.41k | node_ = list_->FindLast(); | 327 | 1.41k | if (node_ == list_->head_) { | 328 | 88 | node_ = nullptr; | 329 | 88 | } | 330 | 1.41k | } |
|
331 | | |
332 | | template<class Key, class Comparator, class NodeType> |
333 | 127M | int SkipListBase<Key, Comparator, NodeType>::RandomHeight() { |
334 | 127M | auto rnd = Random::GetTLSInstance(); |
335 | | |
336 | | // Increase height with probability 1 in kBranching |
337 | 127M | int height = 1; |
338 | 170M | while (height < kMaxHeight_ && rnd->Next() < kScaledInverseBranching_) { |
339 | 42.5M | height++; |
340 | 42.5M | } |
341 | 127M | return height; |
342 | 127M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE12RandomHeightEv _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE12RandomHeightEv Line | Count | Source | 333 | 5.08M | int SkipListBase<Key, Comparator, NodeType>::RandomHeight() { | 334 | 5.08M | auto rnd = Random::GetTLSInstance(); | 335 | | | 336 | | // Increase height with probability 1 in kBranching | 337 | 5.08M | int height = 1; | 338 | 6.77M | while (height < kMaxHeight_ && rnd->Next() < kScaledInverseBranching_) { | 339 | 1.69M | height++; | 340 | 1.69M | } | 341 | 5.08M | return height; | 342 | 5.08M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE12RandomHeightEv Line | Count | Source | 333 | 1.03M | int SkipListBase<Key, Comparator, NodeType>::RandomHeight() { | 334 | 1.03M | auto rnd = Random::GetTLSInstance(); | 335 | | | 336 | | // Increase height with probability 1 in kBranching | 337 | 1.03M | int height = 1; | 338 | 1.37M | while (height < kMaxHeight_ && rnd->Next() < kScaledInverseBranching_) { | 339 | 342k | height++; | 340 | 342k | } | 341 | 1.03M | return height; | 342 | 1.03M | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE12RandomHeightEv Line | Count | Source | 333 | 114M | int SkipListBase<Key, Comparator, NodeType>::RandomHeight() { | 334 | 114M | auto rnd = Random::GetTLSInstance(); | 335 | | | 336 | | // Increase height with probability 1 in kBranching | 337 | 114M | int height = 1; | 338 | 152M | while (height < kMaxHeight_ && rnd->Next() < kScaledInverseBranching_) { | 339 | 38.0M | height++; | 340 | 38.0M | } | 341 | 114M | return height; | 342 | 114M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE12RandomHeightEv Line | Count | Source | 333 | 7.36M | int SkipListBase<Key, Comparator, NodeType>::RandomHeight() { | 334 | 7.36M | auto rnd = Random::GetTLSInstance(); | 335 | | | 336 | | // Increase height with probability 1 in kBranching | 337 | 7.36M | int height = 1; | 338 | 9.81M | while (height < kMaxHeight_ && rnd->Next() < kScaledInverseBranching_) { | 339 | 2.45M | height++; | 340 | 2.45M | } | 341 | 7.36M | return height; | 342 | 7.36M | } |
|
343 | | |
344 | | template<class Key, class Comparator, class NodeType> |
345 | 5.79G | bool SkipListBase<Key, Comparator, NodeType>::KeyIsAfterNode(Key key, Node* n) const { |
346 | | // nullptr n is considered infinite |
347 | 5.79G | return (n != nullptr) && (compare_(n->key, key) < 0); |
348 | 5.79G | } Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE14KeyIsAfterNodeES2_PS4_ _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE14KeyIsAfterNodeES2_PS5_ Line | Count | Source | 345 | 183M | bool SkipListBase<Key, Comparator, NodeType>::KeyIsAfterNode(Key key, Node* n) const { | 346 | | // nullptr n is considered infinite | 347 | 183M | return (n != nullptr) && (compare_(n->key, key) < 0); | 348 | 183M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE14KeyIsAfterNodeES4_PSA_ Line | Count | Source | 345 | 112M | bool SkipListBase<Key, Comparator, NodeType>::KeyIsAfterNode(Key key, Node* n) const { | 346 | | // nullptr n is considered infinite | 347 | 112M | return (n != nullptr) && (compare_(n->key, key) < 0); | 348 | 112M | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE14KeyIsAfterNodeES2_PS7_ Line | Count | Source | 345 | 5.46G | bool SkipListBase<Key, Comparator, NodeType>::KeyIsAfterNode(Key key, Node* n) const { | 346 | | // nullptr n is considered infinite | 347 | 5.46G | return (n != nullptr) && (compare_(n->key, key) < 0); | 348 | 5.46G | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE14KeyIsAfterNodeES4_PS9_ Line | Count | Source | 345 | 31.6M | bool SkipListBase<Key, Comparator, NodeType>::KeyIsAfterNode(Key key, Node* n) const { | 346 | | // nullptr n is considered infinite | 347 | 31.6M | return (n != nullptr) && (compare_(n->key, key) < 0); | 348 | 31.6M | } |
|
349 | | |
350 | | template<class Key, class Comparator, class NodeType> |
351 | | typename SkipListBase<Key, Comparator, NodeType>::Node* SkipListBase<Key, Comparator, NodeType>:: |
352 | 71.3M | FindGreaterOrEqual(Key key) const { |
353 | | // Note: It looks like we could reduce duplication by implementing |
354 | | // this function as FindLessThan(key)->Next(0), but we wouldn't be able |
355 | | // to exit early on equality and the result wouldn't even be correct. |
356 | | // A concurrent insert might occur after FindLessThan(key) but before |
357 | | // we get a chance to call Next(0). |
358 | 71.3M | Node* x = head_; |
359 | 71.3M | int level = GetMaxHeight() - 1; |
360 | 71.3M | Node* last_bigger = nullptr; |
361 | 1.44G | while (true) { |
362 | 1.44G | Node* next = x->Next(level); |
363 | | // Make sure the lists are sorted |
364 | 1.44G | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); |
365 | | // Make sure we haven't overshot during our search |
366 | 1.44G | DCHECK(x == head_ || KeyIsAfterNode(key, x)); |
367 | 1.44G | int cmp = (next == nullptr || next == last_bigger) |
368 | 1.17G | ? 1 : compare_(next->key, key); |
369 | 1.44G | if (cmp == 0 || (cmp > 0 && level == 0)) { |
370 | 71.3M | return next; |
371 | 1.37G | } else if (cmp < 0) { |
372 | | // Keep searching in this list |
373 | 908M | x = next; |
374 | 465M | } else { |
375 | | // Switch to next list, reuse compare_() result |
376 | 465M | last_bigger = next; |
377 | 465M | level--; |
378 | 465M | } |
379 | 1.44G | } |
380 | 71.3M | } Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE18FindGreaterOrEqualES2_ _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE18FindGreaterOrEqualES2_ Line | Count | Source | 352 | 2.56M | FindGreaterOrEqual(Key key) const { | 353 | | // Note: It looks like we could reduce duplication by implementing | 354 | | // this function as FindLessThan(key)->Next(0), but we wouldn't be able | 355 | | // to exit early on equality and the result wouldn't even be correct. | 356 | | // A concurrent insert might occur after FindLessThan(key) but before | 357 | | // we get a chance to call Next(0). | 358 | 2.56M | Node* x = head_; | 359 | 2.56M | int level = GetMaxHeight() - 1; | 360 | 2.56M | Node* last_bigger = nullptr; | 361 | 36.8M | while (true) { | 362 | 36.8M | Node* next = x->Next(level); | 363 | | // Make sure the lists are sorted | 364 | 36.8M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 365 | | // Make sure we haven't overshot during our search | 366 | 36.8M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 367 | 36.8M | int cmp = (next == nullptr || next == last_bigger) | 368 | 29.6M | ? 1 : compare_(next->key, key); | 369 | 36.8M | if (cmp == 0 || (cmp > 0 && level == 0)) { | 370 | 2.56M | return next; | 371 | 34.3M | } else if (cmp < 0) { | 372 | | // Keep searching in this list | 373 | 24.6M | x = next; | 374 | 9.68M | } else { | 375 | | // Switch to next list, reuse compare_() result | 376 | 9.68M | last_bigger = next; | 377 | 9.68M | level--; | 378 | 9.68M | } | 379 | 36.8M | } | 380 | 2.56M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE18FindGreaterOrEqualES4_ Line | Count | Source | 352 | 1.22M | FindGreaterOrEqual(Key key) const { | 353 | | // Note: It looks like we could reduce duplication by implementing | 354 | | // this function as FindLessThan(key)->Next(0), but we wouldn't be able | 355 | | // to exit early on equality and the result wouldn't even be correct. | 356 | | // A concurrent insert might occur after FindLessThan(key) but before | 357 | | // we get a chance to call Next(0). | 358 | 1.22M | Node* x = head_; | 359 | 1.22M | int level = GetMaxHeight() - 1; | 360 | 1.22M | Node* last_bigger = nullptr; | 361 | 35.0M | while (true) { | 362 | 35.0M | Node* next = x->Next(level); | 363 | | // Make sure the lists are sorted | 364 | 35.0M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 365 | | // Make sure we haven't overshot during our search | 366 | 35.0M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 367 | 35.0M | int cmp = (next == nullptr || next == last_bigger) | 368 | 33.0M | ? 1 : compare_(next->key, key); | 369 | 35.1M | if (cmp == 0 || (cmp > 0 && level == 0)) { | 370 | 1.22M | return next; | 371 | 33.8M | } else if (cmp < 0) { | 372 | | // Keep searching in this list | 373 | 28.9M | x = next; | 374 | 4.90M | } else { | 375 | | // Switch to next list, reuse compare_() result | 376 | 4.90M | last_bigger = next; | 377 | 4.90M | level--; | 378 | 4.90M | } | 379 | 35.0M | } | 380 | 1.22M | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE18FindGreaterOrEqualES2_ Line | Count | Source | 352 | 66.7M | FindGreaterOrEqual(Key key) const { | 353 | | // Note: It looks like we could reduce duplication by implementing | 354 | | // this function as FindLessThan(key)->Next(0), but we wouldn't be able | 355 | | // to exit early on equality and the result wouldn't even be correct. | 356 | | // A concurrent insert might occur after FindLessThan(key) but before | 357 | | // we get a chance to call Next(0). | 358 | 66.7M | Node* x = head_; | 359 | 66.7M | int level = GetMaxHeight() - 1; | 360 | 66.7M | Node* last_bigger = nullptr; | 361 | 1.36G | while (true) { | 362 | 1.36G | Node* next = x->Next(level); | 363 | | // Make sure the lists are sorted | 364 | 1.36G | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 365 | | // Make sure we haven't overshot during our search | 366 | 1.36G | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 367 | 1.36G | int cmp = (next == nullptr || next == last_bigger) | 368 | 1.10G | ? 1 : compare_(next->key, key); | 369 | 1.36G | if (cmp == 0 || (cmp > 0 && level == 0)) { | 370 | 66.8M | return next; | 371 | 1.29G | } else if (cmp < 0) { | 372 | | // Keep searching in this list | 373 | 851M | x = next; | 374 | 447M | } else { | 375 | | // Switch to next list, reuse compare_() result | 376 | 447M | last_bigger = next; | 377 | 447M | level--; | 378 | 447M | } | 379 | 1.36G | } | 380 | 66.7M | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE18FindGreaterOrEqualES4_ Line | Count | Source | 352 | 756k | FindGreaterOrEqual(Key key) const { | 353 | | // Note: It looks like we could reduce duplication by implementing | 354 | | // this function as FindLessThan(key)->Next(0), but we wouldn't be able | 355 | | // to exit early on equality and the result wouldn't even be correct. | 356 | | // A concurrent insert might occur after FindLessThan(key) but before | 357 | | // we get a chance to call Next(0). | 358 | 756k | Node* x = head_; | 359 | 756k | int level = GetMaxHeight() - 1; | 360 | 756k | Node* last_bigger = nullptr; | 361 | 8.45M | while (true) { | 362 | 8.45M | Node* next = x->Next(level); | 363 | | // Make sure the lists are sorted | 364 | 8.45M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 365 | | // Make sure we haven't overshot during our search | 366 | 8.45M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 367 | 8.45M | int cmp = (next == nullptr || next == last_bigger) | 368 | 6.26M | ? 1 : compare_(next->key, key); | 369 | 8.45M | if (cmp == 0 || (cmp > 0 && level == 0)) { | 370 | 756k | return next; | 371 | 7.69M | } else if (cmp < 0) { | 372 | | // Keep searching in this list | 373 | 3.93M | x = next; | 374 | 3.75M | } else { | 375 | | // Switch to next list, reuse compare_() result | 376 | 3.75M | last_bigger = next; | 377 | 3.75M | level--; | 378 | 3.75M | } | 379 | 8.45M | } | 380 | 756k | } |
|
381 | | |
382 | | template<class Key, class Comparator, class NodeType> |
383 | | typename SkipListBase<Key, Comparator, NodeType>::Node* |
384 | 79.1M | SkipListBase<Key, Comparator, NodeType>::FindLessThan(Key key, Node** prev) const { |
385 | 79.1M | Node* x = head_; |
386 | 79.1M | int level = GetMaxHeight() - 1; |
387 | | // KeyIsAfter(key, last_not_after) is definitely false |
388 | 79.1M | Node* last_not_after = nullptr; |
389 | 1.53G | while (true) { |
390 | 1.53G | Node* next = x->Next(level); |
391 | 1.53G | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); |
392 | 1.53G | DCHECK(x == head_ || KeyIsAfterNode(key, x)); |
393 | 1.53G | if (next != last_not_after && KeyIsAfterNode(key, next)) { |
394 | | // Keep searching in this list |
395 | 886M | x = next; |
396 | 650M | } else { |
397 | 661M | if (prev != nullptr) { |
398 | 661M | prev[level] = x; |
399 | 661M | } |
400 | 650M | if (level == 0) { |
401 | 79.1M | return x; |
402 | 571M | } else { |
403 | | // Switch to next list, reuse KeyIUsAfterNode() result |
404 | 571M | last_not_after = next; |
405 | 571M | level--; |
406 | 571M | } |
407 | 650M | } |
408 | 1.53G | } |
409 | 79.1M | } Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE12FindLessThanES2_PPS4_ _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE12FindLessThanES2_PPS5_ Line | Count | Source | 384 | 3.88M | SkipListBase<Key, Comparator, NodeType>::FindLessThan(Key key, Node** prev) const { | 385 | 3.88M | Node* x = head_; | 386 | 3.88M | int level = GetMaxHeight() - 1; | 387 | | // KeyIsAfter(key, last_not_after) is definitely false | 388 | 3.88M | Node* last_not_after = nullptr; | 389 | 62.8M | while (true) { | 390 | 62.8M | Node* next = x->Next(level); | 391 | 62.8M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 392 | 62.8M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 393 | 62.8M | if (next != last_not_after && KeyIsAfterNode(key, next)) { | 394 | | // Keep searching in this list | 395 | 42.8M | x = next; | 396 | 19.9M | } else { | 397 | 19.9M | if (prev != nullptr) { | 398 | 19.9M | prev[level] = x; | 399 | 19.9M | } | 400 | 19.9M | if (level == 0) { | 401 | 3.88M | return x; | 402 | 16.1M | } else { | 403 | | // Switch to next list, reuse KeyIUsAfterNode() result | 404 | 16.1M | last_not_after = next; | 405 | 16.1M | level--; | 406 | 16.1M | } | 407 | 19.9M | } | 408 | 62.8M | } | 409 | 3.88M | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE12FindLessThanES4_PPSA_ Line | Count | Source | 384 | 517k | SkipListBase<Key, Comparator, NodeType>::FindLessThan(Key key, Node** prev) const { | 385 | 517k | Node* x = head_; | 386 | 517k | int level = GetMaxHeight() - 1; | 387 | | // KeyIsAfter(key, last_not_after) is definitely false | 388 | 517k | Node* last_not_after = nullptr; | 389 | 17.9M | while (true) { | 390 | 17.9M | Node* next = x->Next(level); | 391 | 17.9M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 392 | 17.9M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 393 | 17.9M | if (next != last_not_after && KeyIsAfterNode(key, next)) { | 394 | | // Keep searching in this list | 395 | 14.7M | x = next; | 396 | 3.17M | } else { | 397 | 3.17M | if (prev != nullptr) { | 398 | 3.17M | prev[level] = x; | 399 | 3.17M | } | 400 | 3.17M | if (level == 0) { | 401 | 517k | return x; | 402 | 2.66M | } else { | 403 | | // Switch to next list, reuse KeyIUsAfterNode() result | 404 | 2.66M | last_not_after = next; | 405 | 2.66M | level--; | 406 | 2.66M | } | 407 | 3.17M | } | 408 | 17.9M | } | 409 | 517k | } |
_ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE12FindLessThanES2_PPS7_ Line | Count | Source | 384 | 74.4M | SkipListBase<Key, Comparator, NodeType>::FindLessThan(Key key, Node** prev) const { | 385 | 74.4M | Node* x = head_; | 386 | 74.4M | int level = GetMaxHeight() - 1; | 387 | | // KeyIsAfter(key, last_not_after) is definitely false | 388 | 74.4M | Node* last_not_after = nullptr; | 389 | 1.45G | while (true) { | 390 | 1.45G | Node* next = x->Next(level); | 391 | 1.45G | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 392 | 1.45G | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 393 | 1.45G | if (next != last_not_after && KeyIsAfterNode(key, next)) { | 394 | | // Keep searching in this list | 395 | 827M | x = next; | 396 | 625M | } else { | 397 | 638M | if (prev != nullptr) { | 398 | 638M | prev[level] = x; | 399 | 638M | } | 400 | 625M | if (level == 0) { | 401 | 74.4M | return x; | 402 | 551M | } else { | 403 | | // Switch to next list, reuse KeyIUsAfterNode() result | 404 | 551M | last_not_after = next; | 405 | 551M | level--; | 406 | 551M | } | 407 | 625M | } | 408 | 1.45G | } | 409 | 74.4M | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE12FindLessThanES4_PPS9_ Line | Count | Source | 384 | 304k | SkipListBase<Key, Comparator, NodeType>::FindLessThan(Key key, Node** prev) const { | 385 | 304k | Node* x = head_; | 386 | 304k | int level = GetMaxHeight() - 1; | 387 | | // KeyIsAfter(key, last_not_after) is definitely false | 388 | 304k | Node* last_not_after = nullptr; | 389 | 3.43M | while (true) { | 390 | 3.43M | Node* next = x->Next(level); | 391 | 3.43M | DCHECK(x == head_ || next == nullptr || KeyIsAfterNode(next->key, x)); | 392 | 3.43M | DCHECK(x == head_ || KeyIsAfterNode(key, x)); | 393 | 3.43M | if (next != last_not_after && KeyIsAfterNode(key, next)) { | 394 | | // Keep searching in this list | 395 | 1.62M | x = next; | 396 | 1.81M | } else { | 397 | 1.81M | if (prev != nullptr) { | 398 | 512 | prev[level] = x; | 399 | 512 | } | 400 | 1.81M | if (level == 0) { | 401 | 304k | return x; | 402 | 1.50M | } else { | 403 | | // Switch to next list, reuse KeyIUsAfterNode() result | 404 | 1.50M | last_not_after = next; | 405 | 1.50M | level--; | 406 | 1.50M | } | 407 | 1.81M | } | 408 | 3.43M | } | 409 | 304k | } |
|
410 | | |
411 | | template<class Key, class Comparator, class NodeType> |
412 | | typename SkipListBase<Key, Comparator, NodeType>::Node* |
413 | 453k | SkipListBase<Key, Comparator, NodeType>::FindLast() const { |
414 | 453k | Node* x = head_; |
415 | 453k | int level = GetMaxHeight() - 1; |
416 | 6.54M | while (true) { |
417 | 6.54M | Node* next = x->Next(level); |
418 | 6.54M | if (next == nullptr) { |
419 | 1.97M | if (level == 0) { |
420 | 452k | return x; |
421 | 1.52M | } else { |
422 | | // Switch to next list |
423 | 1.52M | level--; |
424 | 1.52M | } |
425 | 4.56M | } else { |
426 | 4.56M | x = next; |
427 | 4.56M | } |
428 | 6.54M | } |
429 | 453k | } _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8FindLastEv Line | Count | Source | 413 | 3 | SkipListBase<Key, Comparator, NodeType>::FindLast() const { | 414 | 3 | Node* x = head_; | 415 | 3 | int level = GetMaxHeight() - 1; | 416 | 37 | while (true) { | 417 | 37 | Node* next = x->Next(level); | 418 | 37 | if (next == nullptr) { | 419 | 11 | if (level == 0) { | 420 | 3 | return x; | 421 | 8 | } else { | 422 | | // Switch to next list | 423 | 8 | level--; | 424 | 8 | } | 425 | 26 | } else { | 426 | 26 | x = next; | 427 | 26 | } | 428 | 37 | } | 429 | 3 | } |
Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8FindLastEv _ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8FindLastEv Line | Count | Source | 413 | 451k | SkipListBase<Key, Comparator, NodeType>::FindLast() const { | 414 | 451k | Node* x = head_; | 415 | 451k | int level = GetMaxHeight() - 1; | 416 | 6.53M | while (true) { | 417 | 6.53M | Node* next = x->Next(level); | 418 | 6.53M | if (next == nullptr) { | 419 | 1.97M | if (level == 0) { | 420 | 451k | return x; | 421 | 1.52M | } else { | 422 | | // Switch to next list | 423 | 1.52M | level--; | 424 | 1.52M | } | 425 | 4.56M | } else { | 426 | 4.56M | x = next; | 427 | 4.56M | } | 428 | 6.53M | } | 429 | 451k | } |
_ZNK7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE8FindLastEv Line | Count | Source | 413 | 1.41k | SkipListBase<Key, Comparator, NodeType>::FindLast() const { | 414 | 1.41k | Node* x = head_; | 415 | 1.41k | int level = GetMaxHeight() - 1; | 416 | 8.06k | while (true) { | 417 | 8.06k | Node* next = x->Next(level); | 418 | 8.06k | if (next == nullptr) { | 419 | 3.24k | if (level == 0) { | 420 | 1.41k | return x; | 421 | 1.83k | } else { | 422 | | // Switch to next list | 423 | 1.83k | level--; | 424 | 1.83k | } | 425 | 4.81k | } else { | 426 | 4.81k | x = next; | 427 | 4.81k | } | 428 | 8.06k | } | 429 | 1.41k | } |
|
430 | | |
431 | | template<class Key, class Comparator, class NodeType> |
432 | 0 | uint64_t SkipListBase<Key, Comparator, NodeType>::EstimateCount(Key key) const { |
433 | 0 | uint64_t count = 0; |
434 | |
|
435 | 0 | Node* x = head_; |
436 | 0 | int level = GetMaxHeight() - 1; |
437 | 0 | while (true) { |
438 | 0 | DCHECK(x == head_ || compare_(x->key, key) < 0); |
439 | 0 | Node* next = x->Next(level); |
440 | 0 | if (next == nullptr || compare_(next->key, key) >= 0) { |
441 | 0 | if (level == 0) { |
442 | 0 | return count; |
443 | 0 | } else { |
444 | | // Switch to next list |
445 | 0 | count *= kBranching_; |
446 | 0 | level--; |
447 | 0 | } |
448 | 0 | } else { |
449 | 0 | x = next; |
450 | 0 | count++; |
451 | 0 | } |
452 | 0 | } |
453 | 0 | } |
454 | | |
455 | | template<class Key, class Comparator, class NodeType> |
456 | 127M | void SkipListBase<Key, Comparator, NodeType>::PrepareInsert(Key key) { |
457 | | // fast path for sequential insertion |
458 | 127M | if (prev_valid_ && !KeyIsAfterNode(key, prev_[0]->NoBarrier_Next(0)) && |
459 | 110M | (prev_[0] == head_ || KeyIsAfterNode(key, prev_[0]))) { |
460 | 18.4E | DCHECK(prev_[0] != head_ || (prev_height_ == 1 && GetMaxHeight() == 1)) |
461 | 18.4E | << "prev_height_: " << prev_height_ << ", GetMaxHeight(): " << GetMaxHeight(); |
462 | | |
463 | | // Outside of this method prev_[1..max_height_] is the predecessor |
464 | | // of prev_[0], and prev_height_ refers to prev_[0]. Inside Insert |
465 | | // prev_[0..max_height - 1] is the predecessor of key. Switch from |
466 | | // the external state to the internal |
467 | 140M | for (int i = 1; i < prev_height_; i++) { |
468 | 34.9M | prev_[i] = prev_[0]; |
469 | 34.9M | } |
470 | 21.9M | } else { |
471 | | // TODO(opt): we could use a NoBarrier predecessor search as an |
472 | | // optimization for architectures where memory_order_acquire needs |
473 | | // a synchronization instruction. Doesn't matter on x86 |
474 | 21.9M | FindLessThan(key, prev_); |
475 | 21.9M | prev_valid_ = true; |
476 | 21.9M | } |
477 | | |
478 | | // Our data structure does not allow duplicate insertion |
479 | 127M | DCHECK(prev_[0]->Next(0) == nullptr || !Equal(key, prev_[0]->Next(0)->key)); |
480 | 127M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE13PrepareInsertES2_ _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE13PrepareInsertES2_ Line | Count | Source | 456 | 5.08M | void SkipListBase<Key, Comparator, NodeType>::PrepareInsert(Key key) { | 457 | | // fast path for sequential insertion | 458 | 5.08M | if (prev_valid_ && !KeyIsAfterNode(key, prev_[0]->NoBarrier_Next(0)) && | 459 | 3.16M | (prev_[0] == head_ || KeyIsAfterNode(key, prev_[0]))) { | 460 | 0 | DCHECK(prev_[0] != head_ || (prev_height_ == 1 && GetMaxHeight() == 1)) | 461 | 0 | << "prev_height_: " << prev_height_ << ", GetMaxHeight(): " << GetMaxHeight(); | 462 | | | 463 | | // Outside of this method prev_[1..max_height_] is the predecessor | 464 | | // of prev_[0], and prev_height_ refers to prev_[0]. Inside Insert | 465 | | // prev_[0..max_height - 1] is the predecessor of key. Switch from | 466 | | // the external state to the internal | 467 | 1.68M | for (int i = 1; i < prev_height_; i++) { | 468 | 421k | prev_[i] = prev_[0]; | 469 | 421k | } | 470 | 3.81M | } else { | 471 | | // TODO(opt): we could use a NoBarrier predecessor search as an | 472 | | // optimization for architectures where memory_order_acquire needs | 473 | | // a synchronization instruction. Doesn't matter on x86 | 474 | 3.81M | FindLessThan(key, prev_); | 475 | 3.81M | prev_valid_ = true; | 476 | 3.81M | } | 477 | | | 478 | | // Our data structure does not allow duplicate insertion | 479 | 5.08M | DCHECK(prev_[0]->Next(0) == nullptr || !Equal(key, prev_[0]->Next(0)->key)); | 480 | 5.08M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE13PrepareInsertES4_ Line | Count | Source | 456 | 1.03M | void SkipListBase<Key, Comparator, NodeType>::PrepareInsert(Key key) { | 457 | | // fast path for sequential insertion | 458 | 1.03M | if (prev_valid_ && !KeyIsAfterNode(key, prev_[0]->NoBarrier_Next(0)) && | 459 | 774k | (prev_[0] == head_ || KeyIsAfterNode(key, prev_[0]))) { | 460 | 18.4E | DCHECK(prev_[0] != head_ || (prev_height_ == 1 && GetMaxHeight() == 1)) | 461 | 18.4E | << "prev_height_: " << prev_height_ << ", GetMaxHeight(): " << GetMaxHeight(); | 462 | | | 463 | | // Outside of this method prev_[1..max_height_] is the predecessor | 464 | | // of prev_[0], and prev_height_ refers to prev_[0]. Inside Insert | 465 | | // prev_[0..max_height - 1] is the predecessor of key. Switch from | 466 | | // the external state to the internal | 467 | 666k | for (int i = 1; i < prev_height_; i++) { | 468 | 150k | prev_[i] = prev_[0]; | 469 | 150k | } | 470 | 516k | } else { | 471 | | // TODO(opt): we could use a NoBarrier predecessor search as an | 472 | | // optimization for architectures where memory_order_acquire needs | 473 | | // a synchronization instruction. Doesn't matter on x86 | 474 | 516k | FindLessThan(key, prev_); | 475 | 516k | prev_valid_ = true; | 476 | 516k | } | 477 | | | 478 | | // Our data structure does not allow duplicate insertion | 479 | 1.03M | DCHECK(prev_[0]->Next(0) == nullptr || !Equal(key, prev_[0]->Next(0)->key)); | 480 | 1.03M | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE13PrepareInsertES2_ Line | Count | Source | 456 | 114M | void SkipListBase<Key, Comparator, NodeType>::PrepareInsert(Key key) { | 457 | | // fast path for sequential insertion | 458 | 114M | if (prev_valid_ && !KeyIsAfterNode(key, prev_[0]->NoBarrier_Next(0)) && | 459 | 99.2M | (prev_[0] == head_ || KeyIsAfterNode(key, prev_[0]))) { | 460 | 18.4E | DCHECK(prev_[0] != head_ || (prev_height_ == 1 && GetMaxHeight() == 1)) | 461 | 18.4E | << "prev_height_: " << prev_height_ << ", GetMaxHeight(): " << GetMaxHeight(); | 462 | | | 463 | | // Outside of this method prev_[1..max_height_] is the predecessor | 464 | | // of prev_[0], and prev_height_ refers to prev_[0]. Inside Insert | 465 | | // prev_[0..max_height - 1] is the predecessor of key. Switch from | 466 | | // the external state to the internal | 467 | 128M | for (int i = 1; i < prev_height_; i++) { | 468 | 32.2M | prev_[i] = prev_[0]; | 469 | 32.2M | } | 470 | 17.5M | } else { | 471 | | // TODO(opt): we could use a NoBarrier predecessor search as an | 472 | | // optimization for architectures where memory_order_acquire needs | 473 | | // a synchronization instruction. Doesn't matter on x86 | 474 | 17.5M | FindLessThan(key, prev_); | 475 | 17.5M | prev_valid_ = true; | 476 | 17.5M | } | 477 | | | 478 | | // Our data structure does not allow duplicate insertion | 479 | 114M | DCHECK(prev_[0]->Next(0) == nullptr || !Equal(key, prev_[0]->Next(0)->key)); | 480 | 114M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE13PrepareInsertES4_ Line | Count | Source | 456 | 7.36M | void SkipListBase<Key, Comparator, NodeType>::PrepareInsert(Key key) { | 457 | | // fast path for sequential insertion | 458 | 7.36M | if (prev_valid_ && !KeyIsAfterNode(key, prev_[0]->NoBarrier_Next(0)) && | 459 | 7.36M | (prev_[0] == head_ || KeyIsAfterNode(key, prev_[0]))) { | 460 | 18.4E | DCHECK(prev_[0] != head_ || (prev_height_ == 1 && GetMaxHeight() == 1)) | 461 | 18.4E | << "prev_height_: " << prev_height_ << ", GetMaxHeight(): " << GetMaxHeight(); | 462 | | | 463 | | // Outside of this method prev_[1..max_height_] is the predecessor | 464 | | // of prev_[0], and prev_height_ refers to prev_[0]. Inside Insert | 465 | | // prev_[0..max_height - 1] is the predecessor of key. Switch from | 466 | | // the external state to the internal | 467 | 9.57M | for (int i = 1; i < prev_height_; i++) { | 468 | 2.21M | prev_[i] = prev_[0]; | 469 | 2.21M | } | 470 | 2.45k | } else { | 471 | | // TODO(opt): we could use a NoBarrier predecessor search as an | 472 | | // optimization for architectures where memory_order_acquire needs | 473 | | // a synchronization instruction. Doesn't matter on x86 | 474 | 2.45k | FindLessThan(key, prev_); | 475 | 2.45k | prev_valid_ = true; | 476 | 2.45k | } | 477 | | | 478 | | // Our data structure does not allow duplicate insertion | 479 | 7.36M | DCHECK(prev_[0]->Next(0) == nullptr || !Equal(key, prev_[0]->Next(0)->key)); | 480 | 7.36M | } |
|
481 | | |
482 | | template<class Key, class Comparator, class NodeType> |
483 | | SkipListBase<Key, Comparator, NodeType>::SkipListBase( |
484 | | const Comparator cmp, Allocator* allocator, int32_t max_height, int32_t branching_factor) |
485 | | : allocator_(allocator), |
486 | | kMaxHeight_(max_height), |
487 | | kBranching_(branching_factor), |
488 | | kScaledInverseBranching_((Random::kMaxNext + 1) / kBranching_), |
489 | | compare_(cmp), |
490 | | head_(Node::CreateHead(allocator, max_height)), |
491 | | max_height_(1), |
492 | 1.14M | prev_height_(1) { |
493 | 1.14M | DCHECK(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height)); |
494 | 1.14M | DCHECK(branching_factor > 0 && |
495 | 1.14M | kBranching_ == static_cast<uint32_t>(branching_factor)); |
496 | 1.14M | DCHECK_GT(kScaledInverseBranching_, 0); |
497 | | // Allocate the prev_ Node* array, directly from the passed-in allocator. |
498 | | // prev_ does not need to be freed, as its life cycle is tied up with |
499 | | // the allocator as a whole. |
500 | 1.14M | prev_ = reinterpret_cast<Node**>(allocator_->AllocateAligned(sizeof(Node*) * kMaxHeight_)); |
501 | 14.3M | for (int i = 0; i < kMaxHeight_; i++) { |
502 | 13.2M | head_->SetNext(i, nullptr); |
503 | 13.2M | prev_[i] = head_; |
504 | 13.2M | } |
505 | 1.14M | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEEC2ES3_PNS_9AllocatorEii Line | Count | Source | 492 | 5.20k | prev_height_(1) { | 493 | 5.20k | DCHECK(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height)); | 494 | 5.20k | DCHECK(branching_factor > 0 && | 495 | 5.20k | kBranching_ == static_cast<uint32_t>(branching_factor)); | 496 | 5.20k | DCHECK_GT(kScaledInverseBranching_, 0); | 497 | | // Allocate the prev_ Node* array, directly from the passed-in allocator. | 498 | | // prev_ does not need to be freed, as its life cycle is tied up with | 499 | | // the allocator as a whole. | 500 | 5.20k | prev_ = reinterpret_cast<Node**>(allocator_->AllocateAligned(sizeof(Node*) * kMaxHeight_)); | 501 | 67.6k | for (int i = 0; i < kMaxHeight_; i++) { | 502 | 62.4k | head_->SetNext(i, nullptr); | 503 | 62.4k | prev_[i] = head_; | 504 | 62.4k | } | 505 | 5.20k | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEEC2ES8_PNS_9AllocatorEii Line | Count | Source | 492 | 64.7k | prev_height_(1) { | 493 | 64.7k | DCHECK(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height)); | 494 | 64.7k | DCHECK(branching_factor > 0 && | 495 | 64.7k | kBranching_ == static_cast<uint32_t>(branching_factor)); | 496 | 64.7k | DCHECK_GT(kScaledInverseBranching_, 0); | 497 | | // Allocate the prev_ Node* array, directly from the passed-in allocator. | 498 | | // prev_ does not need to be freed, as its life cycle is tied up with | 499 | | // the allocator as a whole. | 500 | 64.7k | prev_ = reinterpret_cast<Node**>(allocator_->AllocateAligned(sizeof(Node*) * kMaxHeight_)); | 501 | 334k | for (int i = 0; i < kMaxHeight_; i++) { | 502 | 269k | head_->SetNext(i, nullptr); | 503 | 269k | prev_[i] = head_; | 504 | 269k | } | 505 | 64.7k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEEC2ES6_PNS_9AllocatorEii Line | Count | Source | 492 | 332k | prev_height_(1) { | 493 | 332k | DCHECK(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height)); | 494 | 332k | DCHECK(branching_factor > 0 && | 495 | 332k | kBranching_ == static_cast<uint32_t>(branching_factor)); | 496 | 332k | DCHECK_GT(kScaledInverseBranching_, 0); | 497 | | // Allocate the prev_ Node* array, directly from the passed-in allocator. | 498 | | // prev_ does not need to be freed, as its life cycle is tied up with | 499 | | // the allocator as a whole. | 500 | 332k | prev_ = reinterpret_cast<Node**>(allocator_->AllocateAligned(sizeof(Node*) * kMaxHeight_)); | 501 | 4.31M | for (int i = 0; i < kMaxHeight_; i++) { | 502 | 3.98M | head_->SetNext(i, nullptr); | 503 | 3.98M | prev_[i] = head_; | 504 | 3.98M | } | 505 | 332k | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEEC2ES7_PNS_9AllocatorEii Line | Count | Source | 492 | 744k | prev_height_(1) { | 493 | 744k | DCHECK(max_height > 0 && kMaxHeight_ == static_cast<uint32_t>(max_height)); | 494 | 744k | DCHECK(branching_factor > 0 && | 495 | 744k | kBranching_ == static_cast<uint32_t>(branching_factor)); | 496 | 744k | DCHECK_GT(kScaledInverseBranching_, 0); | 497 | | // Allocate the prev_ Node* array, directly from the passed-in allocator. | 498 | | // prev_ does not need to be freed, as its life cycle is tied up with | 499 | | // the allocator as a whole. | 500 | 744k | prev_ = reinterpret_cast<Node**>(allocator_->AllocateAligned(sizeof(Node*) * kMaxHeight_)); | 501 | 9.64M | for (int i = 0; i < kMaxHeight_; i++) { | 502 | 8.89M | head_->SetNext(i, nullptr); | 503 | 8.89M | prev_[i] = head_; | 504 | 8.89M | } | 505 | 744k | } |
|
506 | | |
507 | | template<class Key, class Comparator, class NodeType> |
508 | 127M | void SkipListBase<Key, Comparator, NodeType>::CompleteInsert(NodeType* node, int height) { |
509 | 127M | DCHECK_GT(height, 0); |
510 | 127M | DCHECK_LE(height, kMaxHeight_); |
511 | | |
512 | 127M | if (height > GetMaxHeight()) { |
513 | 2.39M | for (int i = GetMaxHeight(); i < height; i++) { |
514 | 1.36M | prev_[i] = head_; |
515 | 1.36M | } |
516 | | |
517 | | // It is ok to mutate max_height_ without any synchronization |
518 | | // with concurrent readers. A concurrent reader that observes |
519 | | // the new value of max_height_ will see either the old value of |
520 | | // new level pointers from head_ (nullptr), or a new value set in |
521 | | // the loop below. In the former case the reader will |
522 | | // immediately drop to the next level since nullptr sorts after all |
523 | | // keys. In the latter case the reader will use the new node. |
524 | 1.02M | max_height_.store(height, std::memory_order_relaxed); |
525 | 1.02M | } |
526 | | |
527 | 297M | for (int i = 0; i < height; i++) { |
528 | | // NoBarrier_SetNext() suffices since we will add a barrier when |
529 | | // we publish a pointer to "x" in prev[i]. |
530 | 170M | node->NoBarrier_SetNext(i, prev_[i]->NoBarrier_Next(i)); |
531 | 170M | prev_[i]->SetNext(i, node); |
532 | 170M | } |
533 | 127M | prev_[0] = node; |
534 | 127M | prev_height_ = height; |
535 | 127M | } Unexecuted instantiation: _ZN7rocksdb12SkipListBaseIPKcNS_14TestComparatorENS_30SingleWriterInlineSkipListNodeEE14CompleteInsertEPS4_i _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE14CompleteInsertEPS5_i Line | Count | Source | 508 | 5.08M | void SkipListBase<Key, Comparator, NodeType>::CompleteInsert(NodeType* node, int height) { | 509 | 5.08M | DCHECK_GT(height, 0); | 510 | 5.08M | DCHECK_LE(height, kMaxHeight_); | 511 | | | 512 | 5.08M | if (height > GetMaxHeight()) { | 513 | 44.1k | for (int i = GetMaxHeight(); i < height; i++) { | 514 | 25.2k | prev_[i] = head_; | 515 | 25.2k | } | 516 | | | 517 | | // It is ok to mutate max_height_ without any synchronization | 518 | | // with concurrent readers. A concurrent reader that observes | 519 | | // the new value of max_height_ will see either the old value of | 520 | | // new level pointers from head_ (nullptr), or a new value set in | 521 | | // the loop below. In the former case the reader will | 522 | | // immediately drop to the next level since nullptr sorts after all | 523 | | // keys. In the latter case the reader will use the new node. | 524 | 18.8k | max_height_.store(height, std::memory_order_relaxed); | 525 | 18.8k | } | 526 | | | 527 | 11.8M | for (int i = 0; i < height; i++) { | 528 | | // NoBarrier_SetNext() suffices since we will add a barrier when | 529 | | // we publish a pointer to "x" in prev[i]. | 530 | 6.77M | node->NoBarrier_SetNext(i, prev_[i]->NoBarrier_Next(i)); | 531 | 6.77M | prev_[i]->SetNext(i, node); | 532 | 6.77M | } | 533 | 5.08M | prev_[0] = node; | 534 | 5.08M | prev_height_ = height; | 535 | 5.08M | } |
_ZN7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE14CompleteInsertEPSA_i Line | Count | Source | 508 | 1.03M | void SkipListBase<Key, Comparator, NodeType>::CompleteInsert(NodeType* node, int height) { | 509 | 1.03M | DCHECK_GT(height, 0); | 510 | 1.03M | DCHECK_LE(height, kMaxHeight_); | 511 | | | 512 | 1.03M | if (height > GetMaxHeight()) { | 513 | 58.0k | for (int i = GetMaxHeight(); i < height; i++) { | 514 | 32.9k | prev_[i] = head_; | 515 | 32.9k | } | 516 | | | 517 | | // It is ok to mutate max_height_ without any synchronization | 518 | | // with concurrent readers. A concurrent reader that observes | 519 | | // the new value of max_height_ will see either the old value of | 520 | | // new level pointers from head_ (nullptr), or a new value set in | 521 | | // the loop below. In the former case the reader will | 522 | | // immediately drop to the next level since nullptr sorts after all | 523 | | // keys. In the latter case the reader will use the new node. | 524 | 25.0k | max_height_.store(height, std::memory_order_relaxed); | 525 | 25.0k | } | 526 | | | 527 | 2.40M | for (int i = 0; i < height; i++) { | 528 | | // NoBarrier_SetNext() suffices since we will add a barrier when | 529 | | // we publish a pointer to "x" in prev[i]. | 530 | 1.37M | node->NoBarrier_SetNext(i, prev_[i]->NoBarrier_Next(i)); | 531 | 1.37M | prev_[i]->SetNext(i, node); | 532 | 1.37M | } | 533 | 1.03M | prev_[0] = node; | 534 | 1.03M | prev_height_ = height; | 535 | 1.03M | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE14CompleteInsertEPS7_i Line | Count | Source | 508 | 114M | void SkipListBase<Key, Comparator, NodeType>::CompleteInsert(NodeType* node, int height) { | 509 | 114M | DCHECK_GT(height, 0); | 510 | 114M | DCHECK_LE(height, kMaxHeight_); | 511 | | | 512 | 114M | if (height > GetMaxHeight()) { | 513 | 203k | for (int i = GetMaxHeight(); i < height; i++) { | 514 | 116k | prev_[i] = head_; | 515 | 116k | } | 516 | | | 517 | | // It is ok to mutate max_height_ without any synchronization | 518 | | // with concurrent readers. A concurrent reader that observes | 519 | | // the new value of max_height_ will see either the old value of | 520 | | // new level pointers from head_ (nullptr), or a new value set in | 521 | | // the loop below. In the former case the reader will | 522 | | // immediately drop to the next level since nullptr sorts after all | 523 | | // keys. In the latter case the reader will use the new node. | 524 | 87.4k | max_height_.store(height, std::memory_order_relaxed); | 525 | 87.4k | } | 526 | | | 527 | 266M | for (int i = 0; i < height; i++) { | 528 | | // NoBarrier_SetNext() suffices since we will add a barrier when | 529 | | // we publish a pointer to "x" in prev[i]. | 530 | 152M | node->NoBarrier_SetNext(i, prev_[i]->NoBarrier_Next(i)); | 531 | 152M | prev_[i]->SetNext(i, node); | 532 | 152M | } | 533 | 114M | prev_[0] = node; | 534 | 114M | prev_height_ = height; | 535 | 114M | } |
_ZN7rocksdb12SkipListBaseIRKPNS_20WriteBatchIndexEntryERKNS_25WriteBatchEntryComparatorENS_12SkipListNodeIS2_EEE14CompleteInsertEPS9_i Line | Count | Source | 508 | 7.36M | void SkipListBase<Key, Comparator, NodeType>::CompleteInsert(NodeType* node, int height) { | 509 | 7.36M | DCHECK_GT(height, 0); | 510 | 7.36M | DCHECK_LE(height, kMaxHeight_); | 511 | | | 512 | 7.36M | if (height > GetMaxHeight()) { | 513 | 2.08M | for (int i = GetMaxHeight(); i < height; i++) { | 514 | 1.19M | prev_[i] = head_; | 515 | 1.19M | } | 516 | | | 517 | | // It is ok to mutate max_height_ without any synchronization | 518 | | // with concurrent readers. A concurrent reader that observes | 519 | | // the new value of max_height_ will see either the old value of | 520 | | // new level pointers from head_ (nullptr), or a new value set in | 521 | | // the loop below. In the former case the reader will | 522 | | // immediately drop to the next level since nullptr sorts after all | 523 | | // keys. In the latter case the reader will use the new node. | 524 | 893k | max_height_.store(height, std::memory_order_relaxed); | 525 | 893k | } | 526 | | | 527 | 17.1M | for (int i = 0; i < height; i++) { | 528 | | // NoBarrier_SetNext() suffices since we will add a barrier when | 529 | | // we publish a pointer to "x" in prev[i]. | 530 | 9.80M | node->NoBarrier_SetNext(i, prev_[i]->NoBarrier_Next(i)); | 531 | 9.80M | prev_[i]->SetNext(i, node); | 532 | 9.80M | } | 533 | 7.36M | prev_[0] = node; | 534 | 7.36M | prev_height_ = height; | 535 | 7.36M | } |
|
536 | | |
537 | | template<class Key, class Comparator, class NodeType> |
538 | 566k | bool SkipListBase<Key, Comparator, NodeType>::Contains(Key key) const { |
539 | 566k | Node* x = FindGreaterOrEqual(key); |
540 | 566k | return x != nullptr && Equal(key, x->key); |
541 | 566k | } _ZNK7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE8ContainsES2_ Line | Count | Source | 538 | 5.00k | bool SkipListBase<Key, Comparator, NodeType>::Contains(Key key) const { | 539 | 5.00k | Node* x = FindGreaterOrEqual(key); | 540 | 5.00k | return x != nullptr && Equal(key, x->key); | 541 | 5.00k | } |
_ZNK7rocksdb12SkipListBaseIRKPKcRKNS_11MemTableRep13KeyComparatorENS_12SkipListNodeIS2_EEE8ContainsES4_ Line | Count | Source | 538 | 561k | bool SkipListBase<Key, Comparator, NodeType>::Contains(Key key) const { | 539 | 561k | Node* x = FindGreaterOrEqual(key); | 540 | 561k | return x != nullptr && Equal(key, x->key); | 541 | 561k | } |
Unexecuted instantiation: _ZNK7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE8ContainsES2_ |
542 | | |
543 | | template<class Key, class Comparator, class NodeType> |
544 | 56.4M | bool SkipListBase<Key, Comparator, NodeType>::Erase(Key key, Comparator cmp) { |
545 | 56.4M | auto prev = static_cast<Node**>(alloca(sizeof(Node*) * kMaxHeight_)); |
546 | 56.4M | auto node = FindLessThan(key, prev); |
547 | 56.4M | node = node->Next(0); |
548 | 56.4M | if (node == nullptr || cmp(key, node->key) != 0) { |
549 | 975k | return false; |
550 | 975k | } |
551 | | |
552 | 547M | for (int level = max_height_; --level >= 0;) { |
553 | 492M | if (prev[level]->NoBarrier_Next(level) == node) { |
554 | 74.0M | prev[level]->SetNext(level, node->Next(level)); |
555 | 74.0M | } |
556 | 492M | } |
557 | | |
558 | 55.5M | prev_valid_ = false; |
559 | | |
560 | 55.5M | return true; |
561 | 55.5M | } _ZN7rocksdb12SkipListBaseIRKyNS_14TestComparatorENS_12SkipListNodeIyEEE5EraseES2_S3_ Line | Count | Source | 544 | 67.7k | bool SkipListBase<Key, Comparator, NodeType>::Erase(Key key, Comparator cmp) { | 545 | 67.7k | auto prev = static_cast<Node**>(alloca(sizeof(Node*) * kMaxHeight_)); | 546 | 67.7k | auto node = FindLessThan(key, prev); | 547 | 67.7k | node = node->Next(0); | 548 | 67.7k | if (node == nullptr || cmp(key, node->key) != 0) { | 549 | 0 | return false; | 550 | 0 | } | 551 | | | 552 | 381k | for (int level = max_height_; --level >= 0;) { | 553 | 314k | if (prev[level]->NoBarrier_Next(level) == node) { | 554 | 90.4k | prev[level]->SetNext(level, node->Next(level)); | 555 | 90.4k | } | 556 | 314k | } | 557 | | | 558 | 67.7k | prev_valid_ = false; | 559 | | | 560 | 67.7k | return true; | 561 | 67.7k | } |
_ZN7rocksdb12SkipListBaseIPKcRKNS_11MemTableRep13KeyComparatorENS_30SingleWriterInlineSkipListNodeEE5EraseES2_S6_ Line | Count | Source | 544 | 56.4M | bool SkipListBase<Key, Comparator, NodeType>::Erase(Key key, Comparator cmp) { | 545 | 56.4M | auto prev = static_cast<Node**>(alloca(sizeof(Node*) * kMaxHeight_)); | 546 | 56.4M | auto node = FindLessThan(key, prev); | 547 | 56.4M | node = node->Next(0); | 548 | 56.4M | if (node == nullptr || cmp(key, node->key) != 0) { | 549 | 975k | return false; | 550 | 975k | } | 551 | | | 552 | 547M | for (int level = max_height_; --level >= 0;) { | 553 | 492M | if (prev[level]->NoBarrier_Next(level) == node) { | 554 | 73.9M | prev[level]->SetNext(level, node->Next(level)); | 555 | 73.9M | } | 556 | 492M | } | 557 | | | 558 | 55.4M | prev_valid_ = false; | 559 | | | 560 | 55.4M | return true; | 561 | 55.4M | } |
|
562 | | |
563 | | struct SingleWriterInlineSkipListNode { |
564 | | std::atomic<SingleWriterInlineSkipListNode*> next_[1]; |
565 | | char key[0]; |
566 | | |
567 | 114M | explicit SingleWriterInlineSkipListNode(int height) { |
568 | 114M | memcpy(static_cast<void*>(&next_[0]), &height, sizeof(int)); |
569 | 114M | } |
570 | | |
571 | | // Accessors/mutators for links. Wrapped in methods so we can add |
572 | | // the appropriate barriers as necessary, and perform the necessary |
573 | | // addressing trickery for storing links below the Node in memory. |
574 | 3.54G | ATTRIBUTE_NO_SANITIZE_UNDEFINED SingleWriterInlineSkipListNode* Next(int n) { |
575 | 3.54G | DCHECK_GE(n, 0); |
576 | | // Use an 'acquire load' so that we observe a fully initialized |
577 | | // version of the returned Node. |
578 | 3.54G | return (next_[-n].load(std::memory_order_acquire)); |
579 | 3.54G | } |
580 | | |
581 | 230M | ATTRIBUTE_NO_SANITIZE_UNDEFINED void SetNext(int n, SingleWriterInlineSkipListNode* x) { |
582 | 230M | DCHECK_GE(n, 0); |
583 | | // Use a 'release store' so that anybody who reads through this |
584 | | // pointer observes a fully initialized version of the inserted node. |
585 | 230M | next_[-n].store(x, std::memory_order_release); |
586 | 230M | } |
587 | | |
588 | | // No-barrier variants that can be safely used in a few locations. |
589 | 757M | ATTRIBUTE_NO_SANITIZE_UNDEFINED SingleWriterInlineSkipListNode* NoBarrier_Next(int n) { |
590 | 757M | DCHECK_GE(n, 0); |
591 | 757M | return next_[-n].load(std::memory_order_relaxed); |
592 | 757M | } |
593 | | |
594 | 152M | ATTRIBUTE_NO_SANITIZE_UNDEFINED void NoBarrier_SetNext(int n, SingleWriterInlineSkipListNode* x) { |
595 | 152M | DCHECK_GE(n, 0); |
596 | 152M | next_[-n].store(x, std::memory_order_relaxed); |
597 | 152M | } |
598 | | |
599 | 114M | int UnstashHeight() const { |
600 | 114M | int rv; |
601 | 114M | memcpy(&rv, &next_[0], sizeof(int)); |
602 | 114M | return rv; |
603 | 114M | } |
604 | | |
605 | 114M | static SingleWriterInlineSkipListNode* Create(Allocator* allocator, size_t key_size, int height) { |
606 | 114M | auto prefix = sizeof(std::atomic<SingleWriterInlineSkipListNode*>) * (height - 1); |
607 | | |
608 | | // prefix is space for the height - 1 pointers that we store before |
609 | | // the Node instance (next_[-(height - 1) .. -1]). Node starts at |
610 | | // raw + prefix, and holds the bottom-mode (level 0) skip list pointer |
611 | | // next_[0]. key_size is the bytes for the key. |
612 | 114M | char* mem = allocator->AllocateAligned( |
613 | 114M | prefix + offsetof(SingleWriterInlineSkipListNode, key) + key_size); |
614 | 114M | return new (mem + prefix) SingleWriterInlineSkipListNode(height); |
615 | 114M | } |
616 | | |
617 | 332k | static SingleWriterInlineSkipListNode* CreateHead(Allocator* allocator, int height) { |
618 | 332k | return Create(allocator, 0 /* key_size */, height); |
619 | 332k | } |
620 | | }; |
621 | | |
622 | | // Skip list designed for using variable size byte arrays as a key. |
623 | | // Node has variable size and key is copied directly to the node. |
624 | | // Please note thread safety at top of this file. |
625 | | template <class Comparator> |
626 | | class SingleWriterInlineSkipList : |
627 | | public SkipListBase<const char*, Comparator, SingleWriterInlineSkipListNode> { |
628 | | private: |
629 | | typedef SkipListBase<const char*, Comparator, SingleWriterInlineSkipListNode> Base; |
630 | | |
631 | | public: |
632 | | template<class... Args> |
633 | | explicit SingleWriterInlineSkipList(Args&&... args) |
634 | 332k | : Base(std::forward<Args>(args)...) { |
635 | 332k | } Unexecuted instantiation: _ZN7rocksdb26SingleWriterInlineSkipListINS_14TestComparatorEEC2IJRS1_PNS_5ArenaEEEEDpOT_ _ZN7rocksdb26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEC2IJS4_RPNS_17MemTableAllocatorEEEEDpOT_ Line | Count | Source | 634 | 332k | : Base(std::forward<Args>(args)...) { | 635 | 332k | } |
|
636 | | |
637 | 114M | char* AllocateKey(size_t key_size) { |
638 | 114M | return SingleWriterInlineSkipListNode::Create( |
639 | 114M | Base::allocator_, key_size, Base::RandomHeight())->key; |
640 | 114M | } Unexecuted instantiation: _ZN7rocksdb26SingleWriterInlineSkipListINS_14TestComparatorEE11AllocateKeyEm _ZN7rocksdb26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEE11AllocateKeyEm Line | Count | Source | 637 | 114M | char* AllocateKey(size_t key_size) { | 638 | 114M | return SingleWriterInlineSkipListNode::Create( | 639 | 114M | Base::allocator_, key_size, Base::RandomHeight())->key; | 640 | 114M | } |
|
641 | | |
642 | 114M | void Insert(const char* key) { |
643 | 114M | Base::PrepareInsert(key); |
644 | 114M | auto node = reinterpret_cast<SingleWriterInlineSkipListNode*>( |
645 | 114M | const_cast<char*>(key) - offsetof(SingleWriterInlineSkipListNode, key)); |
646 | 114M | Base::CompleteInsert(node, node->UnstashHeight()); |
647 | 114M | } Unexecuted instantiation: _ZN7rocksdb26SingleWriterInlineSkipListINS_14TestComparatorEE6InsertEPKc _ZN7rocksdb26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEE6InsertEPKc Line | Count | Source | 642 | 114M | void Insert(const char* key) { | 643 | 114M | Base::PrepareInsert(key); | 644 | 114M | auto node = reinterpret_cast<SingleWriterInlineSkipListNode*>( | 645 | 114M | const_cast<char*>(key) - offsetof(SingleWriterInlineSkipListNode, key)); | 646 | 114M | Base::CompleteInsert(node, node->UnstashHeight()); | 647 | 114M | } |
|
648 | | |
649 | 0 | void InsertConcurrently(const char* key) { |
650 | 0 | LOG(FATAL) << "Concurrent insert is not supported"; |
651 | 0 | } |
652 | | }; |
653 | | |
654 | | } // namespace rocksdb |
655 | | |
656 | | #endif // YB_ROCKSDB_DB_SKIPLIST_H |