1 //===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===//
25 /// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing
27 /// can also efficiently tell us the full accumulated delta for a specific
32 /// former and adds children pointers.  Each node knows the full delta of all
34 /// full delta implied by a whole subtree in constant time.
43     int Delta;  member
46       SourceDelta Delta;  in get()  local
47       Delta.FileLoc = Loc;  in get()
48       Delta.Delta = D;  in get()
49       return Delta;  in get()
82     /// FullDelta - This is the full delta of all the values in this node and
105     /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
109     bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
141       FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;  in DeltaTreeInteriorNode()
173     NewFullDelta += Values[i].Delta;  in RecomputeFullDeltaLocally()
180 /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
184 bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,  in DoInsertion()  argument
186   // Maintain full delta for this node.  in DoInsertion()
187   FullDelta += Delta;  in DoInsertion()
189   // Find the insertion point, the first delta whose index is >= FileIndex.  in DoInsertion()
197     // NOTE: Delta could drop to zero here.  This means that the delta entry is  in DoInsertion()
199     // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in  in DoInsertion()
201     Values[i].Delta += Delta;  in DoInsertion()
213       Values[i] = SourceDelta::get(FileIndex, Delta);  in DoInsertion()
224       InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);  in DoInsertion()
226       InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/);  in DoInsertion()
232   if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))  in DoInsertion()
274   // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.  in DoInsertion()
291   InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta();  in DoInsertion()
327   // Recompute the two nodes' full delta.  in DoSplit()
354       FullDelta += N->getValue(i).Delta;  in VerifyTree()
368     FullDelta += IVal.Delta;  in VerifyTree()
405 /// getDeltaAt - Return the accumulated delta at the specified file offset.
425       Result += Val.Delta;  in getDeltaAt()
453 /// this method is used to record that info.  It inserts a delta of 'Delta'
455 void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {  in AddDelta()  argument
456   assert(Delta && "Adding a noop?");  in AddDelta()
460   if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {  in AddDelta()