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 17f56faa01936b9cf909623d7f06e3c2569ca4a78eDmitri Gribenko#include "llvm/Support/Compiler.h" 18f56faa01936b9cf909623d7f06e3c2569ca4a78eDmitri Gribenko 195c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattnernamespace clang { 201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 215c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// DeltaTree - a multiway search tree (BTree) structure with some fancy 223ea5cf8889f48809a94e886d013a911128664c88Chris Lattner /// features. B-Trees are generally more memory and cache efficient than 235c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// binary trees, because they store multiple keys/values in each node. This 245c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// implements a key/value mapping from index to delta, and allows fast lookup 255c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// on index. However, an added (important) bonus is that it can also 265c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// efficiently tell us the full accumulated delta for a specific file offset 275c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// as well, without traversing the whole tree. 285c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner class DeltaTree { 298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void *Root; // "DeltaTreeNode *" 30f56faa01936b9cf909623d7f06e3c2569ca4a78eDmitri Gribenko void operator=(const DeltaTree &) LLVM_DELETED_FUNCTION; 315c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner public: 328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTree(); 335c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Note: Currently we only support copying when the RHS is empty. 358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTree(const DeltaTree &RHS); 368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ~DeltaTree(); 371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 385c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// getDeltaAt - Return the accumulated delta at the specified file offset. 395c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// This includes all insertions or delections that occurred *before* the 405c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// specified file index. 411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump int getDeltaAt(unsigned FileIndex) const; 425c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 435c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// AddDelta - When a change is made that shifts around the text buffer, 445c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// this method is used to record that info. It inserts a delta of 'Delta' 455c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner /// into the current DeltaTree at offset FileIndex. 461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump void AddDelta(unsigned FileIndex, int Delta); 475c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner }; 488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end namespace clang 495c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner 505c9dc5ac75de8d620311cdc20223998e0293d61fChris Lattner#endif 51