]>
Commit | Line | Data |
---|---|---|
9f95a23c | 1 | // Copyright 2018 The Abseil Authors. |
7c673cae FG |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); | |
4 | // you may not use this file except in compliance with the License. | |
5 | // You may obtain a copy of the License at | |
6 | // | |
9f95a23c | 7 | // https://www.apache.org/licenses/LICENSE-2.0 |
7c673cae FG |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software | |
10 | // distributed under the License is distributed on an "AS IS" BASIS, | |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
12 | // See the License for the specific language governing permissions and | |
13 | // limitations under the License. | |
9f95a23c TL |
14 | |
15 | // A btree implementation of the STL set and map interfaces. A btree is smaller | |
16 | // and generally also faster than STL set/map (refer to the benchmarks below). | |
17 | // The red-black tree implementation of STL set/map has an overhead of 3 | |
18 | // pointers (left, right and parent) plus the node color information for each | |
19 | // stored value. So a set<int32_t> consumes 40 bytes for each value stored in | |
20 | // 64-bit mode. This btree implementation stores multiple values on fixed | |
21 | // size nodes (usually 256 bytes) and doesn't store child pointers for leaf | |
22 | // nodes. The result is that a btree_set<int32_t> may use much less memory per | |
23 | // stored value. For the random insertion benchmark in btree_bench.cc, a | |
24 | // btree_set<int32_t> with node-size of 256 uses 5.1 bytes per stored value. | |
7c673cae FG |
25 | // |
26 | // The packing of multiple values on to each node of a btree has another effect | |
27 | // besides better space utilization: better cache locality due to fewer cache | |
28 | // lines being accessed. Better cache locality translates into faster | |
29 | // operations. | |
30 | // | |
31 | // CAVEATS | |
32 | // | |
33 | // Insertions and deletions on a btree can cause splitting, merging or | |
34 | // rebalancing of btree nodes. And even without these operations, insertions | |
35 | // and deletions on a btree will move values around within a node. In both | |
36 | // cases, the result is that insertions and deletions can invalidate iterators | |
9f95a23c TL |
37 | // pointing to values other than the one being inserted/deleted. Therefore, this |
38 | // container does not provide pointer stability. This is notably different from | |
39 | // STL set/map which takes care to not invalidate iterators on insert/erase | |
40 | // except, of course, for iterators pointing to the value being erased. A | |
41 | // partial workaround when erasing is available: erase() returns an iterator | |
42 | // pointing to the item just after the one that was erased (or end() if none | |
43 | // exists). | |
44 | ||
45 | #pragma once | |
46 | ||
7c673cae | 47 | #include <algorithm> |
9f95a23c TL |
48 | #include <cassert> |
49 | #include <cstddef> | |
50 | #include <cstdint> | |
51 | #include <cstring> | |
52 | #include <experimental/type_traits> | |
7c673cae | 53 | #include <functional> |
7c673cae FG |
54 | #include <iterator> |
55 | #include <limits> | |
7c673cae | 56 | #include <new> |
9f95a23c | 57 | #include <type_traits> |
7c673cae FG |
58 | #include <utility> |
59 | ||
9f95a23c TL |
60 | namespace btree::internal { |
61 | ||
62 | template <typename Compare, typename T> | |
63 | using btree_is_key_compare_to = | |
64 | std::is_signed<std::invoke_result_t<Compare, T, T>>; | |
65 | ||
66 | template<typename T> | |
67 | using compare_to_t = decltype(std::declval<T&>().compare(std::declval<const T&>())); | |
68 | template<typename T> | |
69 | inline constexpr bool has_compare_to = std::experimental::is_detected_v<compare_to_t, T>; | |
70 | // A helper class to convert a boolean comparison into a three-way "compare-to" | |
71 | // comparison that returns a negative value to indicate less-than, zero to | |
72 | // indicate equality and a positive value to indicate greater-than. This helper | |
73 | // class is specialized for less<std::string>, greater<std::string>, | |
74 | // less<string_view>, and greater<string_view>. | |
75 | // | |
76 | // key_compare_to_adapter is provided so that btree users | |
77 | // automatically get the more efficient compare-to code when using common | |
78 | // google string types with common comparison functors. | |
79 | // These string-like specializations also turn on heterogeneous lookup by | |
80 | // default. | |
81 | template <typename Compare, typename=void> | |
82 | struct key_compare_to_adapter { | |
83 | using type = Compare; | |
7c673cae FG |
84 | }; |
85 | ||
9f95a23c TL |
86 | template <typename K> |
87 | struct key_compare_to_adapter<std::less<K>, std::enable_if_t<has_compare_to<K>>> | |
88 | { | |
89 | struct type { | |
90 | inline int operator()(const K& lhs, const K& rhs) const noexcept { | |
91 | return lhs.compare(rhs); | |
92 | } | |
93 | }; | |
7c673cae FG |
94 | }; |
95 | ||
9f95a23c TL |
96 | template <typename K> |
97 | struct key_compare_to_adapter<std::less<K>, std::enable_if_t<std::is_signed_v<K>>> | |
98 | { | |
99 | struct type { | |
100 | inline K operator()(const K& lhs, const K& rhs) const noexcept { | |
101 | return lhs - rhs; | |
102 | } | |
103 | }; | |
7c673cae FG |
104 | }; |
105 | ||
9f95a23c TL |
106 | template <typename K> |
107 | struct key_compare_to_adapter<std::less<K>, std::enable_if_t<std::is_unsigned_v<K>>> | |
108 | { | |
109 | struct type { | |
110 | inline int operator()(const K& lhs, const K& rhs) const noexcept { | |
111 | if (lhs < rhs) { | |
112 | return -1; | |
113 | } else if (lhs > rhs) { | |
114 | return 1; | |
115 | } else { | |
116 | return 0; | |
117 | } | |
118 | } | |
119 | }; | |
7c673cae FG |
120 | }; |
121 | ||
9f95a23c TL |
122 | template <typename Key, typename Compare, typename Alloc, |
123 | int TargetNodeSize, int ValueSize, | |
124 | bool Multi> | |
125 | struct common_params { | |
126 | // If Compare is a common comparator for a std::string-like type, then we adapt it | |
127 | // to use heterogeneous lookup and to be a key-compare-to comparator. | |
128 | using key_compare = typename key_compare_to_adapter<Compare>::type; | |
129 | // A type which indicates if we have a key-compare-to functor or a plain old | |
130 | // key-compare functor. | |
131 | using is_key_compare_to = btree_is_key_compare_to<key_compare, Key>; | |
7c673cae | 132 | |
9f95a23c TL |
133 | using allocator_type = Alloc; |
134 | using key_type = Key; | |
135 | using size_type = std::make_signed<size_t>::type; | |
136 | using difference_type = ptrdiff_t; | |
7c673cae | 137 | |
9f95a23c TL |
138 | // True if this is a multiset or multimap. |
139 | using is_multi_container = std::integral_constant<bool, Multi>; | |
7c673cae | 140 | |
9f95a23c TL |
141 | constexpr static int kTargetNodeSize = TargetNodeSize; |
142 | constexpr static int kValueSize = ValueSize; | |
143 | // Upper bound for the available space for values. This is largest for leaf | |
144 | // nodes, which have overhead of at least a pointer + 3 bytes (for storing | |
145 | // 3 field_types) + paddings. if alignof(key_type) is 1, the size of padding | |
146 | // would be 0. | |
147 | constexpr static int kNodeValueSpace = | |
148 | TargetNodeSize - /*minimum overhead=*/(sizeof(void *) + 4); | |
7c673cae | 149 | |
9f95a23c TL |
150 | // This is an integral type large enough to hold as many |
151 | // ValueSize-values as will fit a node of TargetNodeSize bytes. | |
152 | using node_count_type = | |
153 | std::conditional_t<(kNodeValueSpace / ValueSize > | |
154 | (std::numeric_limits<uint8_t>::max)()), | |
155 | uint16_t, | |
156 | uint8_t>; | |
7c673cae FG |
157 | }; |
158 | ||
9f95a23c TL |
159 | // The internal storage type |
160 | // | |
161 | // It is convenient for the value_type of a btree_map<K, V> to be | |
162 | // pair<const K, V>; the "const K" prevents accidental modification of the key | |
163 | // when dealing with the reference returned from find() and similar methods. | |
164 | // However, this creates other problems; we want to be able to emplace(K, V) | |
165 | // efficiently with move operations, and similarly be able to move a | |
166 | // pair<K, V> in insert(). | |
167 | // | |
168 | // The solution is this union, which aliases the const and non-const versions | |
169 | // of the pair. This also allows flat_hash_map<const K, V> to work, even though | |
170 | // that has the same efficiency issues with move in emplace() and insert() - | |
171 | // but people do it anyway. | |
172 | template <class K, class V> | |
173 | union map_slot_type { | |
174 | map_slot_type() {} | |
175 | ~map_slot_type() = delete; | |
176 | map_slot_type& operator=(const map_slot_type& slot) { | |
177 | mutable_value = slot.mutable_value; | |
178 | return *this; | |
7c673cae | 179 | } |
9f95a23c TL |
180 | map_slot_type& operator=(map_slot_type&& slot) { |
181 | mutable_value = std::move(slot.mutable_value); | |
182 | return *this; | |
7c673cae | 183 | } |
9f95a23c TL |
184 | using value_type = std::pair<const K, V>; |
185 | using mutable_value_type = std::pair<K, V>; | |
7c673cae | 186 | |
9f95a23c TL |
187 | value_type value; |
188 | mutable_value_type mutable_value; | |
189 | K key; | |
7c673cae FG |
190 | }; |
191 | ||
9f95a23c TL |
192 | template <class K, class V> |
193 | void swap(map_slot_type<K, V>& lhs, map_slot_type<K, V>& rhs) { | |
194 | std::swap(lhs.mutable_value, rhs.mutable_value); | |
7c673cae FG |
195 | } |
196 | ||
7c673cae | 197 | // A parameters structure for holding the type parameters for a btree_map. |
9f95a23c TL |
198 | // Compare and Alloc should be nothrow copy-constructible. |
199 | template <typename Key, typename Data, typename Compare, typename Alloc, | |
200 | int TargetNodeSize, bool Multi> | |
201 | struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, | |
202 | sizeof(Key) + sizeof(Data), Multi> { | |
203 | using super_type = typename map_params::common_params; | |
204 | using mapped_type = Data; | |
205 | using value_type = std::pair<const Key, mapped_type>; | |
206 | using mutable_value_type = std::pair<Key, mapped_type>; | |
207 | using slot_type = map_slot_type<Key, mapped_type>; | |
208 | using pointer = value_type*; | |
209 | using const_pointer = const value_type *; | |
210 | using reference = value_type &; | |
211 | using const_reference = const value_type &; | |
212 | using key_compare = typename super_type::key_compare; | |
213 | using init_type = mutable_value_type; | |
214 | ||
215 | static constexpr size_t kValueSize = sizeof(Key) + sizeof(mapped_type); | |
216 | ||
217 | // Inherit from key_compare for empty base class optimization. | |
218 | struct value_compare : private key_compare { | |
219 | value_compare() = default; | |
220 | explicit value_compare(const key_compare &cmp) : key_compare(cmp) {} | |
221 | ||
222 | template <typename T, typename U> | |
223 | auto operator()(const T &left, const U &right) const | |
224 | -> decltype(std::declval<key_compare>()(left.first, right.first)) { | |
225 | return key_compare::operator()(left.first, right.first); | |
226 | } | |
7c673cae | 227 | }; |
9f95a23c TL |
228 | using is_map_container = std::true_type; |
229 | ||
230 | static const Key &key(const value_type &value) { return value.first; } | |
231 | static mapped_type &value(value_type *value) { return value->second; } | |
232 | static const Key &key(const slot_type *slot) { return slot->key; } | |
233 | static value_type& element(slot_type* slot) { return slot->value; } | |
234 | static const value_type& element(const slot_type* slot) { return slot->value; } | |
235 | template <class... Args> | |
236 | static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { | |
237 | std::allocator_traits<Alloc>::construct(*alloc, | |
238 | &slot->mutable_value, | |
239 | std::forward<Args>(args)...); | |
240 | } | |
241 | // Construct this slot by moving from another slot. | |
242 | static void construct(Alloc* alloc, slot_type* slot, slot_type* other) { | |
243 | emplace(slot); | |
244 | std::allocator_traits<Alloc>::construct(*alloc, &slot->value, | |
245 | std::move(other->value)); | |
246 | } | |
247 | static void move(Alloc *alloc, slot_type *src, slot_type *dest) { | |
248 | dest->mutable_value = std::move(src->mutable_value); | |
249 | } | |
250 | static void destroy(Alloc *alloc, slot_type *slot) { | |
251 | std::allocator_traits<Alloc>::destroy(*alloc, &slot->mutable_value); | |
252 | } | |
253 | ||
254 | private: | |
255 | static void emplace(slot_type* slot) { | |
256 | // The construction of union doesn't do anything at runtime but it allows us | |
257 | // to access its members without violating aliasing rules. | |
258 | new (slot) slot_type; | |
7c673cae FG |
259 | } |
260 | }; | |
261 | ||
262 | // A parameters structure for holding the type parameters for a btree_set. | |
9f95a23c TL |
263 | template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, bool Multi> |
264 | struct set_params | |
265 | : public common_params<Key, Compare, Alloc, TargetNodeSize, | |
266 | sizeof(Key), Multi> { | |
267 | using value_type = Key; | |
268 | using mutable_value_type = value_type; | |
269 | using slot_type = Key; | |
270 | using pointer = value_type *; | |
271 | using const_pointer = const value_type *; | |
272 | using value_compare = typename set_params::common_params::key_compare; | |
273 | using reference = value_type &; | |
274 | using const_reference = const value_type &; | |
275 | using is_map_container = std::false_type; | |
276 | using init_type = mutable_value_type; | |
277 | ||
278 | template <class... Args> | |
279 | static void construct(Alloc *alloc, slot_type *slot, Args &&... args) { | |
280 | std::allocator_traits<Alloc>::construct(*alloc, | |
281 | slot, | |
282 | std::forward<Args>(args)...); | |
283 | } | |
284 | static void construct(Alloc *alloc, slot_type *slot, slot_type *other) { | |
285 | std::allocator_traits<Alloc>::construct(*alloc, slot, std::move(*other)); | |
286 | } | |
287 | static void move(Alloc *alloc, slot_type *src, slot_type *dest) { | |
288 | *dest = std::move(*src); | |
289 | } | |
290 | static void destroy(Alloc *alloc, slot_type *slot) { | |
291 | std::allocator_traits<Alloc>::destroy(*alloc, slot); | |
292 | } | |
293 | static const Key &key(const value_type &x) { return x; } | |
294 | static const Key &key(const slot_type *slot) { return *slot; } | |
295 | static value_type &element(slot_type *slot) { return *slot; } | |
296 | static const value_type &element(const slot_type *slot) { return *slot; } | |
7c673cae FG |
297 | }; |
298 | ||
9f95a23c TL |
299 | // Helper functions to do a boolean comparison of two keys given a boolean |
300 | // or three-way comparator. | |
301 | // SFINAE prevents implicit conversions to bool (such as from int). | |
302 | template <typename Result> | |
303 | constexpr bool compare_result_as_less_than(const Result r) { | |
304 | if constexpr (std::is_signed_v<Result>) { | |
305 | return r < 0; | |
306 | } else { | |
307 | return r; | |
7c673cae | 308 | } |
9f95a23c TL |
309 | } |
310 | // An adapter class that converts a lower-bound compare into an upper-bound | |
311 | // compare. Note: there is no need to make a version of this adapter specialized | |
312 | // for key-compare-to functors because the upper-bound (the first value greater | |
313 | // than the input) is never an exact match. | |
314 | template <typename Compare> | |
315 | struct upper_bound_adapter { | |
316 | explicit upper_bound_adapter(const Compare &c) : comp(c) {} | |
317 | template <typename K, typename LK> | |
318 | bool operator()(const K &a, const LK &b) const { | |
319 | // Returns true when a is not greater than b. | |
320 | return !compare_result_as_less_than(comp(b, a)); | |
321 | } | |
322 | private: | |
323 | const Compare& comp; | |
7c673cae FG |
324 | }; |
325 | ||
9f95a23c | 326 | enum class MatchKind : uint8_t { kEq, kNe }; |
7c673cae | 327 | |
9f95a23c TL |
328 | template <typename V, bool IsCompareTo> |
329 | struct SearchResult { | |
330 | V value; | |
331 | MatchKind match; | |
7c673cae | 332 | |
9f95a23c TL |
333 | static constexpr bool has_match = true; |
334 | bool IsEq() const { return match == MatchKind::kEq; } | |
7c673cae FG |
335 | }; |
336 | ||
9f95a23c TL |
337 | // When we don't use CompareTo, `match` is not present. |
338 | // This ensures that callers can't use it accidentally when it provides no | |
339 | // useful information. | |
340 | template <typename V> | |
341 | struct SearchResult<V, false> { | |
342 | V value; | |
7c673cae | 343 | |
9f95a23c TL |
344 | static constexpr bool has_match = false; |
345 | static constexpr bool IsEq() { return false; } | |
7c673cae FG |
346 | }; |
347 | ||
348 | // A node in the btree holding. The same node type is used for both internal | |
349 | // and leaf nodes in the btree, though the nodes are allocated in such a way | |
350 | // that the children array is only valid in internal nodes. | |
351 | template <typename Params> | |
352 | class btree_node { | |
9f95a23c TL |
353 | using is_key_compare_to = typename Params::is_key_compare_to; |
354 | using is_multi_container = typename Params::is_multi_container; | |
355 | using field_type = typename Params::node_count_type; | |
356 | using allocator_type = typename Params::allocator_type; | |
357 | using slot_type = typename Params::slot_type; | |
358 | ||
7c673cae | 359 | public: |
9f95a23c TL |
360 | using params_type = Params; |
361 | using key_type = typename Params::key_type; | |
362 | using value_type = typename Params::value_type; | |
363 | using mutable_value_type = typename Params::mutable_value_type; | |
364 | using pointer = typename Params::pointer; | |
365 | using const_pointer = typename Params::const_pointer; | |
366 | using reference = typename Params::reference; | |
367 | using const_reference = typename Params::const_reference; | |
368 | using key_compare = typename Params::key_compare; | |
369 | using size_type = typename Params::size_type; | |
370 | using difference_type = typename Params::difference_type; | |
371 | ||
372 | // Btree decides whether to use linear node search as follows: | |
373 | // - If the key is arithmetic and the comparator is std::less or | |
374 | // std::greater, choose linear. | |
375 | // - Otherwise, choose binary. | |
376 | // TODO(ezb): Might make sense to add condition(s) based on node-size. | |
377 | using use_linear_search = std::integral_constant< | |
378 | bool, | |
379 | std::is_arithmetic_v<key_type> && | |
380 | (std::is_same_v<std::less<key_type>, key_compare> || | |
381 | std::is_same_v<std::greater<key_type>, key_compare>)>; | |
382 | ||
383 | ~btree_node() = default; | |
384 | btree_node(const btree_node&) = delete; | |
385 | btree_node& operator=(const btree_node&) = delete; | |
386 | ||
387 | protected: | |
388 | btree_node() = default; | |
7c673cae | 389 | |
9f95a23c TL |
390 | private: |
391 | constexpr static size_type SizeWithNValues(size_type n) { | |
392 | return sizeof(base_fields) + n * sizeof(value_type);; | |
393 | } | |
394 | // A lower bound for the overhead of fields other than values in a leaf node. | |
395 | constexpr static size_type MinimumOverhead() { | |
396 | return SizeWithNValues(1) - sizeof(value_type); | |
397 | } | |
398 | ||
399 | // Compute how many values we can fit onto a leaf node taking into account | |
400 | // padding. | |
401 | constexpr static size_type NodeTargetValues(const int begin, const int end) { | |
402 | return begin == end ? begin | |
403 | : SizeWithNValues((begin + end) / 2 + 1) > | |
404 | params_type::kTargetNodeSize | |
405 | ? NodeTargetValues(begin, (begin + end) / 2) | |
406 | : NodeTargetValues((begin + end) / 2 + 1, end); | |
407 | } | |
408 | ||
409 | constexpr static int kValueSize = params_type::kValueSize; | |
410 | constexpr static int kTargetNodeSize = params_type::kTargetNodeSize; | |
411 | constexpr static int kNodeTargetValues = NodeTargetValues(0, kTargetNodeSize); | |
7c673cae | 412 | |
9f95a23c TL |
413 | // We need a minimum of 3 values per internal node in order to perform |
414 | // splitting (1 value for the two nodes involved in the split and 1 value | |
415 | // propagated to the parent as the delimiter for the split). | |
416 | constexpr static size_type kNodeValues = std::max(kNodeTargetValues, 3); | |
417 | ||
418 | // The node is internal (i.e. is not a leaf node) if and only if `max_count` | |
419 | // has this value. | |
420 | constexpr static size_type kInternalNodeMaxCount = 0; | |
421 | ||
422 | struct base_fields { | |
423 | // A pointer to the node's parent. | |
424 | btree_node *parent; | |
7c673cae FG |
425 | // The position of the node in the node's parent. |
426 | field_type position; | |
7c673cae FG |
427 | // The count of the number of values in the node. |
428 | field_type count; | |
9f95a23c TL |
429 | // The maximum number of values the node can hold. |
430 | field_type max_count; | |
7c673cae FG |
431 | }; |
432 | ||
433 | struct leaf_fields : public base_fields { | |
434 | // The array of values. Only the first count of these values have been | |
435 | // constructed and are valid. | |
9f95a23c | 436 | slot_type values[kNodeValues]; |
7c673cae FG |
437 | }; |
438 | ||
439 | struct internal_fields : public leaf_fields { | |
440 | // The array of child pointers. The keys in children_[i] are all less than | |
441 | // key(i). The keys in children_[i + 1] are all greater than key(i). There | |
442 | // are always count + 1 children. | |
443 | btree_node *children[kNodeValues + 1]; | |
444 | }; | |
445 | ||
9f95a23c TL |
446 | constexpr static size_type LeafSize(const int max_values = kNodeValues) { |
447 | return SizeWithNValues(max_values); | |
448 | } | |
449 | constexpr static size_type InternalSize() { | |
450 | return sizeof(internal_fields); | |
451 | } | |
452 | ||
453 | template<auto MemPtr> | |
454 | auto& GetField() { | |
455 | return reinterpret_cast<internal_fields*>(this)->*MemPtr; | |
456 | } | |
457 | ||
458 | template<auto MemPtr> | |
459 | auto& GetField() const { | |
460 | return reinterpret_cast<const internal_fields*>(this)->*MemPtr; | |
461 | } | |
462 | ||
463 | void set_parent(btree_node *p) { GetField<&base_fields::parent>() = p; } | |
464 | field_type &mutable_count() { return GetField<&base_fields::count>(); } | |
465 | slot_type *slot(int i) { return &GetField<&leaf_fields::values>()[i]; } | |
466 | const slot_type *slot(int i) const { return &GetField<&leaf_fields::values>()[i]; } | |
467 | void set_position(field_type v) { GetField<&base_fields::position>() = v; } | |
468 | void set_count(field_type v) { GetField<&base_fields::count>() = v; } | |
469 | // This method is only called by the node init methods. | |
470 | void set_max_count(field_type v) { GetField<&base_fields::max_count>() = v; } | |
471 | ||
472 | public: | |
473 | constexpr static size_type Alignment() { | |
474 | static_assert(alignof(leaf_fields) == alignof(internal_fields), | |
475 | "Alignment of all nodes must be equal."); | |
476 | return alignof(internal_fields); | |
477 | } | |
7c673cae | 478 | |
7c673cae FG |
479 | // Getter/setter for whether this is a leaf node or not. This value doesn't |
480 | // change after the node is created. | |
9f95a23c | 481 | bool leaf() const { return GetField<&base_fields::max_count>() != kInternalNodeMaxCount; } |
7c673cae FG |
482 | |
483 | // Getter for the position of this node in its parent. | |
9f95a23c | 484 | field_type position() const { return GetField<&base_fields::position>(); } |
7c673cae | 485 | |
9f95a23c TL |
486 | // Getter for the number of values stored in this node. |
487 | field_type count() const { return GetField<&base_fields::count>(); } | |
488 | field_type max_count() const { | |
489 | // Internal nodes have max_count==kInternalNodeMaxCount. | |
490 | // Leaf nodes have max_count in [1, kNodeValues]. | |
491 | const field_type max_count = GetField<&base_fields::max_count>(); | |
492 | return max_count == field_type{kInternalNodeMaxCount} | |
493 | ? field_type{kNodeValues} | |
494 | : max_count; | |
495 | } | |
7c673cae FG |
496 | |
497 | // Getter for the parent of this node. | |
9f95a23c | 498 | btree_node* parent() const { return GetField<&base_fields::parent>(); } |
7c673cae FG |
499 | // Getter for whether the node is the root of the tree. The parent of the |
500 | // root of the tree is the leftmost node in the tree which is guaranteed to | |
501 | // be a leaf. | |
502 | bool is_root() const { return parent()->leaf(); } | |
503 | void make_root() { | |
9f95a23c TL |
504 | assert(parent()->is_root()); |
505 | set_parent(parent()->parent()); | |
7c673cae FG |
506 | } |
507 | ||
7c673cae | 508 | // Getters for the key/value at position i in the node. |
9f95a23c TL |
509 | const key_type& key(int i) const { return params_type::key(slot(i)); } |
510 | reference value(int i) { return params_type::element(slot(i)); } | |
511 | const_reference value(int i) const { return params_type::element(slot(i)); } | |
7c673cae FG |
512 | |
513 | // Getters/setter for the child at position i in the node. | |
9f95a23c TL |
514 | btree_node* child(int i) const { return GetField<&internal_fields::children>()[i]; } |
515 | btree_node*& mutable_child(int i) { return GetField<&internal_fields::children>()[i]; } | |
516 | void clear_child(int i) { | |
517 | #ifndef NDEBUG | |
518 | memset(&mutable_child(i), 0, sizeof(btree_node*)); | |
519 | #endif | |
520 | } | |
7c673cae | 521 | void set_child(int i, btree_node *c) { |
9f95a23c TL |
522 | mutable_child(i) = c; |
523 | c->set_position(i); | |
524 | } | |
525 | void init_child(int i, btree_node *c) { | |
526 | set_child(i, c); | |
527 | c->set_parent(this); | |
7c673cae | 528 | } |
7c673cae | 529 | // Returns the position of the first value whose key is not less than k. |
9f95a23c TL |
530 | template <typename K> |
531 | SearchResult<int, is_key_compare_to::value> lower_bound( | |
532 | const K &k, const key_compare &comp) const { | |
533 | return use_linear_search::value ? linear_search(k, comp) | |
534 | : binary_search(k, comp); | |
7c673cae FG |
535 | } |
536 | // Returns the position of the first value whose key is greater than k. | |
9f95a23c TL |
537 | template <typename K> |
538 | int upper_bound(const K &k, const key_compare &comp) const { | |
539 | auto upper_compare = upper_bound_adapter<key_compare>(comp); | |
540 | return use_linear_search::value ? linear_search(k, upper_compare).value | |
541 | : binary_search(k, upper_compare).value; | |
542 | } | |
543 | ||
544 | template <typename K, typename Compare> | |
545 | SearchResult<int, btree_is_key_compare_to<Compare, key_type>::value> | |
546 | linear_search(const K &k, const Compare &comp) const { | |
547 | return linear_search_impl(k, 0, count(), comp, | |
548 | btree_is_key_compare_to<Compare, key_type>()); | |
7c673cae FG |
549 | } |
550 | ||
9f95a23c TL |
551 | template <typename K, typename Compare> |
552 | SearchResult<int, btree_is_key_compare_to<Compare, key_type>::value> | |
553 | binary_search(const K &k, const Compare &comp) const { | |
554 | return binary_search_impl(k, 0, count(), comp, | |
555 | btree_is_key_compare_to<Compare, key_type>()); | |
556 | } | |
7c673cae FG |
557 | // Returns the position of the first value whose key is not less than k using |
558 | // linear search performed using plain compare. | |
9f95a23c TL |
559 | template <typename K, typename Compare> |
560 | SearchResult<int, false> linear_search_impl( | |
561 | const K &k, int s, const int e, const Compare &comp, | |
562 | std::false_type /* IsCompareTo */) const { | |
7c673cae | 563 | while (s < e) { |
9f95a23c | 564 | if (!comp(key(s), k)) { |
7c673cae FG |
565 | break; |
566 | } | |
567 | ++s; | |
568 | } | |
9f95a23c | 569 | return {s}; |
7c673cae FG |
570 | } |
571 | ||
572 | // Returns the position of the first value whose key is not less than k using | |
573 | // linear search performed using compare-to. | |
9f95a23c TL |
574 | template <typename K, typename Compare> |
575 | SearchResult<int, true> linear_search_impl( | |
576 | const K &k, int s, const int e, const Compare &comp, | |
577 | std::true_type /* IsCompareTo */) const { | |
7c673cae | 578 | while (s < e) { |
9f95a23c | 579 | const auto c = comp(key(s), k); |
7c673cae | 580 | if (c == 0) { |
9f95a23c | 581 | return {s, MatchKind::kEq}; |
7c673cae FG |
582 | } else if (c > 0) { |
583 | break; | |
584 | } | |
585 | ++s; | |
586 | } | |
9f95a23c | 587 | return {s, MatchKind::kNe}; |
7c673cae FG |
588 | } |
589 | ||
590 | // Returns the position of the first value whose key is not less than k using | |
591 | // binary search performed using plain compare. | |
9f95a23c TL |
592 | template <typename K, typename Compare> |
593 | SearchResult<int, false> binary_search_impl( | |
594 | const K &k, int s, int e, const Compare &comp, | |
595 | std::false_type /* IsCompareTo */) const { | |
7c673cae | 596 | while (s != e) { |
9f95a23c TL |
597 | const int mid = (s + e) >> 1; |
598 | if (comp(key(mid), k)) { | |
7c673cae FG |
599 | s = mid + 1; |
600 | } else { | |
601 | e = mid; | |
602 | } | |
603 | } | |
9f95a23c | 604 | return {s}; |
7c673cae FG |
605 | } |
606 | ||
607 | // Returns the position of the first value whose key is not less than k using | |
608 | // binary search performed using compare-to. | |
9f95a23c TL |
609 | template <typename K, typename CompareTo> |
610 | SearchResult<int, true> binary_search_impl( | |
611 | const K &k, int s, int e, const CompareTo &comp, | |
612 | std::true_type /* IsCompareTo */) const { | |
613 | if constexpr (is_multi_container::value) { | |
614 | MatchKind exact_match = MatchKind::kNe; | |
615 | while (s != e) { | |
616 | const int mid = (s + e) >> 1; | |
617 | const auto c = comp(key(mid), k); | |
618 | if (c < 0) { | |
619 | s = mid + 1; | |
620 | } else { | |
621 | e = mid; | |
622 | if (c == 0) { | |
623 | // Need to return the first value whose key is not less than k, | |
624 | // which requires continuing the binary search if this is a | |
625 | // multi-container. | |
626 | exact_match = MatchKind::kEq; | |
627 | } | |
628 | } | |
7c673cae | 629 | } |
9f95a23c TL |
630 | return {s, exact_match}; |
631 | } else { // Not a multi-container. | |
632 | while (s != e) { | |
633 | const int mid = (s + e) >> 1; | |
634 | const auto c = comp(key(mid), k); | |
635 | if (c < 0) { | |
636 | s = mid + 1; | |
637 | } else if (c > 0) { | |
638 | e = mid; | |
639 | } else { | |
640 | return {mid, MatchKind::kEq}; | |
641 | } | |
642 | } | |
643 | return {s, MatchKind::kNe}; | |
7c673cae | 644 | } |
7c673cae FG |
645 | } |
646 | ||
9f95a23c | 647 | // Emplaces a value at position i, shifting all existing values and |
7c673cae | 648 | // children at positions >= i to the right by 1. |
9f95a23c TL |
649 | template <typename... Args> |
650 | void emplace_value(size_type i, allocator_type *alloc, Args &&... args); | |
7c673cae FG |
651 | |
652 | // Removes the value at position i, shifting all existing values and children | |
653 | // at positions > i to the left by 1. | |
9f95a23c TL |
654 | void remove_value(const int i, allocator_type *alloc); |
655 | ||
656 | // Removes the values at positions [i, i + to_erase), shifting all values | |
657 | // after that range to the left by to_erase. Does not change children at all. | |
658 | void remove_values_ignore_children(int i, int to_erase, | |
659 | allocator_type *alloc); | |
7c673cae FG |
660 | |
661 | // Rebalances a node with its right sibling. | |
9f95a23c TL |
662 | void rebalance_right_to_left(const int to_move, btree_node *right, |
663 | allocator_type *alloc); | |
664 | void rebalance_left_to_right(const int to_move, btree_node *right, | |
665 | allocator_type *alloc); | |
7c673cae FG |
666 | |
667 | // Splits a node, moving a portion of the node's values to its right sibling. | |
9f95a23c | 668 | void split(const int insert_position, btree_node *dest, allocator_type *alloc); |
7c673cae FG |
669 | |
670 | // Merges a node with its right sibling, moving all of the values and the | |
671 | // delimiting key in the parent node onto itself. | |
9f95a23c | 672 | void merge(btree_node *sibling, allocator_type *alloc); |
7c673cae FG |
673 | |
674 | // Swap the contents of "this" and "src". | |
9f95a23c | 675 | void swap(btree_node *src, allocator_type *alloc); |
7c673cae FG |
676 | |
677 | // Node allocation/deletion routines. | |
9f95a23c TL |
678 | static btree_node *init_leaf(btree_node *n, btree_node *parent, |
679 | int max_count) { | |
680 | n->set_parent(parent); | |
681 | n->set_position(0); | |
682 | n->set_count(0); | |
683 | n->set_max_count(max_count); | |
7c673cae FG |
684 | return n; |
685 | } | |
9f95a23c TL |
686 | static btree_node *init_internal(btree_node *n, btree_node *parent) { |
687 | init_leaf(n, parent, kNodeValues); | |
688 | // Set `max_count` to a sentinel value to indicate that this node is | |
689 | // internal. | |
690 | n->set_max_count(kInternalNodeMaxCount); | |
7c673cae FG |
691 | return n; |
692 | } | |
9f95a23c | 693 | void destroy(allocator_type *alloc) { |
7c673cae | 694 | for (int i = 0; i < count(); ++i) { |
9f95a23c | 695 | value_destroy(i, alloc); |
7c673cae FG |
696 | } |
697 | } | |
698 | ||
699 | private: | |
9f95a23c TL |
700 | template <typename... Args> |
701 | void value_init(const size_type i, allocator_type *alloc, Args &&... args) { | |
702 | params_type::construct(alloc, slot(i), std::forward<Args>(args)...); | |
7c673cae | 703 | } |
9f95a23c TL |
704 | void value_destroy(const size_type i, allocator_type *alloc) { |
705 | params_type::destroy(alloc, slot(i)); | |
7c673cae | 706 | } |
9f95a23c TL |
707 | |
708 | // Move n values starting at value i in this node into the values starting at | |
709 | // value j in node x. | |
710 | void uninitialized_move_n(const size_type n, const size_type i, | |
711 | const size_type j, btree_node *x, | |
712 | allocator_type *alloc) { | |
713 | for (slot_type *src = slot(i), *end = src + n, *dest = x->slot(j); | |
714 | src != end; ++src, ++dest) { | |
715 | params_type::construct(alloc, dest, src); | |
716 | } | |
7c673cae FG |
717 | } |
718 | ||
9f95a23c TL |
719 | // Destroys a range of n values, starting at index i. |
720 | void value_destroy_n(const size_type i, const size_type n, | |
721 | allocator_type *alloc) { | |
722 | for (int j = 0; j < n; ++j) { | |
723 | value_destroy(i + j, alloc); | |
724 | } | |
725 | } | |
7c673cae | 726 | |
9f95a23c TL |
727 | private: |
728 | template <typename P> | |
729 | friend class btree; | |
730 | template <typename N, typename R, typename P> | |
731 | friend struct btree_iterator; | |
7c673cae FG |
732 | }; |
733 | ||
734 | template <typename Node, typename Reference, typename Pointer> | |
735 | struct btree_iterator { | |
9f95a23c TL |
736 | private: |
737 | using key_type = typename Node::key_type; | |
738 | using size_type = typename Node::size_type; | |
739 | using params_type = typename Node::params_type; | |
740 | ||
741 | using node_type = Node; | |
742 | using normal_node = typename std::remove_const<Node>::type; | |
743 | using const_node = const Node; | |
744 | using normal_pointer = typename params_type::pointer; | |
745 | using normal_reference = typename params_type::reference; | |
746 | using const_pointer = typename params_type::const_pointer; | |
747 | using const_reference = typename params_type::const_reference; | |
748 | using slot_type = typename params_type::slot_type; | |
749 | ||
750 | using iterator = | |
751 | btree_iterator<normal_node, normal_reference, normal_pointer>; | |
752 | using const_iterator = | |
753 | btree_iterator<const_node, const_reference, const_pointer>; | |
754 | ||
755 | public: | |
756 | // These aliases are public for std::iterator_traits. | |
757 | using difference_type = typename Node::difference_type; | |
758 | using value_type = typename params_type::value_type; | |
759 | using pointer = Pointer; | |
760 | using reference = Reference; | |
761 | using iterator_category = std::bidirectional_iterator_tag; | |
762 | ||
763 | btree_iterator() = default; | |
764 | btree_iterator(Node *n, int p) : node(n), position(p) {} | |
765 | ||
766 | // NOTE: this SFINAE allows for implicit conversions from iterator to | |
767 | // const_iterator, but it specifically avoids defining copy constructors so | |
768 | // that btree_iterator can be trivially copyable. This is for performance and | |
769 | // binary size reasons. | |
770 | template<typename N, typename R, typename P, | |
771 | std::enable_if_t< | |
772 | std::is_same_v<btree_iterator<N, R, P>, iterator> && | |
773 | std::is_same_v<btree_iterator, const_iterator>, | |
774 | int> = 0> | |
775 | btree_iterator(const btree_iterator<N, R, P> &x) | |
776 | : node(x.node), position(x.position) {} | |
777 | ||
778 | private: | |
779 | // This SFINAE allows explicit conversions from const_iterator to | |
780 | // iterator, but also avoids defining a copy constructor. | |
781 | // NOTE: the const_cast is safe because this constructor is only called by | |
782 | // non-const methods and the container owns the nodes. | |
783 | template <typename N, typename R, typename P, | |
784 | std::enable_if_t< | |
785 | std::is_same_v<btree_iterator<N, R, P>, const_iterator> && | |
786 | std::is_same_v<btree_iterator, iterator>, | |
787 | int> = 0> | |
788 | explicit btree_iterator(const btree_iterator<N, R, P> &x) | |
789 | : node(const_cast<node_type *>(x.node)), position(x.position) {} | |
7c673cae FG |
790 | |
791 | // Increment/decrement the iterator. | |
792 | void increment() { | |
793 | if (node->leaf() && ++position < node->count()) { | |
794 | return; | |
795 | } | |
796 | increment_slow(); | |
797 | } | |
7c673cae FG |
798 | void increment_slow(); |
799 | ||
800 | void decrement() { | |
801 | if (node->leaf() && --position >= 0) { | |
802 | return; | |
803 | } | |
804 | decrement_slow(); | |
805 | } | |
806 | void decrement_slow(); | |
807 | ||
9f95a23c | 808 | public: |
7c673cae FG |
809 | bool operator==(const const_iterator &x) const { |
810 | return node == x.node && position == x.position; | |
811 | } | |
812 | bool operator!=(const const_iterator &x) const { | |
813 | return node != x.node || position != x.position; | |
1e59de90 TL |
814 | } |
815 | bool operator==(const iterator& x) const { | |
816 | return node == x.node && position == x.position; | |
817 | } | |
818 | bool operator!=(const iterator& x) const { | |
819 | return node != x.node || position != x.position; | |
7c673cae FG |
820 | } |
821 | ||
822 | // Accessors for the key/value the iterator is pointing at. | |
7c673cae FG |
823 | reference operator*() const { |
824 | return node->value(position); | |
825 | } | |
826 | pointer operator->() const { | |
827 | return &node->value(position); | |
828 | } | |
829 | ||
9f95a23c | 830 | btree_iterator& operator++() { |
7c673cae FG |
831 | increment(); |
832 | return *this; | |
833 | } | |
9f95a23c | 834 | btree_iterator& operator--() { |
7c673cae FG |
835 | decrement(); |
836 | return *this; | |
837 | } | |
9f95a23c TL |
838 | btree_iterator operator++(int) { |
839 | btree_iterator tmp = *this; | |
7c673cae FG |
840 | ++*this; |
841 | return tmp; | |
842 | } | |
9f95a23c TL |
843 | btree_iterator operator--(int) { |
844 | btree_iterator tmp = *this; | |
7c673cae FG |
845 | --*this; |
846 | return tmp; | |
847 | } | |
848 | ||
9f95a23c TL |
849 | private: |
850 | template <typename Params> | |
851 | friend class btree; | |
852 | template <typename Tree> | |
853 | friend class btree_container; | |
854 | template <typename Tree> | |
855 | friend class btree_set_container; | |
856 | template <typename Tree> | |
857 | friend class btree_map_container; | |
858 | template <typename Tree> | |
859 | friend class btree_multiset_container; | |
860 | template <typename N, typename R, typename P> | |
861 | friend struct btree_iterator; | |
862 | ||
863 | const key_type &key() const { return node->key(position); } | |
864 | slot_type *slot() { return node->slot(position); } | |
865 | ||
7c673cae | 866 | // The node in the tree the iterator is pointing at. |
9f95a23c | 867 | Node *node = nullptr; |
7c673cae | 868 | // The position within the node of the tree the iterator is pointing at. |
9f95a23c | 869 | int position = -1; |
7c673cae FG |
870 | }; |
871 | ||
9f95a23c TL |
872 | template <size_t Alignment, class Alloc> |
873 | class AlignedAlloc { | |
874 | struct alignas(Alignment) M {}; | |
875 | using alloc_t = | |
876 | typename std::allocator_traits<Alloc>::template rebind_alloc<M>; | |
877 | using traits_t = | |
878 | typename std::allocator_traits<Alloc>::template rebind_traits<M>; | |
879 | static constexpr size_t num_aligned_objects(size_t size) { | |
880 | return (size + sizeof(M) - 1) / sizeof(M); | |
881 | } | |
882 | public: | |
883 | static void* allocate(Alloc* alloc, size_t size) { | |
884 | alloc_t aligned_alloc(*alloc); | |
885 | void* p = traits_t::allocate(aligned_alloc, | |
886 | num_aligned_objects(size)); | |
887 | assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 && | |
888 | "allocator does not respect alignment"); | |
889 | return p; | |
890 | } | |
891 | static void deallocate(Alloc* alloc, void* p, size_t size) { | |
892 | alloc_t aligned_alloc(*alloc); | |
893 | traits_t::deallocate(aligned_alloc, static_cast<M*>(p), | |
894 | num_aligned_objects(size)); | |
7c673cae FG |
895 | } |
896 | }; | |
897 | ||
898 | template <typename Params> | |
9f95a23c TL |
899 | class btree { |
900 | using node_type = btree_node<Params>; | |
901 | using is_key_compare_to = typename Params::is_key_compare_to; | |
902 | ||
903 | // We use a static empty node for the root/leftmost/rightmost of empty btrees | |
904 | // in order to avoid branching in begin()/end(). | |
905 | struct alignas(node_type::Alignment()) EmptyNodeType : node_type { | |
906 | using field_type = typename node_type::field_type; | |
907 | node_type *parent; | |
908 | field_type position = 0; | |
909 | field_type count = 0; | |
910 | // max_count must be != kInternalNodeMaxCount (so that this node is regarded | |
911 | // as a leaf node). max_count() is never called when the tree is empty. | |
912 | field_type max_count = node_type::kInternalNodeMaxCount + 1; | |
913 | ||
914 | constexpr EmptyNodeType(node_type *p) : parent(p) {} | |
7c673cae FG |
915 | }; |
916 | ||
9f95a23c TL |
917 | static node_type *EmptyNode() { |
918 | static constexpr EmptyNodeType empty_node( | |
919 | const_cast<EmptyNodeType *>(&empty_node)); | |
920 | return const_cast<EmptyNodeType *>(&empty_node); | |
921 | } | |
922 | ||
923 | constexpr static int kNodeValues = node_type::kNodeValues; | |
924 | constexpr static int kMinNodeValues = kNodeValues / 2; | |
925 | constexpr static int kValueSize = node_type::kValueSize; | |
926 | ||
7c673cae | 927 | // A helper class to get the empty base class optimization for 0-size |
9f95a23c TL |
928 | // allocators. Base is allocator_type. |
929 | // (e.g. empty_base_handle<key_compare, allocator_type, node_type*>). If Base is | |
7c673cae FG |
930 | // 0-size, the compiler doesn't have to reserve any space for it and |
931 | // sizeof(empty_base_handle) will simply be sizeof(Data). Google [empty base | |
932 | // class optimization] for more details. | |
9f95a23c TL |
933 | template <typename Base1, typename Base2, typename Data> |
934 | struct empty_base_handle : public Base1, Base2 { | |
935 | empty_base_handle(const Base1 &b1, const Base2 &b2, const Data &d) | |
936 | : Base1(b1), | |
937 | Base2(b2), | |
938 | data(d) {} | |
7c673cae FG |
939 | Data data; |
940 | }; | |
941 | ||
942 | struct node_stats { | |
9f95a23c TL |
943 | using size_type = typename Params::size_type; |
944 | ||
945 | node_stats(size_type l, size_type i) | |
7c673cae FG |
946 | : leaf_nodes(l), |
947 | internal_nodes(i) { | |
948 | } | |
949 | ||
950 | node_stats& operator+=(const node_stats &x) { | |
951 | leaf_nodes += x.leaf_nodes; | |
952 | internal_nodes += x.internal_nodes; | |
953 | return *this; | |
954 | } | |
955 | ||
9f95a23c TL |
956 | size_type leaf_nodes; |
957 | size_type internal_nodes; | |
7c673cae FG |
958 | }; |
959 | ||
960 | public: | |
9f95a23c TL |
961 | using key_type = typename Params::key_type; |
962 | using value_type = typename Params::value_type; | |
963 | using size_type = typename Params::size_type; | |
964 | using difference_type = typename Params::difference_type; | |
965 | using key_compare = typename Params::key_compare; | |
966 | using value_compare = typename Params::value_compare; | |
967 | using allocator_type = typename Params::allocator_type; | |
968 | using reference = typename Params::reference; | |
969 | using const_reference = typename Params::const_reference; | |
970 | using pointer = typename Params::pointer; | |
971 | using const_pointer = typename Params::const_pointer; | |
972 | using iterator = btree_iterator<node_type, reference, pointer>; | |
973 | using const_iterator = typename iterator::const_iterator; | |
974 | using reverse_iterator = std::reverse_iterator<iterator>; | |
975 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; | |
976 | ||
977 | // Internal types made public for use by btree_container types. | |
978 | using params_type = Params; | |
979 | ||
980 | private: | |
981 | // For use in copy_or_move_values_in_order. | |
982 | const value_type &maybe_move_from_iterator(const_iterator x) { return *x; } | |
983 | value_type &&maybe_move_from_iterator(iterator x) { return std::move(*x); } | |
984 | ||
985 | // Copies or moves (depending on the template parameter) the values in | |
986 | // x into this btree in their order in x. This btree must be empty before this | |
987 | // method is called. This method is used in copy construction, copy | |
988 | // assignment, and move assignment. | |
989 | template <typename Btree> | |
990 | void copy_or_move_values_in_order(Btree *x); | |
991 | ||
992 | // Validates that various assumptions/requirements are true at compile time. | |
993 | constexpr static bool static_assert_validation(); | |
7c673cae FG |
994 | |
995 | public: | |
7c673cae FG |
996 | btree(const key_compare &comp, const allocator_type &alloc); |
997 | ||
9f95a23c TL |
998 | btree(const btree &x); |
999 | btree(btree &&x) noexcept | |
1000 | : root_(std::move(x.root_)), | |
1001 | rightmost_(std::exchange(x.rightmost_, EmptyNode())), | |
1002 | size_(std::exchange(x.size_, 0)) { | |
1003 | x.mutable_root() = EmptyNode(); | |
1004 | } | |
7c673cae | 1005 | |
7c673cae | 1006 | ~btree() { |
9f95a23c TL |
1007 | // Put static_asserts in destructor to avoid triggering them before the type |
1008 | // is complete. | |
1009 | static_assert(static_assert_validation(), "This call must be elided."); | |
7c673cae FG |
1010 | clear(); |
1011 | } | |
1012 | ||
9f95a23c TL |
1013 | // Assign the contents of x to *this. |
1014 | btree &operator=(const btree &x); | |
1015 | btree &operator=(btree &&x) noexcept; | |
1016 | ||
7c673cae FG |
1017 | iterator begin() { |
1018 | return iterator(leftmost(), 0); | |
1019 | } | |
1020 | const_iterator begin() const { | |
1021 | return const_iterator(leftmost(), 0); | |
1022 | } | |
1023 | iterator end() { | |
9f95a23c | 1024 | return iterator(rightmost_, rightmost_->count()); |
7c673cae FG |
1025 | } |
1026 | const_iterator end() const { | |
9f95a23c | 1027 | return const_iterator(rightmost_, rightmost_->count()); |
7c673cae FG |
1028 | } |
1029 | reverse_iterator rbegin() { | |
1030 | return reverse_iterator(end()); | |
1031 | } | |
1032 | const_reverse_iterator rbegin() const { | |
1033 | return const_reverse_iterator(end()); | |
1034 | } | |
1035 | reverse_iterator rend() { | |
1036 | return reverse_iterator(begin()); | |
1037 | } | |
1038 | const_reverse_iterator rend() const { | |
1039 | return const_reverse_iterator(begin()); | |
1040 | } | |
1041 | ||
1042 | // Finds the first element whose key is not less than key. | |
9f95a23c TL |
1043 | template <typename K> |
1044 | iterator lower_bound(const K &key) { | |
1045 | return internal_end(internal_lower_bound(key)); | |
7c673cae | 1046 | } |
9f95a23c TL |
1047 | template <typename K> |
1048 | const_iterator lower_bound(const K &key) const { | |
1049 | return internal_end(internal_lower_bound(key)); | |
7c673cae FG |
1050 | } |
1051 | ||
1052 | // Finds the first element whose key is greater than key. | |
9f95a23c TL |
1053 | template <typename K> |
1054 | iterator upper_bound(const K &key) { | |
1055 | return internal_end(internal_upper_bound(key)); | |
7c673cae | 1056 | } |
9f95a23c TL |
1057 | template <typename K> |
1058 | const_iterator upper_bound(const K &key) const { | |
1059 | return internal_end(internal_upper_bound(key)); | |
7c673cae FG |
1060 | } |
1061 | ||
1062 | // Finds the range of values which compare equal to key. The first member of | |
1063 | // the returned pair is equal to lower_bound(key). The second member pair of | |
1064 | // the pair is equal to upper_bound(key). | |
9f95a23c TL |
1065 | template <typename K> |
1066 | std::pair<iterator, iterator> equal_range(const K &key) { | |
1067 | return {lower_bound(key), upper_bound(key)}; | |
7c673cae | 1068 | } |
9f95a23c TL |
1069 | template <typename K> |
1070 | std::pair<const_iterator, const_iterator> equal_range(const K &key) const { | |
1071 | return {lower_bound(key), upper_bound(key)}; | |
7c673cae FG |
1072 | } |
1073 | ||
7c673cae FG |
1074 | // Inserts a value into the btree only if it does not already exist. The |
1075 | // boolean return value indicates whether insertion succeeded or failed. | |
9f95a23c TL |
1076 | // Requirement: if `key` already exists in the btree, does not consume `args`. |
1077 | // Requirement: `key` is never referenced after consuming `args`. | |
1078 | template <typename... Args> | |
1079 | std::pair<iterator, bool> insert_unique(const key_type &key, Args &&... args); | |
7c673cae | 1080 | |
9f95a23c TL |
1081 | // Inserts with hint. Checks to see if the value should be placed immediately |
1082 | // before `position` in the tree. If so, then the insertion will take | |
7c673cae | 1083 | // amortized constant time. If not, the insertion will take amortized |
9f95a23c TL |
1084 | // logarithmic time as if a call to insert_unique() were made. |
1085 | // Requirement: if `key` already exists in the btree, does not consume `args`. | |
1086 | // Requirement: `key` is never referenced after consuming `args`. | |
1087 | template <typename... Args> | |
1088 | std::pair<iterator, bool> insert_hint_unique(iterator position, | |
1089 | const key_type &key, | |
1090 | Args &&... args); | |
7c673cae FG |
1091 | |
1092 | // Insert a range of values into the btree. | |
1093 | template <typename InputIterator> | |
9f95a23c | 1094 | void insert_iterator_unique(InputIterator b, InputIterator e); |
7c673cae | 1095 | |
9f95a23c TL |
1096 | // Inserts a value into the btree. |
1097 | template <typename ValueType> | |
1098 | iterator insert_multi(const key_type &key, ValueType &&v); | |
7c673cae FG |
1099 | |
1100 | // Inserts a value into the btree. | |
9f95a23c TL |
1101 | template <typename ValueType> |
1102 | iterator insert_multi(ValueType &&v) { | |
1103 | return insert_multi(params_type::key(v), std::forward<ValueType>(v)); | |
7c673cae FG |
1104 | } |
1105 | ||
1106 | // Insert with hint. Check to see if the value should be placed immediately | |
1107 | // before position in the tree. If it does, then the insertion will take | |
1108 | // amortized constant time. If not, the insertion will take amortized | |
1109 | // logarithmic time as if a call to insert_multi(v) were made. | |
9f95a23c TL |
1110 | template <typename ValueType> |
1111 | iterator insert_hint_multi(iterator position, ValueType &&v); | |
7c673cae FG |
1112 | |
1113 | // Insert a range of values into the btree. | |
1114 | template <typename InputIterator> | |
9f95a23c | 1115 | void insert_iterator_multi(InputIterator b, InputIterator e); |
7c673cae FG |
1116 | |
1117 | // Erase the specified iterator from the btree. The iterator must be valid | |
1118 | // (i.e. not equal to end()). Return an iterator pointing to the node after | |
1119 | // the one that was erased (or end() if none exists). | |
9f95a23c | 1120 | // Requirement: does not read the value at `*iter`. |
7c673cae FG |
1121 | iterator erase(iterator iter); |
1122 | ||
9f95a23c TL |
1123 | // Erases range. Returns the number of keys erased and an iterator pointing |
1124 | // to the element after the last erased element. | |
1125 | std::pair<size_type, iterator> erase(iterator begin, iterator end); | |
7c673cae FG |
1126 | |
1127 | // Erases the specified key from the btree. Returns 1 if an element was | |
1128 | // erased and 0 otherwise. | |
9f95a23c TL |
1129 | template <typename K> |
1130 | size_type erase_unique(const K &key); | |
7c673cae FG |
1131 | |
1132 | // Erases all of the entries matching the specified key from the | |
1133 | // btree. Returns the number of elements erased. | |
9f95a23c TL |
1134 | template <typename K> |
1135 | size_type erase_multi(const K &key); | |
7c673cae FG |
1136 | |
1137 | // Finds the iterator corresponding to a key or returns end() if the key is | |
1138 | // not present. | |
9f95a23c TL |
1139 | template <typename K> |
1140 | iterator find(const K &key) { | |
1141 | return internal_end(internal_find(key)); | |
7c673cae | 1142 | } |
9f95a23c TL |
1143 | template <typename K> |
1144 | const_iterator find(const K &key) const { | |
1145 | return internal_end(internal_find(key)); | |
7c673cae FG |
1146 | } |
1147 | ||
1148 | // Returns a count of the number of times the key appears in the btree. | |
9f95a23c TL |
1149 | template <typename K> |
1150 | size_type count_unique(const K &key) const { | |
1151 | const iterator begin = internal_find(key); | |
1152 | if (begin.node == nullptr) { | |
7c673cae FG |
1153 | // The key doesn't exist in the tree. |
1154 | return 0; | |
1155 | } | |
1156 | return 1; | |
1157 | } | |
1158 | // Returns a count of the number of times the key appears in the btree. | |
9f95a23c TL |
1159 | template <typename K> |
1160 | size_type count_multi(const K &key) const { | |
1161 | const auto range = equal_range(key); | |
1162 | return std::distance(range.first, range.second); | |
7c673cae FG |
1163 | } |
1164 | ||
1165 | // Clear the btree, deleting all of the values it contains. | |
1166 | void clear(); | |
1167 | ||
1168 | // Swap the contents of *this and x. | |
9f95a23c | 1169 | void swap(btree &x); |
7c673cae | 1170 | |
9f95a23c TL |
1171 | const key_compare &key_comp() const noexcept { |
1172 | return *static_cast<const key_compare*>(&root_); | |
7c673cae | 1173 | } |
9f95a23c TL |
1174 | template <typename K, typename LK> |
1175 | bool compare_keys(const K &x, const LK &y) const { | |
1176 | return compare_result_as_less_than(key_comp()(x, y)); | |
7c673cae FG |
1177 | } |
1178 | ||
1179 | // Verifies the structure of the btree. | |
1180 | void verify() const; | |
1181 | ||
9f95a23c TL |
1182 | // Size routines. |
1183 | size_type size() const { return size_; } | |
7c673cae | 1184 | size_type max_size() const { return std::numeric_limits<size_type>::max(); } |
9f95a23c | 1185 | bool empty() const { return size_ == 0; } |
7c673cae FG |
1186 | |
1187 | // The height of the btree. An empty tree will have height 0. | |
1188 | size_type height() const { | |
1189 | size_type h = 0; | |
9f95a23c | 1190 | if (!empty()) { |
7c673cae FG |
1191 | // Count the length of the chain from the leftmost node up to the |
1192 | // root. We actually count from the root back around to the level below | |
1193 | // the root, but the calculation is the same because of the circularity | |
1194 | // of that traversal. | |
1195 | const node_type *n = root(); | |
1196 | do { | |
1197 | ++h; | |
1198 | n = n->parent(); | |
1199 | } while (n != root()); | |
1200 | } | |
1201 | return h; | |
1202 | } | |
1203 | ||
1204 | // The number of internal, leaf and total nodes used by the btree. | |
1205 | size_type leaf_nodes() const { | |
1206 | return internal_stats(root()).leaf_nodes; | |
1207 | } | |
1208 | size_type internal_nodes() const { | |
1209 | return internal_stats(root()).internal_nodes; | |
1210 | } | |
1211 | size_type nodes() const { | |
1212 | node_stats stats = internal_stats(root()); | |
1213 | return stats.leaf_nodes + stats.internal_nodes; | |
1214 | } | |
1215 | ||
1216 | // The total number of bytes used by the btree. | |
1217 | size_type bytes_used() const { | |
1218 | node_stats stats = internal_stats(root()); | |
1219 | if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) { | |
1220 | return sizeof(*this) + | |
9f95a23c | 1221 | node_type::LeafSize(root()->max_count()); |
7c673cae FG |
1222 | } else { |
1223 | return sizeof(*this) + | |
9f95a23c TL |
1224 | stats.leaf_nodes * node_type::LeafSize() + |
1225 | stats.internal_nodes * node_type::InternalSize(); | |
7c673cae FG |
1226 | } |
1227 | } | |
1228 | ||
1229 | // The average number of bytes used per value stored in the btree. | |
1230 | static double average_bytes_per_value() { | |
1231 | // Returns the number of bytes per value on a leaf node that is 75% | |
1232 | // full. Experimentally, this matches up nicely with the computed number of | |
1233 | // bytes per value in trees that had their values inserted in random order. | |
9f95a23c | 1234 | return node_type::LeafSize() / (kNodeValues * 0.75); |
7c673cae FG |
1235 | } |
1236 | ||
1237 | // The fullness of the btree. Computed as the number of elements in the btree | |
1238 | // divided by the maximum number of elements a tree with the current number | |
1239 | // of nodes could hold. A value of 1 indicates perfect space | |
1240 | // utilization. Smaller values indicate space wastage. | |
9f95a23c | 1241 | // Returns 0 for empty trees. |
7c673cae | 1242 | double fullness() const { |
9f95a23c TL |
1243 | if (empty()) return 0.0; |
1244 | return static_cast<double>(size()) / (nodes() * kNodeValues); | |
7c673cae FG |
1245 | } |
1246 | // The overhead of the btree structure in bytes per node. Computed as the | |
1247 | // total number of bytes used by the btree minus the number of bytes used for | |
1248 | // storing elements divided by the number of elements. | |
9f95a23c | 1249 | // Returns 0 for empty trees. |
7c673cae | 1250 | double overhead() const { |
9f95a23c TL |
1251 | if (empty()) return 0.0; |
1252 | return (bytes_used() - size() * sizeof(value_type)) / | |
1253 | static_cast<double>(size()); | |
1254 | } | |
1255 | ||
1256 | // The allocator used by the btree. | |
1257 | allocator_type get_allocator() const { | |
1258 | return allocator(); | |
7c673cae FG |
1259 | } |
1260 | ||
1261 | private: | |
1262 | // Internal accessor routines. | |
9f95a23c TL |
1263 | node_type *root() { return root_.data; } |
1264 | const node_type *root() const { return root_.data; } | |
1265 | node_type *&mutable_root() { return root_.data; } | |
1266 | key_compare *mutable_key_comp() noexcept { | |
1267 | return static_cast<key_compare*>(&root_); | |
1268 | } | |
7c673cae | 1269 | |
7c673cae | 1270 | node_type* rightmost() { |
9f95a23c | 1271 | return rightmost_; |
7c673cae FG |
1272 | } |
1273 | const node_type* rightmost() const { | |
9f95a23c | 1274 | return rightmost_; |
7c673cae | 1275 | } |
7c673cae FG |
1276 | // The leftmost node is stored as the parent of the root node. |
1277 | node_type* leftmost() { return root() ? root()->parent() : NULL; } | |
1278 | const node_type* leftmost() const { return root() ? root()->parent() : NULL; } | |
1279 | ||
1280 | // The size of the tree is stored in the root node. | |
1281 | size_type* mutable_size() { return root()->mutable_size(); } | |
1282 | ||
1283 | // Allocator routines. | |
9f95a23c TL |
1284 | allocator_type* mutable_allocator() noexcept { |
1285 | return static_cast<allocator_type*>(&root_); | |
7c673cae | 1286 | } |
9f95a23c TL |
1287 | const allocator_type& allocator() const noexcept { |
1288 | return *static_cast<const allocator_type*>(&root_); | |
1289 | } | |
1290 | ||
1291 | node_type *allocate(const size_type size) { | |
1292 | using aligned_alloc_t = | |
1293 | AlignedAlloc<node_type::Alignment(), allocator_type>; | |
1294 | return static_cast<node_type*>( | |
1295 | aligned_alloc_t::allocate(mutable_allocator(), size)); | |
7c673cae FG |
1296 | } |
1297 | ||
1298 | // Node creation/deletion routines. | |
1299 | node_type* new_internal_node(node_type *parent) { | |
9f95a23c | 1300 | node_type *p = allocate(node_type::InternalSize()); |
7c673cae FG |
1301 | return node_type::init_internal(p, parent); |
1302 | } | |
7c673cae | 1303 | node_type* new_leaf_node(node_type *parent) { |
9f95a23c | 1304 | node_type *p = allocate(node_type::LeafSize()); |
7c673cae FG |
1305 | return node_type::init_leaf(p, parent, kNodeValues); |
1306 | } | |
9f95a23c TL |
1307 | node_type *new_leaf_root_node(const int max_count) { |
1308 | node_type *p = allocate(node_type::LeafSize(max_count)); | |
1309 | return node_type::init_leaf(p, p, max_count); | |
7c673cae | 1310 | } |
9f95a23c TL |
1311 | |
1312 | // Deletion helper routines. | |
1313 | void erase_same_node(iterator begin, iterator end); | |
1314 | iterator erase_from_leaf_node(iterator begin, size_type to_erase); | |
1315 | iterator rebalance_after_delete(iterator iter); | |
1316 | ||
1317 | // Deallocates a node of a certain size in bytes using the allocator. | |
1318 | void deallocate(const size_type size, node_type *node) { | |
1319 | using aligned_alloc_t = | |
1320 | AlignedAlloc<node_type::Alignment(), allocator_type>; | |
1321 | aligned_alloc_t::deallocate(mutable_allocator(), node, size); | |
7c673cae | 1322 | } |
9f95a23c TL |
1323 | |
1324 | void delete_internal_node(node_type *node) { | |
1325 | node->destroy(mutable_allocator()); | |
1326 | deallocate(node_type::InternalSize(), node); | |
7c673cae FG |
1327 | } |
1328 | void delete_leaf_node(node_type *node) { | |
9f95a23c TL |
1329 | node->destroy(mutable_allocator()); |
1330 | deallocate(node_type::LeafSize(node->max_count()), node); | |
7c673cae FG |
1331 | } |
1332 | ||
1333 | // Rebalances or splits the node iter points to. | |
1334 | void rebalance_or_split(iterator *iter); | |
1335 | ||
1336 | // Merges the values of left, right and the delimiting key on their parent | |
1337 | // onto left, removing the delimiting key and deleting right. | |
1338 | void merge_nodes(node_type *left, node_type *right); | |
1339 | ||
1340 | // Tries to merge node with its left or right sibling, and failing that, | |
1341 | // rebalance with its left or right sibling. Returns true if a merge | |
1342 | // occurred, at which point it is no longer valid to access node. Returns | |
1343 | // false if no merging took place. | |
1344 | bool try_merge_or_rebalance(iterator *iter); | |
1345 | ||
1346 | // Tries to shrink the height of the tree by 1. | |
1347 | void try_shrink(); | |
1348 | ||
1349 | iterator internal_end(iterator iter) { | |
9f95a23c | 1350 | return iter.node != nullptr ? iter : end(); |
7c673cae FG |
1351 | } |
1352 | const_iterator internal_end(const_iterator iter) const { | |
9f95a23c | 1353 | return iter.node != nullptr ? iter : end(); |
7c673cae FG |
1354 | } |
1355 | ||
9f95a23c | 1356 | // Emplaces a value into the btree immediately before iter. Requires that |
7c673cae | 1357 | // key(v) <= iter.key() and (--iter).key() <= key(v). |
9f95a23c TL |
1358 | template <typename... Args> |
1359 | iterator internal_emplace(iterator iter, Args &&... args); | |
7c673cae FG |
1360 | |
1361 | // Returns an iterator pointing to the first value >= the value "iter" is | |
1362 | // pointing at. Note that "iter" might be pointing to an invalid location as | |
1363 | // iter.position == iter.node->count(). This routine simply moves iter up in | |
1364 | // the tree to a valid location. | |
9f95a23c | 1365 | // Requires: iter.node is non-null. |
7c673cae FG |
1366 | template <typename IterType> |
1367 | static IterType internal_last(IterType iter); | |
1368 | ||
1369 | // Returns an iterator pointing to the leaf position at which key would | |
1370 | // reside in the tree. We provide 2 versions of internal_locate. The first | |
9f95a23c TL |
1371 | // version uses a less-than comparator and is incapable of distinguishing when |
1372 | // there is an exact match. The second version is for the key-compare-to | |
1373 | // specialization and distinguishes exact matches. The key-compare-to | |
1374 | // specialization allows the caller to avoid a subsequent comparison to | |
1375 | // determine if an exact match was made, which is important for keys with | |
1376 | // expensive comparison, such as strings. | |
1377 | template <typename K> | |
1378 | SearchResult<iterator, is_key_compare_to::value> internal_locate( | |
1379 | const K &key) const; | |
1380 | ||
1381 | template <typename K> | |
1382 | SearchResult<iterator, false> internal_locate_impl( | |
1383 | const K &key, std::false_type /* IsCompareTo */) const; | |
1384 | ||
1385 | template <typename K> | |
1386 | SearchResult<iterator, true> internal_locate_impl( | |
1387 | const K &key, std::true_type /* IsCompareTo */) const; | |
7c673cae FG |
1388 | |
1389 | // Internal routine which implements lower_bound(). | |
9f95a23c TL |
1390 | template <typename K> |
1391 | iterator internal_lower_bound(const K &key) const; | |
7c673cae FG |
1392 | |
1393 | // Internal routine which implements upper_bound(). | |
9f95a23c TL |
1394 | template <typename K> |
1395 | iterator internal_upper_bound(const K &key) const; | |
7c673cae | 1396 | |
9f95a23c TL |
1397 | // Internal routine which implements find(). |
1398 | template <typename K> | |
1399 | iterator internal_find(const K &key) const; | |
7c673cae FG |
1400 | |
1401 | // Deletes a node and all of its children. | |
1402 | void internal_clear(node_type *node); | |
1403 | ||
7c673cae FG |
1404 | // Verifies the tree structure of node. |
1405 | int internal_verify(const node_type *node, | |
1406 | const key_type *lo, const key_type *hi) const; | |
1407 | ||
1408 | node_stats internal_stats(const node_type *node) const { | |
9f95a23c TL |
1409 | // The root can be a static empty node. |
1410 | if (node == nullptr || (node == root() && empty())) { | |
7c673cae FG |
1411 | return node_stats(0, 0); |
1412 | } | |
1413 | if (node->leaf()) { | |
1414 | return node_stats(1, 0); | |
1415 | } | |
1416 | node_stats res(0, 1); | |
1417 | for (int i = 0; i <= node->count(); ++i) { | |
1418 | res += internal_stats(node->child(i)); | |
1419 | } | |
1420 | return res; | |
1421 | } | |
1422 | ||
1423 | private: | |
9f95a23c | 1424 | empty_base_handle<key_compare, allocator_type, node_type*> root_; |
7c673cae | 1425 | |
9f95a23c TL |
1426 | // A pointer to the rightmost node. Note that the leftmost node is stored as |
1427 | // the root's parent. | |
1428 | node_type *rightmost_; | |
7c673cae | 1429 | |
9f95a23c TL |
1430 | // Number of values. |
1431 | size_type size_; | |
7c673cae FG |
1432 | }; |
1433 | ||
1434 | //// | |
1435 | // btree_node methods | |
1436 | template <typename P> | |
9f95a23c TL |
1437 | template <typename... Args> |
1438 | inline void btree_node<P>::emplace_value(const size_type i, | |
1439 | allocator_type *alloc, | |
1440 | Args &&... args) { | |
1441 | assert(i <= count()); | |
1442 | // Shift old values to create space for new value and then construct it in | |
1443 | // place. | |
1444 | if (i < count()) { | |
1445 | value_init(count(), alloc, slot(count() - 1)); | |
1446 | std::copy_backward(std::make_move_iterator(slot(i)), | |
1447 | std::make_move_iterator(slot(count() - 1)), | |
1448 | slot(count())); | |
1449 | value_destroy(i, alloc); | |
1450 | } | |
1451 | value_init(i, alloc, std::forward<Args>(args)...); | |
7c673cae FG |
1452 | set_count(count() + 1); |
1453 | ||
9f95a23c TL |
1454 | if (!leaf() && count() > i + 1) { |
1455 | for (int j = count(); j > i + 1; --j) { | |
1456 | set_child(j, child(j - 1)); | |
7c673cae | 1457 | } |
9f95a23c | 1458 | clear_child(i + 1); |
7c673cae FG |
1459 | } |
1460 | } | |
1461 | ||
1462 | template <typename P> | |
9f95a23c TL |
1463 | inline void btree_node<P>::remove_value(const int i, allocator_type *alloc) { |
1464 | if (!leaf() && count() > i + 1) { | |
1465 | assert(child(i + 1)->count() == 0); | |
1466 | for (size_type j = i + 1; j < count(); ++j) { | |
1467 | set_child(j, child(j + 1)); | |
7c673cae | 1468 | } |
9f95a23c | 1469 | clear_child(count()); |
7c673cae FG |
1470 | } |
1471 | ||
9f95a23c | 1472 | remove_values_ignore_children(i, /*to_erase=*/1, alloc); |
7c673cae FG |
1473 | } |
1474 | ||
1475 | template <typename P> | |
9f95a23c TL |
1476 | inline void btree_node<P>::remove_values_ignore_children( |
1477 | const int i, const int to_erase, allocator_type *alloc) { | |
1478 | assert(to_erase >= 0); | |
1479 | std::copy(std::make_move_iterator(slot(i + to_erase)), | |
1480 | std::make_move_iterator(slot(count())), | |
1481 | slot(i)); | |
1482 | value_destroy_n(count() - to_erase, to_erase, alloc); | |
1483 | set_count(count() - to_erase); | |
1484 | } | |
7c673cae | 1485 | |
9f95a23c TL |
1486 | template <typename P> |
1487 | void btree_node<P>::rebalance_right_to_left(const int to_move, | |
1488 | btree_node *right, | |
1489 | allocator_type *alloc) { | |
1490 | assert(parent() == right->parent()); | |
1491 | assert(position() + 1 == right->position()); | |
1492 | assert(right->count() >= count()); | |
1493 | assert(to_move >= 1); | |
1494 | assert(to_move <= right->count()); | |
7c673cae | 1495 | |
9f95a23c TL |
1496 | // 1) Move the delimiting value in the parent to the left node. |
1497 | value_init(count(), alloc, parent()->slot(position())); | |
7c673cae | 1498 | |
9f95a23c TL |
1499 | // 2) Move the (to_move - 1) values from the right node to the left node. |
1500 | right->uninitialized_move_n(to_move - 1, 0, count() + 1, this, alloc); | |
1501 | ||
1502 | // 3) Move the new delimiting value to the parent from the right node. | |
1503 | params_type::move(alloc, right->slot(to_move - 1), | |
1504 | parent()->slot(position())); | |
1505 | ||
1506 | // 4) Shift the values in the right node to their correct position. | |
1507 | std::copy(std::make_move_iterator(right->slot(to_move)), | |
1508 | std::make_move_iterator(right->slot(right->count())), | |
1509 | right->slot(0)); | |
1510 | ||
1511 | // 5) Destroy the now-empty to_move entries in the right node. | |
1512 | right->value_destroy_n(right->count() - to_move, to_move, alloc); | |
7c673cae FG |
1513 | |
1514 | if (!leaf()) { | |
1515 | // Move the child pointers from the right to the left node. | |
1516 | for (int i = 0; i < to_move; ++i) { | |
9f95a23c | 1517 | init_child(count() + i + 1, right->child(i)); |
7c673cae | 1518 | } |
9f95a23c TL |
1519 | for (int i = 0; i <= right->count() - to_move; ++i) { |
1520 | assert(i + to_move <= right->max_count()); | |
1521 | right->init_child(i, right->child(i + to_move)); | |
1522 | right->clear_child(i + to_move); | |
7c673cae FG |
1523 | } |
1524 | } | |
1525 | ||
9f95a23c | 1526 | // Fixup the counts on the left and right nodes. |
7c673cae | 1527 | set_count(count() + to_move); |
9f95a23c | 1528 | right->set_count(right->count() - to_move); |
7c673cae FG |
1529 | } |
1530 | ||
1531 | template <typename P> | |
9f95a23c TL |
1532 | void btree_node<P>::rebalance_left_to_right(const int to_move, |
1533 | btree_node *right, | |
1534 | allocator_type *alloc) { | |
1535 | assert(parent() == right->parent()); | |
1536 | assert(position() + 1 == right->position()); | |
1537 | assert(count() >= right->count()); | |
1538 | assert(to_move >= 1); | |
1539 | assert(to_move <= count()); | |
1540 | ||
1541 | // Values in the right node are shifted to the right to make room for the | |
1542 | // new to_move values. Then, the delimiting value in the parent and the | |
1543 | // other (to_move - 1) values in the left node are moved into the right node. | |
1544 | // Lastly, a new delimiting value is moved from the left node into the | |
1545 | // parent, and the remaining empty left node entries are destroyed. | |
1546 | ||
1547 | if (right->count() >= to_move) { | |
1548 | // The original location of the right->count() values are sufficient to hold | |
1549 | // the new to_move entries from the parent and left node. | |
1550 | ||
1551 | // 1) Shift existing values in the right node to their correct positions. | |
1552 | right->uninitialized_move_n(to_move, right->count() - to_move, | |
1553 | right->count(), right, alloc); | |
1554 | std::copy_backward(std::make_move_iterator(right->slot(0)), | |
1555 | std::make_move_iterator(right->slot(right->count() - to_move)), | |
1556 | right->slot(right->count())); | |
1557 | ||
1558 | // 2) Move the delimiting value in the parent to the right node. | |
1559 | params_type::move(alloc, parent()->slot(position()), | |
1560 | right->slot(to_move - 1)); | |
1561 | ||
1562 | // 3) Move the (to_move - 1) values from the left node to the right node. | |
1563 | std::copy(std::make_move_iterator(slot(count() - (to_move - 1))), | |
1564 | std::make_move_iterator(slot(count())), | |
1565 | right->slot(0)); | |
1566 | } else { | |
1567 | // The right node does not have enough initialized space to hold the new | |
1568 | // to_move entries, so part of them will move to uninitialized space. | |
7c673cae | 1569 | |
9f95a23c TL |
1570 | // 1) Shift existing values in the right node to their correct positions. |
1571 | right->uninitialized_move_n(right->count(), 0, to_move, right, alloc); | |
7c673cae | 1572 | |
9f95a23c TL |
1573 | // 2) Move the delimiting value in the parent to the right node. |
1574 | right->value_init(to_move - 1, alloc, parent()->slot(position())); | |
7c673cae | 1575 | |
9f95a23c TL |
1576 | // 3) Move the (to_move - 1) values from the left node to the right node. |
1577 | const size_type uninitialized_remaining = to_move - right->count() - 1; | |
1578 | uninitialized_move_n(uninitialized_remaining, | |
1579 | count() - uninitialized_remaining, right->count(), | |
1580 | right, alloc); | |
1581 | std::copy(std::make_move_iterator(slot(count() - (to_move - 1))), | |
1582 | std::make_move_iterator(slot(count() - uninitialized_remaining)), | |
1583 | right->slot(0)); | |
7c673cae FG |
1584 | } |
1585 | ||
9f95a23c TL |
1586 | // 4) Move the new delimiting value to the parent from the left node. |
1587 | params_type::move(alloc, slot(count() - to_move), parent()->slot(position())); | |
1588 | ||
1589 | // 5) Destroy the now-empty to_move entries in the left node. | |
1590 | value_destroy_n(count() - to_move, to_move, alloc); | |
1591 | ||
7c673cae FG |
1592 | if (!leaf()) { |
1593 | // Move the child pointers from the left to the right node. | |
9f95a23c TL |
1594 | for (int i = right->count(); i >= 0; --i) { |
1595 | right->init_child(i + to_move, right->child(i)); | |
1596 | right->clear_child(i); | |
7c673cae FG |
1597 | } |
1598 | for (int i = 1; i <= to_move; ++i) { | |
9f95a23c TL |
1599 | right->init_child(i - 1, child(count() - to_move + i)); |
1600 | clear_child(count() - to_move + i); | |
7c673cae FG |
1601 | } |
1602 | } | |
1603 | ||
9f95a23c | 1604 | // Fixup the counts on the left and right nodes. |
7c673cae | 1605 | set_count(count() - to_move); |
9f95a23c | 1606 | right->set_count(right->count() + to_move); |
7c673cae FG |
1607 | } |
1608 | ||
1609 | template <typename P> | |
9f95a23c TL |
1610 | void btree_node<P>::split(const int insert_position, btree_node *dest, |
1611 | allocator_type *alloc) { | |
1612 | assert(dest->count() == 0); | |
1613 | assert(max_count() == kNodeValues); | |
7c673cae FG |
1614 | |
1615 | // We bias the split based on the position being inserted. If we're | |
1616 | // inserting at the beginning of the left node then bias the split to put | |
1617 | // more values on the right node. If we're inserting at the end of the | |
1618 | // right node then bias the split to put more values on the left node. | |
1619 | if (insert_position == 0) { | |
1620 | dest->set_count(count() - 1); | |
9f95a23c | 1621 | } else if (insert_position == kNodeValues) { |
7c673cae FG |
1622 | dest->set_count(0); |
1623 | } else { | |
1624 | dest->set_count(count() / 2); | |
1625 | } | |
1626 | set_count(count() - dest->count()); | |
9f95a23c | 1627 | assert(count() >= 1); |
7c673cae FG |
1628 | |
1629 | // Move values from the left sibling to the right sibling. | |
9f95a23c TL |
1630 | uninitialized_move_n(dest->count(), count(), 0, dest, alloc); |
1631 | ||
1632 | // Destroy the now-empty entries in the left node. | |
1633 | value_destroy_n(count(), dest->count(), alloc); | |
7c673cae FG |
1634 | |
1635 | // The split key is the largest value in the left sibling. | |
1636 | set_count(count() - 1); | |
9f95a23c TL |
1637 | parent()->emplace_value(position(), alloc, slot(count())); |
1638 | value_destroy(count(), alloc); | |
1639 | parent()->init_child(position() + 1, dest); | |
7c673cae FG |
1640 | |
1641 | if (!leaf()) { | |
1642 | for (int i = 0; i <= dest->count(); ++i) { | |
9f95a23c TL |
1643 | assert(child(count() + i + 1) != nullptr); |
1644 | dest->init_child(i, child(count() + i + 1)); | |
1645 | clear_child(count() + i + 1); | |
7c673cae FG |
1646 | } |
1647 | } | |
1648 | } | |
1649 | ||
1650 | template <typename P> | |
9f95a23c TL |
1651 | void btree_node<P>::merge(btree_node *src, allocator_type *alloc) { |
1652 | assert(parent() == src->parent()); | |
1653 | assert(position() + 1 == src->position()); | |
7c673cae FG |
1654 | |
1655 | // Move the delimiting value to the left node. | |
9f95a23c | 1656 | value_init(count(), alloc, parent()->slot(position())); |
7c673cae | 1657 | |
9f95a23c TL |
1658 | // Move the values from the right to the left node. |
1659 | src->uninitialized_move_n(src->count(), 0, count() + 1, this, alloc); | |
1660 | ||
1661 | // Destroy the now-empty entries in the right node. | |
1662 | src->value_destroy_n(0, src->count(), alloc); | |
7c673cae FG |
1663 | |
1664 | if (!leaf()) { | |
1665 | // Move the child pointers from the right to the left node. | |
1666 | for (int i = 0; i <= src->count(); ++i) { | |
9f95a23c TL |
1667 | init_child(count() + i + 1, src->child(i)); |
1668 | src->clear_child(i); | |
7c673cae FG |
1669 | } |
1670 | } | |
1671 | ||
1672 | // Fixup the counts on the src and dest nodes. | |
1673 | set_count(1 + count() + src->count()); | |
1674 | src->set_count(0); | |
1675 | ||
1676 | // Remove the value on the parent node. | |
9f95a23c | 1677 | parent()->remove_value(position(), alloc); |
7c673cae FG |
1678 | } |
1679 | ||
1680 | template <typename P> | |
9f95a23c TL |
1681 | void btree_node<P>::swap(btree_node *x, allocator_type *alloc) { |
1682 | using std::swap; | |
1683 | assert(leaf() == x->leaf()); | |
7c673cae | 1684 | |
9f95a23c TL |
1685 | // Determine which is the smaller/larger node. |
1686 | btree_node *smaller = this, *larger = x; | |
1687 | if (smaller->count() > larger->count()) { | |
1688 | swap(smaller, larger); | |
7c673cae FG |
1689 | } |
1690 | ||
9f95a23c TL |
1691 | // Swap the values. |
1692 | std::swap_ranges(smaller->slot(0), smaller->slot(smaller->count()), | |
1693 | larger->slot(0)); | |
1694 | ||
1695 | // Move values that can't be swapped. | |
1696 | const size_type to_move = larger->count() - smaller->count(); | |
1697 | larger->uninitialized_move_n(to_move, smaller->count(), smaller->count(), | |
1698 | smaller, alloc); | |
1699 | larger->value_destroy_n(smaller->count(), to_move, alloc); | |
1700 | ||
7c673cae FG |
1701 | if (!leaf()) { |
1702 | // Swap the child pointers. | |
9f95a23c TL |
1703 | std::swap_ranges(&smaller->mutable_child(0), |
1704 | &smaller->mutable_child(smaller->count() + 1), | |
1705 | &larger->mutable_child(0)); | |
1706 | // Update swapped children's parent pointers. | |
1707 | int i = 0; | |
1708 | for (; i <= smaller->count(); ++i) { | |
1709 | smaller->child(i)->set_parent(smaller); | |
1710 | larger->child(i)->set_parent(larger); | |
7c673cae | 1711 | } |
9f95a23c TL |
1712 | // Move the child pointers that couldn't be swapped. |
1713 | for (; i <= larger->count(); ++i) { | |
1714 | smaller->init_child(i, larger->child(i)); | |
1715 | larger->clear_child(i); | |
7c673cae FG |
1716 | } |
1717 | } | |
1718 | ||
1719 | // Swap the counts. | |
9f95a23c | 1720 | swap(mutable_count(), x->mutable_count()); |
7c673cae FG |
1721 | } |
1722 | ||
1723 | //// | |
1724 | // btree_iterator methods | |
1725 | template <typename N, typename R, typename P> | |
1726 | void btree_iterator<N, R, P>::increment_slow() { | |
1727 | if (node->leaf()) { | |
9f95a23c TL |
1728 | assert(position >= node->count()); |
1729 | btree_iterator save(*this); | |
7c673cae | 1730 | while (position == node->count() && !node->is_root()) { |
9f95a23c | 1731 | assert(node->parent()->child(node->position()) == node); |
7c673cae FG |
1732 | position = node->position(); |
1733 | node = node->parent(); | |
1734 | } | |
1735 | if (position == node->count()) { | |
1736 | *this = save; | |
1737 | } | |
1738 | } else { | |
9f95a23c | 1739 | assert(position < node->count()); |
7c673cae FG |
1740 | node = node->child(position + 1); |
1741 | while (!node->leaf()) { | |
1742 | node = node->child(0); | |
1743 | } | |
1744 | position = 0; | |
1745 | } | |
1746 | } | |
1747 | ||
7c673cae FG |
1748 | template <typename N, typename R, typename P> |
1749 | void btree_iterator<N, R, P>::decrement_slow() { | |
1750 | if (node->leaf()) { | |
9f95a23c TL |
1751 | assert(position <= -1); |
1752 | btree_iterator save(*this); | |
7c673cae | 1753 | while (position < 0 && !node->is_root()) { |
9f95a23c | 1754 | assert(node->parent()->child(node->position()) == node); |
7c673cae FG |
1755 | position = node->position() - 1; |
1756 | node = node->parent(); | |
1757 | } | |
1758 | if (position < 0) { | |
1759 | *this = save; | |
1760 | } | |
1761 | } else { | |
9f95a23c | 1762 | assert(position >= 0); |
7c673cae FG |
1763 | node = node->child(position); |
1764 | while (!node->leaf()) { | |
1765 | node = node->child(node->count()); | |
1766 | } | |
1767 | position = node->count() - 1; | |
1768 | } | |
1769 | } | |
1770 | ||
1771 | //// | |
1772 | // btree methods | |
1773 | template <typename P> | |
9f95a23c TL |
1774 | template <typename Btree> |
1775 | void btree<P>::copy_or_move_values_in_order(Btree *x) { | |
1776 | static_assert(std::is_same_v<btree, Btree>|| | |
1777 | std::is_same_v<const btree, Btree>, | |
1778 | "Btree type must be same or const."); | |
1779 | assert(empty()); | |
1780 | ||
1781 | // We can avoid key comparisons because we know the order of the | |
1782 | // values is the same order we'll store them in. | |
1783 | auto iter = x->begin(); | |
1784 | if (iter == x->end()) return; | |
1785 | insert_multi(maybe_move_from_iterator(iter)); | |
1786 | ++iter; | |
1787 | for (; iter != x->end(); ++iter) { | |
1788 | // If the btree is not empty, we can just insert the new value at the end | |
1789 | // of the tree. | |
1790 | internal_emplace(end(), maybe_move_from_iterator(iter)); | |
1791 | } | |
7c673cae FG |
1792 | } |
1793 | ||
1794 | template <typename P> | |
9f95a23c TL |
1795 | constexpr bool btree<P>::static_assert_validation() { |
1796 | static_assert(std::is_nothrow_copy_constructible_v<key_compare>, | |
1797 | "Key comparison must be nothrow copy constructible"); | |
1798 | static_assert(std::is_nothrow_copy_constructible_v<allocator_type>, | |
1799 | "Allocator must be nothrow copy constructible"); | |
1800 | static_assert(std::is_trivially_copyable_v<iterator>, | |
1801 | "iterator not trivially copyable."); | |
1802 | ||
1803 | // Note: We assert that kTargetValues, which is computed from | |
1804 | // Params::kTargetNodeSize, must fit the base_fields::field_type. | |
1805 | static_assert( | |
1806 | kNodeValues < (1 << (8 * sizeof(typename node_type::field_type))), | |
1807 | "target node size too large"); | |
1808 | ||
1809 | // Verify that key_compare returns an absl::{weak,strong}_ordering or bool. | |
1810 | using compare_result_type = | |
1811 | std::invoke_result_t<key_compare, key_type, key_type>; | |
1812 | static_assert( | |
1813 | std::is_same_v<compare_result_type, bool> || | |
1814 | std::is_signed_v<compare_result_type>, | |
1815 | "key comparison function must return a signed value or " | |
1816 | "bool."); | |
1817 | ||
1818 | // Test the assumption made in setting kNodeValueSpace. | |
1819 | static_assert(node_type::MinimumOverhead() >= sizeof(void *) + 4, | |
1820 | "node space assumption incorrect"); | |
1821 | ||
1822 | return true; | |
7c673cae FG |
1823 | } |
1824 | ||
9f95a23c TL |
1825 | template <typename P> |
1826 | btree<P>::btree(const key_compare &comp, const allocator_type &alloc) | |
1827 | : root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {} | |
1828 | ||
1829 | template <typename P> | |
1830 | btree<P>::btree(const btree &x) : btree(x.key_comp(), x.allocator()) { | |
1831 | copy_or_move_values_in_order(&x); | |
1832 | } | |
1833 | ||
1834 | template <typename P> | |
1835 | template <typename... Args> | |
1836 | auto btree<P>::insert_unique(const key_type &key, Args &&... args) | |
1837 | -> std::pair<iterator, bool> { | |
7c673cae | 1838 | if (empty()) { |
9f95a23c | 1839 | mutable_root() = rightmost_ = new_leaf_root_node(1); |
7c673cae FG |
1840 | } |
1841 | ||
9f95a23c TL |
1842 | auto res = internal_locate(key); |
1843 | iterator &iter = res.value; | |
1844 | ||
1845 | if constexpr (res.has_match) { | |
1846 | if (res.IsEq()) { | |
1847 | // The key already exists in the tree, do nothing. | |
1848 | return {iter, false}; | |
1849 | } | |
1850 | } else { | |
7c673cae FG |
1851 | iterator last = internal_last(iter); |
1852 | if (last.node && !compare_keys(key, last.key())) { | |
1853 | // The key already exists in the tree, do nothing. | |
9f95a23c | 1854 | return {last, false}; |
7c673cae FG |
1855 | } |
1856 | } | |
9f95a23c | 1857 | return {internal_emplace(iter, std::forward<Args>(args)...), true}; |
7c673cae FG |
1858 | } |
1859 | ||
1860 | template <typename P> | |
9f95a23c TL |
1861 | template <typename... Args> |
1862 | inline auto btree<P>::insert_hint_unique(iterator position, const key_type &key, | |
1863 | Args &&... args) | |
1864 | -> std::pair<iterator, bool> { | |
7c673cae | 1865 | if (!empty()) { |
7c673cae FG |
1866 | if (position == end() || compare_keys(key, position.key())) { |
1867 | iterator prev = position; | |
1868 | if (position == begin() || compare_keys((--prev).key(), key)) { | |
1869 | // prev.key() < key < position.key() | |
9f95a23c | 1870 | return {internal_emplace(position, std::forward<Args>(args)...), true}; |
7c673cae FG |
1871 | } |
1872 | } else if (compare_keys(position.key(), key)) { | |
9f95a23c TL |
1873 | ++position; |
1874 | if (position == end() || compare_keys(key, position.key())) { | |
1875 | // {original `position`}.key() < key < {current `position`}.key() | |
1876 | return {internal_emplace(position, std::forward<Args>(args)...), true}; | |
7c673cae FG |
1877 | } |
1878 | } else { | |
1879 | // position.key() == key | |
9f95a23c | 1880 | return {position, false}; |
7c673cae FG |
1881 | } |
1882 | } | |
9f95a23c | 1883 | return insert_unique(key, std::forward<Args>(args)...); |
7c673cae FG |
1884 | } |
1885 | ||
9f95a23c TL |
1886 | template <typename P> |
1887 | template <typename InputIterator> | |
1888 | void btree<P>::insert_iterator_unique(InputIterator b, InputIterator e) { | |
7c673cae | 1889 | for (; b != e; ++b) { |
9f95a23c | 1890 | insert_hint_unique(end(), params_type::key(*b), *b); |
7c673cae FG |
1891 | } |
1892 | } | |
1893 | ||
9f95a23c TL |
1894 | template <typename P> |
1895 | template <typename ValueType> | |
1896 | auto btree<P>::insert_multi(const key_type &key, ValueType&& v) -> iterator { | |
7c673cae | 1897 | if (empty()) { |
9f95a23c | 1898 | mutable_root() = rightmost_ = new_leaf_root_node(1); |
7c673cae FG |
1899 | } |
1900 | ||
9f95a23c TL |
1901 | iterator iter = internal_upper_bound(key); |
1902 | if (iter.node == nullptr) { | |
7c673cae FG |
1903 | iter = end(); |
1904 | } | |
9f95a23c | 1905 | return internal_emplace(iter, std::forward<ValueType>(v)); |
7c673cae FG |
1906 | } |
1907 | ||
1908 | template <typename P> | |
9f95a23c TL |
1909 | template <typename ValueType> |
1910 | auto btree<P>::insert_hint_multi(iterator position, ValueType &&v) -> iterator { | |
7c673cae FG |
1911 | if (!empty()) { |
1912 | const key_type &key = params_type::key(v); | |
1913 | if (position == end() || !compare_keys(position.key(), key)) { | |
1914 | iterator prev = position; | |
1915 | if (position == begin() || !compare_keys(key, (--prev).key())) { | |
1916 | // prev.key() <= key <= position.key() | |
9f95a23c | 1917 | return internal_emplace(position, std::forward<ValueType>(v)); |
7c673cae FG |
1918 | } |
1919 | } else { | |
1920 | iterator next = position; | |
1921 | ++next; | |
1922 | if (next == end() || !compare_keys(next.key(), key)) { | |
1923 | // position.key() < key <= next.key() | |
9f95a23c | 1924 | return internal_emplace(next, std::forward<ValueType>(v)); |
7c673cae FG |
1925 | } |
1926 | } | |
1927 | } | |
9f95a23c | 1928 | return insert_multi(std::forward<ValueType>(v)); |
7c673cae FG |
1929 | } |
1930 | ||
9f95a23c TL |
1931 | template <typename P> |
1932 | template <typename InputIterator> | |
1933 | void btree<P>::insert_iterator_multi(InputIterator b, InputIterator e) { | |
7c673cae | 1934 | for (; b != e; ++b) { |
9f95a23c | 1935 | insert_hint_multi(end(), *b); |
7c673cae FG |
1936 | } |
1937 | } | |
1938 | ||
1939 | template <typename P> | |
9f95a23c TL |
1940 | auto btree<P>::operator=(const btree &x) -> btree & { |
1941 | if (this != &x) { | |
1942 | clear(); | |
7c673cae | 1943 | |
9f95a23c TL |
1944 | *mutable_key_comp() = x.key_comp(); |
1945 | if constexpr (std::allocator_traits< | |
1946 | allocator_type>::propagate_on_container_copy_assignment::value) { | |
1947 | *mutable_allocator() = x.allocator(); | |
1948 | } | |
7c673cae | 1949 | |
9f95a23c TL |
1950 | copy_or_move_values_in_order(&x); |
1951 | } | |
1952 | return *this; | |
1953 | } | |
1954 | ||
1955 | template <typename P> | |
1956 | auto btree<P>::operator=(btree &&x) noexcept -> btree & { | |
1957 | if (this != &x) { | |
1958 | clear(); | |
1959 | ||
1960 | using std::swap; | |
1961 | if constexpr (std::allocator_traits< | |
1962 | allocator_type>::propagate_on_container_copy_assignment::value) { | |
1963 | // Note: `root_` also contains the allocator and the key comparator. | |
1964 | swap(root_, x.root_); | |
1965 | swap(rightmost_, x.rightmost_); | |
1966 | swap(size_, x.size_); | |
7c673cae | 1967 | } else { |
9f95a23c TL |
1968 | if (allocator() == x.allocator()) { |
1969 | swap(mutable_root(), x.mutable_root()); | |
1970 | swap(*mutable_key_comp(), *x.mutable_key_comp()); | |
1971 | swap(rightmost_, x.rightmost_); | |
1972 | swap(size_, x.size_); | |
1973 | } else { | |
1974 | // We aren't allowed to propagate the allocator and the allocator is | |
1975 | // different so we can't take over its memory. We must move each element | |
1976 | // individually. We need both `x` and `this` to have `x`s key comparator | |
1977 | // while moving the values so we can't swap the key comparators. | |
1978 | *mutable_key_comp() = x.key_comp(); | |
1979 | copy_or_move_values_in_order(&x); | |
1980 | } | |
7c673cae FG |
1981 | } |
1982 | } | |
9f95a23c | 1983 | return *this; |
7c673cae FG |
1984 | } |
1985 | ||
1986 | template <typename P> | |
9f95a23c | 1987 | auto btree<P>::erase(iterator iter) -> iterator { |
7c673cae FG |
1988 | bool internal_delete = false; |
1989 | if (!iter.node->leaf()) { | |
9f95a23c TL |
1990 | // Deletion of a value on an internal node. First, move the largest value |
1991 | // from our left child here, then delete that position (in remove_value() | |
1992 | // below). We can get to the largest value from our left child by | |
1993 | // decrementing iter. | |
1994 | iterator internal_iter(iter); | |
1995 | --iter; | |
1996 | assert(iter.node->leaf()); | |
1997 | params_type::move(mutable_allocator(), iter.node->slot(iter.position), | |
1998 | internal_iter.node->slot(internal_iter.position)); | |
7c673cae | 1999 | internal_delete = true; |
7c673cae FG |
2000 | } |
2001 | ||
2002 | // Delete the key from the leaf. | |
9f95a23c TL |
2003 | iter.node->remove_value(iter.position, mutable_allocator()); |
2004 | --size_; | |
7c673cae FG |
2005 | |
2006 | // We want to return the next value after the one we just erased. If we | |
2007 | // erased from an internal node (internal_delete == true), then the next | |
2008 | // value is ++(++iter). If we erased from a leaf node (internal_delete == | |
2009 | // false) then the next value is ++iter. Note that ++iter may point to an | |
2010 | // internal node and the value in the internal node may move to a leaf node | |
2011 | // (iter.node) when rebalancing is performed at the leaf level. | |
2012 | ||
9f95a23c TL |
2013 | iterator res = rebalance_after_delete(iter); |
2014 | ||
2015 | // If we erased from an internal node, advance the iterator. | |
2016 | if (internal_delete) { | |
2017 | ++res; | |
2018 | } | |
2019 | return res; | |
2020 | } | |
2021 | ||
2022 | template <typename P> | |
2023 | auto btree<P>::rebalance_after_delete(iterator iter) -> iterator { | |
7c673cae FG |
2024 | // Merge/rebalance as we walk back up the tree. |
2025 | iterator res(iter); | |
9f95a23c | 2026 | bool first_iteration = true; |
7c673cae FG |
2027 | for (;;) { |
2028 | if (iter.node == root()) { | |
2029 | try_shrink(); | |
2030 | if (empty()) { | |
2031 | return end(); | |
2032 | } | |
2033 | break; | |
2034 | } | |
2035 | if (iter.node->count() >= kMinNodeValues) { | |
2036 | break; | |
2037 | } | |
2038 | bool merged = try_merge_or_rebalance(&iter); | |
9f95a23c TL |
2039 | // On the first iteration, we should update `res` with `iter` because `res` |
2040 | // may have been invalidated. | |
2041 | if (first_iteration) { | |
7c673cae | 2042 | res = iter; |
9f95a23c | 2043 | first_iteration = false; |
7c673cae FG |
2044 | } |
2045 | if (!merged) { | |
2046 | break; | |
2047 | } | |
9f95a23c | 2048 | iter.position = iter.node->position(); |
7c673cae FG |
2049 | iter.node = iter.node->parent(); |
2050 | } | |
2051 | ||
2052 | // Adjust our return value. If we're pointing at the end of a node, advance | |
2053 | // the iterator. | |
2054 | if (res.position == res.node->count()) { | |
2055 | res.position = res.node->count() - 1; | |
2056 | ++res; | |
2057 | } | |
9f95a23c | 2058 | |
7c673cae FG |
2059 | return res; |
2060 | } | |
2061 | ||
2062 | template <typename P> | |
9f95a23c TL |
2063 | auto btree<P>::erase(iterator begin, iterator end) |
2064 | -> std::pair<size_type, iterator> { | |
2065 | difference_type count = std::distance(begin, end); | |
2066 | assert(count >= 0); | |
2067 | ||
2068 | if (count == 0) { | |
2069 | return {0, begin}; | |
7c673cae | 2070 | } |
9f95a23c TL |
2071 | |
2072 | if (count == size_) { | |
2073 | clear(); | |
2074 | return {count, this->end()}; | |
2075 | } | |
2076 | ||
2077 | if (begin.node == end.node) { | |
2078 | erase_same_node(begin, end); | |
2079 | size_ -= count; | |
2080 | return {count, rebalance_after_delete(begin)}; | |
2081 | } | |
2082 | ||
2083 | const size_type target_size = size_ - count; | |
2084 | while (size_ > target_size) { | |
2085 | if (begin.node->leaf()) { | |
2086 | const size_type remaining_to_erase = size_ - target_size; | |
2087 | const size_type remaining_in_node = begin.node->count() - begin.position; | |
2088 | begin = erase_from_leaf_node( | |
2089 | begin, std::min(remaining_to_erase, remaining_in_node)); | |
2090 | } else { | |
2091 | begin = erase(begin); | |
2092 | } | |
2093 | } | |
2094 | return {count, begin}; | |
7c673cae FG |
2095 | } |
2096 | ||
2097 | template <typename P> | |
9f95a23c TL |
2098 | void btree<P>::erase_same_node(iterator begin, iterator end) { |
2099 | assert(begin.node == end.node); | |
2100 | assert(end.position > begin.position); | |
2101 | ||
2102 | node_type *node = begin.node; | |
2103 | size_type to_erase = end.position - begin.position; | |
2104 | if (!node->leaf()) { | |
2105 | // Delete all children between begin and end. | |
2106 | for (size_type i = 0; i < to_erase; ++i) { | |
2107 | internal_clear(node->child(begin.position + i + 1)); | |
2108 | } | |
2109 | // Rotate children after end into new positions. | |
2110 | for (size_type i = begin.position + to_erase + 1; i <= node->count(); ++i) { | |
2111 | node->set_child(i - to_erase, node->child(i)); | |
2112 | node->clear_child(i); | |
2113 | } | |
2114 | } | |
2115 | node->remove_values_ignore_children(begin.position, to_erase, | |
2116 | mutable_allocator()); | |
2117 | ||
2118 | // Do not need to update rightmost_, because | |
2119 | // * either end == this->end(), and therefore node == rightmost_, and still | |
2120 | // exists | |
2121 | // * or end != this->end(), and therefore rightmost_ hasn't been erased, since | |
2122 | // it wasn't covered in [begin, end) | |
2123 | } | |
2124 | ||
2125 | template <typename P> | |
2126 | auto btree<P>::erase_from_leaf_node(iterator begin, size_type to_erase) | |
2127 | -> iterator { | |
2128 | node_type *node = begin.node; | |
2129 | assert(node->leaf()); | |
2130 | assert(node->count() > begin.position); | |
2131 | assert(begin.position + to_erase <= node->count()); | |
2132 | ||
2133 | node->remove_values_ignore_children(begin.position, to_erase, | |
2134 | mutable_allocator()); | |
2135 | ||
2136 | size_ -= to_erase; | |
2137 | ||
2138 | return rebalance_after_delete(begin); | |
2139 | } | |
2140 | ||
2141 | template <typename P> | |
2142 | template <typename K> | |
2143 | auto btree<P>::erase_unique(const K &key) -> size_type { | |
2144 | const iterator iter = internal_find(key); | |
2145 | if (iter.node == nullptr) { | |
7c673cae FG |
2146 | // The key doesn't exist in the tree, return nothing done. |
2147 | return 0; | |
2148 | } | |
2149 | erase(iter); | |
2150 | return 1; | |
2151 | } | |
2152 | ||
2153 | template <typename P> | |
9f95a23c TL |
2154 | template <typename K> |
2155 | auto btree<P>::erase_multi(const K &key) -> size_type { | |
2156 | const iterator begin = internal_lower_bound(key); | |
2157 | if (begin.node == nullptr) { | |
7c673cae FG |
2158 | // The key doesn't exist in the tree, return nothing done. |
2159 | return 0; | |
2160 | } | |
2161 | // Delete all of the keys between begin and upper_bound(key). | |
9f95a23c TL |
2162 | const iterator end = internal_end(internal_upper_bound(key)); |
2163 | return erase(begin, end).first; | |
7c673cae FG |
2164 | } |
2165 | ||
2166 | template <typename P> | |
2167 | void btree<P>::clear() { | |
9f95a23c | 2168 | if (!empty()) { |
7c673cae FG |
2169 | internal_clear(root()); |
2170 | } | |
9f95a23c TL |
2171 | mutable_root() = EmptyNode(); |
2172 | rightmost_ = EmptyNode(); | |
2173 | size_ = 0; | |
7c673cae FG |
2174 | } |
2175 | ||
2176 | template <typename P> | |
9f95a23c TL |
2177 | void btree<P>::swap(btree &x) { |
2178 | using std::swap; | |
2179 | if (std::allocator_traits< | |
2180 | allocator_type>::propagate_on_container_swap::value) { | |
2181 | // Note: `root_` also contains the allocator and the key comparator. | |
2182 | swap(root_, x.root_); | |
2183 | } else { | |
2184 | // It's undefined behavior if the allocators are unequal here. | |
2185 | assert(allocator() == x.allocator()); | |
2186 | swap(mutable_root(), x.mutable_root()); | |
2187 | swap(*mutable_key_comp(), *x.mutable_key_comp()); | |
2188 | } | |
2189 | swap(rightmost_, x.rightmost_); | |
2190 | swap(size_, x.size_); | |
7c673cae FG |
2191 | } |
2192 | ||
2193 | template <typename P> | |
2194 | void btree<P>::verify() const { | |
9f95a23c TL |
2195 | assert(root() != nullptr); |
2196 | assert(leftmost() != nullptr); | |
2197 | assert(rightmost_ != nullptr); | |
2198 | assert(empty() || size() == internal_verify(root(), nullptr, nullptr)); | |
2199 | assert(leftmost() == (++const_iterator(root(), -1)).node); | |
2200 | assert(rightmost_ == (--const_iterator(root(), root()->count())).node); | |
2201 | assert(leftmost()->leaf()); | |
2202 | assert(rightmost_->leaf()); | |
7c673cae FG |
2203 | } |
2204 | ||
2205 | template <typename P> | |
2206 | void btree<P>::rebalance_or_split(iterator *iter) { | |
2207 | node_type *&node = iter->node; | |
2208 | int &insert_position = iter->position; | |
9f95a23c TL |
2209 | assert(node->count() == node->max_count()); |
2210 | assert(kNodeValues == node->max_count()); | |
7c673cae FG |
2211 | |
2212 | // First try to make room on the node by rebalancing. | |
2213 | node_type *parent = node->parent(); | |
2214 | if (node != root()) { | |
2215 | if (node->position() > 0) { | |
2216 | // Try rebalancing with our left sibling. | |
2217 | node_type *left = parent->child(node->position() - 1); | |
9f95a23c TL |
2218 | assert(left->max_count() == kNodeValues); |
2219 | if (left->count() < kNodeValues) { | |
7c673cae FG |
2220 | // We bias rebalancing based on the position being inserted. If we're |
2221 | // inserting at the end of the right node then we bias rebalancing to | |
2222 | // fill up the left node. | |
9f95a23c TL |
2223 | int to_move = (kNodeValues - left->count()) / |
2224 | (1 + (insert_position < kNodeValues)); | |
7c673cae FG |
2225 | to_move = std::max(1, to_move); |
2226 | ||
2227 | if (((insert_position - to_move) >= 0) || | |
9f95a23c TL |
2228 | ((left->count() + to_move) < kNodeValues)) { |
2229 | left->rebalance_right_to_left(to_move, node, mutable_allocator()); | |
7c673cae | 2230 | |
9f95a23c | 2231 | assert(node->max_count() - node->count() == to_move); |
7c673cae FG |
2232 | insert_position = insert_position - to_move; |
2233 | if (insert_position < 0) { | |
2234 | insert_position = insert_position + left->count() + 1; | |
2235 | node = left; | |
2236 | } | |
2237 | ||
9f95a23c | 2238 | assert(node->count() < node->max_count()); |
7c673cae FG |
2239 | return; |
2240 | } | |
2241 | } | |
2242 | } | |
2243 | ||
2244 | if (node->position() < parent->count()) { | |
2245 | // Try rebalancing with our right sibling. | |
2246 | node_type *right = parent->child(node->position() + 1); | |
9f95a23c TL |
2247 | assert(right->max_count() == kNodeValues); |
2248 | if (right->count() < kNodeValues) { | |
7c673cae FG |
2249 | // We bias rebalancing based on the position being inserted. If we're |
2250 | // inserting at the beginning of the left node then we bias rebalancing | |
2251 | // to fill up the right node. | |
9f95a23c TL |
2252 | int to_move = |
2253 | (kNodeValues - right->count()) / (1 + (insert_position > 0)); | |
2254 | to_move = (std::max)(1, to_move); | |
7c673cae FG |
2255 | |
2256 | if ((insert_position <= (node->count() - to_move)) || | |
9f95a23c TL |
2257 | ((right->count() + to_move) < kNodeValues)) { |
2258 | node->rebalance_left_to_right(to_move, right, mutable_allocator()); | |
7c673cae FG |
2259 | |
2260 | if (insert_position > node->count()) { | |
2261 | insert_position = insert_position - node->count() - 1; | |
2262 | node = right; | |
2263 | } | |
2264 | ||
9f95a23c | 2265 | assert(node->count() < node->max_count()); |
7c673cae FG |
2266 | return; |
2267 | } | |
2268 | } | |
2269 | } | |
2270 | ||
2271 | // Rebalancing failed, make sure there is room on the parent node for a new | |
2272 | // value. | |
9f95a23c TL |
2273 | assert(parent->max_count() == kNodeValues); |
2274 | if (parent->count() == kNodeValues) { | |
7c673cae FG |
2275 | iterator parent_iter(node->parent(), node->position()); |
2276 | rebalance_or_split(&parent_iter); | |
2277 | } | |
2278 | } else { | |
2279 | // Rebalancing not possible because this is the root node. | |
9f95a23c TL |
2280 | // Create a new root node and set the current root node as the child of the |
2281 | // new root. | |
2282 | parent = new_internal_node(parent); | |
2283 | parent->init_child(0, root()); | |
2284 | mutable_root() = parent; | |
2285 | // If the former root was a leaf node, then it's now the rightmost node. | |
2286 | assert(!parent->child(0)->leaf() || parent->child(0) == rightmost_); | |
7c673cae FG |
2287 | } |
2288 | ||
2289 | // Split the node. | |
2290 | node_type *split_node; | |
2291 | if (node->leaf()) { | |
2292 | split_node = new_leaf_node(parent); | |
9f95a23c TL |
2293 | node->split(insert_position, split_node, mutable_allocator()); |
2294 | if (rightmost_ == node) rightmost_ = split_node; | |
7c673cae FG |
2295 | } else { |
2296 | split_node = new_internal_node(parent); | |
9f95a23c | 2297 | node->split(insert_position, split_node, mutable_allocator()); |
7c673cae FG |
2298 | } |
2299 | ||
2300 | if (insert_position > node->count()) { | |
2301 | insert_position = insert_position - node->count() - 1; | |
2302 | node = split_node; | |
2303 | } | |
2304 | } | |
2305 | ||
2306 | template <typename P> | |
2307 | void btree<P>::merge_nodes(node_type *left, node_type *right) { | |
9f95a23c | 2308 | left->merge(right, mutable_allocator()); |
7c673cae | 2309 | if (right->leaf()) { |
9f95a23c | 2310 | if (rightmost_ == right) rightmost_ = left; |
7c673cae FG |
2311 | delete_leaf_node(right); |
2312 | } else { | |
2313 | delete_internal_node(right); | |
2314 | } | |
2315 | } | |
2316 | ||
2317 | template <typename P> | |
2318 | bool btree<P>::try_merge_or_rebalance(iterator *iter) { | |
2319 | node_type *parent = iter->node->parent(); | |
2320 | if (iter->node->position() > 0) { | |
2321 | // Try merging with our left sibling. | |
2322 | node_type *left = parent->child(iter->node->position() - 1); | |
9f95a23c TL |
2323 | assert(left->max_count() == kNodeValues); |
2324 | if ((1 + left->count() + iter->node->count()) <= kNodeValues) { | |
7c673cae FG |
2325 | iter->position += 1 + left->count(); |
2326 | merge_nodes(left, iter->node); | |
2327 | iter->node = left; | |
2328 | return true; | |
2329 | } | |
2330 | } | |
2331 | if (iter->node->position() < parent->count()) { | |
2332 | // Try merging with our right sibling. | |
2333 | node_type *right = parent->child(iter->node->position() + 1); | |
9f95a23c TL |
2334 | assert(right->max_count() == kNodeValues); |
2335 | if ((1 + iter->node->count() + right->count()) <= kNodeValues) { | |
7c673cae FG |
2336 | merge_nodes(iter->node, right); |
2337 | return true; | |
2338 | } | |
2339 | // Try rebalancing with our right sibling. We don't perform rebalancing if | |
2340 | // we deleted the first element from iter->node and the node is not | |
2341 | // empty. This is a small optimization for the common pattern of deleting | |
2342 | // from the front of the tree. | |
2343 | if ((right->count() > kMinNodeValues) && | |
2344 | ((iter->node->count() == 0) || | |
2345 | (iter->position > 0))) { | |
2346 | int to_move = (right->count() - iter->node->count()) / 2; | |
2347 | to_move = std::min(to_move, right->count() - 1); | |
9f95a23c | 2348 | iter->node->rebalance_right_to_left(to_move, right, mutable_allocator()); |
7c673cae FG |
2349 | return false; |
2350 | } | |
2351 | } | |
2352 | if (iter->node->position() > 0) { | |
2353 | // Try rebalancing with our left sibling. We don't perform rebalancing if | |
2354 | // we deleted the last element from iter->node and the node is not | |
2355 | // empty. This is a small optimization for the common pattern of deleting | |
2356 | // from the back of the tree. | |
2357 | node_type *left = parent->child(iter->node->position() - 1); | |
2358 | if ((left->count() > kMinNodeValues) && | |
2359 | ((iter->node->count() == 0) || | |
2360 | (iter->position < iter->node->count()))) { | |
2361 | int to_move = (left->count() - iter->node->count()) / 2; | |
2362 | to_move = std::min(to_move, left->count() - 1); | |
9f95a23c | 2363 | left->rebalance_left_to_right(to_move, iter->node, mutable_allocator()); |
7c673cae FG |
2364 | iter->position += to_move; |
2365 | return false; | |
2366 | } | |
2367 | } | |
2368 | return false; | |
2369 | } | |
2370 | ||
2371 | template <typename P> | |
2372 | void btree<P>::try_shrink() { | |
2373 | if (root()->count() > 0) { | |
2374 | return; | |
2375 | } | |
2376 | // Deleted the last item on the root node, shrink the height of the tree. | |
2377 | if (root()->leaf()) { | |
9f95a23c | 2378 | assert(size() == 0); |
7c673cae | 2379 | delete_leaf_node(root()); |
9f95a23c TL |
2380 | mutable_root() = EmptyNode(); |
2381 | rightmost_ = EmptyNode(); | |
7c673cae FG |
2382 | } else { |
2383 | node_type *child = root()->child(0); | |
9f95a23c TL |
2384 | child->make_root(); |
2385 | delete_internal_node(root()); | |
2386 | mutable_root() = child; | |
7c673cae FG |
2387 | } |
2388 | } | |
2389 | ||
9f95a23c TL |
2390 | template <typename P> |
2391 | template <typename IterType> | |
7c673cae | 2392 | inline IterType btree<P>::internal_last(IterType iter) { |
9f95a23c TL |
2393 | assert(iter.node != nullptr); |
2394 | while (iter.position == iter.node->count()) { | |
7c673cae FG |
2395 | iter.position = iter.node->position(); |
2396 | iter.node = iter.node->parent(); | |
2397 | if (iter.node->leaf()) { | |
9f95a23c TL |
2398 | iter.node = nullptr; |
2399 | break; | |
7c673cae FG |
2400 | } |
2401 | } | |
2402 | return iter; | |
2403 | } | |
2404 | ||
2405 | template <typename P> | |
9f95a23c TL |
2406 | template <typename... Args> |
2407 | inline auto btree<P>::internal_emplace(iterator iter, Args &&... args) | |
2408 | -> iterator { | |
7c673cae FG |
2409 | if (!iter.node->leaf()) { |
2410 | // We can't insert on an internal node. Instead, we'll insert after the | |
2411 | // previous value which is guaranteed to be on a leaf node. | |
2412 | --iter; | |
2413 | ++iter.position; | |
2414 | } | |
9f95a23c TL |
2415 | const int max_count = iter.node->max_count(); |
2416 | if (iter.node->count() == max_count) { | |
7c673cae | 2417 | // Make room in the leaf for the new item. |
9f95a23c TL |
2418 | if (max_count < kNodeValues) { |
2419 | // Insertion into the root where the root is smaller than the full node | |
7c673cae | 2420 | // size. Simply grow the size of the root node. |
9f95a23c TL |
2421 | assert(iter.node == root()); |
2422 | iter.node = | |
2423 | new_leaf_root_node(std::min(kNodeValues, 2 * max_count)); | |
2424 | iter.node->swap(root(), mutable_allocator()); | |
7c673cae | 2425 | delete_leaf_node(root()); |
9f95a23c TL |
2426 | mutable_root() = iter.node; |
2427 | rightmost_ = iter.node; | |
7c673cae FG |
2428 | } else { |
2429 | rebalance_or_split(&iter); | |
7c673cae | 2430 | } |
7c673cae | 2431 | } |
9f95a23c TL |
2432 | iter.node->emplace_value(iter.position, mutable_allocator(), |
2433 | std::forward<Args>(args)...); | |
2434 | ++size_; | |
7c673cae FG |
2435 | return iter; |
2436 | } | |
2437 | ||
9f95a23c TL |
2438 | template <typename P> |
2439 | template <typename K> | |
2440 | inline auto btree<P>::internal_locate(const K &key) const | |
2441 | -> SearchResult<iterator, is_key_compare_to::value> { | |
2442 | return internal_locate_impl(key, is_key_compare_to()); | |
7c673cae FG |
2443 | } |
2444 | ||
9f95a23c TL |
2445 | template <typename P> |
2446 | template <typename K> | |
2447 | inline auto btree<P>::internal_locate_impl( | |
2448 | const K &key, std::false_type /* IsCompareTo */) const | |
2449 | -> SearchResult<iterator, false> { | |
2450 | iterator iter(const_cast<node_type *>(root()), 0); | |
7c673cae | 2451 | for (;;) { |
9f95a23c TL |
2452 | iter.position = iter.node->lower_bound(key, key_comp()).value; |
2453 | // NOTE: we don't need to walk all the way down the tree if the keys are | |
2454 | // equal, but determining equality would require doing an extra comparison | |
2455 | // on each node on the way down, and we will need to go all the way to the | |
2456 | // leaf node in the expected case. | |
7c673cae FG |
2457 | if (iter.node->leaf()) { |
2458 | break; | |
2459 | } | |
2460 | iter.node = iter.node->child(iter.position); | |
2461 | } | |
9f95a23c | 2462 | return {iter}; |
7c673cae FG |
2463 | } |
2464 | ||
9f95a23c TL |
2465 | template <typename P> |
2466 | template <typename K> | |
2467 | inline auto btree<P>::internal_locate_impl( | |
2468 | const K &key, std::true_type /* IsCompareTo */) const | |
2469 | -> SearchResult<iterator, true> { | |
2470 | iterator iter(const_cast<node_type *>(root()), 0); | |
7c673cae | 2471 | for (;;) { |
9f95a23c TL |
2472 | SearchResult<int, true> res = iter.node->lower_bound(key, key_comp()); |
2473 | iter.position = res.value; | |
2474 | if (res.match == MatchKind::kEq) { | |
2475 | return {iter, MatchKind::kEq}; | |
7c673cae FG |
2476 | } |
2477 | if (iter.node->leaf()) { | |
2478 | break; | |
2479 | } | |
2480 | iter.node = iter.node->child(iter.position); | |
2481 | } | |
9f95a23c | 2482 | return {iter, MatchKind::kNe}; |
7c673cae FG |
2483 | } |
2484 | ||
9f95a23c TL |
2485 | template <typename P> |
2486 | template <typename K> | |
2487 | auto btree<P>::internal_lower_bound(const K &key) const -> iterator { | |
2488 | iterator iter(const_cast<node_type *>(root()), 0); | |
2489 | for (;;) { | |
2490 | iter.position = iter.node->lower_bound(key, key_comp()).value; | |
2491 | if (iter.node->leaf()) { | |
2492 | break; | |
7c673cae | 2493 | } |
9f95a23c | 2494 | iter.node = iter.node->child(iter.position); |
7c673cae | 2495 | } |
9f95a23c | 2496 | return internal_last(iter); |
7c673cae FG |
2497 | } |
2498 | ||
9f95a23c TL |
2499 | template <typename P> |
2500 | template <typename K> | |
2501 | auto btree<P>::internal_upper_bound(const K &key) const -> iterator { | |
2502 | iterator iter(const_cast<node_type *>(root()), 0); | |
2503 | for (;;) { | |
2504 | iter.position = iter.node->upper_bound(key, key_comp()); | |
2505 | if (iter.node->leaf()) { | |
2506 | break; | |
7c673cae | 2507 | } |
9f95a23c | 2508 | iter.node = iter.node->child(iter.position); |
7c673cae | 2509 | } |
9f95a23c | 2510 | return internal_last(iter); |
7c673cae FG |
2511 | } |
2512 | ||
9f95a23c TL |
2513 | template <typename P> |
2514 | template <typename K> | |
2515 | auto btree<P>::internal_find(const K &key) const -> iterator { | |
2516 | auto res = internal_locate(key); | |
2517 | if constexpr (res.has_match) { | |
2518 | if (res.IsEq()) { | |
2519 | return res.value; | |
7c673cae | 2520 | } |
9f95a23c TL |
2521 | } else { |
2522 | const iterator iter = internal_last(res.value); | |
2523 | if (iter.node != nullptr && !compare_keys(key, iter.key())) { | |
2524 | return iter; | |
7c673cae FG |
2525 | } |
2526 | } | |
9f95a23c | 2527 | return {nullptr, 0}; |
7c673cae FG |
2528 | } |
2529 | ||
2530 | template <typename P> | |
2531 | void btree<P>::internal_clear(node_type *node) { | |
2532 | if (!node->leaf()) { | |
2533 | for (int i = 0; i <= node->count(); ++i) { | |
2534 | internal_clear(node->child(i)); | |
2535 | } | |
9f95a23c | 2536 | delete_internal_node(node); |
7c673cae FG |
2537 | } else { |
2538 | delete_leaf_node(node); | |
2539 | } | |
2540 | } | |
2541 | ||
7c673cae FG |
2542 | template <typename P> |
2543 | int btree<P>::internal_verify( | |
2544 | const node_type *node, const key_type *lo, const key_type *hi) const { | |
9f95a23c TL |
2545 | assert(node->count() > 0); |
2546 | assert(node->count() <= node->max_count()); | |
7c673cae | 2547 | if (lo) { |
9f95a23c | 2548 | assert(!compare_keys(node->key(0), *lo)); |
7c673cae FG |
2549 | } |
2550 | if (hi) { | |
9f95a23c | 2551 | assert(!compare_keys(*hi, node->key(node->count() - 1))); |
7c673cae FG |
2552 | } |
2553 | for (int i = 1; i < node->count(); ++i) { | |
9f95a23c | 2554 | assert(!compare_keys(node->key(i), node->key(i - 1))); |
7c673cae FG |
2555 | } |
2556 | int count = node->count(); | |
2557 | if (!node->leaf()) { | |
2558 | for (int i = 0; i <= node->count(); ++i) { | |
9f95a23c TL |
2559 | assert(node->child(i) != nullptr); |
2560 | assert(node->child(i)->parent() == node); | |
2561 | assert(node->child(i)->position() == i); | |
7c673cae FG |
2562 | count += internal_verify( |
2563 | node->child(i), | |
2564 | (i == 0) ? lo : &node->key(i - 1), | |
2565 | (i == node->count()) ? hi : &node->key(i)); | |
2566 | } | |
2567 | } | |
2568 | return count; | |
2569 | } | |
2570 | ||
9f95a23c | 2571 | } // namespace btree::internal |