1 /******************************************************************************** 2 3 Internal (non-user facing) implementation of BTreeMap. 4 5 Copyright: 6 Copyright (c) 2017 dunnhumby Germany GmbH. All rights reserved. 7 8 License: 9 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 10 Alternatively, this file may be distributed under the terms of the Tango 11 3-Clause BSD License (see LICENSE_BSD.txt for details). 12 13 *******************************************************************************/ 14 15 module ocean.util.container.btree.Implementation; 16 17 import ocean.meta.types.Qualifiers; 18 19 /******************************************************************************* 20 21 Internal (non-user facing) implementation of BTreeMap. 22 23 Params: 24 KeyType = type of the key 25 ValueType = type of the value 26 tree_degree = degree of the tree. 27 28 *******************************************************************************/ 29 30 package struct BTreeMapImplementation (KeyType, ValueType, int tree_degree) 31 { 32 import ocean.core.array.Mutation; 33 import ocean.core.array.Search; 34 import ocean.core.Enforce; 35 import ocean.meta.types.Function; 36 import ocean.core.Verify; 37 import ocean.util.container.mem.MemManager; 38 39 /************************************************************************** 40 41 Node of the tree. Contains at most (degree * 2 - 1) elements and 42 (degree * 2) subtrees. 43 44 **************************************************************************/ 45 46 package struct BTreeMapNode 47 { 48 /********************************************************************** 49 50 KeyValue structure which binds key and a value to be stored in the 51 node. 52 53 NOTE: In addition of ordering notion, this is really the only thing 54 that makes this an implementation of the map, not of the set. If we're 55 going to add set support, we should probably do it via templating 56 this implementation on the actual content of the node's element 57 (replace KeyValue with just a value) and with the ordering operation 58 inserted as a policy (to compare the values, and not the nodes). 59 60 ***********************************************************************/ 61 62 private struct KeyValue 63 { 64 KeyType key; 65 // Storing the unqual ValueType here, as we need to reorder 66 // the elements in the node without creating new nodes. User 67 // facing API never sees unqualed type. 68 Unqual!(ValueType) value; 69 } 70 71 /// Number of the elements currently in the node 72 int number_of_elements; 73 74 /// Indicator if the given node is a leaf 75 bool is_leaf; 76 77 /// Array of the elements 78 package KeyValue[tree_degree * 2 - 1] elements; 79 80 /// Array of the pointers to the subtrees 81 package BTreeMapNode*[tree_degree * 2] child_nodes; 82 } 83 84 /************************************************************************** 85 86 Root of the tree. 87 88 ***************************************************************************/ 89 90 package BTreeMapNode* root; 91 92 /*************************************************************************** 93 94 Type of the element actually stored in the node. The type stored in the 95 node is unqualed version of the type that's accessible to the user, since 96 the container needs to change the content of the actual array, without 97 a need to always allocate a new one. 98 99 ***************************************************************************/ 100 101 private alias typeof(BTreeMapNode.elements[0].value) StoredValueType; 102 103 /*************************************************************************** 104 105 Convenience constant describing the tree's degree. 106 107 ***************************************************************************/ 108 109 private enum degree = tree_degree; 110 111 /*************************************************************************** 112 113 Memory manager used for allocating and deallocating memory. Refer to 114 ocean.util.container.mem.MemManager for potential options. 115 116 ***************************************************************************/ 117 118 package IMemManager allocator; 119 120 121 /*************************************************************************** 122 123 "version" of the tree's state. Will be incremented on any removal/adding 124 the element. On the iteration's start, range will record the current 125 "version" of the tree, and, and before proceeding with the iteration, 126 it will check if any changes were performed on the tree, to prevent 127 iteration over an undefined region. 128 129 ***************************************************************************/ 130 131 package ulong content_version; 132 133 /*************************************************************************** 134 135 Constructor-like method (as a workaround of a fact that D1 doesn't provide 136 struct constructors). 137 138 Params: 139 allocator = memory manager to use to allocate/deallocate memory 140 141 ***************************************************************************/ 142 143 package void initialize (IMemManager allocator = mallocMemManager) 144 { 145 verify (this.allocator is null); 146 this.allocator = allocator; 147 } 148 149 150 /************************************************************************** 151 152 Inserts the element in the tree. 153 154 Params: 155 key = key to insert 156 value = associated value to insert. 157 added = indicator if the element was added 158 159 Returns: 160 pointer to the element 161 162 ***************************************************************************/ 163 164 package ValueType* insert (KeyType key, ValueType el, out bool added) 165 { 166 verify(this.allocator !is null); 167 168 if (this.root is null) 169 { 170 this.root = this.insertNewNode(); 171 } 172 173 if (auto ptr = this.get(key)) 174 { 175 return ptr; 176 } 177 178 // unqualed for internal storage only. User will never access it as 179 // unqualed reference. 180 auto unqualed_el = cast(Unqual!(ValueType))el; 181 auto r = this.root; 182 added = true; 183 if (this.root.number_of_elements == this.root.elements.length) 184 { 185 auto node = this.insertNewNode(); 186 // this is a new root 187 this.root = node; 188 node.is_leaf = false; 189 node.number_of_elements = 0; 190 191 // Old root node is the first child 192 node.child_nodes[0] = r; 193 194 this.splitChild(node, 0, r); 195 auto ret = this.insertNonFull(node, key, unqualed_el); 196 debug (BTreeMapSanity) check_invariants(this); 197 this.content_version++; 198 return ret; 199 } 200 else 201 { 202 auto ret = this.insertNonFull(this.root, key, unqualed_el); 203 debug (BTreeMapSanity) check_invariants(this); 204 this.content_version++; 205 return ret; 206 } 207 } 208 209 /****************************************************************************** 210 211 Removes the element with the given key from the BTreeMap. 212 213 Params: 214 key = key associated with the element to delete. 215 216 Returns: 217 true if the element with the given key was found and deleted, 218 false otherwise. 219 220 ******************************************************************************/ 221 222 package bool remove (KeyType key) 223 { 224 verify(this.allocator !is null); 225 226 BTreeMapNode* parent = null; 227 228 bool rebalance_parent; 229 auto res = this.deleteFromNode(this.root, 230 parent, key, rebalance_parent); 231 232 // can't rebalance the root node here, as they should all be 233 // rebalanced internally by deleteFromNode 234 verify(rebalance_parent == false); 235 236 debug (BTreeMapSanity) check_invariants(this); 237 238 if (res) 239 this.content_version++; 240 241 return res; 242 } 243 244 /*************************************************************************** 245 246 Returns: 247 true if the tree is empty, false otherwise. 248 249 ***************************************************************************/ 250 251 package bool empty () 252 { 253 return this.root is null; 254 } 255 256 /****************************************************************************** 257 258 Searches the tree for the element with the given key and returns its 259 value if found. 260 261 Params: 262 key = key to find in the tree. 263 found = indicator if the element was found 264 265 Returns: 266 value associated with the key, or ValueType.init if not found. 267 268 *******************************************************************************/ 269 270 package ValueType get (KeyType key, out bool found_element) 271 { 272 size_t index; 273 auto node = this.get(key, index); 274 if (!node) return ValueType.init; 275 276 found_element = true; 277 return node.elements[index].value; 278 } 279 280 /****************************************************************************** 281 282 Searches the tree for the element with the given key and returns pointer 283 to it's value, or null if not found. 284 285 Params: 286 key = key to find in the tree. 287 288 Returns: 289 pointer to the value associated with the key, or null if not found. 290 291 *******************************************************************************/ 292 293 package ValueType* get (KeyType key) 294 { 295 size_t index; 296 297 if (auto node = this.get(key, index)) 298 return &node.elements[index].value; 299 else 300 return null; 301 } 302 303 // implementation 304 305 /*************************************************************************** 306 307 Finds the requested element in the tree. 308 309 Params: 310 key = key associated with the element to return 311 index = out parameter, holding the index of the element in the node 312 313 Returns: 314 pointer to the node holding `element`, null otherwise 315 316 ***************************************************************************/ 317 318 private BTreeMapNode* get (KeyType key, 319 out size_t index) 320 { 321 /// internal function for recursion 322 /// which does the actual search (outer function just accepts the tree) 323 static BTreeMapNode* getImpl (BTreeMapNode* root, 324 KeyType key, out size_t index) 325 { 326 auto pos = 0; 327 328 // TODO: binary search 329 while (pos < root.number_of_elements 330 && key > root.elements[pos].key) 331 { 332 pos++; 333 } 334 335 // now pos is the least index in the key array such 336 // that f < elements[pos] 337 if (pos < root.number_of_elements 338 && key == root.elements[pos].key) 339 { 340 index = pos; 341 return root; 342 } 343 344 // Nowhere to descend 345 if (root.is_leaf) 346 { 347 return null; 348 } 349 350 return getImpl(root.child_nodes[pos], key, index); 351 } 352 353 if (this.root is null) 354 { 355 return null; 356 } 357 358 return getImpl(this.root, key, index); 359 } 360 361 /****************************************************************************** 362 363 Does the necessary traversal to delete an element and rebalance parents 364 in the process. 365 366 Params: 367 node = node currently being inspected for the removal (as we go down 368 the tree, this parameter is being updated). 369 parent = parent of the node (needed when merging the neighbour nodes) 370 to_delete = key of the element to remove 371 rebalance_parent = indicator if while traversing back to the root, the 372 parent node should be rebalanced 373 374 Returns: true if the current node needs to be rebalanced 375 376 ******************************************************************************/ 377 378 private bool deleteFromNode ( BTreeMapNode* node, BTreeMapNode* parent, 379 KeyType to_delete, out bool rebalance_parent) 380 { 381 // does this node contain the element we want to delete? Or is it one of it's children? 382 foreach (i, ref element; node.elements[0..node.number_of_elements]) 383 { 384 if (element.key > to_delete) 385 { 386 // not found if it's the leaf 387 if (node.is_leaf) 388 return false; 389 390 auto delete_result = deleteFromNode(node.child_nodes[i], 391 node, to_delete, rebalance_parent); 392 if (rebalance_parent) 393 { 394 this.rebalanceAfterDeletion(node, parent, rebalance_parent); 395 } 396 397 return delete_result; 398 } 399 else if (element.key == to_delete) 400 { 401 auto element_index = i; 402 if (node.is_leaf) 403 { 404 deleteFromLeaf(node, i); 405 this.rebalanceAfterDeletion(node, parent, rebalance_parent); 406 407 return true; 408 } 409 else 410 { 411 // if we have the element in the internal node, then 412 // the highest element in the left subtree is still 413 // smaller than this element, so this element could just 414 // be replaced with it, and then that element in the 415 // left subtree should be removed. 416 auto victim_node = node.child_nodes[element_index]; 417 418 // find the highest element: 419 size_t highest_index; 420 auto highest_node = findMaximum(victim_node, highest_index); 421 auto highest_element = &highest_node.elements[highest_index]; 422 node.elements[element_index] = *highest_element; 423 424 auto delete_result = deleteFromNode(victim_node, 425 node, highest_element.key, rebalance_parent); 426 427 // The deletion of the element in the internal node is very simple: 428 // we need to find the largest element in the left subtree, put it 429 // instead of the element we want to delete, remove it from the subtree 430 // and rebalance the tree starting from that node. 431 if (rebalance_parent) 432 { 433 this.rebalanceAfterDeletion(node, parent, rebalance_parent); 434 } 435 return delete_result; 436 } 437 } 438 } 439 440 // no left subtree was found that it could contain this key. 441 // we need to check only for the most-right subtree. If it doesn't 442 // exists, there's no such key 443 if (node.is_leaf) 444 { 445 return false; 446 } 447 else 448 { 449 auto delete_result = deleteFromNode(node.child_nodes[node.number_of_elements], 450 node, to_delete, rebalance_parent); 451 452 if (rebalance_parent) 453 454 { 455 this.rebalanceAfterDeletion(node, parent, rebalance_parent); 456 } 457 458 return delete_result; 459 } 460 } 461 462 /****************************************************************************** 463 464 Allocates and initializes new node. 465 466 *******************************************************************************/ 467 468 private BTreeMapNode* insertNewNode() 469 { 470 auto node = cast(BTreeMapNode*)this.allocator.create(BTreeMapNode.sizeof).ptr; 471 *node = BTreeMapNode.init; 472 473 node.is_leaf = true; 474 node.number_of_elements = 0; 475 return node; 476 } 477 478 /************************************************************************** 479 480 Insert the element into the non-full node. If the node is leaf and not 481 full, then no spliting will be done, the element will simply be inserted 482 into it. 483 484 If the target node is non-leaf node, we also know that even if the 485 child node is split, there will be bplace to split it. 486 487 Params: 488 node = non-full node to insert the element into 489 key = key to insert 490 value = value to insert 491 492 Returns: 493 true if the element was inserted, false otherwise. 494 495 ***************************************************************************/ 496 497 private ValueType* insertNonFull 498 (BTreeMapNode* node, KeyType key, StoredValueType value) 499 { 500 if (node.is_leaf) 501 { 502 return insertIntoLeaf(node, key, value); 503 } 504 else 505 { 506 int i = node.number_of_elements - 1; 507 508 // find the child where new key belongs: 509 while (i >= 0 && key < node.elements[i].key) 510 i--; 511 512 // if the file should be in children[i], then f < elements[i] 513 // Well go back to the last key where we found this to be true, 514 // and get that child node 515 i++; 516 517 if (node.child_nodes[i].number_of_elements == node.child_nodes[i].elements.length) 518 { 519 splitChild(node, i, node.child_nodes[i]); 520 521 // now children[i] and children[i+] are the new 522 // children, and the elements[i] might been changed (we got it from the 523 // split child) 524 // we'll see if k belongs in the first or the second 525 if (key > node.elements[i].key) 526 i++; 527 } 528 529 // call ourself recursively to do the insertion 530 return insertNonFull(node.child_nodes[i], key, value); 531 } 532 } 533 534 /************************************************************************** 535 536 Splits the full child, so it can accept the new element. 537 538 New node is allocated and it gets the half of the elements from the 539 previous node, and the median element from the old node is moved into 540 the parent, separating these two child nodes. 541 542 Params: 543 parent = parent node 544 child_index = index of the subtree in the parent 545 child = the root of the subtree 546 547 ***************************************************************************/ 548 549 private void splitChild (BTreeMapNode* parent, 550 int child_index, 551 BTreeMapNode* child) 552 { 553 auto new_node = this.insertNewNode(); 554 // new node is a leaf if old node was 555 new_node.is_leaf = child.is_leaf; 556 moveElementsAt(new_node, 0, child, degree); 557 558 // Now put the median element in the parent, and insert the new 559 // node in the parent 560 shiftElements(parent, child_index, 1); 561 parent.elements[child_index] = child.elements[degree-1]; 562 parent.child_nodes[child_index+1] = new_node; 563 child.number_of_elements--; 564 } 565 566 /*************************************************************************** 567 568 569 Rebalances the tree after removal of the element. 570 Makes sure that the tree is still holding the invariants. 571 572 Params: 573 node = node from where the element was removed 574 parent = parent of the node. 575 rebalance_parent = indicator if the parent is now due to rebalancing. 576 577 ***************************************************************************/ 578 579 private void rebalanceAfterDeletion ( 580 BTreeMapNode* node, BTreeMapNode* parent, out bool rebalance_parent) 581 { 582 // check for the underflow. If the node now contains 583 // less than `degree-1` entries, we need to borrow the 584 // element from the neighbouring nodes 585 // note that the root is the only node which is allowed to have 586 // more than a minimum elements, so we will never rebalance it 587 if (node != this.root && node.number_of_elements < this.degree - 1) 588 { 589 long position_in_parent = -1; 590 591 for (auto i = 0; i < parent.number_of_elements + 1; i++) 592 { 593 if (parent.child_nodes[i] == node) 594 { 595 position_in_parent = i; 596 break; 597 } 598 } 599 600 verify (position_in_parent >= 0); 601 602 // case 1 - the neighbouring node contains more than 603 // (2 * degree - 1) - can't have less because of the invariant 604 // - in which case we join the node into the new one, 605 // and split it into the two, where the median element 606 // goes into the parent node. 607 if (parent.number_of_elements > position_in_parent) 608 { 609 auto next_neighbour = 610 parent.child_nodes[position_in_parent+1]; 611 612 // Now, either this exists or not, and if it exists, 613 // it has the spare elements, or it does't (in which case 614 // it's merged with the parent 615 616 if (next_neighbour && next_neighbour.number_of_elements > this.degree -1) 617 { 618 // copy the separator from the parent node 619 // into the deficient node 620 node.elements[node.number_of_elements] = parent.elements[position_in_parent]; 621 node.number_of_elements++; 622 node.child_nodes[node.number_of_elements] = next_neighbour.child_nodes[0]; 623 624 // replace the separator in the parent with the first 625 // element of the right sibling 626 parent.elements[position_in_parent] = popFromNode(next_neighbour, 0); 627 628 return; 629 } 630 } 631 632 // let's try with the left sibling 633 if (position_in_parent > 0) 634 { 635 // do the same thing but with the left sibling 636 auto previous_neighbour = 637 parent.child_nodes[position_in_parent-1]; 638 639 // Now, either this exists or not, and if it exists, 640 // it has the spare elements, or it does't (in which case 641 // it's merged with the parent 642 643 if (previous_neighbour.number_of_elements > this.degree -1) 644 { 645 shiftElements(node, 0, 1); 646 // copy the separator from the parent node 647 // into the deficient node 648 // 649 node.elements[0] = parent.elements[position_in_parent-1]; 650 651 // replace the separator in the parent with the last 652 // element of the left sibling 653 parent.elements[position_in_parent-1] = 654 previous_neighbour.elements[previous_neighbour.number_of_elements-1]; 655 656 // and move the top-right child of the left neighbourhood as the first 657 // child of the new one 658 node.child_nodes[0] = previous_neighbour.child_nodes[previous_neighbour.number_of_elements]; 659 660 previous_neighbour.number_of_elements--; 661 return; 662 } 663 } 664 665 // both immediate siblings have the only the minimum 666 // number of elements. Merge with a sibling then. 667 // this merging causes the parent to loose the element 668 // (because there will be no need for separating) two nodes, 669 // so we need to rebalance it with the neighbouring nodes 670 671 // Node that will accept everything afer the merge 672 BTreeMapNode* remaining_node; 673 674 // The edge cases are top-left or top-right nodes 675 // Note: Although these two cases are very same, 676 // it's easier to follow them if the code is slightly duplicated 677 if (position_in_parent < parent.number_of_elements) 678 { 679 auto next_neighbour = 680 parent.child_nodes[position_in_parent+1]; 681 682 node.elements[node.number_of_elements] = popFromNode(parent, position_in_parent); 683 node.number_of_elements++; 684 685 // parent.pop removed the node from it's list, put it now there 686 parent.child_nodes[position_in_parent] = node; 687 688 moveElementsAt(node, 689 node.number_of_elements, next_neighbour, 0); 690 691 remaining_node = node; 692 693 this.allocator.destroy(cast(ubyte[])(next_neighbour[0..1])); 694 } 695 else 696 { 697 auto previous_neighbour = 698 parent.child_nodes[position_in_parent-1]; 699 700 previous_neighbour.elements[previous_neighbour.number_of_elements] = popFromNode(parent, position_in_parent-1); 701 previous_neighbour.number_of_elements++; 702 703 // parent.pop removed the node from it's list, put it now there 704 parent.child_nodes[position_in_parent-1] = previous_neighbour; 705 706 moveElementsAt(previous_neighbour, 707 previous_neighbour.number_of_elements, node, 0); 708 709 remaining_node = previous_neighbour; 710 711 this.allocator.destroy(cast(ubyte[])((node)[0..1])); 712 } 713 714 // TODO: comment this 715 if (parent == this.root && parent.number_of_elements == 0) 716 { 717 this.allocator.destroy(cast(ubyte[])(parent[0..1])); 718 this.root = remaining_node; 719 return; 720 } 721 else if (parent != this.root && parent.number_of_elements < this.degree - 1) 722 { 723 rebalance_parent = true; 724 return; 725 } 726 else 727 { 728 // either is root, or it has enough elements 729 return; 730 } 731 732 assert(false); 733 } 734 // else - nothing to rebalance, node from which we've removed 735 // the element still has the right amount of the elements 736 } 737 738 /*************************************************************************** 739 740 Inserts the element into the leaf. 741 742 The simpliest version of the insertion - it just moves the elements 743 to create space for the new one and inserts it. 744 745 Params: 746 node = leaf node to insert the element into 747 key = key to insert 748 value = value to insert 749 750 ***************************************************************************/ 751 752 private static ValueType* insertIntoLeaf(BTreeMapNode* node, KeyType key, 753 StoredValueType value) 754 { 755 verify(node.is_leaf); 756 757 // shift all elements to make space for it 758 auto i = node.number_of_elements; 759 760 // shift everything over to the "right", up to the 761 // point where the new element should go 762 for (; i > 0 && key < node.elements[i-1].key; i--) 763 { 764 node.elements[i] = node.elements[i-1]; 765 } 766 767 node.elements[i].key = key; 768 node.elements[i].value = value; 769 node.number_of_elements++; 770 771 return &node.elements[i].value; 772 } 773 774 /*************************************************************************** 775 776 Removes the element from the leaf. 777 778 The simpliest version of the removal - it just removes the element 779 by moving all the elements next to it by one step. 780 781 Params: 782 node = pointer to the leaf node to remove the element from. 783 element_index = index of the element in the node to remove. 784 785 ***************************************************************************/ 786 787 private static void deleteFromLeaf(BTreeMapNode* node, size_t element_index) 788 { 789 verify(node.is_leaf); 790 791 // deletion from the leaf is easy - just remove it 792 // and shift all the ones left 793 foreach (j, ref el; node.elements[element_index..node.number_of_elements-1]) 794 { 795 el = node.elements[element_index + j + 1]; 796 } 797 798 node.number_of_elements--; 799 } 800 801 /*************************************************************************** 802 803 Shifts the element and subtree pointers inside a node starting from 804 `position` by `count`. 805 806 Params: 807 node = node to edit. 808 position = position to start shifting on 809 count = count of the shifts to perform.; 810 811 ***************************************************************************/ 812 813 private static void shiftElements (BTreeMapNode* node, int position, int count) 814 { 815 for (auto i = node.number_of_elements+count; i > position; i--) 816 { 817 node.child_nodes[i] = node.child_nodes[i-count]; 818 } 819 820 for (auto i = node.number_of_elements+count-1; i > position; i--) 821 { 822 node.elements[i] = node.elements[i-count]; 823 } 824 825 node.number_of_elements += count; 826 } 827 828 /*************************************************************************** 829 830 Moves the elements from one node to another. 831 832 In case we need to merge/split the nodes, we need to move the elements 833 and their subtrees to the new node. Remember that each element in the 834 node is dividing the subtrees to the one less than it is and the other 835 that's higher than it, so simply moving elements is not possible. 836 837 Params: 838 dest = destination node 839 destination_start = first index in the dest. node to copy to 840 source = source node 841 source_start = first index in the source node to copy from. 842 843 ***************************************************************************/ 844 845 private static void moveElementsAt (BTreeMapNode* dest, int destination_start, 846 BTreeMapNode* source, int source_start) 847 { 848 int end = source.number_of_elements; 849 verify(source.number_of_elements >= end - source_start); 850 851 auto old_number = dest.number_of_elements; 852 dest.number_of_elements += end - source_start; 853 854 // Move the elements from the source to this 855 foreach (i, ref el; dest.elements[old_number..dest.number_of_elements]) 856 { 857 el = source.elements[source_start + i]; 858 } 859 860 if (!dest.is_leaf) 861 { 862 // TODO: assert (!souce.is_leaf) 863 foreach (i, ref child_node; 864 dest.child_nodes[old_number..dest.number_of_elements+1]) 865 { 866 child_node = source.child_nodes[source_start + i]; 867 } 868 } 869 870 source.number_of_elements = source_start; 871 } 872 873 /*************************************************************************** 874 875 Removes the element from the node. This removes the element from the node 876 and reorganizes the subtrees. 877 878 Params: 879 node = node to remove from 880 position = position of the element to remove. 881 882 Returns: 883 the removed element. 884 885 ***************************************************************************/ 886 887 private static BTreeMapNode.KeyValue popFromNode (BTreeMapNode* node, size_t position) 888 { 889 auto element = node.elements[position]; 890 891 // rotate the next neighbour elements 892 for (auto i = position; i < node.number_of_elements-1; i++) 893 { 894 node.elements[i] = node.elements[i+1]; 895 } 896 897 if (!node.is_leaf) 898 { 899 for (auto i = position; i < node.number_of_elements; i++) 900 { 901 node.child_nodes[i] = node.child_nodes[i+1]; 902 } 903 } 904 905 node.number_of_elements--; 906 return element; 907 } 908 909 /****************************************************************************** 910 911 Finds the maxima in the subtree. 912 913 Params: 914 node = root of the (sub)tree 915 index = element index in the node. 916 917 Returns: 918 pointer to the node containing the maximum element 919 920 ******************************************************************************/ 921 922 private static BTreeMapNode* findMaximum (BTreeMapNode* node, 923 out size_t index) 924 { 925 if (node.is_leaf) 926 { 927 index = node.number_of_elements - 1; 928 return node; 929 } 930 else 931 { 932 return findMaximum(node.child_nodes[node.number_of_elements], index); 933 } 934 } 935 936 /****************************************************************************** 937 938 Visits the tree in the inorder order. 939 940 Params: 941 tree = tree to visit 942 dg = delegate to call for each visited element. Delegate should return 943 non-zero value if the visiting should be aborted. 944 945 Returns: 946 return value of the last dg call. 947 948 ******************************************************************************/ 949 950 package int inorder (scope int delegate(ref KeyType key, ref ValueType value) dg) 951 { 952 if (this.root is null) 953 { 954 return 0; 955 } 956 957 return inorderImpl(this.content_version, *this.root, dg); 958 } 959 960 /****************************************************************************** 961 962 Visits the tree in the inorder order. 963 964 Params: 965 tree = tree to visit 966 dg = delegate to call for each visited element. Delegate should return 967 non-zero value if the visiting should be aborted. 968 969 Returns: 970 return value of the last dg call. 971 972 ******************************************************************************/ 973 974 package int inorder (scope int delegate(ref ValueType value) dg) 975 { 976 if (this.root is null) 977 { 978 return 0; 979 } 980 981 return inorderImpl(this.content_version, *this.root, dg); 982 } 983 984 /*************************************************************************** 985 986 Traverses the BTreeMap in the inorder, starting from the root. 987 988 Params: 989 version = "version" of the tree at the time of starting the visit 990 root = root of a (sub)tree to visit 991 dg = delegate to call with the key/value 992 993 Returns: 994 return value of the delegate dg 995 996 ***************************************************************************/ 997 998 private int inorderImpl (UserDg)(ulong start_version, ref BTreeMapNode root, 999 UserDg dg) 1000 { 1001 for (int i = 0; i < root.number_of_elements; i++) 1002 { 1003 int res; 1004 if (!root.is_leaf) 1005 { 1006 res = inorderImpl(start_version, *root.child_nodes[i], dg); 1007 if (res) return res; 1008 } 1009 1010 static if ( 1011 is(ReturnTypeOf!(UserDg) == int) 1012 && is(ParametersOf!(UserDg) == Tuple!(ValueType))) 1013 { 1014 res = dg (root.elements[i].value); 1015 } 1016 else static if ( 1017 is(ReturnTypeOf!(UserDg) == int) 1018 && is(ParametersOf!(UserDg) == Tuple!(KeyType, ValueType))) 1019 { 1020 res = dg (root.elements[i].key, root.elements[i].value); 1021 } 1022 else 1023 { 1024 static assert(false); 1025 } 1026 1027 // check if the tree is valid 1028 if (start_version != this.content_version) return 1; 1029 1030 if (res) 1031 return res; 1032 } 1033 1034 if (!root.is_leaf) 1035 { 1036 auto res = inorderImpl(start_version, 1037 *root.child_nodes[root.number_of_elements], dg); 1038 if (res) 1039 return res; 1040 } 1041 1042 return 0; 1043 } 1044 } 1045 1046 /// Checks if all invariants of the tree are still valid 1047 debug (BTreeMapSanity) 1048 { 1049 /// Confirms if the invariants of btree stands: 1050 /// 1. All leaves have the same height - h 1051 /// 2. Every node other than the root must have at least degree - 1 1052 /// keys. If the tree is nonempty, the root must have at least one 1053 /// key. 1054 /// 3. Every node may contain at most 2degree - 1 keys - enforced through 1055 /// the array range exception 1056 /// 4. The root must have at least two keys if it's not a leaf. 1057 /// 5. The elements stored in a given subtree all have keys that are 1058 /// between the keys in the parent node on either side of the subtree 1059 /// pointer. 1060 1061 void check_invariants(BTreeMap)(ref BTreeMap tree) 1062 { 1063 verify(tree.root.is_leaf || tree.root.number_of_elements >= 1); 1064 1065 /// Traverses the BTreeMap in the inorder, starting from root, 1066 /// and returns the btree's node. 1067 static void traverse (BTreeMap.BTreeMapNode* root, ref int current_height, 1068 scope void delegate(BTreeMap.BTreeMapNode* b, int current_height) dg) 1069 { 1070 for (int i = 0; i < root.number_of_elements; i++) 1071 { 1072 if (!root.is_leaf) 1073 { 1074 current_height += 1; 1075 traverse(root.child_nodes[i], current_height, dg); 1076 current_height -= 1; 1077 } 1078 } 1079 1080 dg (root, current_height); 1081 } 1082 1083 int tree_height = -1; 1084 int current_height; 1085 1086 // traverse the tree and inspect other invariants 1087 traverse(tree.root, current_height, 1088 (BTreeMap.BTreeMapNode* node, int height) 1089 { 1090 if (node.is_leaf) 1091 { 1092 // all leaves must have the same level 1093 if (tree_height == -1) 1094 { 1095 tree_height = height; 1096 } 1097 verify(tree_height == height); 1098 } 1099 else 1100 { 1101 // every node must have at least degree - 1 keys 1102 if (node != tree.root) 1103 { 1104 verify(node.number_of_elements >= tree.degree - 1); 1105 } 1106 1107 // and if we get into each one of them, we will not find keys 1108 // equal or larger/smaller (depending on the side) of the keys 1109 for (int i = 0; i < node.number_of_elements; i++) 1110 { 1111 auto current_value = &node.elements[i]; 1112 1113 // let's traverse into each the left one and assert they are 1114 // all smaller 1115 int dummy; 1116 1117 traverse(node.child_nodes[i], dummy, (BTreeMap.BTreeMapNode* b, int height){ 1118 for (int j = 0; j < b.number_of_elements; j++) 1119 { 1120 verify(b.elements[j] < *current_value); 1121 } 1122 }); 1123 1124 // and traverse to the right subtree and inspect it 1125 traverse(node.child_nodes[i+1], dummy, (BTreeMap.BTreeMapNode* b, int height){ 1126 for (int j = 0; j < b.number_of_elements; j++) 1127 { 1128 verify(b.elements[j] > *current_value); 1129 } 1130 }); 1131 } 1132 } 1133 }); 1134 } 1135 } 1136 1137 unittest 1138 { 1139 foreach (allocator; [mallocMemManager, gcMemManager]) 1140 { 1141 testRandomTree(allocator); 1142 } 1143 } 1144 1145 version (unittest) 1146 { 1147 import ocean.util.container.mem.MemManager; 1148 import ocean.math.random.Random; 1149 import ocean.core.Test; 1150 import ocean.core.Tuple; 1151 1152 // Workaround for the D1 issue where we can't have the 1153 // delegate used in the static foreach 1154 private void testRandomTree(IMemManager allocator) 1155 { 1156 auto random = new Random(); 1157 bool found; 1158 1159 for (int count = 0; count < 5; count++) 1160 { 1161 auto random_tree = BTreeMapImplementation!(int, int, 3).init; 1162 random_tree.initialize(allocator); 1163 1164 int removed_count; 1165 int remaining_elements; 1166 int total_elements; 1167 int to_insert = 10_000; 1168 size_t my_index; 1169 1170 // create completely random tree and remove completely random values 1171 for (int i = 0; i < to_insert; i++) 1172 { 1173 int element = random.uniformR(to_insert); 1174 // don't count double elements (they are not inserted) 1175 bool added; 1176 random_tree.insert(element, element, added); 1177 total_elements += added? 1 : 0; 1178 auto res = random_tree.get(element, found); 1179 test(found); 1180 test!("==")(res, element); 1181 } 1182 1183 // reseed, so that the difference two random number generated sets 1184 // is not zero 1185 1186 for (int i = 0; i < to_insert; i++) 1187 { 1188 int element = random.uniformR(to_insert); 1189 removed_count += random_tree.remove(element)? 1 : 0; 1190 test(random_tree.get(element, found) == int.init && !found); 1191 } 1192 1193 int previous_value; 1194 bool started; 1195 1196 random_tree.inorder((ref int value) 1197 { 1198 if (!started) 1199 { 1200 previous_value = value; 1201 started = true; 1202 remaining_elements++; 1203 return 0; 1204 } 1205 1206 // enforce that the order is preserved 1207 test!(">")(value, previous_value); 1208 previous_value = value; 1209 remaining_elements++; 1210 return 0; 1211 }); 1212 1213 test!("==")(total_elements - remaining_elements, removed_count); 1214 1215 // Test the iterative version 1216 started = false; 1217 previous_value = previous_value.init; 1218 remaining_elements = 0; 1219 } 1220 } 1221 }