EIC code displayed by LXR master/​include/​llvm/​ADT/​RewriteRope.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:07

 //===- 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_ADT_REWRITEROPE_H
 #define LLVM_ADT_REWRITEROPE_H
 
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/StringRef.h"
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <utility>
 
 namespace llvm {
 
 //===--------------------------------------------------------------------===//
 // 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) {}
 
   // The copy assignment operator is defined as deleted pending further
   // motivation.
   RewriteRope &operator=(const RewriteRope &) = delete;
 
   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 llvm
 
 #endif // LLVM_ADT_REWRITEROPE_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team