1341825Sdim//===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===// 2274958Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6274958Sdim// 7274958Sdim//===----------------------------------------------------------------------===// 8274958Sdim// 9274958Sdim// This file implements the DeltaTree and related classes. 10274958Sdim// 11274958Sdim//===----------------------------------------------------------------------===// 12274958Sdim 13274958Sdim#include "clang/Rewrite/Core/DeltaTree.h" 14274958Sdim#include "clang/Basic/LLVM.h" 15341825Sdim#include "llvm/Support/Casting.h" 16341825Sdim#include <cassert> 17274958Sdim#include <cstring> 18341825Sdim 19274958Sdimusing namespace clang; 20274958Sdim 21274958Sdim/// The DeltaTree class is a multiway search tree (BTree) structure with some 22274958Sdim/// fancy features. B-Trees are generally more memory and cache efficient 23274958Sdim/// than binary trees, because they store multiple keys/values in each node. 24274958Sdim/// 25274958Sdim/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing 26274958Sdim/// fast lookup by FileIndex. However, an added (important) bonus is that it 27274958Sdim/// can also efficiently tell us the full accumulated delta for a specific 28274958Sdim/// file offset as well, without traversing the whole tree. 29274958Sdim/// 30274958Sdim/// The nodes of the tree are made up of instances of two classes: 31274958Sdim/// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the 32274958Sdim/// former and adds children pointers. Each node knows the full delta of all 33274958Sdim/// entries (recursively) contained inside of it, which allows us to get the 34274958Sdim/// full delta implied by a whole subtree in constant time. 35274958Sdim 36274958Sdimnamespace { 37341825Sdim 38274958Sdim /// SourceDelta - As code in the original input buffer is added and deleted, 39274958Sdim /// SourceDelta records are used to keep track of how the input SourceLocation 40274958Sdim /// object is mapped into the output buffer. 41274958Sdim struct SourceDelta { 42274958Sdim unsigned FileLoc; 43274958Sdim int Delta; 44274958Sdim 45274958Sdim static SourceDelta get(unsigned Loc, int D) { 46274958Sdim SourceDelta Delta; 47274958Sdim Delta.FileLoc = Loc; 48274958Sdim Delta.Delta = D; 49274958Sdim return Delta; 50274958Sdim } 51274958Sdim }; 52341825Sdim 53274958Sdim /// DeltaTreeNode - The common part of all nodes. 54274958Sdim /// 55274958Sdim class DeltaTreeNode { 56274958Sdim public: 57274958Sdim struct InsertResult { 58274958Sdim DeltaTreeNode *LHS, *RHS; 59274958Sdim SourceDelta Split; 60274958Sdim }; 61341825Sdim 62274958Sdim private: 63274958Sdim friend class DeltaTreeInteriorNode; 64274958Sdim 65274958Sdim /// WidthFactor - This controls the number of K/V slots held in the BTree: 66274958Sdim /// how wide it is. Each level of the BTree is guaranteed to have at least 67274958Sdim /// WidthFactor-1 K/V pairs (except the root) and may have at most 68274958Sdim /// 2*WidthFactor-1 K/V pairs. 69274958Sdim enum { WidthFactor = 8 }; 70274958Sdim 71274958Sdim /// Values - This tracks the SourceDelta's currently in this node. 72274958Sdim SourceDelta Values[2*WidthFactor-1]; 73274958Sdim 74274958Sdim /// NumValuesUsed - This tracks the number of values this node currently 75274958Sdim /// holds. 76341825Sdim unsigned char NumValuesUsed = 0; 77274958Sdim 78274958Sdim /// IsLeaf - This is true if this is a leaf of the btree. If false, this is 79274958Sdim /// an interior node, and is actually an instance of DeltaTreeInteriorNode. 80274958Sdim bool IsLeaf; 81274958Sdim 82274958Sdim /// FullDelta - This is the full delta of all the values in this node and 83274958Sdim /// all children nodes. 84341825Sdim int FullDelta = 0; 85341825Sdim 86274958Sdim public: 87341825Sdim DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {} 88274958Sdim 89274958Sdim bool isLeaf() const { return IsLeaf; } 90274958Sdim int getFullDelta() const { return FullDelta; } 91274958Sdim bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; } 92274958Sdim 93274958Sdim unsigned getNumValuesUsed() const { return NumValuesUsed; } 94341825Sdim 95274958Sdim const SourceDelta &getValue(unsigned i) const { 96274958Sdim assert(i < NumValuesUsed && "Invalid value #"); 97274958Sdim return Values[i]; 98274958Sdim } 99341825Sdim 100274958Sdim SourceDelta &getValue(unsigned i) { 101274958Sdim assert(i < NumValuesUsed && "Invalid value #"); 102274958Sdim return Values[i]; 103274958Sdim } 104274958Sdim 105274958Sdim /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 106274958Sdim /// this node. If insertion is easy, do it and return false. Otherwise, 107274958Sdim /// split the node, populate InsertRes with info about the split, and return 108274958Sdim /// true. 109274958Sdim bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); 110274958Sdim 111274958Sdim void DoSplit(InsertResult &InsertRes); 112274958Sdim 113274958Sdim 114274958Sdim /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 115274958Sdim /// local walk over our contained deltas. 116274958Sdim void RecomputeFullDeltaLocally(); 117274958Sdim 118274958Sdim void Destroy(); 119274958Sdim }; 120274958Sdim 121274958Sdim /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. 122274958Sdim /// This class tracks them. 123274958Sdim class DeltaTreeInteriorNode : public DeltaTreeNode { 124341825Sdim friend class DeltaTreeNode; 125341825Sdim 126274958Sdim DeltaTreeNode *Children[2*WidthFactor]; 127341825Sdim 128274958Sdim ~DeltaTreeInteriorNode() { 129274958Sdim for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) 130274958Sdim Children[i]->Destroy(); 131274958Sdim } 132341825Sdim 133274958Sdim public: 134274958Sdim DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} 135274958Sdim 136274958Sdim DeltaTreeInteriorNode(const InsertResult &IR) 137341825Sdim : DeltaTreeNode(false /*nonleaf*/) { 138274958Sdim Children[0] = IR.LHS; 139274958Sdim Children[1] = IR.RHS; 140274958Sdim Values[0] = IR.Split; 141274958Sdim FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta; 142274958Sdim NumValuesUsed = 1; 143274958Sdim } 144274958Sdim 145274958Sdim const DeltaTreeNode *getChild(unsigned i) const { 146274958Sdim assert(i < getNumValuesUsed()+1 && "Invalid child"); 147274958Sdim return Children[i]; 148274958Sdim } 149341825Sdim 150274958Sdim DeltaTreeNode *getChild(unsigned i) { 151274958Sdim assert(i < getNumValuesUsed()+1 && "Invalid child"); 152274958Sdim return Children[i]; 153274958Sdim } 154274958Sdim 155341825Sdim static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } 156274958Sdim }; 157274958Sdim 158341825Sdim} // namespace 159274958Sdim 160274958Sdim/// Destroy - A 'virtual' destructor. 161274958Sdimvoid DeltaTreeNode::Destroy() { 162274958Sdim if (isLeaf()) 163274958Sdim delete this; 164274958Sdim else 165274958Sdim delete cast<DeltaTreeInteriorNode>(this); 166274958Sdim} 167274958Sdim 168274958Sdim/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 169274958Sdim/// local walk over our contained deltas. 170274958Sdimvoid DeltaTreeNode::RecomputeFullDeltaLocally() { 171274958Sdim int NewFullDelta = 0; 172274958Sdim for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) 173274958Sdim NewFullDelta += Values[i].Delta; 174341825Sdim if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) 175274958Sdim for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) 176274958Sdim NewFullDelta += IN->getChild(i)->getFullDelta(); 177274958Sdim FullDelta = NewFullDelta; 178274958Sdim} 179274958Sdim 180274958Sdim/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 181274958Sdim/// this node. If insertion is easy, do it and return false. Otherwise, 182274958Sdim/// split the node, populate InsertRes with info about the split, and return 183274958Sdim/// true. 184274958Sdimbool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, 185274958Sdim InsertResult *InsertRes) { 186274958Sdim // Maintain full delta for this node. 187274958Sdim FullDelta += Delta; 188274958Sdim 189274958Sdim // Find the insertion point, the first delta whose index is >= FileIndex. 190274958Sdim unsigned i = 0, e = getNumValuesUsed(); 191274958Sdim while (i != e && FileIndex > getValue(i).FileLoc) 192274958Sdim ++i; 193274958Sdim 194274958Sdim // If we found an a record for exactly this file index, just merge this 195274958Sdim // value into the pre-existing record and finish early. 196274958Sdim if (i != e && getValue(i).FileLoc == FileIndex) { 197274958Sdim // NOTE: Delta could drop to zero here. This means that the delta entry is 198274958Sdim // useless and could be removed. Supporting erases is more complex than 199274958Sdim // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in 200274958Sdim // the tree. 201274958Sdim Values[i].Delta += Delta; 202274958Sdim return false; 203274958Sdim } 204274958Sdim 205274958Sdim // Otherwise, we found an insertion point, and we know that the value at the 206274958Sdim // specified index is > FileIndex. Handle the leaf case first. 207274958Sdim if (isLeaf()) { 208274958Sdim if (!isFull()) { 209274958Sdim // For an insertion into a non-full leaf node, just insert the value in 210274958Sdim // its sorted position. This requires moving later values over. 211274958Sdim if (i != e) 212274958Sdim memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); 213274958Sdim Values[i] = SourceDelta::get(FileIndex, Delta); 214274958Sdim ++NumValuesUsed; 215274958Sdim return false; 216274958Sdim } 217274958Sdim 218274958Sdim // Otherwise, if this is leaf is full, split the node at its median, insert 219274958Sdim // the value into one of the children, and return the result. 220274958Sdim assert(InsertRes && "No result location specified"); 221274958Sdim DoSplit(*InsertRes); 222274958Sdim 223274958Sdim if (InsertRes->Split.FileLoc > FileIndex) 224274958Sdim InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 225274958Sdim else 226274958Sdim InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 227274958Sdim return true; 228274958Sdim } 229274958Sdim 230274958Sdim // Otherwise, this is an interior node. Send the request down the tree. 231341825Sdim auto *IN = cast<DeltaTreeInteriorNode>(this); 232274958Sdim if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) 233274958Sdim return false; // If there was space in the child, just return. 234274958Sdim 235274958Sdim // Okay, this split the subtree, producing a new value and two children to 236274958Sdim // insert here. If this node is non-full, we can just insert it directly. 237274958Sdim if (!isFull()) { 238274958Sdim // Now that we have two nodes and a new element, insert the perclated value 239274958Sdim // into ourself by moving all the later values/children down, then inserting 240274958Sdim // the new one. 241274958Sdim if (i != e) 242274958Sdim memmove(&IN->Children[i+2], &IN->Children[i+1], 243274958Sdim (e-i)*sizeof(IN->Children[0])); 244274958Sdim IN->Children[i] = InsertRes->LHS; 245274958Sdim IN->Children[i+1] = InsertRes->RHS; 246274958Sdim 247274958Sdim if (e != i) 248274958Sdim memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0])); 249274958Sdim Values[i] = InsertRes->Split; 250274958Sdim ++NumValuesUsed; 251274958Sdim return false; 252274958Sdim } 253274958Sdim 254274958Sdim // Finally, if this interior node was full and a node is percolated up, split 255274958Sdim // ourself and return that up the chain. Start by saving all our info to 256274958Sdim // avoid having the split clobber it. 257274958Sdim IN->Children[i] = InsertRes->LHS; 258274958Sdim DeltaTreeNode *SubRHS = InsertRes->RHS; 259274958Sdim SourceDelta SubSplit = InsertRes->Split; 260274958Sdim 261274958Sdim // Do the split. 262274958Sdim DoSplit(*InsertRes); 263274958Sdim 264274958Sdim // Figure out where to insert SubRHS/NewSplit. 265274958Sdim DeltaTreeInteriorNode *InsertSide; 266274958Sdim if (SubSplit.FileLoc < InsertRes->Split.FileLoc) 267274958Sdim InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS); 268274958Sdim else 269274958Sdim InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS); 270274958Sdim 271274958Sdim // We now have a non-empty interior node 'InsertSide' to insert 272274958Sdim // SubRHS/SubSplit into. Find out where to insert SubSplit. 273274958Sdim 274274958Sdim // Find the insertion point, the first delta whose index is >SubSplit.FileLoc. 275274958Sdim i = 0; e = InsertSide->getNumValuesUsed(); 276274958Sdim while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) 277274958Sdim ++i; 278274958Sdim 279274958Sdim // Now we know that i is the place to insert the split value into. Insert it 280274958Sdim // and the child right after it. 281274958Sdim if (i != e) 282274958Sdim memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1], 283274958Sdim (e-i)*sizeof(IN->Children[0])); 284274958Sdim InsertSide->Children[i+1] = SubRHS; 285274958Sdim 286274958Sdim if (e != i) 287274958Sdim memmove(&InsertSide->Values[i+1], &InsertSide->Values[i], 288274958Sdim (e-i)*sizeof(Values[0])); 289274958Sdim InsertSide->Values[i] = SubSplit; 290274958Sdim ++InsertSide->NumValuesUsed; 291274958Sdim InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta(); 292274958Sdim return true; 293274958Sdim} 294274958Sdim 295274958Sdim/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values) 296274958Sdim/// into two subtrees each with "WidthFactor-1" values and a pivot value. 297274958Sdim/// Return the pieces in InsertRes. 298274958Sdimvoid DeltaTreeNode::DoSplit(InsertResult &InsertRes) { 299274958Sdim assert(isFull() && "Why split a non-full node?"); 300274958Sdim 301274958Sdim // Since this node is full, it contains 2*WidthFactor-1 values. We move 302274958Sdim // the first 'WidthFactor-1' values to the LHS child (which we leave in this 303274958Sdim // node), propagate one value up, and move the last 'WidthFactor-1' values 304274958Sdim // into the RHS child. 305274958Sdim 306274958Sdim // Create the new child node. 307274958Sdim DeltaTreeNode *NewNode; 308341825Sdim if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 309274958Sdim // If this is an interior node, also move over 'WidthFactor' children 310274958Sdim // into the new node. 311274958Sdim DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); 312274958Sdim memcpy(&New->Children[0], &IN->Children[WidthFactor], 313274958Sdim WidthFactor*sizeof(IN->Children[0])); 314274958Sdim NewNode = New; 315274958Sdim } else { 316274958Sdim // Just create the new leaf node. 317274958Sdim NewNode = new DeltaTreeNode(); 318274958Sdim } 319274958Sdim 320274958Sdim // Move over the last 'WidthFactor-1' values from here to NewNode. 321274958Sdim memcpy(&NewNode->Values[0], &Values[WidthFactor], 322274958Sdim (WidthFactor-1)*sizeof(Values[0])); 323274958Sdim 324274958Sdim // Decrease the number of values in the two nodes. 325274958Sdim NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; 326274958Sdim 327274958Sdim // Recompute the two nodes' full delta. 328274958Sdim NewNode->RecomputeFullDeltaLocally(); 329274958Sdim RecomputeFullDeltaLocally(); 330274958Sdim 331274958Sdim InsertRes.LHS = this; 332274958Sdim InsertRes.RHS = NewNode; 333274958Sdim InsertRes.Split = Values[WidthFactor-1]; 334274958Sdim} 335274958Sdim 336274958Sdim//===----------------------------------------------------------------------===// 337274958Sdim// DeltaTree Implementation 338274958Sdim//===----------------------------------------------------------------------===// 339274958Sdim 340274958Sdim//#define VERIFY_TREE 341274958Sdim 342274958Sdim#ifdef VERIFY_TREE 343274958Sdim/// VerifyTree - Walk the btree performing assertions on various properties to 344274958Sdim/// verify consistency. This is useful for debugging new changes to the tree. 345274958Sdimstatic void VerifyTree(const DeltaTreeNode *N) { 346341825Sdim const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N); 347274958Sdim if (IN == 0) { 348274958Sdim // Verify leaves, just ensure that FullDelta matches up and the elements 349274958Sdim // are in proper order. 350274958Sdim int FullDelta = 0; 351274958Sdim for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { 352274958Sdim if (i) 353274958Sdim assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); 354274958Sdim FullDelta += N->getValue(i).Delta; 355274958Sdim } 356274958Sdim assert(FullDelta == N->getFullDelta()); 357274958Sdim return; 358274958Sdim } 359274958Sdim 360274958Sdim // Verify interior nodes: Ensure that FullDelta matches up and the 361274958Sdim // elements are in proper order and the children are in proper order. 362274958Sdim int FullDelta = 0; 363274958Sdim for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { 364274958Sdim const SourceDelta &IVal = N->getValue(i); 365274958Sdim const DeltaTreeNode *IChild = IN->getChild(i); 366274958Sdim if (i) 367274958Sdim assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); 368274958Sdim FullDelta += IVal.Delta; 369274958Sdim FullDelta += IChild->getFullDelta(); 370274958Sdim 371274958Sdim // The largest value in child #i should be smaller than FileLoc. 372274958Sdim assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < 373274958Sdim IVal.FileLoc); 374274958Sdim 375274958Sdim // The smallest value in child #i+1 should be larger than FileLoc. 376274958Sdim assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); 377274958Sdim VerifyTree(IChild); 378274958Sdim } 379274958Sdim 380274958Sdim FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); 381274958Sdim 382274958Sdim assert(FullDelta == N->getFullDelta()); 383274958Sdim} 384274958Sdim#endif // VERIFY_TREE 385274958Sdim 386274958Sdimstatic DeltaTreeNode *getRoot(void *Root) { 387274958Sdim return (DeltaTreeNode*)Root; 388274958Sdim} 389274958Sdim 390274958SdimDeltaTree::DeltaTree() { 391274958Sdim Root = new DeltaTreeNode(); 392274958Sdim} 393341825Sdim 394274958SdimDeltaTree::DeltaTree(const DeltaTree &RHS) { 395274958Sdim // Currently we only support copying when the RHS is empty. 396274958Sdim assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && 397274958Sdim "Can only copy empty tree"); 398274958Sdim Root = new DeltaTreeNode(); 399274958Sdim} 400274958Sdim 401274958SdimDeltaTree::~DeltaTree() { 402274958Sdim getRoot(Root)->Destroy(); 403274958Sdim} 404274958Sdim 405274958Sdim/// getDeltaAt - Return the accumulated delta at the specified file offset. 406274958Sdim/// This includes all insertions or delections that occurred *before* the 407274958Sdim/// specified file index. 408274958Sdimint DeltaTree::getDeltaAt(unsigned FileIndex) const { 409274958Sdim const DeltaTreeNode *Node = getRoot(Root); 410274958Sdim 411274958Sdim int Result = 0; 412274958Sdim 413274958Sdim // Walk down the tree. 414341825Sdim while (true) { 415274958Sdim // For all nodes, include any local deltas before the specified file 416274958Sdim // index by summing them up directly. Keep track of how many were 417274958Sdim // included. 418274958Sdim unsigned NumValsGreater = 0; 419274958Sdim for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; 420274958Sdim ++NumValsGreater) { 421274958Sdim const SourceDelta &Val = Node->getValue(NumValsGreater); 422274958Sdim 423274958Sdim if (Val.FileLoc >= FileIndex) 424274958Sdim break; 425274958Sdim Result += Val.Delta; 426274958Sdim } 427274958Sdim 428274958Sdim // If we have an interior node, include information about children and 429274958Sdim // recurse. Otherwise, if we have a leaf, we're done. 430341825Sdim const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node); 431274958Sdim if (!IN) return Result; 432274958Sdim 433274958Sdim // Include any children to the left of the values we skipped, all of 434274958Sdim // their deltas should be included as well. 435274958Sdim for (unsigned i = 0; i != NumValsGreater; ++i) 436274958Sdim Result += IN->getChild(i)->getFullDelta(); 437274958Sdim 438274958Sdim // If we found exactly the value we were looking for, break off the 439274958Sdim // search early. There is no need to search the RHS of the value for 440274958Sdim // partial results. 441274958Sdim if (NumValsGreater != Node->getNumValuesUsed() && 442274958Sdim Node->getValue(NumValsGreater).FileLoc == FileIndex) 443274958Sdim return Result+IN->getChild(NumValsGreater)->getFullDelta(); 444274958Sdim 445274958Sdim // Otherwise, traverse down the tree. The selected subtree may be 446274958Sdim // partially included in the range. 447274958Sdim Node = IN->getChild(NumValsGreater); 448274958Sdim } 449274958Sdim // NOT REACHED. 450274958Sdim} 451274958Sdim 452274958Sdim/// AddDelta - When a change is made that shifts around the text buffer, 453274958Sdim/// this method is used to record that info. It inserts a delta of 'Delta' 454274958Sdim/// into the current DeltaTree at offset FileIndex. 455274958Sdimvoid DeltaTree::AddDelta(unsigned FileIndex, int Delta) { 456274958Sdim assert(Delta && "Adding a noop?"); 457274958Sdim DeltaTreeNode *MyRoot = getRoot(Root); 458274958Sdim 459274958Sdim DeltaTreeNode::InsertResult InsertRes; 460274958Sdim if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { 461274958Sdim Root = MyRoot = new DeltaTreeInteriorNode(InsertRes); 462274958Sdim } 463274958Sdim 464274958Sdim#ifdef VERIFY_TREE 465274958Sdim VerifyTree(MyRoot); 466274958Sdim#endif 467274958Sdim} 468