1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#include <string.h>
40#include <db.h>
41
42#include <portability/memory.h>
43
44namespace toku {
45
46template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
47void omt<omtdata_t, omtdataout_t, supports_marks>::create(void) {
48 this->create_internal(2);
49 if (supports_marks) {
50 this->convert_to_tree();
51 }
52}
53
54template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
55void omt<omtdata_t, omtdataout_t, supports_marks>::create_no_array(void) {
56 if (!supports_marks) {
57 this->create_internal_no_array(0);
58 } else {
59 this->is_array = false;
60 this->capacity = 0;
61 this->d.t.nodes = nullptr;
62 this->d.t.root.set_to_null();
63 this->d.t.free_idx = 0;
64 }
65}
66
67template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
68void omt<omtdata_t, omtdataout_t, supports_marks>::create_from_sorted_array(const omtdata_t *const values, const uint32_t numvalues) {
69 this->create_internal(numvalues);
70 memcpy(this->d.a.values, values, numvalues * (sizeof values[0]));
71 this->d.a.num_values = numvalues;
72 if (supports_marks) {
73 this->convert_to_tree();
74 }
75}
76
77template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
78void omt<omtdata_t, omtdataout_t, supports_marks>::create_steal_sorted_array(omtdata_t **const values, const uint32_t numvalues, const uint32_t new_capacity) {
79 paranoid_invariant_notnull(values);
80 this->create_internal_no_array(new_capacity);
81 this->d.a.num_values = numvalues;
82 this->d.a.values = *values;
83 *values = nullptr;
84 if (supports_marks) {
85 this->convert_to_tree();
86 }
87}
88
89template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
90int omt<omtdata_t, omtdataout_t, supports_marks>::split_at(omt *const newomt, const uint32_t idx) {
91 barf_if_marked(*this);
92 paranoid_invariant_notnull(newomt);
93 if (idx > this->size()) { return EINVAL; }
94 this->convert_to_array();
95 const uint32_t newsize = this->size() - idx;
96 newomt->create_from_sorted_array(&this->d.a.values[this->d.a.start_idx + idx], newsize);
97 this->d.a.num_values = idx;
98 this->maybe_resize_array(idx);
99 if (supports_marks) {
100 this->convert_to_tree();
101 }
102 return 0;
103}
104
105template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
106void omt<omtdata_t, omtdataout_t, supports_marks>::merge(omt *const leftomt, omt *const rightomt) {
107 barf_if_marked(*this);
108 paranoid_invariant_notnull(leftomt);
109 paranoid_invariant_notnull(rightomt);
110 const uint32_t leftsize = leftomt->size();
111 const uint32_t rightsize = rightomt->size();
112 const uint32_t newsize = leftsize + rightsize;
113
114 if (leftomt->is_array) {
115 if (leftomt->capacity - (leftomt->d.a.start_idx + leftomt->d.a.num_values) >= rightsize) {
116 this->create_steal_sorted_array(&leftomt->d.a.values, leftomt->d.a.num_values, leftomt->capacity);
117 this->d.a.start_idx = leftomt->d.a.start_idx;
118 } else {
119 this->create_internal(newsize);
120 memcpy(&this->d.a.values[0],
121 &leftomt->d.a.values[leftomt->d.a.start_idx],
122 leftomt->d.a.num_values * (sizeof this->d.a.values[0]));
123 }
124 } else {
125 this->create_internal(newsize);
126 leftomt->fill_array_with_subtree_values(&this->d.a.values[0], leftomt->d.t.root);
127 }
128 leftomt->destroy();
129 this->d.a.num_values = leftsize;
130
131 if (rightomt->is_array) {
132 memcpy(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values],
133 &rightomt->d.a.values[rightomt->d.a.start_idx],
134 rightomt->d.a.num_values * (sizeof this->d.a.values[0]));
135 } else {
136 rightomt->fill_array_with_subtree_values(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values],
137 rightomt->d.t.root);
138 }
139 rightomt->destroy();
140 this->d.a.num_values += rightsize;
141 paranoid_invariant(this->size() == newsize);
142 if (supports_marks) {
143 this->convert_to_tree();
144 }
145}
146
147template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
148void omt<omtdata_t, omtdataout_t, supports_marks>::clone(const omt &src) {
149 barf_if_marked(*this);
150 this->create_internal(src.size());
151 if (src.is_array) {
152 memcpy(&this->d.a.values[0], &src.d.a.values[src.d.a.start_idx], src.d.a.num_values * (sizeof this->d.a.values[0]));
153 } else {
154 src.fill_array_with_subtree_values(&this->d.a.values[0], src.d.t.root);
155 }
156 this->d.a.num_values = src.size();
157 if (supports_marks) {
158 this->convert_to_tree();
159 }
160}
161
162template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
163void omt<omtdata_t, omtdataout_t, supports_marks>::clear(void) {
164 if (this->is_array) {
165 this->d.a.start_idx = 0;
166 this->d.a.num_values = 0;
167 } else {
168 this->d.t.root.set_to_null();
169 this->d.t.free_idx = 0;
170 }
171}
172
173template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
174void omt<omtdata_t, omtdataout_t, supports_marks>::destroy(void) {
175 this->clear();
176 this->capacity = 0;
177 if (this->is_array) {
178 if (this->d.a.values != nullptr) {
179 toku_free(this->d.a.values);
180 }
181 this->d.a.values = nullptr;
182 } else {
183 if (this->d.t.nodes != nullptr) {
184 toku_free(this->d.t.nodes);
185 }
186 this->d.t.nodes = nullptr;
187 }
188}
189
190template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
191uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::size(void) const {
192 if (this->is_array) {
193 return this->d.a.num_values;
194 } else {
195 return this->nweight(this->d.t.root);
196 }
197}
198
199
200template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
201template<typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)>
202int omt<omtdata_t, omtdataout_t, supports_marks>::insert(const omtdata_t &value, const omtcmp_t &v, uint32_t *const idx) {
203 int r;
204 uint32_t insert_idx;
205
206 r = this->find_zero<omtcmp_t, h>(v, nullptr, &insert_idx);
207 if (r==0) {
208 if (idx) *idx = insert_idx;
209 return DB_KEYEXIST;
210 }
211 if (r != DB_NOTFOUND) return r;
212
213 if ((r = this->insert_at(value, insert_idx))) return r;
214 if (idx) *idx = insert_idx;
215
216 return 0;
217}
218
219// The following 3 functions implement a static if for us.
220template<typename omtdata_t, typename omtdataout_t>
221static void barf_if_marked(const omt<omtdata_t, omtdataout_t, false> &UU(omt)) {
222}
223
224template<typename omtdata_t, typename omtdataout_t>
225static void barf_if_marked(const omt<omtdata_t, omtdataout_t, true> &omt) {
226 invariant(!omt.has_marks());
227}
228
229template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
230bool omt<omtdata_t, omtdataout_t, supports_marks>::has_marks(void) const {
231 static_assert(supports_marks, "Does not support marks");
232 if (this->d.t.root.is_null()) {
233 return false;
234 }
235 const omt_node &node = this->d.t.nodes[this->d.t.root.get_index()];
236 return node.get_marks_below() || node.get_marked();
237}
238
239template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
240int omt<omtdata_t, omtdataout_t, supports_marks>::insert_at(const omtdata_t &value, const uint32_t idx) {
241 barf_if_marked(*this);
242 if (idx > this->size()) { return EINVAL; }
243
244 this->maybe_resize_or_convert(this->size() + 1);
245 if (this->is_array && idx != this->d.a.num_values &&
246 (idx != 0 || this->d.a.start_idx == 0)) {
247 this->convert_to_tree();
248 }
249 if (this->is_array) {
250 if (idx == this->d.a.num_values) {
251 this->d.a.values[this->d.a.start_idx + this->d.a.num_values] = value;
252 }
253 else {
254 this->d.a.values[--this->d.a.start_idx] = value;
255 }
256 this->d.a.num_values++;
257 }
258 else {
259 subtree *rebalance_subtree = nullptr;
260 this->insert_internal(&this->d.t.root, value, idx, &rebalance_subtree);
261 if (rebalance_subtree != nullptr) {
262 this->rebalance(rebalance_subtree);
263 }
264 }
265 return 0;
266}
267
268template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
269int omt<omtdata_t, omtdataout_t, supports_marks>::set_at(const omtdata_t &value, const uint32_t idx) {
270 barf_if_marked(*this);
271 if (idx >= this->size()) { return EINVAL; }
272
273 if (this->is_array) {
274 this->set_at_internal_array(value, idx);
275 } else {
276 this->set_at_internal(this->d.t.root, value, idx);
277 }
278 return 0;
279}
280
281template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
282int omt<omtdata_t, omtdataout_t, supports_marks>::delete_at(const uint32_t idx) {
283 barf_if_marked(*this);
284 if (idx >= this->size()) { return EINVAL; }
285
286 this->maybe_resize_or_convert(this->size() - 1);
287 if (this->is_array && idx != 0 && idx != this->d.a.num_values - 1) {
288 this->convert_to_tree();
289 }
290 if (this->is_array) {
291 //Testing for 0 does not rule out it being the last entry.
292 //Test explicitly for num_values-1
293 if (idx != this->d.a.num_values - 1) {
294 this->d.a.start_idx++;
295 }
296 this->d.a.num_values--;
297 } else {
298 subtree *rebalance_subtree = nullptr;
299 this->delete_internal(&this->d.t.root, idx, nullptr, &rebalance_subtree);
300 if (rebalance_subtree != nullptr) {
301 this->rebalance(rebalance_subtree);
302 }
303 }
304 return 0;
305}
306
307template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
308template<typename iterate_extra_t,
309 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
310int omt<omtdata_t, omtdataout_t, supports_marks>::iterate(iterate_extra_t *const iterate_extra) const {
311 return this->iterate_on_range<iterate_extra_t, f>(0, this->size(), iterate_extra);
312}
313
314template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
315template<typename iterate_extra_t,
316 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
317int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_on_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) const {
318 if (right > this->size()) { return EINVAL; }
319 if (left == right) { return 0; }
320 if (this->is_array) {
321 return this->iterate_internal_array<iterate_extra_t, f>(left, right, iterate_extra);
322 }
323 return this->iterate_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra);
324}
325
326template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
327template<typename iterate_extra_t,
328 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
329int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) {
330 static_assert(supports_marks, "does not support marks");
331 if (right > this->size()) { return EINVAL; }
332 if (left == right) { return 0; }
333 paranoid_invariant(!this->is_array);
334 return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra);
335}
336
337//TODO: We can optimize this if we steal 3 bits. 1 bit: this node is marked. 1 bit: left subtree has marks. 1 bit: right subtree has marks.
338template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
339template<typename iterate_extra_t,
340 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
341int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked(iterate_extra_t *const iterate_extra) const {
342 static_assert(supports_marks, "does not support marks");
343 paranoid_invariant(!this->is_array);
344 return this->iterate_over_marked_internal<iterate_extra_t, f>(this->d.t.root, 0, iterate_extra);
345}
346
347template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
348void omt<omtdata_t, omtdataout_t, supports_marks>::unmark(const subtree &subtree, const uint32_t index, GrowableArray<node_idx> *const indexes) {
349 if (subtree.is_null()) { return; }
350 omt_node &n = this->d.t.nodes[subtree.get_index()];
351 const uint32_t index_root = index + this->nweight(n.left);
352
353 const bool below = n.get_marks_below();
354 if (below) {
355 this->unmark(n.left, index, indexes);
356 }
357 if (n.get_marked()) {
358 indexes->push(index_root);
359 }
360 n.clear_stolen_bits();
361 if (below) {
362 this->unmark(n.right, index_root + 1, indexes);
363 }
364}
365
366template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
367void omt<omtdata_t, omtdataout_t, supports_marks>::delete_all_marked(void) {
368 static_assert(supports_marks, "does not support marks");
369 if (!this->has_marks()) {
370 return;
371 }
372 paranoid_invariant(!this->is_array);
373 GrowableArray<node_idx> marked_indexes;
374 marked_indexes.init();
375
376 // Remove all marks.
377 // We need to delete all the stolen bits before calling delete_at to prevent barfing.
378 this->unmark(this->d.t.root, 0, &marked_indexes);
379
380 for (uint32_t i = 0; i < marked_indexes.get_size(); i++) {
381 // Delete from left to right, shift by number already deleted.
382 // Alternative is delete from right to left.
383 int r = this->delete_at(marked_indexes.fetch_unchecked(i) - i);
384 lazy_assert_zero(r);
385 }
386 marked_indexes.deinit();
387 barf_if_marked(*this);
388}
389
390template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
391uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent_internal(const subtree &subtree, const bool UU(allow_marks)) const {
392 if (subtree.is_null()) {
393 return 0;
394 }
395 const omt_node &node = this->d.t.nodes[subtree.get_index()];
396 uint32_t num_marks = verify_marks_consistent_internal(node.left, node.get_marks_below());
397 num_marks += verify_marks_consistent_internal(node.right, node.get_marks_below());
398 if (node.get_marks_below()) {
399 paranoid_invariant(allow_marks);
400 paranoid_invariant(num_marks > 0);
401 } else {
402 // redundant with invariant below, but nice to have explicitly
403 paranoid_invariant(num_marks == 0);
404 }
405 if (node.get_marked()) {
406 paranoid_invariant(allow_marks);
407 ++num_marks;
408 }
409 return num_marks;
410}
411
412template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
413void omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent(void) const {
414 static_assert(supports_marks, "does not support marks");
415 paranoid_invariant(!this->is_array);
416 this->verify_marks_consistent_internal(this->d.t.root, true);
417}
418
419template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
420template<typename iterate_extra_t,
421 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)>
422void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr(iterate_extra_t *const iterate_extra) {
423 if (this->is_array) {
424 this->iterate_ptr_internal_array<iterate_extra_t, f>(0, this->size(), iterate_extra);
425 } else {
426 this->iterate_ptr_internal<iterate_extra_t, f>(0, this->size(), this->d.t.root, 0, iterate_extra);
427 }
428}
429
430template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
431int omt<omtdata_t, omtdataout_t, supports_marks>::fetch(const uint32_t idx, omtdataout_t *const value) const {
432 if (idx >= this->size()) { return EINVAL; }
433 if (this->is_array) {
434 this->fetch_internal_array(idx, value);
435 } else {
436 this->fetch_internal(this->d.t.root, idx, value);
437 }
438 return 0;
439}
440
441template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
442template<typename omtcmp_t,
443 int (*h)(const omtdata_t &, const omtcmp_t &)>
444int omt<omtdata_t, omtdataout_t, supports_marks>::find_zero(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
445 uint32_t tmp_index;
446 uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index;
447 int r;
448 if (this->is_array) {
449 r = this->find_internal_zero_array<omtcmp_t, h>(extra, value, child_idxp);
450 }
451 else {
452 r = this->find_internal_zero<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp);
453 }
454 return r;
455}
456
457template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
458template<typename omtcmp_t,
459 int (*h)(const omtdata_t &, const omtcmp_t &)>
460int omt<omtdata_t, omtdataout_t, supports_marks>::find(const omtcmp_t &extra, int direction, omtdataout_t *const value, uint32_t *const idxp) const {
461 uint32_t tmp_index;
462 uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index;
463 paranoid_invariant(direction != 0);
464 if (direction < 0) {
465 if (this->is_array) {
466 return this->find_internal_minus_array<omtcmp_t, h>(extra, value, child_idxp);
467 } else {
468 return this->find_internal_minus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp);
469 }
470 } else {
471 if (this->is_array) {
472 return this->find_internal_plus_array<omtcmp_t, h>(extra, value, child_idxp);
473 } else {
474 return this->find_internal_plus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp);
475 }
476 }
477}
478
479template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
480size_t omt<omtdata_t, omtdataout_t, supports_marks>::memory_size(void) {
481 if (this->is_array) {
482 return (sizeof *this) + this->capacity * (sizeof this->d.a.values[0]);
483 }
484 return (sizeof *this) + this->capacity * (sizeof this->d.t.nodes[0]);
485}
486
487
488template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
489void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal_no_array(const uint32_t new_capacity) {
490 this->is_array = true;
491 this->d.a.start_idx = 0;
492 this->d.a.num_values = 0;
493 this->d.a.values = nullptr;
494 this->capacity = new_capacity;
495}
496
497template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
498void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal(const uint32_t new_capacity) {
499 this->create_internal_no_array(new_capacity);
500 XMALLOC_N(this->capacity, this->d.a.values);
501}
502
503template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
504uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::nweight(const subtree &subtree) const {
505 if (subtree.is_null()) {
506 return 0;
507 } else {
508 return this->d.t.nodes[subtree.get_index()].weight;
509 }
510}
511
512template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
513typename omt<omtdata_t, omtdataout_t, supports_marks>::node_idx omt<omtdata_t, omtdataout_t, supports_marks>::node_malloc(void) {
514 paranoid_invariant(this->d.t.free_idx < this->capacity);
515 omt_node &n = this->d.t.nodes[this->d.t.free_idx];
516 n.clear_stolen_bits();
517 return this->d.t.free_idx++;
518}
519
520template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
521void omt<omtdata_t, omtdataout_t, supports_marks>::node_free(const node_idx UU(idx)) {
522 paranoid_invariant(idx < this->capacity);
523}
524
525template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
526void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_array(const uint32_t n) {
527 const uint32_t new_size = n<=2 ? 4 : 2*n;
528 const uint32_t room = this->capacity - this->d.a.start_idx;
529
530 if (room < n || this->capacity / 2 >= new_size) {
531 omtdata_t *XMALLOC_N(new_size, tmp_values);
532 memcpy(tmp_values, &this->d.a.values[this->d.a.start_idx],
533 this->d.a.num_values * (sizeof tmp_values[0]));
534 this->d.a.start_idx = 0;
535 this->capacity = new_size;
536 toku_free(this->d.a.values);
537 this->d.a.values = tmp_values;
538 }
539}
540
541template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
542void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_values(omtdata_t *const array, const subtree &subtree) const {
543 if (subtree.is_null()) return;
544 const omt_node &tree = this->d.t.nodes[subtree.get_index()];
545 this->fill_array_with_subtree_values(&array[0], tree.left);
546 array[this->nweight(tree.left)] = tree.value;
547 this->fill_array_with_subtree_values(&array[this->nweight(tree.left) + 1], tree.right);
548}
549
550template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
551void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_array(void) {
552 if (!this->is_array) {
553 const uint32_t num_values = this->size();
554 uint32_t new_size = 2*num_values;
555 new_size = new_size < 4 ? 4 : new_size;
556
557 omtdata_t *XMALLOC_N(new_size, tmp_values);
558 this->fill_array_with_subtree_values(tmp_values, this->d.t.root);
559 toku_free(this->d.t.nodes);
560 this->is_array = true;
561 this->capacity = new_size;
562 this->d.a.num_values = num_values;
563 this->d.a.values = tmp_values;
564 this->d.a.start_idx = 0;
565 }
566}
567
568template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
569void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_from_sorted_array(subtree *const subtree, const omtdata_t *const values, const uint32_t numvalues) {
570 if (numvalues==0) {
571 subtree->set_to_null();
572 } else {
573 const uint32_t halfway = numvalues/2;
574 const node_idx newidx = this->node_malloc();
575 omt_node *const newnode = &this->d.t.nodes[newidx];
576 newnode->weight = numvalues;
577 newnode->value = values[halfway];
578 subtree->set_index(newidx);
579 // update everything before the recursive calls so the second call can be a tail call.
580 this->rebuild_from_sorted_array(&newnode->left, &values[0], halfway);
581 this->rebuild_from_sorted_array(&newnode->right, &values[halfway+1], numvalues - (halfway+1));
582 }
583}
584
585template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
586void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_tree(void) {
587 if (this->is_array) {
588 const uint32_t num_nodes = this->size();
589 uint32_t new_size = num_nodes*2;
590 new_size = new_size < 4 ? 4 : new_size;
591
592 omt_node *XMALLOC_N(new_size, new_nodes);
593 omtdata_t *const values = this->d.a.values;
594 omtdata_t *const tmp_values = &values[this->d.a.start_idx];
595 this->is_array = false;
596 this->d.t.nodes = new_nodes;
597 this->capacity = new_size;
598 this->d.t.free_idx = 0;
599 this->d.t.root.set_to_null();
600 this->rebuild_from_sorted_array(&this->d.t.root, tmp_values, num_nodes);
601 toku_free(values);
602 }
603}
604
605template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
606void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_or_convert(const uint32_t n) {
607 if (this->is_array) {
608 this->maybe_resize_array(n);
609 } else {
610 const uint32_t new_size = n<=2 ? 4 : 2*n;
611 const uint32_t num_nodes = this->nweight(this->d.t.root);
612 if ((this->capacity/2 >= new_size) ||
613 (this->d.t.free_idx >= this->capacity && num_nodes < n) ||
614 (this->capacity<n)) {
615 this->convert_to_array();
616 // if we had a free list, the "supports_marks" version could
617 // just resize, as it is now, we have to convert to and back
618 // from an array.
619 if (supports_marks) {
620 this->convert_to_tree();
621 }
622 }
623 }
624}
625
626template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
627bool omt<omtdata_t, omtdataout_t, supports_marks>::will_need_rebalance(const subtree &subtree, const int leftmod, const int rightmod) const {
628 if (subtree.is_null()) { return false; }
629 const omt_node &n = this->d.t.nodes[subtree.get_index()];
630 // one of the 1's is for the root.
631 // the other is to take ceil(n/2)
632 const uint32_t weight_left = this->nweight(n.left) + leftmod;
633 const uint32_t weight_right = this->nweight(n.right) + rightmod;
634 return ((1+weight_left < (1+1+weight_right)/2)
635 ||
636 (1+weight_right < (1+1+weight_left)/2));
637}
638
639template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
640void omt<omtdata_t, omtdataout_t, supports_marks>::insert_internal(subtree *const subtreep, const omtdata_t &value, const uint32_t idx, subtree **const rebalance_subtree) {
641 if (subtreep->is_null()) {
642 paranoid_invariant_zero(idx);
643 const node_idx newidx = this->node_malloc();
644 omt_node *const newnode = &this->d.t.nodes[newidx];
645 newnode->weight = 1;
646 newnode->left.set_to_null();
647 newnode->right.set_to_null();
648 newnode->value = value;
649 subtreep->set_index(newidx);
650 } else {
651 omt_node &n = this->d.t.nodes[subtreep->get_index()];
652 n.weight++;
653 if (idx <= this->nweight(n.left)) {
654 if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 1, 0)) {
655 *rebalance_subtree = subtreep;
656 }
657 this->insert_internal(&n.left, value, idx, rebalance_subtree);
658 } else {
659 if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, 1)) {
660 *rebalance_subtree = subtreep;
661 }
662 const uint32_t sub_index = idx - this->nweight(n.left) - 1;
663 this->insert_internal(&n.right, value, sub_index, rebalance_subtree);
664 }
665 }
666}
667
668template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
669void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal_array(const omtdata_t &value, const uint32_t idx) {
670 this->d.a.values[this->d.a.start_idx + idx] = value;
671}
672
673template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
674void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal(const subtree &subtree, const omtdata_t &value, const uint32_t idx) {
675 paranoid_invariant(!subtree.is_null());
676 omt_node &n = this->d.t.nodes[subtree.get_index()];
677 const uint32_t leftweight = this->nweight(n.left);
678 if (idx < leftweight) {
679 this->set_at_internal(n.left, value, idx);
680 } else if (idx == leftweight) {
681 n.value = value;
682 } else {
683 this->set_at_internal(n.right, value, idx - leftweight - 1);
684 }
685}
686
687template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
688void omt<omtdata_t, omtdataout_t, supports_marks>::delete_internal(subtree *const subtreep, const uint32_t idx, omt_node *const copyn, subtree **const rebalance_subtree) {
689 paranoid_invariant_notnull(subtreep);
690 paranoid_invariant_notnull(rebalance_subtree);
691 paranoid_invariant(!subtreep->is_null());
692 omt_node &n = this->d.t.nodes[subtreep->get_index()];
693 const uint32_t leftweight = this->nweight(n.left);
694 if (idx < leftweight) {
695 n.weight--;
696 if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, -1, 0)) {
697 *rebalance_subtree = subtreep;
698 }
699 this->delete_internal(&n.left, idx, copyn, rebalance_subtree);
700 } else if (idx == leftweight) {
701 if (n.left.is_null()) {
702 const uint32_t oldidx = subtreep->get_index();
703 *subtreep = n.right;
704 if (copyn != nullptr) {
705 copyn->value = n.value;
706 }
707 this->node_free(oldidx);
708 } else if (n.right.is_null()) {
709 const uint32_t oldidx = subtreep->get_index();
710 *subtreep = n.left;
711 if (copyn != nullptr) {
712 copyn->value = n.value;
713 }
714 this->node_free(oldidx);
715 } else {
716 if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) {
717 *rebalance_subtree = subtreep;
718 }
719 // don't need to copy up value, it's only used by this
720 // next call, and when that gets to the bottom there
721 // won't be any more recursion
722 n.weight--;
723 this->delete_internal(&n.right, 0, &n, rebalance_subtree);
724 }
725 } else {
726 n.weight--;
727 if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) {
728 *rebalance_subtree = subtreep;
729 }
730 this->delete_internal(&n.right, idx - leftweight - 1, copyn, rebalance_subtree);
731 }
732}
733
734template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
735template<typename iterate_extra_t,
736 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
737int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal_array(const uint32_t left, const uint32_t right,
738 iterate_extra_t *const iterate_extra) const {
739 int r;
740 for (uint32_t i = left; i < right; ++i) {
741 r = f(this->d.a.values[this->d.a.start_idx + i], i, iterate_extra);
742 if (r != 0) {
743 return r;
744 }
745 }
746 return 0;
747}
748
749template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
750template<typename iterate_extra_t,
751 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)>
752void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal(const uint32_t left, const uint32_t right,
753 const subtree &subtree, const uint32_t idx,
754 iterate_extra_t *const iterate_extra) {
755 if (!subtree.is_null()) {
756 omt_node &n = this->d.t.nodes[subtree.get_index()];
757 const uint32_t idx_root = idx + this->nweight(n.left);
758 if (left < idx_root) {
759 this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra);
760 }
761 if (left <= idx_root && idx_root < right) {
762 int r = f(&n.value, idx_root, iterate_extra);
763 lazy_assert_zero(r);
764 }
765 if (idx_root + 1 < right) {
766 this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra);
767 }
768 }
769}
770
771template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
772template<typename iterate_extra_t,
773 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)>
774void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal_array(const uint32_t left, const uint32_t right,
775 iterate_extra_t *const iterate_extra) {
776 for (uint32_t i = left; i < right; ++i) {
777 int r = f(&this->d.a.values[this->d.a.start_idx + i], i, iterate_extra);
778 lazy_assert_zero(r);
779 }
780}
781
782template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
783template<typename iterate_extra_t,
784 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
785int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal(const uint32_t left, const uint32_t right,
786 const subtree &subtree, const uint32_t idx,
787 iterate_extra_t *const iterate_extra) const {
788 if (subtree.is_null()) { return 0; }
789 int r;
790 const omt_node &n = this->d.t.nodes[subtree.get_index()];
791 const uint32_t idx_root = idx + this->nweight(n.left);
792 if (left < idx_root) {
793 r = this->iterate_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra);
794 if (r != 0) { return r; }
795 }
796 if (left <= idx_root && idx_root < right) {
797 r = f(n.value, idx_root, iterate_extra);
798 if (r != 0) { return r; }
799 }
800 if (idx_root + 1 < right) {
801 return this->iterate_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra);
802 }
803 return 0;
804}
805
806template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
807template<typename iterate_extra_t,
808 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
809int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range_internal(const uint32_t left, const uint32_t right,
810 const subtree &subtree, const uint32_t idx,
811 iterate_extra_t *const iterate_extra) {
812 paranoid_invariant(!subtree.is_null());
813 int r;
814 omt_node &n = this->d.t.nodes[subtree.get_index()];
815 const uint32_t idx_root = idx + this->nweight(n.left);
816 if (left < idx_root && !n.left.is_null()) {
817 n.set_marks_below_bit();
818 r = this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra);
819 if (r != 0) { return r; }
820 }
821 if (left <= idx_root && idx_root < right) {
822 n.set_marked_bit();
823 r = f(n.value, idx_root, iterate_extra);
824 if (r != 0) { return r; }
825 }
826 if (idx_root + 1 < right && !n.right.is_null()) {
827 n.set_marks_below_bit();
828 return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra);
829 }
830 return 0;
831}
832
833template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
834template<typename iterate_extra_t,
835 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)>
836int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked_internal(const subtree &subtree, const uint32_t idx,
837 iterate_extra_t *const iterate_extra) const {
838 if (subtree.is_null()) { return 0; }
839 int r;
840 const omt_node &n = this->d.t.nodes[subtree.get_index()];
841 const uint32_t idx_root = idx + this->nweight(n.left);
842 if (n.get_marks_below()) {
843 r = this->iterate_over_marked_internal<iterate_extra_t, f>(n.left, idx, iterate_extra);
844 if (r != 0) { return r; }
845 }
846 if (n.get_marked()) {
847 r = f(n.value, idx_root, iterate_extra);
848 if (r != 0) { return r; }
849 }
850 if (n.get_marks_below()) {
851 return this->iterate_over_marked_internal<iterate_extra_t, f>(n.right, idx_root + 1, iterate_extra);
852 }
853 return 0;
854}
855
856template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
857void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal_array(const uint32_t i, omtdataout_t *const value) const {
858 if (value != nullptr) {
859 copyout(value, &this->d.a.values[this->d.a.start_idx + i]);
860 }
861}
862
863template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
864void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal(const subtree &subtree, const uint32_t i, omtdataout_t *const value) const {
865 omt_node &n = this->d.t.nodes[subtree.get_index()];
866 const uint32_t leftweight = this->nweight(n.left);
867 if (i < leftweight) {
868 this->fetch_internal(n.left, i, value);
869 } else if (i == leftweight) {
870 if (value != nullptr) {
871 copyout(value, &n);
872 }
873 } else {
874 this->fetch_internal(n.right, i - leftweight - 1, value);
875 }
876}
877
878template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
879void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_idxs(node_idx *const array, const subtree &subtree) const {
880 if (!subtree.is_null()) {
881 const omt_node &tree = this->d.t.nodes[subtree.get_index()];
882 this->fill_array_with_subtree_idxs(&array[0], tree.left);
883 array[this->nweight(tree.left)] = subtree.get_index();
884 this->fill_array_with_subtree_idxs(&array[this->nweight(tree.left) + 1], tree.right);
885 }
886}
887
888template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
889void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_subtree_from_idxs(subtree *const subtree, const node_idx *const idxs, const uint32_t numvalues) {
890 if (numvalues==0) {
891 subtree->set_to_null();
892 } else {
893 uint32_t halfway = numvalues/2;
894 subtree->set_index(idxs[halfway]);
895 //node_idx newidx = idxs[halfway];
896 omt_node &newnode = this->d.t.nodes[subtree->get_index()];
897 newnode.weight = numvalues;
898 // value is already in there.
899 this->rebuild_subtree_from_idxs(&newnode.left, &idxs[0], halfway);
900 this->rebuild_subtree_from_idxs(&newnode.right, &idxs[halfway+1], numvalues-(halfway+1));
901 //n_idx = newidx;
902 }
903}
904
905template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
906void omt<omtdata_t, omtdataout_t, supports_marks>::rebalance(subtree *const subtree) {
907 node_idx idx = subtree->get_index();
908 if (idx==this->d.t.root.get_index()) {
909 //Try to convert to an array.
910 //If this fails, (malloc) nothing will have changed.
911 //In the failure case we continue on to the standard rebalance
912 //algorithm.
913 this->convert_to_array();
914 if (supports_marks) {
915 this->convert_to_tree();
916 }
917 } else {
918 const omt_node &n = this->d.t.nodes[idx];
919 node_idx *tmp_array;
920 size_t mem_needed = n.weight * (sizeof tmp_array[0]);
921 size_t mem_free = (this->capacity - this->d.t.free_idx) * (sizeof this->d.t.nodes[0]);
922 bool malloced;
923 if (mem_needed<=mem_free) {
924 //There is sufficient free space at the end of the nodes array
925 //to hold enough node indexes to rebalance.
926 malloced = false;
927 tmp_array = reinterpret_cast<node_idx *>(&this->d.t.nodes[this->d.t.free_idx]);
928 }
929 else {
930 malloced = true;
931 XMALLOC_N(n.weight, tmp_array);
932 }
933 this->fill_array_with_subtree_idxs(tmp_array, *subtree);
934 this->rebuild_subtree_from_idxs(subtree, tmp_array, n.weight);
935 if (malloced) toku_free(tmp_array);
936 }
937}
938
939template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
940void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omt_node *const n) {
941 *out = n->value;
942}
943
944template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
945void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omt_node *const n) {
946 *out = &n->value;
947}
948
949template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
950void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omtdata_t *const stored_value_ptr) {
951 *out = *stored_value_ptr;
952}
953
954template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
955void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omtdata_t *const stored_value_ptr) {
956 *out = stored_value_ptr;
957}
958
959template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
960template<typename omtcmp_t,
961 int (*h)(const omtdata_t &, const omtcmp_t &)>
962int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
963 paranoid_invariant_notnull(idxp);
964 uint32_t min = this->d.a.start_idx;
965 uint32_t limit = this->d.a.start_idx + this->d.a.num_values;
966 uint32_t best_pos = subtree::NODE_NULL;
967 uint32_t best_zero = subtree::NODE_NULL;
968
969 while (min!=limit) {
970 uint32_t mid = (min + limit) / 2;
971 int hv = h(this->d.a.values[mid], extra);
972 if (hv<0) {
973 min = mid+1;
974 }
975 else if (hv>0) {
976 best_pos = mid;
977 limit = mid;
978 }
979 else {
980 best_zero = mid;
981 limit = mid;
982 }
983 }
984 if (best_zero!=subtree::NODE_NULL) {
985 //Found a zero
986 if (value != nullptr) {
987 copyout(value, &this->d.a.values[best_zero]);
988 }
989 *idxp = best_zero - this->d.a.start_idx;
990 return 0;
991 }
992 if (best_pos!=subtree::NODE_NULL) *idxp = best_pos - this->d.a.start_idx;
993 else *idxp = this->d.a.num_values;
994 return DB_NOTFOUND;
995}
996
997template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
998template<typename omtcmp_t,
999 int (*h)(const omtdata_t &, const omtcmp_t &)>
1000int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
1001 paranoid_invariant_notnull(idxp);
1002 if (subtree.is_null()) {
1003 *idxp = 0;
1004 return DB_NOTFOUND;
1005 }
1006 omt_node &n = this->d.t.nodes[subtree.get_index()];
1007 int hv = h(n.value, extra);
1008 if (hv<0) {
1009 int r = this->find_internal_zero<omtcmp_t, h>(n.right, extra, value, idxp);
1010 *idxp += this->nweight(n.left)+1;
1011 return r;
1012 } else if (hv>0) {
1013 return this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp);
1014 } else {
1015 int r = this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp);
1016 if (r==DB_NOTFOUND) {
1017 *idxp = this->nweight(n.left);
1018 if (value != nullptr) {
1019 copyout(value, &n);
1020 }
1021 r = 0;
1022 }
1023 return r;
1024 }
1025}
1026
1027template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
1028template<typename omtcmp_t,
1029 int (*h)(const omtdata_t &, const omtcmp_t &)>
1030int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
1031 paranoid_invariant_notnull(idxp);
1032 uint32_t min = this->d.a.start_idx;
1033 uint32_t limit = this->d.a.start_idx + this->d.a.num_values;
1034 uint32_t best = subtree::NODE_NULL;
1035
1036 while (min != limit) {
1037 const uint32_t mid = (min + limit) / 2;
1038 const int hv = h(this->d.a.values[mid], extra);
1039 if (hv > 0) {
1040 best = mid;
1041 limit = mid;
1042 } else {
1043 min = mid + 1;
1044 }
1045 }
1046 if (best == subtree::NODE_NULL) { return DB_NOTFOUND; }
1047 if (value != nullptr) {
1048 copyout(value, &this->d.a.values[best]);
1049 }
1050 *idxp = best - this->d.a.start_idx;
1051 return 0;
1052}
1053
1054template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
1055template<typename omtcmp_t,
1056 int (*h)(const omtdata_t &, const omtcmp_t &)>
1057int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
1058 paranoid_invariant_notnull(idxp);
1059 if (subtree.is_null()) {
1060 return DB_NOTFOUND;
1061 }
1062 omt_node *const n = &this->d.t.nodes[subtree.get_index()];
1063 int hv = h(n->value, extra);
1064 int r;
1065 if (hv > 0) {
1066 r = this->find_internal_plus<omtcmp_t, h>(n->left, extra, value, idxp);
1067 if (r == DB_NOTFOUND) {
1068 *idxp = this->nweight(n->left);
1069 if (value != nullptr) {
1070 copyout(value, n);
1071 }
1072 r = 0;
1073 }
1074 } else {
1075 r = this->find_internal_plus<omtcmp_t, h>(n->right, extra, value, idxp);
1076 if (r == 0) {
1077 *idxp += this->nweight(n->left) + 1;
1078 }
1079 }
1080 return r;
1081}
1082
1083template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
1084template<typename omtcmp_t,
1085 int (*h)(const omtdata_t &, const omtcmp_t &)>
1086int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
1087 paranoid_invariant_notnull(idxp);
1088 uint32_t min = this->d.a.start_idx;
1089 uint32_t limit = this->d.a.start_idx + this->d.a.num_values;
1090 uint32_t best = subtree::NODE_NULL;
1091
1092 while (min != limit) {
1093 const uint32_t mid = (min + limit) / 2;
1094 const int hv = h(this->d.a.values[mid], extra);
1095 if (hv < 0) {
1096 best = mid;
1097 min = mid + 1;
1098 } else {
1099 limit = mid;
1100 }
1101 }
1102 if (best == subtree::NODE_NULL) { return DB_NOTFOUND; }
1103 if (value != nullptr) {
1104 copyout(value, &this->d.a.values[best]);
1105 }
1106 *idxp = best - this->d.a.start_idx;
1107 return 0;
1108}
1109
1110template<typename omtdata_t, typename omtdataout_t, bool supports_marks>
1111template<typename omtcmp_t,
1112 int (*h)(const omtdata_t &, const omtcmp_t &)>
1113int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const {
1114 paranoid_invariant_notnull(idxp);
1115 if (subtree.is_null()) {
1116 return DB_NOTFOUND;
1117 }
1118 omt_node *const n = &this->d.t.nodes[subtree.get_index()];
1119 int hv = h(n->value, extra);
1120 if (hv < 0) {
1121 int r = this->find_internal_minus<omtcmp_t, h>(n->right, extra, value, idxp);
1122 if (r == 0) {
1123 *idxp += this->nweight(n->left) + 1;
1124 } else if (r == DB_NOTFOUND) {
1125 *idxp = this->nweight(n->left);
1126 if (value != nullptr) {
1127 copyout(value, n);
1128 }
1129 r = 0;
1130 }
1131 return r;
1132 } else {
1133 return this->find_internal_minus<omtcmp_t, h>(n->left, extra, value, idxp);
1134 }
1135}
1136} // namespace toku
1137