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 /*====== 5 This file is part of PerconaFT. 6 7 8 Copyright (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 38 Licensed under the Apache License, Version 2.0 (the "License"); 39 you may not use this file except in compliance with the License. 40 You may obtain a copy of the License at G_DEFINE_TYPE_WITH_PRIVATE(GenericProgressDialogWidget,generic_progress_dialog_widget,GTK_TYPE_DIALOG)41 42 http://www.apache.org/licenses/LICENSE-2.0 43 44 Unless required by applicable law or agreed to in writing, software 45 distributed under the License is distributed on an "AS IS" BASIS, 46 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 47 See the License for the specific language governing permissions and 48 limitations under the License. 49 ======= */ 50 51 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." 52 53 #pragma once 54 55 #include <stdint.h> 56 #include <memory.h> 57 #include <toku_portability.h> 58 #include <toku_race_tools.h> 59 #include "growable_array.h" 60 61 namespace toku { 62 63 /** 64 * Order Maintenance Tree (OMT) 65 * 66 * Maintains a collection of totally ordered values, where each value has an integer weight. 67 * The OMT is a mutable datatype. 68 * 69 * The Abstraction: 70 * 71 * An OMT is a vector of values, $V$, where $|V|$ is the length of the vector. 72 * The vector is numbered from $0$ to $|V|-1$. 73 * Each value has a weight. The weight of the $i$th element is denoted $w(V_i)$. 74 * 75 * We can create a new OMT, which is the empty vector. 76 * 77 * We can insert a new element $x$ into slot $i$, changing $V$ into $V'$ where 78 * $|V'|=1+|V|$ and 79 * 80 * V'_j = V_j if $j<i$ 81 * x if $j=i$ 82 * V_{j-1} if $j>i$. 83 * 84 * We can specify $i$ using a kind of function instead of as an integer. 85 * Let $b$ be a function mapping from values to nonzero integers, such that 86 * the signum of $b$ is monotically increasing. 87 * We can specify $i$ as the minimum integer such that $b(V_i)>0$. 88 * 89 * We look up a value using its index, or using a Heaviside function. 90 * For lookups, we allow $b$ to be zero for some values, and again the signum of $b$ must be monotonically increasing. 91 * When lookup up values, we can look up 92 * $V_i$ where $i$ is the minimum integer such that $b(V_i)=0$. (With a special return code if no such value exists.) 93 * (Rationale: Ordinarily we want $i$ to be unique. But for various reasons we want to allow multiple zeros, and we want the smallest $i$ in that case.) 94 * $V_i$ where $i$ is the minimum integer such that $b(V_i)>0$. (Or an indication that no such value exists.) 95 * $V_i$ where $i$ is the maximum integer such that $b(V_i)<0$. (Or an indication that no such value exists.) 96 * 97 * When looking up a value using a Heaviside function, we get the value and its index. 98 * 99 * We can also split an OMT into two OMTs, splitting the weight of the values evenly. 100 * Find a value $j$ such that the values to the left of $j$ have about the same total weight as the values to the right of $j$. 101 * The resulting two OMTs contain the values to the left of $j$ and the values to the right of $j$ respectively. 102 * All of the values from the original OMT go into one of the new OMTs. 103 * If the weights of the values don't split exactly evenly, then the implementation has the freedom to choose whether 104 * the new left OMT or the new right OMT is larger. 105 * 106 * Performance: 107 * Insertion and deletion should run with $O(\log |V|)$ time and $O(\log |V|)$ calls to the Heaviside function. 108 * The memory required is O(|V|). 109 * 110 * Usage: 111 * The omt is templated by two parameters: 112 * - omtdata_t is what will be stored within the omt. These could be pointers or real data types (ints, structs). 113 * - omtdataout_t is what will be returned by find and related functions. By default, it is the same as omtdata_t, but you can set it to (omtdata_t *). 114 * To create an omt which will store "TXNID"s, for example, it is a good idea to typedef the template: 115 * typedef omt<TXNID> txnid_omt_t; 116 * If you are storing structs, you may want to be able to get a pointer to the data actually stored in the omt (see find_zero). To do this, use the second template parameter: 117 * typedef omt<struct foo, struct foo *> foo_omt_t; 118 */ 119 120 namespace omt_internal { 121 122 template<bool subtree_supports_marks> 123 class subtree_templated { 124 private: 125 uint32_t m_index; 126 public: 127 static const uint32_t NODE_NULL = UINT32_MAX; 128 inline void set_to_null(void) { 129 m_index = NODE_NULL; 130 } 131 132 inline bool is_null(void) const { 133 return NODE_NULL == this->get_index(); 134 } 135 136 inline uint32_t get_index(void) const { 137 return m_index; 138 } 139 140 inline void set_index(uint32_t index) { 141 paranoid_invariant(index != NODE_NULL); 142 m_index = index; 143 } 144 } ; 145 146 template<> 147 class subtree_templated<true> { 148 private: 149 uint32_t m_bitfield; 150 static const uint32_t MASK_INDEX = ~(((uint32_t)1) << 31); 151 static const uint32_t MASK_BIT = ((uint32_t)1) << 31; 152 153 inline void set_index_internal(uint32_t new_index) { 154 m_bitfield = (m_bitfield & MASK_BIT) | new_index; 155 } 156 public: 157 static const uint32_t NODE_NULL = INT32_MAX; 158 inline void set_to_null(void) { 159 this->set_index_internal(NODE_NULL); 160 } 161 162 inline bool is_null(void) const { 163 return NODE_NULL == this->get_index(); 164 } 165 166 inline uint32_t get_index(void) const { 167 TOKU_DRD_IGNORE_VAR(m_bitfield); 168 const uint32_t bits = m_bitfield; 169 TOKU_DRD_STOP_IGNORING_VAR(m_bitfield); 170 return bits & MASK_INDEX; 171 } 172 173 inline void set_index(uint32_t index) { 174 paranoid_invariant(index < NODE_NULL); 175 this->set_index_internal(index); 176 } 177 178 inline bool get_bit(void) const { 179 TOKU_DRD_IGNORE_VAR(m_bitfield); 180 const uint32_t bits = m_bitfield; 181 TOKU_DRD_STOP_IGNORING_VAR(m_bitfield); 182 return (bits & MASK_BIT) != 0; 183 } 184 185 inline void enable_bit(void) { 186 // These bits may be set by a thread with a write lock on some 187 // leaf, and the index can be read by another thread with a (read 188 // or write) lock on another thread. Also, the has_marks_below 189 // bit can be set by two threads simultaneously. Neither of these 190 // are real races, so if we are using DRD we should tell it to 191 // ignore these bits just while we set this bit. If there were a 192 // race in setting the index, that would be a real race. 193 TOKU_DRD_IGNORE_VAR(m_bitfield); 194 m_bitfield |= MASK_BIT; 195 TOKU_DRD_STOP_IGNORING_VAR(m_bitfield); 196 } 197 198 inline void disable_bit(void) { 199 m_bitfield &= MASK_INDEX; 200 } 201 } ; 202 203 template<typename omtdata_t, bool subtree_supports_marks> 204 class omt_node_templated { 205 public: 206 uint32_t weight; 207 subtree_templated<subtree_supports_marks> left; 208 subtree_templated<subtree_supports_marks> right; 209 omtdata_t value; 210 211 // this needs to be in both implementations because we don't have 212 // a "static if" the caller can use 213 inline void clear_stolen_bits(void) {} 214 } ; 215 216 template<typename omtdata_t> 217 class omt_node_templated<omtdata_t, true> { 218 public: 219 uint32_t weight; 220 subtree_templated<true> left; 221 subtree_templated<true> right; 222 omtdata_t value; 223 inline bool get_marked(void) const { 224 return left.get_bit(); 225 } 226 inline void set_marked_bit(void) { 227 return left.enable_bit(); 228 } 229 inline void unset_marked_bit(void) { 230 return left.disable_bit(); 231 } 232 233 inline bool get_marks_below(void) const { 234 return right.get_bit(); 235 } 236 inline void set_marks_below_bit(void) { 237 // This function can be called by multiple threads. 238 // Checking first reduces cache invalidation. 239 if (!this->get_marks_below()) { 240 right.enable_bit(); 241 } 242 } 243 inline void unset_marks_below_bit(void) { 244 right.disable_bit(); 245 } 246 247 inline void clear_stolen_bits(void) { 248 this->unset_marked_bit(); 249 this->unset_marks_below_bit(); 250 } 251 } ; 252 253 } 254 255 template<typename omtdata_t, 256 typename omtdataout_t=omtdata_t, 257 bool supports_marks=false> 258 class omt { 259 public: 260 /** 261 * Effect: Create an empty OMT. 262 * Performance: constant time. 263 */ 264 void create(void); 265 266 /** 267 * Effect: Create an empty OMT with no internal allocated space. 268 * Performance: constant time. 269 * Rationale: In some cases we need a valid omt but don't want to malloc. 270 */ 271 void create_no_array(void); 272 273 /** 274 * Effect: Create a OMT containing values. The number of values is in numvalues. 275 * Stores the new OMT in *omtp. 276 * Requires: this has not been created yet 277 * Requires: values != NULL 278 * Requires: values is sorted 279 * Performance: time=O(numvalues) 280 * Rationale: Normally to insert N values takes O(N lg N) amortized time. 281 * If the N values are known in advance, are sorted, and 282 * the structure is empty, we can batch insert them much faster. 283 */ 284 __attribute__((nonnull)) 285 void create_from_sorted_array(const omtdata_t *const values, const uint32_t numvalues); 286 287 /** 288 * Effect: Create an OMT containing values. The number of values is in numvalues. 289 * On success the OMT takes ownership of *values array, and sets values=NULL. 290 * Requires: this has not been created yet 291 * Requires: values != NULL 292 * Requires: *values is sorted 293 * Requires: *values was allocated with toku_malloc 294 * Requires: Capacity of the *values array is <= new_capacity 295 * Requires: On success, *values may not be accessed again by the caller. 296 * Performance: time=O(1) 297 * Rational: create_from_sorted_array takes O(numvalues) time. 298 * By taking ownership of the array, we save a malloc and memcpy, 299 * and possibly a free (if the caller is done with the array). 300 */ 301 void create_steal_sorted_array(omtdata_t **const values, const uint32_t numvalues, const uint32_t new_capacity); 302 303 /** 304 * Effect: Create a new OMT, storing it in *newomt. 305 * The values to the right of index (starting at index) are moved to *newomt. 306 * Requires: newomt != NULL 307 * Returns 308 * 0 success, 309 * EINVAL if index > toku_omt_size(omt) 310 * On nonzero return, omt and *newomt are unmodified. 311 * Performance: time=O(n) 312 * Rationale: We don't need a split-evenly operation. We need to split items so that their total sizes 313 * are even, and other similar splitting criteria. It's easy to split evenly by calling size(), and dividing by two. 314 */ 315 __attribute__((nonnull)) 316 int split_at(omt *const newomt, const uint32_t idx); 317 318 /** 319 * Effect: Appends leftomt and rightomt to produce a new omt. 320 * Creates this as the new omt. 321 * leftomt and rightomt are destroyed. 322 * Performance: time=O(n) is acceptable, but one can imagine implementations that are O(\log n) worst-case. 323 */ 324 __attribute__((nonnull)) 325 void merge(omt *const leftomt, omt *const rightomt); 326 327 /** 328 * Effect: Creates a copy of an omt. 329 * Creates this as the clone. 330 * Each element is copied directly. If they are pointers, the underlying data is not duplicated. 331 * Performance: O(n) or the running time of fill_array_with_subtree_values() 332 */ 333 void clone(const omt &src); 334 335 /** 336 * Effect: Set the tree to be empty. 337 * Note: Will not reallocate or resize any memory. 338 * Performance: time=O(1) 339 */ 340 void clear(void); 341 342 /** 343 * Effect: Destroy an OMT, freeing all its memory. 344 * If the values being stored are pointers, their underlying data is not freed. See free_items() 345 * Those values may be freed before or after calling toku_omt_destroy. 346 * Rationale: Returns no values since free() cannot fail. 347 * Rationale: Does not free the underlying pointers to reduce complexity. 348 * Performance: time=O(1) 349 */ 350 void destroy(void); 351 352 /** 353 * Effect: return |this|. 354 * Performance: time=O(1) 355 */ 356 uint32_t size(void) const; 357 358 359 /** 360 * Effect: Insert value into the OMT. 361 * If there is some i such that $h(V_i, v)=0$ then returns DB_KEYEXIST. 362 * Otherwise, let i be the minimum value such that $h(V_i, v)>0$. 363 * If no such i exists, then let i be |V| 364 * Then this has the same effect as 365 * insert_at(tree, value, i); 366 * If idx!=NULL then i is stored in *idx 367 * Requires: The signum of h must be monotonically increasing. 368 * Returns: 369 * 0 success 370 * DB_KEYEXIST the key is present (h was equal to zero for some value) 371 * On nonzero return, omt is unchanged. 372 * Performance: time=O(\log N) amortized. 373 * Rationale: Some future implementation may be O(\log N) worst-case time, but O(\log N) amortized is good enough for now. 374 */ 375 template<typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> 376 int insert(const omtdata_t &value, const omtcmp_t &v, uint32_t *const idx); 377 378 /** 379 * Effect: Increases indexes of all items at slot >= idx by 1. 380 * Insert value into the position at idx. 381 * Returns: 382 * 0 success 383 * EINVAL if idx > this->size() 384 * On error, omt is unchanged. 385 * Performance: time=O(\log N) amortized time. 386 * Rationale: Some future implementation may be O(\log N) worst-case time, but O(\log N) amortized is good enough for now. 387 */ 388 int insert_at(const omtdata_t &value, const uint32_t idx); 389 390 /** 391 * Effect: Replaces the item at idx with value. 392 * Returns: 393 * 0 success 394 * EINVAL if idx>=this->size() 395 * On error, omt is unchanged. 396 * Performance: time=O(\log N) 397 * Rationale: The FT needs to be able to replace a value with another copy of the same value (allocated in a different location) 398 * 399 */ 400 int set_at(const omtdata_t &value, const uint32_t idx); 401 402 /** 403 * Effect: Delete the item in slot idx. 404 * Decreases indexes of all items at slot > idx by 1. 405 * Returns 406 * 0 success 407 * EINVAL if idx>=this->size() 408 * On error, omt is unchanged. 409 * Rationale: To delete an item, first find its index using find or find_zero, then delete it. 410 * Performance: time=O(\log N) amortized. 411 */ 412 int delete_at(const uint32_t idx); 413 414 /** 415 * Effect: Iterate over the values of the omt, from left to right, calling f on each value. 416 * The first argument passed to f is a ref-to-const of the value stored in the omt. 417 * The second argument passed to f is the index of the value. 418 * The third argument passed to f is iterate_extra. 419 * The indices run from 0 (inclusive) to this->size() (exclusive). 420 * Requires: f != NULL 421 * Returns: 422 * If f ever returns nonzero, then the iteration stops, and the value returned by f is returned by iterate. 423 * If f always returns zero, then iterate returns 0. 424 * Requires: Don't modify the omt while running. (E.g., f may not insert or delete values from the omt.) 425 * Performance: time=O(i+\log N) where i is the number of times f is called, and N is the number of elements in the omt. 426 * Rationale: Although the functional iterator requires defining another function (as opposed to C++ style iterator), it is much easier to read. 427 * Rationale: We may at some point use functors, but for now this is a smaller change from the old OMT. 428 */ 429 template<typename iterate_extra_t, 430 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 431 int iterate(iterate_extra_t *const iterate_extra) const; 432 433 /** 434 * Effect: Iterate over the values of the omt, from left to right, calling f on each value. 435 * The first argument passed to f is a ref-to-const of the value stored in the omt. 436 * The second argument passed to f is the index of the value. 437 * The third argument passed to f is iterate_extra. 438 * The indices run from 0 (inclusive) to this->size() (exclusive). 439 * We will iterate only over [left,right) 440 * 441 * Requires: left <= right 442 * Requires: f != NULL 443 * Returns: 444 * EINVAL if right > this->size() 445 * If f ever returns nonzero, then the iteration stops, and the value returned by f is returned by iterate_on_range. 446 * If f always returns zero, then iterate_on_range returns 0. 447 * Requires: Don't modify the omt while running. (E.g., f may not insert or delete values from the omt.) 448 * Performance: time=O(i+\log N) where i is the number of times f is called, and N is the number of elements in the omt. 449 * Rational: Although the functional iterator requires defining another function (as opposed to C++ style iterator), it is much easier to read. 450 */ 451 template<typename iterate_extra_t, 452 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 453 int iterate_on_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) const; 454 455 /** 456 * Effect: Iterate over the values of the omt, and mark the nodes that are visited. 457 * Other than the marks, this behaves the same as iterate_on_range. 458 * Requires: supports_marks == true 459 * Performance: time=O(i+\log N) where i is the number of times f is called, and N is the number of elements in the omt. 460 * Notes: 461 * This function MAY be called concurrently by multiple threads, but 462 * not concurrently with any other non-const function. 463 */ 464 template<typename iterate_extra_t, 465 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 466 int iterate_and_mark_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra); 467 468 /** 469 * Effect: Iterate over the values of the omt, from left to right, calling f on each value whose node has been marked. 470 * Other than the marks, this behaves the same as iterate. 471 * Requires: supports_marks == true 472 * Performance: time=O(i+\log N) where i is the number of times f is called, and N is the number of elements in the omt. 473 */ 474 template<typename iterate_extra_t, 475 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 476 int iterate_over_marked(iterate_extra_t *const iterate_extra) const; 477 478 /** 479 * Effect: Delete all elements from the omt, whose nodes have been marked. 480 * Requires: supports_marks == true 481 * Performance: time=O(N + i\log N) where i is the number of marked elements, {c,sh}ould be faster 482 */ 483 void delete_all_marked(void); 484 485 /** 486 * Effect: Verify that the internal state of the marks in the tree are self-consistent. 487 * Crashes the system if the marks are in a bad state. 488 * Requires: supports_marks == true 489 * Performance: time=O(N) 490 * Notes: 491 * Even though this is a const function, it requires exclusive access. 492 * Rationale: 493 * The current implementation of the marks relies on a sort of 494 * "cache" bit representing the state of bits below it in the tree. 495 * This allows glass-box testing that these bits are correct. 496 */ 497 void verify_marks_consistent(void) const; 498 499 /** 500 * Effect: None 501 * Returns whether there are any marks in the tree. 502 */ 503 bool has_marks(void) const; 504 505 /** 506 * Effect: Iterate over the values of the omt, from left to right, calling f on each value. 507 * The first argument passed to f is a pointer to the value stored in the omt. 508 * The second argument passed to f is the index of the value. 509 * The third argument passed to f is iterate_extra. 510 * The indices run from 0 (inclusive) to this->size() (exclusive). 511 * Requires: same as for iterate() 512 * Returns: same as for iterate() 513 * Performance: same as for iterate() 514 * Rationale: In general, most iterators should use iterate() since they should not modify the data stored in the omt. This function is for iterators which need to modify values (for example, free_items). 515 * Rationale: We assume if you are transforming the data in place, you want to do it to everything at once, so there is not yet an iterate_on_range_ptr (but there could be). 516 */ 517 template<typename iterate_extra_t, 518 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> 519 void iterate_ptr(iterate_extra_t *const iterate_extra); 520 521 /** 522 * Effect: Set *value=V_idx 523 * Returns 524 * 0 success 525 * EINVAL if index>=toku_omt_size(omt) 526 * On nonzero return, *value is unchanged 527 * Performance: time=O(\log N) 528 */ 529 int fetch(const uint32_t idx, omtdataout_t *const value) const; 530 531 /** 532 * Effect: Find the smallest i such that h(V_i, extra)>=0 533 * If there is such an i and h(V_i,extra)==0 then set *idxp=i, set *value = V_i, and return 0. 534 * If there is such an i and h(V_i,extra)>0 then set *idxp=i and return DB_NOTFOUND. 535 * If there is no such i then set *idx=this->size() and return DB_NOTFOUND. 536 * Note: value is of type omtdataout_t, which may be of type (omtdata_t) or (omtdata_t *) but is fixed by the instantiation. 537 * If it is the value type, then the value is copied out (even if the value type is a pointer to something else) 538 * If it is the pointer type, then *value is set to a pointer to the data within the omt. 539 * This is determined by the type of the omt as initially declared. 540 * If the omt is declared as omt<foo_t>, then foo_t's will be stored and foo_t's will be returned by find and related functions. 541 * If the omt is declared as omt<foo_t, foo_t *>, then foo_t's will be stored, and pointers to the stored items will be returned by find and related functions. 542 * Rationale: 543 * Structs too small for malloc should be stored directly in the omt. 544 * These structs may need to be edited as they exist inside the omt, so we need a way to get a pointer within the omt. 545 * Using separate functions for returning pointers and values increases code duplication and reduces type-checking. 546 * That also reduces the ability of the creator of a data structure to give advice to its future users. 547 * Slight overloading in this case seemed to provide a better API and better type checking. 548 */ 549 template<typename omtcmp_t, 550 int (*h)(const omtdata_t &, const omtcmp_t &)> 551 int find_zero(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 552 553 /** 554 * Effect: 555 * If direction >0 then find the smallest i such that h(V_i,extra)>0. 556 * If direction <0 then find the largest i such that h(V_i,extra)<0. 557 * (Direction may not be equal to zero.) 558 * If value!=NULL then store V_i in *value 559 * If idxp!=NULL then store i in *idxp. 560 * Requires: The signum of h is monotically increasing. 561 * Returns 562 * 0 success 563 * DB_NOTFOUND no such value is found. 564 * On nonzero return, *value and *idxp are unchanged 565 * Performance: time=O(\log N) 566 * Rationale: 567 * Here's how to use the find function to find various things 568 * Cases for find: 569 * find first value: ( h(v)=+1, direction=+1 ) 570 * find last value ( h(v)=-1, direction=-1 ) 571 * find first X ( h(v)=(v< x) ? -1 : 1 direction=+1 ) 572 * find last X ( h(v)=(v<=x) ? -1 : 1 direction=-1 ) 573 * find X or successor to X ( same as find first X. ) 574 * 575 * Rationale: To help understand heaviside functions and behavor of find: 576 * There are 7 kinds of heaviside functions. 577 * The signus of the h must be monotonically increasing. 578 * Given a function of the following form, A is the element 579 * returned for direction>0, B is the element returned 580 * for direction<0, C is the element returned for 581 * direction==0 (see find_zero) (with a return of 0), and D is the element 582 * returned for direction==0 (see find_zero) with a return of DB_NOTFOUND. 583 * If any of A, B, or C are not found, then asking for the 584 * associated direction will return DB_NOTFOUND. 585 * See find_zero for more information. 586 * 587 * Let the following represent the signus of the heaviside function. 588 * 589 * -...- 590 * A 591 * D 592 * 593 * +...+ 594 * B 595 * D 596 * 597 * 0...0 598 * C 599 * 600 * -...-0...0 601 * AC 602 * 603 * 0...0+...+ 604 * C B 605 * 606 * -...-+...+ 607 * AB 608 * D 609 * 610 * -...-0...0+...+ 611 * AC B 612 */ 613 template<typename omtcmp_t, 614 int (*h)(const omtdata_t &, const omtcmp_t &)> 615 int find(const omtcmp_t &extra, int direction, omtdataout_t *const value, uint32_t *const idxp) const; 616 617 /** 618 * Effect: Return the size (in bytes) of the omt, as it resides in main memory. If the data stored are pointers, don't include the size of what they all point to. 619 */ 620 size_t memory_size(void); 621 622 private: 623 typedef uint32_t node_idx; 624 typedef omt_internal::subtree_templated<supports_marks> subtree; 625 typedef omt_internal::omt_node_templated<omtdata_t, supports_marks> omt_node; 626 ENSURE_POD(subtree); 627 628 struct omt_array { 629 uint32_t start_idx; 630 uint32_t num_values; 631 omtdata_t *values; 632 }; 633 634 struct omt_tree { 635 subtree root; 636 uint32_t free_idx; 637 omt_node *nodes; 638 }; 639 640 bool is_array; 641 uint32_t capacity; 642 union { 643 struct omt_array a; 644 struct omt_tree t; 645 } d; 646 647 __attribute__((nonnull)) 648 void unmark(const subtree &subtree, const uint32_t index, GrowableArray<node_idx> *const indexes); 649 650 void create_internal_no_array(const uint32_t new_capacity); 651 652 void create_internal(const uint32_t new_capacity); 653 654 uint32_t nweight(const subtree &subtree) const; 655 656 node_idx node_malloc(void); 657 658 void node_free(const node_idx idx); 659 660 void maybe_resize_array(const uint32_t n); 661 662 __attribute__((nonnull)) 663 void fill_array_with_subtree_values(omtdata_t *const array, const subtree &subtree) const; 664 665 void convert_to_array(void); 666 667 __attribute__((nonnull)) 668 void rebuild_from_sorted_array(subtree *const subtree, const omtdata_t *const values, const uint32_t numvalues); 669 670 void convert_to_tree(void); 671 672 void maybe_resize_or_convert(const uint32_t n); 673 674 bool will_need_rebalance(const subtree &subtree, const int leftmod, const int rightmod) const; 675 676 __attribute__((nonnull)) 677 void insert_internal(subtree *const subtreep, const omtdata_t &value, const uint32_t idx, subtree **const rebalance_subtree); 678 679 void set_at_internal_array(const omtdata_t &value, const uint32_t idx); 680 681 void set_at_internal(const subtree &subtree, const omtdata_t &value, const uint32_t idx); 682 683 void delete_internal(subtree *const subtreep, const uint32_t idx, omt_node *const copyn, subtree **const rebalance_subtree); 684 685 template<typename iterate_extra_t, 686 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 687 int iterate_internal_array(const uint32_t left, const uint32_t right, 688 iterate_extra_t *const iterate_extra) const; 689 690 template<typename iterate_extra_t, 691 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> 692 void iterate_ptr_internal(const uint32_t left, const uint32_t right, 693 const subtree &subtree, const uint32_t idx, 694 iterate_extra_t *const iterate_extra); 695 696 template<typename iterate_extra_t, 697 int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> 698 void iterate_ptr_internal_array(const uint32_t left, const uint32_t right, 699 iterate_extra_t *const iterate_extra); 700 701 template<typename iterate_extra_t, 702 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 703 int iterate_internal(const uint32_t left, const uint32_t right, 704 const subtree &subtree, const uint32_t idx, 705 iterate_extra_t *const iterate_extra) const; 706 707 template<typename iterate_extra_t, 708 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 709 int iterate_and_mark_range_internal(const uint32_t left, const uint32_t right, 710 const subtree &subtree, const uint32_t idx, 711 iterate_extra_t *const iterate_extra); 712 713 template<typename iterate_extra_t, 714 int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> 715 int iterate_over_marked_internal(const subtree &subtree, const uint32_t idx, 716 iterate_extra_t *const iterate_extra) const; 717 718 uint32_t verify_marks_consistent_internal(const subtree &subtree, const bool allow_marks) const; 719 720 void fetch_internal_array(const uint32_t i, omtdataout_t *const value) const; 721 722 void fetch_internal(const subtree &subtree, const uint32_t i, omtdataout_t *const value) const; 723 724 __attribute__((nonnull)) 725 void fill_array_with_subtree_idxs(node_idx *const array, const subtree &subtree) const; 726 727 __attribute__((nonnull)) 728 void rebuild_subtree_from_idxs(subtree *const subtree, const node_idx *const idxs, const uint32_t numvalues); 729 730 __attribute__((nonnull)) 731 void rebalance(subtree *const subtree); 732 733 __attribute__((nonnull)) 734 static void copyout(omtdata_t *const out, const omt_node *const n); 735 736 __attribute__((nonnull)) 737 static void copyout(omtdata_t **const out, omt_node *const n); 738 739 __attribute__((nonnull)) 740 static void copyout(omtdata_t *const out, const omtdata_t *const stored_value_ptr); 741 742 __attribute__((nonnull)) 743 static void copyout(omtdata_t **const out, omtdata_t *const stored_value_ptr); 744 745 template<typename omtcmp_t, 746 int (*h)(const omtdata_t &, const omtcmp_t &)> 747 int find_internal_zero_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 748 749 template<typename omtcmp_t, 750 int (*h)(const omtdata_t &, const omtcmp_t &)> 751 int find_internal_zero(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 752 753 template<typename omtcmp_t, 754 int (*h)(const omtdata_t &, const omtcmp_t &)> 755 int find_internal_plus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 756 757 template<typename omtcmp_t, 758 int (*h)(const omtdata_t &, const omtcmp_t &)> 759 int find_internal_plus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 760 761 template<typename omtcmp_t, 762 int (*h)(const omtdata_t &, const omtcmp_t &)> 763 int find_internal_minus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 764 765 template<typename omtcmp_t, 766 int (*h)(const omtdata_t &, const omtcmp_t &)> 767 int find_internal_minus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const; 768 }; 769 770 } // namespace toku 771 772 // include the implementation here 773 #include "omt.cc" 774