llvm/llvm/include/llvm/ADT/DeltaTree.h

//===- DeltaTree.h - B-Tree for Rewrite Delta tracking ----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the DeltaTree class.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_DELTATREE_H
#define LLVM_ADT_DELTATREE_H

namespace llvm {

/// DeltaTree - a multiway search tree (BTree) structure with some fancy
/// features.  B-Trees are generally more memory and cache efficient than
/// binary trees, because they store multiple keys/values in each node.  This
/// implements a key/value mapping from index to delta, and allows fast lookup
/// on index.  However, an added (important) bonus is that it can also
/// efficiently tell us the full accumulated delta for a specific file offset
/// as well, without traversing the whole tree.
class DeltaTree { … };

} // namespace llvm

#endif // LLVM_ADT_DELTATREE_H