path: root/include/clang/Rewrite/RewriteRope.h

//===--- RewriteRope.h - Rope specialized for rewriter ----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines the RewriteRope class, which is a powerful string class.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_REWRITEROPE_H
#define LLVM_CLANG_REWRITEROPE_H

#include "llvm/ADT/iterator"
#include <list>
#include <cstring>

#include "llvm/Support/Casting.h"

//#define USE_ROPE_VECTOR

namespace clang {

struct RopeRefCountString {
  unsigned RefCount;
  char Data[1];  //  Variable sized.
  
  void addRef() {
    if (this) ++RefCount;
  }
  
  void dropRef() {
    if (this && --RefCount == 0)
      delete [] (char*)this;
  }
};
  
struct RopePiece {
  RopeRefCountString *StrData;
  unsigned StartOffs;
  unsigned EndOffs;
  
  RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {}
  
  RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End)
    : StrData(Str), StartOffs(Start), EndOffs(End) {
    StrData->addRef();
  }
  RopePiece(const RopePiece &RP)
    : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) {
    StrData->addRef();
  }

  ~RopePiece() {
    StrData->dropRef();
  }
  
  void operator=(const RopePiece &RHS) {
    if (StrData != RHS.StrData) {
      StrData->dropRef();
      StrData = RHS.StrData;
      StrData->addRef();
    }
    StartOffs = RHS.StartOffs;
    EndOffs = RHS.EndOffs;
  }
  
  const char &operator[](unsigned Offset) const {
    return StrData->Data[Offset+StartOffs];
  }
  char &operator[](unsigned Offset) {
    return StrData->Data[Offset+StartOffs];
  }
  
  unsigned size() const { return EndOffs-StartOffs; }
};
  
  
  
#ifndef USE_ROPE_VECTOR
  using llvm::dyn_cast;
  using llvm::cast;

/// This is an adapted B+ Tree, ... erases don't keep the tree balanced.
  
class RopePieceBTreeNode;
struct InsertResult {
  RopePieceBTreeNode *LHS, *RHS;
};
  
class RopePieceBTreeNode {
protected:
  /// WidthFactor - This controls the number of K/V slots held in the BTree:
  /// how wide it is.  Each level of the BTree is guaranteed to have at least
  /// 'WidthFactor' elements in it (either ropepieces or children), (except the
  /// root, which may have less) and may have at most 2*WidthFactor elements.
  enum { WidthFactor = 8 };

  /// Size - This is the number of bytes of file this node (including any
  /// potential children) covers.
  unsigned Size;
  
  /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it is
  /// an instance of RopePieceBTreeInterior.
  bool IsLeaf;
  
  RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {}
  ~RopePieceBTreeNode() {}
public:
  
  bool isLeaf() const { return IsLeaf; }
  unsigned size() const { return Size; }

  void Destroy();

  /// split - Split the range containing the specified offset so that we are
  /// guaranteed that there is a place to do an insertion at the specified
  /// offset.  The offset is relative, so "0" is the start of the node.  This
  /// returns true if the insertion could not be done in place, and returns
  /// information in 'Res' about the piece that is percolated up.
  bool split(unsigned Offset, InsertResult *Res);
  
  /// insert - Insert the specified ropepiece into this tree node at the
  /// specified offset.  The offset is relative, so "0" is the start of the
  /// node.  This returns true if the insertion could not be done in place, and
  /// returns information in 'Res' about the piece that is percolated up.
  bool insert(unsigned Offset, const RopePiece &R, InsertResult *Res);

  /// erase - Remove NumBytes from this node at the specified offset.  We are
  /// guaranteed that there is a split at Offset.
  void erase(unsigned Offset, unsigned NumBytes);
  
  static inline bool classof(const RopePieceBTreeNode *) { return true; }

};
  
  

  
class RopePieceBTreeLeaf : public RopePieceBTreeNode {
  /// NumPieces - This holds the number of rope pieces currently active in the
  /// Pieces array.
  unsigned char NumPieces;
  
  /// Pieces - This tracks the file chunks currently in this leaf.
  ///
  RopePiece Pieces[2*WidthFactor];
  
  /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
  /// efficient in-order forward iteration of the tree without traversal.
  const RopePieceBTreeLeaf *NextLeaf;
public:
  RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NextLeaf(0