1 //===--- DeltaTree.h - B-Tree for Rewrite Delta tracking --------*- C++ -*-===// 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 defines the DeltaTree class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef CLANG_REWRITE_DELTATREE_H 15 #define CLANG_REWRITE_DELTATREE_H 16 17 namespace clang { 18 19 /// DeltaTree - a multiway search tree (BTree) structure with some fancy 20 /// features. B-Trees are generally more memory and cache efficient than 21 /// binary trees, because they store multiple keys/values in each node. This 22 /// implements a key/value mapping from index to delta, and allows fast lookup 23 /// on index. However, an added (important) bonus is that it can also 24 /// efficiently tell us the full accumulated delta for a specific file offset 25 /// as well, without traversing the whole tree. 26 class DeltaTree { 27 void *Root; // "DeltaTreeNode *" 28 void operator=(const DeltaTree&); // DO NOT IMPLEMENT 29 public: 30 DeltaTree(); 31 32 // Note: Currently we only support copying when the RHS is empty. 33 DeltaTree(const DeltaTree &RHS); 34 ~DeltaTree(); 35 36 /// getDeltaAt - Return the accumulated delta at the specified file offset. 37 /// This includes all insertions or delections that occurred *before* the 38 /// specified file index. 39 int getDeltaAt(unsigned FileIndex) const; 40 41 /// AddDelta - When a change is made that shifts around the text buffer, 42 /// this method is used to record that info. It inserts a delta of 'Delta' 43 /// into the current DeltaTree at offset FileIndex. 44 void AddDelta(unsigned FileIndex, int Delta); 45 }; 46 } // end namespace clang 47 48 #endif 49