contrib/llvm/tools/clang/include/clang/Rewrite/Core/DeltaTree.h

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