DeltaTree.h revision 3ea5cf8889f48809a94e886d013a911128664c88
15c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner//===--- DeltaTree.h - B-Tree for Rewrite Delta tracking --------*- C++ -*-===// 25c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// 35c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// The LLVM Compiler Infrastructure 45c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// 55c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// This file is distributed under the University of Illinois Open Source 65c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// License. See LICENSE.TXT for details. 75c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// 85c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner//===----------------------------------------------------------------------===// 95c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// 105c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// This file defines the DeltaTree class. 115c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner// 125c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner//===----------------------------------------------------------------------===// 135c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 145c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner#ifndef CLANG_REWRITE_DELTATREE_H 155c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner#define CLANG_REWRITE_DELTATREE_H 165c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 175c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattnernamespace clang { 181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 195c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// DeltaTree - a multiway search tree (BTree) structure with some fancy 203ea5cf8889f48809a94e886d013a911128664c88Chris Lattner /// features. B-Trees are generally more memory and cache efficient than 215c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// binary trees, because they store multiple keys/values in each node. This 225c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// implements a key/value mapping from index to delta, and allows fast lookup 235c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// on index. However, an added (important) bonus is that it can also 245c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// efficiently tell us the full accumulated delta for a specific file offset 255c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// as well, without traversing the whole tree. 265c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner class DeltaTree { 278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void *Root; // "DeltaTreeNode *" 285c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner void operator=(const DeltaTree&); // DO NOT IMPLEMENT 295c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner public: 308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTree(); 315c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Note: Currently we only support copying when the RHS is empty. 338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTree(const DeltaTree &RHS); 348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ~DeltaTree(); 351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 365c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// getDeltaAt - Return the accumulated delta at the specified file offset. 375c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// This includes all insertions or delections that occurred *before* the 385c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// specified file index. 391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump int getDeltaAt(unsigned FileIndex) const; 405c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 415c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// AddDelta - When a change is made that shifts around the text buffer, 425c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// this method is used to record that info. It inserts a delta of 'Delta' 435c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// into the current DeltaTree at offset FileIndex. 441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump void AddDelta(unsigned FileIndex, int Delta); 455c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner }; 468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end namespace clang 475c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 485c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner#endif 49