/Users/deen/code/yugabyte-db/src/yb/rocksdb/memtable/skiplistrep.cc
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 | | |
21 | | #include "yb/rocksdb/db/inlineskiplist.h" |
22 | | #include "yb/rocksdb/db/skiplist.h" |
23 | | |
24 | | #include "yb/rocksdb/db/memtable.h" |
25 | | #include "yb/rocksdb/memtablerep.h" |
26 | | #include "yb/rocksdb/util/arena.h" |
27 | | |
28 | | namespace rocksdb { |
29 | | namespace { |
30 | | |
31 | | template <class SkipListImpl> |
32 | | class SkipListRep : public MemTableRep { |
33 | | SkipListImpl skip_list_; |
34 | | const MemTableRep::KeyComparator& cmp_; |
35 | | const SliceTransform* transform_; |
36 | | const size_t lookahead_; |
37 | | |
38 | | friend class LookaheadIterator; |
39 | | public: |
40 | | explicit SkipListRep(const MemTableRep::KeyComparator& compare, |
41 | | MemTableAllocator* allocator, |
42 | | const SliceTransform* transform, const size_t lookahead) |
43 | | : MemTableRep(allocator), skip_list_(compare, allocator), cmp_(compare), |
44 | 378k | transform_(transform), lookahead_(lookahead) { |
45 | 378k | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEEC2ES6_PNS_17MemTableAllocatorEPKNS_14SliceTransformEm Line | Count | Source | 44 | 45.8k | transform_(transform), lookahead_(lookahead) { | 45 | 45.8k | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEEC2ES6_PNS_17MemTableAllocatorEPKNS_14SliceTransformEm Line | Count | Source | 44 | 332k | transform_(transform), lookahead_(lookahead) { | 45 | 332k | } |
|
46 | | |
47 | 150M | KeyHandle Allocate(const size_t len, char** buf) override { |
48 | 150M | *buf = skip_list_.AllocateKey(len); |
49 | 150M | return static_cast<KeyHandle>(*buf); |
50 | 150M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8AllocateEmPPc Line | Count | Source | 47 | 35.8M | KeyHandle Allocate(const size_t len, char** buf) override { | 48 | 35.8M | *buf = skip_list_.AllocateKey(len); | 49 | 35.8M | return static_cast<KeyHandle>(*buf); | 50 | 35.8M | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8AllocateEmPPc Line | Count | Source | 47 | 114M | KeyHandle Allocate(const size_t len, char** buf) override { | 48 | 114M | *buf = skip_list_.AllocateKey(len); | 49 | 114M | return static_cast<KeyHandle>(*buf); | 50 | 114M | } |
|
51 | | |
52 | | // Insert key into the list. |
53 | | // REQUIRES: nothing that compares equal to key is currently in the list. |
54 | 149M | void Insert(KeyHandle handle) override { |
55 | 149M | skip_list_.Insert(static_cast<char*>(handle)); |
56 | 149M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE6InsertEPv Line | Count | Source | 54 | 35.3M | void Insert(KeyHandle handle) override { | 55 | 35.3M | skip_list_.Insert(static_cast<char*>(handle)); | 56 | 35.3M | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE6InsertEPv Line | Count | Source | 54 | 114M | void Insert(KeyHandle handle) override { | 55 | 114M | skip_list_.Insert(static_cast<char*>(handle)); | 56 | 114M | } |
|
57 | | |
58 | 521k | void InsertConcurrently(KeyHandle handle) override { |
59 | 521k | skip_list_.InsertConcurrently(static_cast<char*>(handle)); |
60 | 521k | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE18InsertConcurrentlyEPv Line | Count | Source | 58 | 521k | void InsertConcurrently(KeyHandle handle) override { | 59 | 521k | skip_list_.InsertConcurrently(static_cast<char*>(handle)); | 60 | 521k | } |
Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE18InsertConcurrentlyEPv |
61 | | |
62 | 56.4M | bool Erase(KeyHandle handle, const MemTableRep::KeyComparator& comparator) override { |
63 | 56.4M | return skip_list_.Erase(static_cast<char*>(handle), comparator); |
64 | 56.4M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE5EraseEPvS6_ Line | Count | Source | 62 | 173 | bool Erase(KeyHandle handle, const MemTableRep::KeyComparator& comparator) override { | 63 | 173 | return skip_list_.Erase(static_cast<char*>(handle), comparator); | 64 | 173 | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE5EraseEPvS6_ Line | Count | Source | 62 | 56.4M | bool Erase(KeyHandle handle, const MemTableRep::KeyComparator& comparator) override { | 63 | 56.4M | return skip_list_.Erase(static_cast<char*>(handle), comparator); | 64 | 56.4M | } |
|
65 | | |
66 | | // Returns true iff an entry that compares equal to key is in the list. |
67 | 0 | bool Contains(const char* key) const override { |
68 | 0 | return skip_list_.Contains(key); |
69 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8ContainsEPKc Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8ContainsEPKc |
70 | | |
71 | 91.4M | size_t ApproximateMemoryUsage() override { |
72 | | // All memory is allocated through allocator; nothing to report here |
73 | 91.4M | return 0; |
74 | 91.4M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE22ApproximateMemoryUsageEv Line | Count | Source | 71 | 30.4M | size_t ApproximateMemoryUsage() override { | 72 | | // All memory is allocated through allocator; nothing to report here | 73 | 30.4M | return 0; | 74 | 30.4M | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE22ApproximateMemoryUsageEv Line | Count | Source | 71 | 61.0M | size_t ApproximateMemoryUsage() override { | 72 | | // All memory is allocated through allocator; nothing to report here | 73 | 61.0M | return 0; | 74 | 61.0M | } |
|
75 | | |
76 | | virtual void Get(const LookupKey& k, void* callback_args, |
77 | | bool (*callback_func)(void* arg, |
78 | 15.7M | const char* entry)) override { |
79 | 15.7M | SkipListRep::Iterator iter(&skip_list_); |
80 | 15.7M | Slice dummy_slice; |
81 | 15.7M | for (iter.Seek(dummy_slice, k.memtable_key().cdata()); |
82 | 15.7M | iter.Valid() && callback_func(callback_args, iter.key()); |
83 | 44.3k | iter.Next()) { |
84 | 44.3k | } |
85 | 15.7M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE3GetERKNS_9LookupKeyEPvPFbSC_PKcE Line | Count | Source | 78 | 15.7M | const char* entry)) override { | 79 | 15.7M | SkipListRep::Iterator iter(&skip_list_); | 80 | 15.7M | Slice dummy_slice; | 81 | 15.7M | for (iter.Seek(dummy_slice, k.memtable_key().cdata()); | 82 | 15.7M | iter.Valid() && callback_func(callback_args, iter.key()); | 83 | 44.3k | iter.Next()) { | 84 | 44.3k | } | 85 | 15.7M | } |
Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE3GetERKNS_9LookupKeyEPvPFbSC_PKcE |
86 | | |
87 | | uint64_t ApproximateNumEntries(const Slice& start_ikey, |
88 | 22 | const Slice& end_ikey) override { |
89 | 22 | std::string tmp; |
90 | 22 | uint64_t start_count = |
91 | 22 | skip_list_.EstimateCount(EncodeKey(&tmp, start_ikey)); |
92 | 22 | uint64_t end_count = skip_list_.EstimateCount(EncodeKey(&tmp, end_ikey)); |
93 | 22 | return (end_count >= start_count) ? (end_count - start_count) : 0; |
94 | 22 | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE21ApproximateNumEntriesERKN2yb5SliceESC_ Line | Count | Source | 88 | 22 | const Slice& end_ikey) override { | 89 | 22 | std::string tmp; | 90 | 22 | uint64_t start_count = | 91 | 22 | skip_list_.EstimateCount(EncodeKey(&tmp, start_ikey)); | 92 | 22 | uint64_t end_count = skip_list_.EstimateCount(EncodeKey(&tmp, end_ikey)); | 93 | 22 | return (end_count >= start_count) ? (end_count - start_count) : 0; | 94 | 22 | } |
Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE21ApproximateNumEntriesERKN2yb5SliceESC_ |
95 | | |
96 | 360k | ~SkipListRep() override { } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEED2Ev Line | Count | Source | 96 | 45.8k | ~SkipListRep() override { } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEED2Ev Line | Count | Source | 96 | 314k | ~SkipListRep() override { } |
|
97 | | |
98 | | // Iteration over the contents of a skip list |
99 | | class Iterator : public MemTableRep::Iterator { |
100 | | typename SkipListImpl::Iterator iter_; |
101 | | |
102 | | public: |
103 | | // Initialize an iterator over the specified list. |
104 | | // The returned iterator is not valid. |
105 | | explicit Iterator(const SkipListImpl* list) |
106 | 31.2M | : iter_(list) {} skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8IteratorC2EPKS7_ Line | Count | Source | 106 | 15.8M | : iter_(list) {} |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8IteratorC2EPKS7_ Line | Count | Source | 106 | 15.4M | : iter_(list) {} |
|
107 | | |
108 | 31.2M | ~Iterator() override { } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8IteratorD2Ev Line | Count | Source | 108 | 15.8M | ~Iterator() override { } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8IteratorD2Ev Line | Count | Source | 108 | 15.4M | ~Iterator() override { } |
|
109 | | |
110 | | // Returns true iff the iterator is positioned at a valid node. |
111 | 557M | bool Valid() const override { |
112 | 557M | return iter_.Valid(); |
113 | 557M | } skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator5ValidEv Line | Count | Source | 111 | 51.2M | bool Valid() const override { | 112 | 51.2M | return iter_.Valid(); | 113 | 51.2M | } |
skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator5ValidEv Line | Count | Source | 111 | 505M | bool Valid() const override { | 112 | 505M | return iter_.Valid(); | 113 | 505M | } |
|
114 | | |
115 | | // Returns the key at the current position. |
116 | | // REQUIRES: Valid() |
117 | 1.05G | const char* key() const override { |
118 | 1.05G | return iter_.key(); |
119 | 1.05G | } skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator3keyEv Line | Count | Source | 117 | 86.8M | const char* key() const override { | 118 | 86.8M | return iter_.key(); | 119 | 86.8M | } |
skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator3keyEv Line | Count | Source | 117 | 967M | const char* key() const override { | 118 | 967M | return iter_.key(); | 119 | 967M | } |
|
120 | | |
121 | | // Advances to the next position. |
122 | | // REQUIRES: Valid() |
123 | 472M | void Next() override { |
124 | 472M | iter_.Next(); |
125 | 472M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4NextEv Line | Count | Source | 123 | 33.8M | void Next() override { | 124 | 33.8M | iter_.Next(); | 125 | 33.8M | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4NextEv Line | Count | Source | 123 | 438M | void Next() override { | 124 | 438M | iter_.Next(); | 125 | 438M | } |
|
126 | | |
127 | | // Advances to the previous position. |
128 | | // REQUIRES: Valid() |
129 | 1.16M | void Prev() override { |
130 | 1.16M | iter_.Prev(); |
131 | 1.16M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4PrevEv Line | Count | Source | 129 | 820k | void Prev() override { | 130 | 820k | iter_.Prev(); | 131 | 820k | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4PrevEv Line | Count | Source | 129 | 349k | void Prev() override { | 130 | 349k | iter_.Prev(); | 131 | 349k | } |
|
132 | | |
133 | | // Advance to the first entry with a key >= target |
134 | | virtual void Seek(const Slice& user_key, const char* memtable_key) |
135 | 82.8M | override { |
136 | 82.8M | if (memtable_key != nullptr) { |
137 | 15.7M | iter_.Seek(memtable_key); |
138 | 67.1M | } else { |
139 | 67.1M | iter_.Seek(EncodeKey(&tmp_, user_key)); |
140 | 67.1M | } |
141 | 82.8M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4SeekERKN2yb5SliceEPKc Line | Count | Source | 135 | 16.0M | override { | 136 | 16.0M | if (memtable_key != nullptr) { | 137 | 15.7M | iter_.Seek(memtable_key); | 138 | 360k | } else { | 139 | 360k | iter_.Seek(EncodeKey(&tmp_, user_key)); | 140 | 360k | } | 141 | 16.0M | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator4SeekERKN2yb5SliceEPKc Line | Count | Source | 135 | 66.7M | override { | 136 | 66.7M | if (memtable_key != nullptr) { | 137 | 0 | iter_.Seek(memtable_key); | 138 | 66.7M | } else { | 139 | 66.7M | iter_.Seek(EncodeKey(&tmp_, user_key)); | 140 | 66.7M | } | 141 | 66.7M | } |
|
142 | | |
143 | | // Position at the first entry in list. |
144 | | // Final state of iterator is Valid() iff list is not empty. |
145 | 366k | void SeekToFirst() override { |
146 | 366k | iter_.SeekToFirst(); |
147 | 366k | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator11SeekToFirstEv Line | Count | Source | 145 | 297k | void SeekToFirst() override { | 146 | 297k | iter_.SeekToFirst(); | 147 | 297k | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator11SeekToFirstEv Line | Count | Source | 145 | 69.9k | void SeekToFirst() override { | 146 | 69.9k | iter_.SeekToFirst(); | 147 | 69.9k | } |
|
148 | | |
149 | | // Position at the last entry in list. |
150 | | // Final state of iterator is Valid() iff list is not empty. |
151 | 718k | void SeekToLast() override { |
152 | 718k | iter_.SeekToLast(); |
153 | 718k | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator10SeekToLastEv Line | Count | Source | 151 | 267k | void SeekToLast() override { | 152 | 267k | iter_.SeekToLast(); | 153 | 267k | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE8Iterator10SeekToLastEv Line | Count | Source | 151 | 451k | void SeekToLast() override { | 152 | 451k | iter_.SeekToLast(); | 153 | 451k | } |
|
154 | | protected: |
155 | | std::string tmp_; // For passing to EncodeKey |
156 | | }; |
157 | | |
158 | | // Iterator over the contents of a skip list which also keeps track of the |
159 | | // previously visited node. In Seek(), it examines a few nodes after it |
160 | | // first, falling back to O(log n) search from the head of the list only if |
161 | | // the target key hasn't been found. |
162 | | class LookaheadIterator : public MemTableRep::Iterator { |
163 | | public: |
164 | | explicit LookaheadIterator(const SkipListRep& rep) : |
165 | 0 | rep_(rep), iter_(&rep_.skip_list_), prev_(iter_) {} Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIteratorC2ERKS8_ Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIteratorC2ERKS8_ |
166 | | |
167 | 0 | ~LookaheadIterator() override {} Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIteratorD2Ev Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIteratorD2Ev |
168 | | |
169 | 0 | bool Valid() const override { |
170 | 0 | return iter_.Valid(); |
171 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator5ValidEv Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator5ValidEv |
172 | | |
173 | 0 | const char *key() const override { |
174 | 0 | assert(Valid()); |
175 | 0 | return iter_.key(); |
176 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator3keyEv Unexecuted instantiation: skiplistrep.cc:_ZNK7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator3keyEv |
177 | | |
178 | 0 | void Next() override { |
179 | 0 | assert(Valid()); |
180 | |
|
181 | 0 | bool advance_prev = true; |
182 | 0 | if (prev_.Valid()) { |
183 | 0 | auto k1 = rep_.UserKey(prev_.key()); |
184 | 0 | auto k2 = rep_.UserKey(iter_.key()); |
185 | |
|
186 | 0 | if (k1.compare(k2) == 0) { |
187 | | // same user key, don't move prev_ |
188 | 0 | advance_prev = false; |
189 | 0 | } else if (rep_.transform_) { |
190 | | // only advance prev_ if it has the same prefix as iter_ |
191 | 0 | auto t1 = rep_.transform_->Transform(k1); |
192 | 0 | auto t2 = rep_.transform_->Transform(k2); |
193 | 0 | advance_prev = t1.compare(t2) == 0; |
194 | 0 | } |
195 | 0 | } |
196 | |
|
197 | 0 | if (advance_prev) { |
198 | 0 | prev_ = iter_; |
199 | 0 | } |
200 | 0 | iter_.Next(); |
201 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4NextEv Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4NextEv |
202 | | |
203 | 0 | void Prev() override { |
204 | 0 | assert(Valid()); |
205 | 0 | iter_.Prev(); |
206 | 0 | prev_ = iter_; |
207 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4PrevEv Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4PrevEv |
208 | | |
209 | | virtual void Seek(const Slice& internal_key, const char *memtable_key) |
210 | 0 | override { |
211 | 0 | const char *encoded_key = |
212 | 0 | (memtable_key != nullptr) ? |
213 | 0 | memtable_key : EncodeKey(&tmp_, internal_key); |
214 | |
|
215 | 0 | if (prev_.Valid() && rep_.cmp_(encoded_key, prev_.key()) >= 0) { |
216 | | // prev_.key() is smaller or equal to our target key; do a quick |
217 | | // linear search (at most lookahead_ steps) starting from prev_ |
218 | 0 | iter_ = prev_; |
219 | |
|
220 | 0 | size_t cur = 0; |
221 | 0 | while (cur++ <= rep_.lookahead_ && iter_.Valid()) { |
222 | 0 | if (rep_.cmp_(encoded_key, iter_.key()) <= 0) { |
223 | 0 | return; |
224 | 0 | } |
225 | 0 | Next(); |
226 | 0 | } |
227 | 0 | } |
228 | |
|
229 | 0 | iter_.Seek(encoded_key); |
230 | 0 | prev_ = iter_; |
231 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4SeekERKN2yb5SliceEPKc Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator4SeekERKN2yb5SliceEPKc |
232 | | |
233 | 0 | void SeekToFirst() override { |
234 | 0 | iter_.SeekToFirst(); |
235 | 0 | prev_ = iter_; |
236 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator11SeekToFirstEv Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator11SeekToFirstEv |
237 | | |
238 | 0 | void SeekToLast() override { |
239 | 0 | iter_.SeekToLast(); |
240 | 0 | prev_ = iter_; |
241 | 0 | } Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator10SeekToLastEv Unexecuted instantiation: skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE17LookaheadIterator10SeekToLastEv |
242 | | |
243 | | protected: |
244 | | std::string tmp_; // For passing to EncodeKey |
245 | | |
246 | | private: |
247 | | const SkipListRep& rep_; |
248 | | typename SkipListImpl::Iterator iter_; |
249 | | typename SkipListImpl::Iterator prev_; |
250 | | }; |
251 | | |
252 | 15.5M | MemTableRep::Iterator* GetIterator(Arena* arena = nullptr) override { |
253 | 15.5M | if (lookahead_ > 0) { |
254 | 0 | void *mem = |
255 | 0 | arena ? arena->AllocateAligned(sizeof(SkipListRep::LookaheadIterator)) |
256 | 0 | : operator new(sizeof(SkipListRep::LookaheadIterator)); |
257 | 0 | return new (mem) SkipListRep::LookaheadIterator(*this); |
258 | 15.5M | } else { |
259 | 15.5M | void *mem = |
260 | 15.5M | arena ? arena->AllocateAligned(sizeof(SkipListRep::Iterator)) |
261 | 5.61k | : operator new(sizeof(SkipListRep::Iterator)); |
262 | 15.5M | return new (mem) SkipListRep::Iterator(&skip_list_); |
263 | 15.5M | } |
264 | 15.5M | } skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_14InlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE11GetIteratorEPNS_5ArenaE Line | Count | Source | 252 | 64.0k | MemTableRep::Iterator* GetIterator(Arena* arena = nullptr) override { | 253 | 64.0k | if (lookahead_ > 0) { | 254 | 0 | void *mem = | 255 | 0 | arena ? arena->AllocateAligned(sizeof(SkipListRep::LookaheadIterator)) | 256 | 0 | : operator new(sizeof(SkipListRep::LookaheadIterator)); | 257 | 0 | return new (mem) SkipListRep::LookaheadIterator(*this); | 258 | 64.0k | } else { | 259 | 64.0k | void *mem = | 260 | 62.3k | arena ? arena->AllocateAligned(sizeof(SkipListRep::Iterator)) | 261 | 1.67k | : operator new(sizeof(SkipListRep::Iterator)); | 262 | 64.0k | return new (mem) SkipListRep::Iterator(&skip_list_); | 263 | 64.0k | } | 264 | 64.0k | } |
skiplistrep.cc:_ZN7rocksdb12_GLOBAL__N_111SkipListRepINS_26SingleWriterInlineSkipListIRKNS_11MemTableRep13KeyComparatorEEEE11GetIteratorEPNS_5ArenaE Line | Count | Source | 252 | 15.4M | MemTableRep::Iterator* GetIterator(Arena* arena = nullptr) override { | 253 | 15.4M | if (lookahead_ > 0) { | 254 | 0 | void *mem = | 255 | 0 | arena ? arena->AllocateAligned(sizeof(SkipListRep::LookaheadIterator)) | 256 | 0 | : operator new(sizeof(SkipListRep::LookaheadIterator)); | 257 | 0 | return new (mem) SkipListRep::LookaheadIterator(*this); | 258 | 15.4M | } else { | 259 | 15.4M | void *mem = | 260 | 15.4M | arena ? arena->AllocateAligned(sizeof(SkipListRep::Iterator)) | 261 | 3.93k | : operator new(sizeof(SkipListRep::Iterator)); | 262 | 15.4M | return new (mem) SkipListRep::Iterator(&skip_list_); | 263 | 15.4M | } | 264 | 15.4M | } |
|
265 | | }; |
266 | | } // namespace |
267 | | |
268 | | MemTableRep* SkipListFactory::CreateMemTableRep( |
269 | | const MemTableRep::KeyComparator& compare, MemTableAllocator* allocator, |
270 | 378k | const SliceTransform* transform, Logger* logger) { |
271 | 378k | if (concurrent_writes_) { |
272 | 45.8k | return new SkipListRep<InlineSkipList<const MemTableRep::KeyComparator&>>( |
273 | 45.8k | compare, allocator, transform, lookahead_); |
274 | 332k | } else { |
275 | 332k | return new SkipListRep<SingleWriterInlineSkipList<const MemTableRep::KeyComparator&>>( |
276 | 332k | compare, allocator, transform, lookahead_); |
277 | 332k | } |
278 | 378k | } |
279 | | |
280 | | } // namespace rocksdb |