Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- RewriteRope.h - Rope specialized for rewriter ------------*- 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 RewriteRope class, which is a powerful string class.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H

#define LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H

#include "llvm/ADT/IntrusiveRefCntPtr.h"

#include "llvm/ADT/StringRef.h"

#include <cassert>

#include <cstddef>

#include <iterator>

#include <utility>

namespace clang {

  //===--------------------------------------------------------------------===//

  // RopeRefCountString Class

  //===--------------------------------------------------------------------===//

  /// RopeRefCountString - This struct is allocated with 'new char[]' from the

  /// heap, and represents a reference counted chunk of string data.  When its

  /// ref count drops to zero, it is delete[]'d.  This is primarily managed

  /// through the RopePiece class below.

  struct RopeRefCountString {

    unsigned RefCount;

    char Data[1];  //  Variable sized.

    void Retain() { ++RefCount; }

    void Release() {

      assert(RefCount > 0 && "Reference count is already zero.");

      if (--RefCount == 0)

        delete [] (char*)this;

    }

  };

  //===--------------------------------------------------------------------===//

  // RopePiece Class

  //===--------------------------------------------------------------------===//

  /// RopePiece - This class represents a view into a RopeRefCountString object.

  /// This allows references to string data to be efficiently chopped up and

  /// moved around without having to push around the string data itself.

  ///

  /// For example, we could have a 1M RopePiece and want to insert something

  /// into the middle of it.  To do this, we split it into two RopePiece objects

  /// that both refer to the same underlying RopeRefCountString (just with

  /// different offsets) which is a nice constant time operation.

  struct RopePiece {

    llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData;

    unsigned StartOffs = 0;

    unsigned EndOffs = 0;

    RopePiece() = default;

    RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,

              unsigned End)

        : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}

    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; }

  };

  //===--------------------------------------------------------------------===//

  // RopePieceBTreeIterator Class

  //===--------------------------------------------------------------------===//

  /// RopePieceBTreeIterator - This class provides read-only forward iteration

  /// over bytes that are in a RopePieceBTree.  This first iterates over bytes

  /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,

  /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.

  class RopePieceBTreeIterator {

    /// CurNode - The current B+Tree node that we are inspecting.

    const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;

    /// CurPiece - The current RopePiece in the B+Tree node that we're

    /// inspecting.

    const RopePiece *CurPiece = nullptr;

    /// CurChar - The current byte in the RopePiece we are pointing to.

    unsigned CurChar = 0;

  public:

    using iterator_category = std::forward_iterator_tag;

    using value_type = const char;

    using difference_type = std::ptrdiff_t;

    using pointer = value_type *;

    using reference = value_type &;

    RopePieceBTreeIterator() = default;

    RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);

    char operator*() const {

      return (*CurPiece)[CurChar];

    }

    bool operator==(const RopePieceBTreeIterator &RHS) const {

      return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;

    }

    bool operator!=(const RopePieceBTreeIterator &RHS) const {

      return !operator==(RHS);

    }

    RopePieceBTreeIterator& operator++() {   // Preincrement

      if (CurChar+1 < CurPiece->size())

        ++CurChar;

      else

        MoveToNextPiece();

      return *this;

    }

    RopePieceBTreeIterator operator++(int) { // Postincrement

      RopePieceBTreeIterator tmp = *this; ++*this; return tmp;

    }

    llvm::StringRef piece() const {

      return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());

    }

    void MoveToNextPiece();

  };

  //===--------------------------------------------------------------------===//

  // RopePieceBTree Class

  //===--------------------------------------------------------------------===//

  class RopePieceBTree {

    void /*RopePieceBTreeNode*/ *Root;

  public:

    RopePieceBTree();

    RopePieceBTree(const RopePieceBTree &RHS);

    RopePieceBTree &operator=(const RopePieceBTree &) = delete;

    ~RopePieceBTree();

    using iterator = RopePieceBTreeIterator;

    iterator begin() const { return iterator(Root); }

    iterator end() const { return iterator(); }

    unsigned size() const;

    unsigned empty() const { return size() == 0; }

    void clear();

    void insert(unsigned Offset, const RopePiece &R);

    void erase(unsigned Offset, unsigned NumBytes);

  };

  //===--------------------------------------------------------------------===//

  // RewriteRope Class

  //===--------------------------------------------------------------------===//

/// RewriteRope - A powerful string class.  This class supports extremely

/// efficient insertions and deletions into the middle of it, even for

/// ridiculously long strings.

class RewriteRope {

  RopePieceBTree Chunks;

  /// We allocate space for string data out of a buffer of size AllocChunkSize.

  /// This keeps track of how much space is left.

  llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;

  enum { AllocChunkSize = 4080 };

  unsigned AllocOffs = AllocChunkSize;

public:

  RewriteRope() = default;

  RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}

  using iterator = RopePieceBTree::iterator;

  using const_iterator = RopePieceBTree::iterator;

  iterator begin() const { return Chunks.begin(); }

  iterator end() const { return Chunks.end(); }

  unsigned size() const { return Chunks.size(); }

  void clear() {

    Chunks.clear();

  }

  void assign(const char *Start, const char *End) {

    clear();

    if (Start != End)

      Chunks.insert(0, MakeRopeString(Start, End));

  }

  void insert(unsigned Offset, const char *Start, const char *End) {

    assert(Offset <= size() && "Invalid position to insert!");

    if (Start == End) return;

    Chunks.insert(Offset, MakeRopeString(Start, End));

  }

  void erase(unsigned Offset, unsigned NumBytes) {

    assert(Offset+NumBytes <= size() && "Invalid region to erase!");

    if (NumBytes == 0) return;

    Chunks.erase(Offset, NumBytes);

  }

private:

  RopePiece MakeRopeString(const char *Start, const char *End);

};

} // namespace clang

#endif // LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H