llvm/ADT/DeltaTree.h

0001 //===- DeltaTree.h - B-Tree for Rewrite Delta tracking ----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the DeltaTree class.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_ADT_DELTATREE_H
0014 #define LLVM_ADT_DELTATREE_H
0015
0016 namespace llvm {
0017
0018 /// DeltaTree - a multiway search tree (BTree) structure with some fancy
0019 /// features.  B-Trees are generally more memory and cache efficient than
0020 /// binary trees, because they store multiple keys/values in each node.  This
0021 /// implements a key/value mapping from index to delta, and allows fast lookup
0022 /// on index.  However, an added (important) bonus is that it can also
0023 /// efficiently tell us the full accumulated delta for a specific file offset
0024 /// as well, without traversing the whole tree.
0025 class DeltaTree {
0026   void *Root; // "DeltaTreeNode *"
0027
0028 public:
0029   DeltaTree();
0030
0031   // Note: Currently we only support copying when the RHS is empty.
0032   DeltaTree(const DeltaTree &RHS);
0033
0034   DeltaTree &operator=(const DeltaTree &) = delete;
0035   ~DeltaTree();
0036
0037   /// getDeltaAt - Return the accumulated delta at the specified file offset.
0038   /// This includes all insertions or delections that occurred *before* the
0039   /// specified file index.
0040   int getDeltaAt(unsigned FileIndex) const;
0041
0042   /// AddDelta - When a change is made that shifts around the text buffer,
0043   /// this method is used to record that info.  It inserts a delta of 'Delta'
0044   /// into the current DeltaTree at offset FileIndex.
0045   void AddDelta(unsigned FileIndex, int Delta);
0046 };
0047
0048 } // namespace llvm
0049
0050 #endif // LLVM_ADT_DELTATREE_H