1 //===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the DeltaTree and related classes.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Rewrite/Core/DeltaTree.h"
15 #include "clang/Basic/LLVM.h"
18 using namespace clang;
20 /// The DeltaTree class is a multiway search tree (BTree) structure with some
21 /// fancy features. B-Trees are generally more memory and cache efficient
22 /// than binary trees, because they store multiple keys/values in each node.
24 /// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
25 /// fast lookup by FileIndex. However, an added (important) bonus is that it
26 /// can also efficiently tell us the full accumulated delta for a specific
27 /// file offset as well, without traversing the whole tree.
29 /// The nodes of the tree are made up of instances of two classes:
30 /// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the
31 /// former and adds children pointers. Each node knows the full delta of all
32 /// entries (recursively) contained inside of it, which allows us to get the
33 /// full delta implied by a whole subtree in constant time.
36 /// SourceDelta - As code in the original input buffer is added and deleted,
37 /// SourceDelta records are used to keep track of how the input SourceLocation
38 /// object is mapped into the output buffer.
43 static SourceDelta get(unsigned Loc, int D) {
51 /// DeltaTreeNode - The common part of all nodes.
56 DeltaTreeNode *LHS, *RHS;
61 friend class DeltaTreeInteriorNode;
63 /// WidthFactor - This controls the number of K/V slots held in the BTree:
64 /// how wide it is. Each level of the BTree is guaranteed to have at least
65 /// WidthFactor-1 K/V pairs (except the root) and may have at most
66 /// 2*WidthFactor-1 K/V pairs.
67 enum { WidthFactor = 8 };
69 /// Values - This tracks the SourceDelta's currently in this node.
71 SourceDelta Values[2*WidthFactor-1];
73 /// NumValuesUsed - This tracks the number of values this node currently
75 unsigned char NumValuesUsed;
77 /// IsLeaf - This is true if this is a leaf of the btree. If false, this is
78 /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
81 /// FullDelta - This is the full delta of all the values in this node and
82 /// all children nodes.
85 DeltaTreeNode(bool isLeaf = true)
86 : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {}
88 bool isLeaf() const { return IsLeaf; }
89 int getFullDelta() const { return FullDelta; }
90 bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
92 unsigned getNumValuesUsed() const { return NumValuesUsed; }
93 const SourceDelta &getValue(unsigned i) const {
94 assert(i < NumValuesUsed && "Invalid value #");
97 SourceDelta &getValue(unsigned i) {
98 assert(i < NumValuesUsed && "Invalid value #");
102 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
103 /// this node. If insertion is easy, do it and return false. Otherwise,
104 /// split the node, populate InsertRes with info about the split, and return
106 bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
108 void DoSplit(InsertResult &InsertRes);
111 /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
112 /// local walk over our contained deltas.
113 void RecomputeFullDeltaLocally();
117 } // end anonymous namespace
120 /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
121 /// This class tracks them.
122 class DeltaTreeInteriorNode : public DeltaTreeNode {
123 DeltaTreeNode *Children[2*WidthFactor];
124 ~DeltaTreeInteriorNode() {
125 for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
126 Children[i]->Destroy();
128 friend class DeltaTreeNode;
130 DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
132 DeltaTreeInteriorNode(const InsertResult &IR)
133 : DeltaTreeNode(false /*nonleaf*/) {
134 Children[0] = IR.LHS;
135 Children[1] = IR.RHS;
136 Values[0] = IR.Split;
137 FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
141 const DeltaTreeNode *getChild(unsigned i) const {
142 assert(i < getNumValuesUsed()+1 && "Invalid child");
145 DeltaTreeNode *getChild(unsigned i) {
146 assert(i < getNumValuesUsed()+1 && "Invalid child");
150 static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
155 /// Destroy - A 'virtual' destructor.
156 void DeltaTreeNode::Destroy() {
160 delete cast<DeltaTreeInteriorNode>(this);
163 /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
164 /// local walk over our contained deltas.
165 void DeltaTreeNode::RecomputeFullDeltaLocally() {
166 int NewFullDelta = 0;
167 for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
168 NewFullDelta += Values[i].Delta;
169 if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this))
170 for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
171 NewFullDelta += IN->getChild(i)->getFullDelta();
172 FullDelta = NewFullDelta;
175 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
176 /// this node. If insertion is easy, do it and return false. Otherwise,
177 /// split the node, populate InsertRes with info about the split, and return
179 bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
180 InsertResult *InsertRes) {
181 // Maintain full delta for this node.
184 // Find the insertion point, the first delta whose index is >= FileIndex.
185 unsigned i = 0, e = getNumValuesUsed();
186 while (i != e && FileIndex > getValue(i).FileLoc)
189 // If we found an a record for exactly this file index, just merge this
190 // value into the pre-existing record and finish early.
191 if (i != e && getValue(i).FileLoc == FileIndex) {
192 // NOTE: Delta could drop to zero here. This means that the delta entry is
193 // useless and could be removed. Supporting erases is more complex than
194 // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
196 Values[i].Delta += Delta;
200 // Otherwise, we found an insertion point, and we know that the value at the
201 // specified index is > FileIndex. Handle the leaf case first.
204 // For an insertion into a non-full leaf node, just insert the value in
205 // its sorted position. This requires moving later values over.
207 memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
208 Values[i] = SourceDelta::get(FileIndex, Delta);
213 // Otherwise, if this is leaf is full, split the node at its median, insert
214 // the value into one of the children, and return the result.
215 assert(InsertRes && "No result location specified");
218 if (InsertRes->Split.FileLoc > FileIndex)
219 InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
221 InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
225 // Otherwise, this is an interior node. Send the request down the tree.
226 DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
227 if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
228 return false; // If there was space in the child, just return.
230 // Okay, this split the subtree, producing a new value and two children to
231 // insert here. If this node is non-full, we can just insert it directly.
233 // Now that we have two nodes and a new element, insert the perclated value
234 // into ourself by moving all the later values/children down, then inserting
237 memmove(&IN->Children[i+2], &IN->Children[i+1],
238 (e-i)*sizeof(IN->Children[0]));
239 IN->Children[i] = InsertRes->LHS;
240 IN->Children[i+1] = InsertRes->RHS;
243 memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
244 Values[i] = InsertRes->Split;
249 // Finally, if this interior node was full and a node is percolated up, split
250 // ourself and return that up the chain. Start by saving all our info to
251 // avoid having the split clobber it.
252 IN->Children[i] = InsertRes->LHS;
253 DeltaTreeNode *SubRHS = InsertRes->RHS;
254 SourceDelta SubSplit = InsertRes->Split;
259 // Figure out where to insert SubRHS/NewSplit.
260 DeltaTreeInteriorNode *InsertSide;
261 if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
262 InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
264 InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
266 // We now have a non-empty interior node 'InsertSide' to insert
267 // SubRHS/SubSplit into. Find out where to insert SubSplit.
269 // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
270 i = 0; e = InsertSide->getNumValuesUsed();
271 while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
274 // Now we know that i is the place to insert the split value into. Insert it
275 // and the child right after it.
277 memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
278 (e-i)*sizeof(IN->Children[0]));
279 InsertSide->Children[i+1] = SubRHS;
282 memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
283 (e-i)*sizeof(Values[0]));
284 InsertSide->Values[i] = SubSplit;
285 ++InsertSide->NumValuesUsed;
286 InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
290 /// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
291 /// into two subtrees each with "WidthFactor-1" values and a pivot value.
292 /// Return the pieces in InsertRes.
293 void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
294 assert(isFull() && "Why split a non-full node?");
296 // Since this node is full, it contains 2*WidthFactor-1 values. We move
297 // the first 'WidthFactor-1' values to the LHS child (which we leave in this
298 // node), propagate one value up, and move the last 'WidthFactor-1' values
299 // into the RHS child.
301 // Create the new child node.
302 DeltaTreeNode *NewNode;
303 if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
304 // If this is an interior node, also move over 'WidthFactor' children
305 // into the new node.
306 DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
307 memcpy(&New->Children[0], &IN->Children[WidthFactor],
308 WidthFactor*sizeof(IN->Children[0]));
311 // Just create the new leaf node.
312 NewNode = new DeltaTreeNode();
315 // Move over the last 'WidthFactor-1' values from here to NewNode.
316 memcpy(&NewNode->Values[0], &Values[WidthFactor],
317 (WidthFactor-1)*sizeof(Values[0]));
319 // Decrease the number of values in the two nodes.
320 NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
322 // Recompute the two nodes' full delta.
323 NewNode->RecomputeFullDeltaLocally();
324 RecomputeFullDeltaLocally();
326 InsertRes.LHS = this;
327 InsertRes.RHS = NewNode;
328 InsertRes.Split = Values[WidthFactor-1];
333 //===----------------------------------------------------------------------===//
334 // DeltaTree Implementation
335 //===----------------------------------------------------------------------===//
337 //#define VERIFY_TREE
340 /// VerifyTree - Walk the btree performing assertions on various properties to
341 /// verify consistency. This is useful for debugging new changes to the tree.
342 static void VerifyTree(const DeltaTreeNode *N) {
343 const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N);
345 // Verify leaves, just ensure that FullDelta matches up and the elements
346 // are in proper order.
348 for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
350 assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
351 FullDelta += N->getValue(i).Delta;
353 assert(FullDelta == N->getFullDelta());
357 // Verify interior nodes: Ensure that FullDelta matches up and the
358 // elements are in proper order and the children are in proper order.
360 for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
361 const SourceDelta &IVal = N->getValue(i);
362 const DeltaTreeNode *IChild = IN->getChild(i);
364 assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
365 FullDelta += IVal.Delta;
366 FullDelta += IChild->getFullDelta();
368 // The largest value in child #i should be smaller than FileLoc.
369 assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
372 // The smallest value in child #i+1 should be larger than FileLoc.
373 assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
377 FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
379 assert(FullDelta == N->getFullDelta());
381 #endif // VERIFY_TREE
383 static DeltaTreeNode *getRoot(void *Root) {
384 return (DeltaTreeNode*)Root;
387 DeltaTree::DeltaTree() {
388 Root = new DeltaTreeNode();
390 DeltaTree::DeltaTree(const DeltaTree &RHS) {
391 // Currently we only support copying when the RHS is empty.
392 assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
393 "Can only copy empty tree");
394 Root = new DeltaTreeNode();
397 DeltaTree::~DeltaTree() {
398 getRoot(Root)->Destroy();
401 /// getDeltaAt - Return the accumulated delta at the specified file offset.
402 /// This includes all insertions or delections that occurred *before* the
403 /// specified file index.
404 int DeltaTree::getDeltaAt(unsigned FileIndex) const {
405 const DeltaTreeNode *Node = getRoot(Root);
409 // Walk down the tree.
411 // For all nodes, include any local deltas before the specified file
412 // index by summing them up directly. Keep track of how many were
414 unsigned NumValsGreater = 0;
415 for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
417 const SourceDelta &Val = Node->getValue(NumValsGreater);
419 if (Val.FileLoc >= FileIndex)
424 // If we have an interior node, include information about children and
425 // recurse. Otherwise, if we have a leaf, we're done.
426 const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
427 if (!IN) return Result;
429 // Include any children to the left of the values we skipped, all of
430 // their deltas should be included as well.
431 for (unsigned i = 0; i != NumValsGreater; ++i)
432 Result += IN->getChild(i)->getFullDelta();
434 // If we found exactly the value we were looking for, break off the
435 // search early. There is no need to search the RHS of the value for
437 if (NumValsGreater != Node->getNumValuesUsed() &&
438 Node->getValue(NumValsGreater).FileLoc == FileIndex)
439 return Result+IN->getChild(NumValsGreater)->getFullDelta();
441 // Otherwise, traverse down the tree. The selected subtree may be
442 // partially included in the range.
443 Node = IN->getChild(NumValsGreater);
448 /// AddDelta - When a change is made that shifts around the text buffer,
449 /// this method is used to record that info. It inserts a delta of 'Delta'
450 /// into the current DeltaTree at offset FileIndex.
451 void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
452 assert(Delta && "Adding a noop?");
453 DeltaTreeNode *MyRoot = getRoot(Root);
455 DeltaTreeNode::InsertResult InsertRes;
456 if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
457 Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);