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
19namespace 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
51