1 files changed, 256 insertions, 0 deletions
diff --git a/clang-r353983/include/clang/Analysis/Support/BumpVector.h b/clang-r353983/include/clang/Analysis/Support/BumpVector.h
new file mode 100644
index 00000000..74092dab
--- /dev/null
+++ b/clang-r353983/include/clang/Analysis/Support/BumpVector.h
@@ -0,0 +1,256 @@
+//===- 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