| //===- BumpVector.h - Vector-like ADT that uses bump allocation -*- 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 provides BumpVector, a vector-like ADT whose contents are |
| // allocated from a BumpPtrAllocator. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // FIXME: Most of this is copy-and-paste from SmallVector.h. We can |
| // refactor this core logic into something common that is shared between |
| // the two. The main thing that is different is the allocation strategy. |
| |
| #ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H |
| #define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H |
| |
| #include "llvm/ADT/PointerIntPair.h" |
| #include "llvm/Support/Allocator.h" |
| #include <cassert> |
| #include <cstddef> |
| #include <cstring> |
| #include <iterator> |
| #include <memory> |
| #include <type_traits> |
| |
| namespace clang { |
| |
| class BumpVectorContext { |
| llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; |
| |
| public: |
| /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator |
| /// and destroys it when the BumpVectorContext object is destroyed. |
| BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} |
| |
| BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) { |
| Other.Alloc.setInt(false); |
| Other.Alloc.setPointer(nullptr); |
| } |
| |
| /// Construct a new BumpVectorContext that reuses an existing |
| /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the |
| /// BumpVectorContext object is destroyed. |
| BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} |
| |
| ~BumpVectorContext() { |
| if (Alloc.getInt()) |
| delete Alloc.getPointer(); |
| } |
| |
| llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } |
| }; |
| |
| template<typename T> |
| class BumpVector { |
| T *Begin = nullptr; |
| T *End = nullptr; |
| T *Capacity = nullptr; |
| |
| public: |
| // Default ctor - Initialize to empty. |
| explicit BumpVector(BumpVectorContext &C, unsigned N) { |
| reserve(C, N); |
| } |
| |
| ~BumpVector() { |
| if (std::is_class<T>::value) { |
| // Destroy the constructed elements in the vector. |
| destroy_range(Begin, End); |
| } |
| } |
| |
| using size_type = size_t; |
| using difference_type = ptrdiff_t; |
| using value_type = T; |
| using iterator = T *; |
| using const_iterator = const T *; |
| |
| using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
| using reverse_iterator = std::reverse_iterator<iterator>; |
| |
| using reference = T &; |
| using const_reference = const T &; |
| using pointer = T *; |
| using const_pointer = const T *; |
| |
| // forward iterator creation methods. |
| iterator begin() { return Begin; } |
| const_iterator begin() const { return Begin; } |
| iterator end() { return End; } |
| const_iterator end() const { return End; } |
| |
| // reverse iterator creation methods. |
| reverse_iterator rbegin() { return reverse_iterator(end()); } |
| const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } |
| reverse_iterator rend() { return reverse_iterator(begin()); } |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| |
| bool empty() const { return Begin == End; } |
| size_type size() const { return End-Begin; } |
| |
| reference operator[](unsigned idx) { |
| assert(Begin + idx < End); |
| return Begin[idx]; |
| } |
| const_reference operator[](unsigned idx) const { |
| assert(Begin + idx < End); |
| return Begin[idx]; |
| } |
| |
| reference front() { |
| return begin()[0]; |
| } |
| const_reference front() const { |
| return begin()[0]; |
| } |
| |
| reference back() { |
| return end()[-1]; |
| } |
| const_reference back() const { |
| return end()[-1]; |
| } |
| |
| void pop_back() { |
| --End; |
| End->~T(); |
| } |
| |
| T pop_back_val() { |
| T Result = back(); |
| pop_back(); |
| return Result; |
| } |
| |
| void clear() { |
| if (std::is_class<T>::value) { |
| destroy_range(Begin, End); |
| } |
| End = Begin; |
| } |
| |
| /// data - Return a pointer to the vector's buffer, even if empty(). |
| pointer data() { |
| return pointer(Begin); |
| } |
| |
| /// data - Return a pointer to the vector's buffer, even if empty(). |
| const_pointer data() const { |
| return const_pointer(Begin); |
| } |
| |
| void push_back(const_reference Elt, BumpVectorContext &C) { |
| if (End < Capacity) { |
| Retry: |
| new (End) T(Elt); |
| ++End; |
| return; |
| } |
| grow(C); |
| goto Retry; |
| } |
| |
| /// insert - Insert some number of copies of element into a position. Return |
| /// iterator to position after last inserted copy. |
| iterator insert(iterator I, size_t Cnt, const_reference E, |
| BumpVectorContext &C) { |
| assert(I >= Begin && I <= End && "Iterator out of bounds."); |
| if (End + Cnt <= Capacity) { |
| Retry: |
| move_range_right(I, End, Cnt); |
| construct_range(I, I + Cnt, E); |
| End += Cnt; |
| return I + Cnt; |
| } |
| ptrdiff_t D = I - Begin; |
| grow(C, size() + Cnt); |
| I = Begin + D; |
| goto Retry; |
| } |
| |
| void reserve(BumpVectorContext &C, unsigned N) { |
| if (unsigned(Capacity-Begin) < N) |
| grow(C, N); |
| } |
| |
| /// capacity - Return the total number of elements in the currently allocated |
| /// buffer. |
| size_t capacity() const { return Capacity - Begin; } |
| |
| private: |
| /// grow - double the size of the allocated memory, guaranteeing space for at |
| /// least one more element or MinSize if specified. |
| void grow(BumpVectorContext &C, size_type MinSize = 1); |
| |
| void construct_range(T *S, T *E, const T &Elt) { |
| for (; S != E; ++S) |
| new (S) T(Elt); |
| } |
| |
| void destroy_range(T *S, T *E) { |
| while (S != E) { |
| --E; |
| E->~T(); |
| } |
| } |
| |
| void move_range_right(T *S, T *E, size_t D) { |
| for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { |
| --E; |
| new (I) T(*E); |
| E->~T(); |
| } |
| } |
| }; |
| |
| // Define this out-of-line to dissuade the C++ compiler from inlining it. |
| template <typename T> |
| void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { |
| size_t CurCapacity = Capacity-Begin; |
| size_t CurSize = size(); |
| size_t NewCapacity = 2*CurCapacity; |
| if (NewCapacity < MinSize) |
| NewCapacity = MinSize; |
| |
| // Allocate the memory from the BumpPtrAllocator. |
| T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); |
| |
| // Copy the elements over. |
| if (Begin != End) { |
| if (std::is_class<T>::value) { |
| std::uninitialized_copy(Begin, End, NewElts); |
| // Destroy the original elements. |
| destroy_range(Begin, End); |
| } else { |
| // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). |
| memcpy(NewElts, Begin, CurSize * sizeof(T)); |
| } |
| } |
| |
| // For now, leak 'Begin'. We can add it back to a freelist in |
| // BumpVectorContext. |
| Begin = NewElts; |
| End = NewElts+CurSize; |
| Capacity = Begin+NewCapacity; |
| } |
| |
| } // namespace clang |
| |
| #endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H |