 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
67.0% |
59 / 88 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
79.5% |
70 / 88 |
| |
|
Line Coverage: |
81.6% |
124 / 152 |
| |
 |
|
 |
1 : //===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the DeltaTree and related classes.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Rewrite/DeltaTree.h"
15 : #include "llvm/Support/Casting.h"
16 : #include <cstring>
17 : #include <cstdio>
18 : using namespace clang;
19 : using llvm::cast;
20 : using llvm::dyn_cast;
21 :
22 : /// The DeltaTree class is a multiway search tree (BTree) structure with some
23 : /// fancy features. B-Trees are generally more memory and cache efficient
24 : /// than binary trees, because they store multiple keys/values in each node.
25 : ///
26 : /// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
27 : /// fast lookup by FileIndex. However, an added (important) bonus is that it
28 : /// can also efficiently tell us the full accumulated delta for a specific
29 : /// file offset as well, without traversing the whole tree.
30 : ///
31 : /// The nodes of the tree are made up of instances of two classes:
32 : /// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the
33 : /// former and adds children pointers. Each node knows the full delta of all
34 : /// entries (recursively) contained inside of it, which allows us to get the
35 : /// full delta implied by a whole subtree in constant time.
36 :
37 : namespace {
38 : /// SourceDelta - As code in the original input buffer is added and deleted,
39 : /// SourceDelta records are used to keep track of how the input SourceLocation
40 : /// object is mapped into the output buffer.
41 : struct SourceDelta {
42 : unsigned FileLoc;
43 : int Delta;
44 :
45 984: static SourceDelta get(unsigned Loc, int D) {
46 : SourceDelta Delta;
47 984: Delta.FileLoc = Loc;
48 984: Delta.Delta = D;
49 : return Delta;
50 : }
51 : };
52 :
53 : /// DeltaTreeNode - The common part of all nodes.
54 : ///
55 : class DeltaTreeNode {
56 : public:
57 : struct InsertResult {
58 : DeltaTreeNode *LHS, *RHS;
59 : SourceDelta Split;
60 : };
61 :
62 : private:
63 : friend class DeltaTreeInteriorNode;
64 :
65 : /// WidthFactor - This controls the number of K/V slots held in the BTree:
66 : /// how wide it is. Each level of the BTree is guaranteed to have at least
67 : /// WidthFactor-1 K/V pairs (except the root) and may have at most
68 : /// 2*WidthFactor-1 K/V pairs.
69 : enum { WidthFactor = 8 };
70 :
71 : /// Values - This tracks the SourceDelta's currently in this node.
72 : ///
73 : SourceDelta Values[2*WidthFactor-1];
74 :
75 : /// NumValuesUsed - This tracks the number of values this node currently
76 : /// holds.
77 : unsigned char NumValuesUsed;
78 :
79 : /// IsLeaf - This is true if this is a leaf of the btree. If false, this is
80 : /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
81 : bool IsLeaf;
82 :
83 : /// FullDelta - This is the full delta of all the values in this node and
84 : /// all children nodes.
85 : int FullDelta;
86 : public:
87 336: DeltaTreeNode(bool isLeaf = true)
88 336: : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {}
89 :
90 4691: bool isLeaf() const { return IsLeaf; }
91 553: int getFullDelta() const { return FullDelta; }
92 1088: bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
93 :
94 5254: unsigned getNumValuesUsed() const { return NumValuesUsed; }
95 11289: const SourceDelta &getValue(unsigned i) const {
0: branch 0 not taken
11289: branch 1 taken
96 11289: assert(i < NumValuesUsed && "Invalid value #");
97 11289: return Values[i];
98 : }
99 8216: SourceDelta &getValue(unsigned i) {
0: branch 0 not taken
8216: branch 1 taken
100 8216: assert(i < NumValuesUsed && "Invalid value #");
101 8216: return Values[i];
102 : }
103 :
104 : /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
105 : /// this node. If insertion is easy, do it and return false. Otherwise,
106 : /// split the node, populate InsertRes with info about the split, and return
107 : /// true.
108 : bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
109 :
110 : void DoSplit(InsertResult &InsertRes);
111 :
112 :
113 : /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
114 : /// local walk over our contained deltas.
115 : void RecomputeFullDeltaLocally();
116 :
117 : void Destroy();
118 :
119 : static inline bool classof(const DeltaTreeNode *) { return true; }
120 : };
121 : } // end anonymous namespace
122 :
123 : namespace {
124 : /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers.
125 : /// This class tracks them.
126 : class DeltaTreeInteriorNode : public DeltaTreeNode {
127 : DeltaTreeNode *Children[2*WidthFactor];
128 25: ~DeltaTreeInteriorNode() {
68: branch 0 taken
25: branch 1 taken
129 93: for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i)
130 68: Children[i]->Destroy();
131 25: }
132 : friend class DeltaTreeNode;
133 : public:
134 0: DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
135 :
136 : DeltaTreeInteriorNode(DeltaTreeNode *FirstChild)
137 : : DeltaTreeNode(false /*nonleaf*/) {
138 : FullDelta = FirstChild->FullDelta;
139 : Children[0] = FirstChild;
140 : }
141 :
142 25: DeltaTreeInteriorNode(const InsertResult &IR)
143 25: : DeltaTreeNode(false /*nonleaf*/) {
144 25: Children[0] = IR.LHS;
145 25: Children[1] = IR.RHS;
146 25: Values[0] = IR.Split;
147 25: FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
148 25: NumValuesUsed = 1;
149 25: }
150 :
151 932: const DeltaTreeNode *getChild(unsigned i) const {
932: branch 1 taken
0: branch 2 not taken
152 932: assert(i < getNumValuesUsed()+1 && "Invalid child");
153 932: return Children[i];
154 : }
155 0: DeltaTreeNode *getChild(unsigned i) {
0: branch 1 not taken
0: branch 2 not taken
156 0: assert(i < getNumValuesUsed()+1 && "Invalid child");
157 0: return Children[i];
158 : }
159 :
160 : static inline bool classof(const DeltaTreeInteriorNode *) { return true; }
161 2989: static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
162 : };
163 : }
164 :
165 :
166 : /// Destroy - A 'virtual' destructor.
167 336: void DeltaTreeNode::Destroy() {
311: branch 1 taken
25: branch 2 taken
168 336: if (isLeaf())
169 311: delete this;
170 : else
25: branch 1 taken
0: branch 2 not taken
171 25: delete cast<DeltaTreeInteriorNode>(this);
172 336: }
173 :
174 : /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
175 : /// local walk over our contained deltas.
176 86: void DeltaTreeNode::RecomputeFullDeltaLocally() {
177 86: int NewFullDelta = 0;
602: branch 1 taken
86: branch 2 taken
178 688: for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i)
179 602: NewFullDelta += Values[i].Delta;
0: branch 1 not taken
86: branch 2 taken
180 86: if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this))
0: branch 1 not taken
0: branch 2 not taken
181 0: for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i)
182 0: NewFullDelta += IN->getChild(i)->getFullDelta();
183 86: FullDelta = NewFullDelta;
184 86: }
185 :
186 : /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
187 : /// this node. If insertion is easy, do it and return false. Otherwise,
188 : /// split the node, populate InsertRes with info about the split, and return
189 : /// true.
190 : bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
191 1539: InsertResult *InsertRes) {
192 : // Maintain full delta for this node.
193 1539: FullDelta += Delta;
194 :
195 : // Find the insertion point, the first delta whose index is >= FileIndex.
196 1539: unsigned i = 0, e = getNumValuesUsed();
7627: branch 0 taken
950: branch 1 taken
7038: branch 3 taken
589: branch 4 taken
7038: branch 5 taken
1539: branch 6 taken
197 10116: while (i != e && FileIndex > getValue(i).FileLoc)
198 7038: ++i;
199 :
200 : // If we found an a record for exactly this file index, just merge this
201 : // value into the pre-existing record and finish early.
589: branch 0 taken
950: branch 1 taken
173: branch 3 taken
416: branch 4 taken
173: branch 5 taken
1366: branch 6 taken
202 1539: if (i != e && getValue(i).FileLoc == FileIndex) {
203 : // NOTE: Delta could drop to zero here. This means that the delta entry is
204 : // useless and could be removed. Supporting erases is more complex than
205 : // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in
206 : // the tree.
207 173: Values[i].Delta += Delta;
208 173: return false;
209 : }
210 :
211 : // Otherwise, we found an insertion point, and we know that the value at the
212 : // specified index is > FileIndex. Handle the leaf case first.
1027: branch 1 taken
339: branch 2 taken
213 1366: if (isLeaf()) {
984: branch 1 taken
43: branch 2 taken
214 1027: if (!isFull()) {
215 : // For an insertion into a non-full leaf node, just insert the value in
216 : // its sorted position. This requires moving later values over.
276: branch 0 taken
708: branch 1 taken
217 984: if (i != e)
218 276: memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i));
219 984: Values[i] = SourceDelta::get(FileIndex, Delta);
220 984: ++NumValuesUsed;
221 984: return false;
222 : }
223 :
224 : // Otherwise, if this is leaf is full, split the node at its median, insert
225 : // the value into one of the children, and return the result.
0: branch 0 not taken
43: branch 1 taken
226 43: assert(InsertRes && "No result location specified");
227 43: DoSplit(*InsertRes);
228 :
7: branch 0 taken
36: branch 1 taken
229 43: if (InsertRes->Split.FileLoc > FileIndex)
230 7: InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
231 : else
232 36: InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
233 43: return true;
234 : }
235 :
236 : // Otherwise, this is an interior node. Send the request down the tree.
237 339: DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
321: branch 1 taken
18: branch 2 taken
238 339: if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
239 321: return false; // If there was space in the child, just return.
240 :
241 : // Okay, this split the subtree, producing a new value and two children to
242 : // insert here. If this node is non-full, we can just insert it directly.
18: branch 1 taken
0: branch 2 not taken
243 18: if (!isFull()) {
244 : // Now that we have two nodes and a new element, insert the perclated value
245 : // into ourself by moving all the later values/children down, then inserting
246 : // the new one.
4: branch 0 taken
14: branch 1 taken
247 18: if (i != e)
248 : memmove(&IN->Children[i+2], &IN->Children[i+1],
249 4: (e-i)*sizeof(IN->Children[0]));
250 18: IN->Children[i] = InsertRes->LHS;
251 18: IN->Children[i+1] = InsertRes->RHS;
252 :
4: branch 0 taken
14: branch 1 taken
253 18: if (e != i)
254 4: memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
255 18: Values[i] = InsertRes->Split;
256 18: ++NumValuesUsed;
257 18: return false;
258 : }
259 :
260 : // Finally, if this interior node was full and a node is percolated up, split
261 : // ourself and return that up the chain. Start by saving all our info to
262 : // avoid having the split clobber it.
263 0: IN->Children[i] = InsertRes->LHS;
264 0: DeltaTreeNode *SubRHS = InsertRes->RHS;
265 0: SourceDelta SubSplit = InsertRes->Split;
266 :
267 : // Do the split.
268 0: DoSplit(*InsertRes);
269 :
270 : // Figure out where to insert SubRHS/NewSplit.
271 : DeltaTreeInteriorNode *InsertSide;
0: branch 0 not taken
0: branch 1 not taken
272 0: if (SubSplit.FileLoc < InsertRes->Split.FileLoc)
273 0: InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
274 : else
275 0: InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
276 :
277 : // We now have a non-empty interior node 'InsertSide' to insert
278 : // SubRHS/SubSplit into. Find out where to insert SubSplit.
279 :
280 : // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
281 0: i = 0; e = InsertSide->getNumValuesUsed();
0: branch 0 not taken
0: branch 1 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
282 0: while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
283 0: ++i;
284 :
285 : // Now we know that i is the place to insert the split value into. Insert it
286 : // and the child right after it.
0: branch 0 not taken
0: branch 1 not taken
287 0: if (i != e)
288 : memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
289 0: (e-i)*sizeof(IN->Children[0]));
290 0: InsertSide->Children[i+1] = SubRHS;
291 :
0: branch 0 not taken
0: branch 1 not taken
292 0: if (e != i)
293 : memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
294 0: (e-i)*sizeof(Values[0]));
295 0: InsertSide->Values[i] = SubSplit;
296 0: ++InsertSide->NumValuesUsed;
297 0: InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();
298 0: return true;
299 : }
300 :
301 : /// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values)
302 : /// into two subtrees each with "WidthFactor-1" values and a pivot value.
303 : /// Return the pieces in InsertRes.
304 43: void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
43: branch 1 taken
0: branch 2 not taken
305 43: assert(isFull() && "Why split a non-full node?");
306 :
307 : // Since this node is full, it contains 2*WidthFactor-1 values. We move
308 : // the first 'WidthFactor-1' values to the LHS child (which we leave in this
309 : // node), propagate one value up, and move the last 'WidthFactor-1' values
310 : // into the RHS child.
311 :
312 : // Create the new child node.
313 : DeltaTreeNode *NewNode;
0: branch 1 not taken
43: branch 2 taken
314 43: if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
315 : // If this is an interior node, also move over 'WidthFactor' children
316 : // into the new node.
317 0: DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode();
318 : memcpy(&New->Children[0], &IN->Children[WidthFactor],
319 0: WidthFactor*sizeof(IN->Children[0]));
320 0: NewNode = New;
321 : } else {
322 : // Just create the new leaf node.
323 43: NewNode = new DeltaTreeNode();
324 : }
325 :
326 : // Move over the last 'WidthFactor-1' values from here to NewNode.
327 : memcpy(&NewNode->Values[0], &Values[WidthFactor],
328 43: (WidthFactor-1)*sizeof(Values[0]));
329 :
330 : // Decrease the number of values in the two nodes.
331 43: NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
332 :
333 : // Recompute the two nodes' full delta.
334 43: NewNode->RecomputeFullDeltaLocally();
335 43: RecomputeFullDeltaLocally();
336 :
337 43: InsertRes.LHS = this;
338 43: InsertRes.RHS = NewNode;
339 43: InsertRes.Split = Values[WidthFactor-1];
340 43: }
341 :
342 :
343 :
344 : //===----------------------------------------------------------------------===//
345 : // DeltaTree Implementation
346 : //===----------------------------------------------------------------------===//
347 :
348 : //#define VERIFY_TREE
349 :
350 : #ifdef VERIFY_TREE
351 : /// VerifyTree - Walk the btree performing assertions on various properties to
352 : /// verify consistency. This is useful for debugging new changes to the tree.
353 : static void VerifyTree(const DeltaTreeNode *N) {
354 : const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N);
355 : if (IN == 0) {
356 : // Verify leaves, just ensure that FullDelta matches up and the elements
357 : // are in proper order.
358 : int FullDelta = 0;
359 : for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) {
360 : if (i)
361 : assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc);
362 : FullDelta += N->getValue(i).Delta;
363 : }
364 : assert(FullDelta == N->getFullDelta());
365 : return;
366 : }
367 :
368 : // Verify interior nodes: Ensure that FullDelta matches up and the
369 : // elements are in proper order and the children are in proper order.
370 : int FullDelta = 0;
371 : for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) {
372 : const SourceDelta &IVal = N->getValue(i);
373 : const DeltaTreeNode *IChild = IN->getChild(i);
374 : if (i)
375 : assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
376 : FullDelta += IVal.Delta;
377 : FullDelta += IChild->getFullDelta();
378 :
379 : // The largest value in child #i should be smaller than FileLoc.
380 : assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
381 : IVal.FileLoc);
382 :
383 : // The smallest value in child #i+1 should be larger than FileLoc.
384 : assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
385 : VerifyTree(IChild);
386 : }
387 :
388 : FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
389 :
390 : assert(FullDelta == N->getFullDelta());
391 : }
392 : #endif // VERIFY_TREE
393 :
394 3263: static DeltaTreeNode *getRoot(void *Root) {
395 3263: return (DeltaTreeNode*)Root;
396 : }
397 :
398 67: DeltaTree::DeltaTree() {
399 67: Root = new DeltaTreeNode();
400 67: }
401 201: DeltaTree::DeltaTree(const DeltaTree &RHS) {
402 : // Currently we only support copying when the RHS is empty.
403 : assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 &&
201: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
404 201: "Can only copy empty tree");
405 201: Root = new DeltaTreeNode();
406 201: }
407 :
408 268: DeltaTree::~DeltaTree() {
409 268: getRoot(Root)->Destroy();
410 268: }
411 :
412 : /// getDeltaAt - Return the accumulated delta at the specified file offset.
413 : /// This includes all insertions or delections that occurred *before* the
414 : /// specified file index.
415 1637: int DeltaTree::getDeltaAt(unsigned FileIndex) const {
416 1637: const DeltaTreeNode *Node = getRoot(Root);
417 :
418 1637: int Result = 0;
419 :
420 : // Walk down the tree.
421 429: while (1) {
422 : // For all nodes, include any local deltas before the specified file
423 : // index by summing them up directly. Keep track of how many were
424 : // included.
425 2066: unsigned NumValsGreater = 0;
11165: branch 1 taken
1446: branch 2 taken
426 12611: for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
427 : ++NumValsGreater) {
428 11165: const SourceDelta &Val = Node->getValue(NumValsGreater);
429 :
620: branch 0 taken
10545: branch 1 taken
430 11165: if (Val.FileLoc >= FileIndex)
431 620: break;
432 10545: Result += Val.Delta;
433 : }
434 :
435 : // If we have an interior node, include information about children and
436 : // recurse. Otherwise, if we have a leaf, we're done.
437 2066: const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
1636: branch 0 taken
430: branch 1 taken
438 2066: if (!IN) return Result;
439 :
440 : // Include any children to the left of the values we skipped, all of
441 : // their deltas should be included as well.
502: branch 0 taken
430: branch 1 taken
442 932: for (unsigned i = 0; i != NumValsGreater; ++i)
443 502: Result += IN->getChild(i)->getFullDelta();
444 :
445 : // If we found exactly the value we were looking for, break off the
446 : // search early. There is no need to search the RHS of the value for
447 : // partial results.
124: branch 1 taken
306: branch 2 taken
1: branch 4 taken
123: branch 5 taken
1: branch 6 taken
429: branch 7 taken
448 430: if (NumValsGreater != Node->getNumValuesUsed() &&
449 : Node->getValue(NumValsGreater).FileLoc == FileIndex)
450 1: return Result+IN->getChild(NumValsGreater)->getFullDelta();
451 :
452 : // Otherwise, traverse down the tree. The selected subtree may be
453 : // partially included in the range.
454 429: Node = IN->getChild(NumValsGreater);
455 : }
456 : // NOT REACHED.
457 : }
458 :
459 : /// AddDelta - When a change is made that shifts around the text buffer,
460 : /// this method is used to record that info. It inserts a delta of 'Delta'
461 : /// into the current DeltaTree at offset FileIndex.
462 1157: void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
0: branch 0 not taken
1157: branch 1 taken
463 1157: assert(Delta && "Adding a noop?");
464 1157: DeltaTreeNode *MyRoot = getRoot(Root);
465 :
466 : DeltaTreeNode::InsertResult InsertRes;
25: branch 1 taken
1132: branch 2 taken
467 1157: if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
468 25: Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
469 : }
470 :
471 : #ifdef VERIFY_TREE
472 : VerifyTree(MyRoot);
473 : #endif
474 1157: }
475 :
Generated: 2010-02-10 01:31 by zcov