contrib/compiler-rt/lib/scudo/standalone/vector.h

   1 //===-- vector.h ------------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef SCUDO_VECTOR_H_
  10 #define SCUDO_VECTOR_H_
  11
  12 #include "common.h"
  13
  14 #include <string.h>
  15
  16 namespace scudo {
  17
  18 // A low-level vector based on map. May incur a significant memory overhead for
  19 // small vectors. The current implementation supports only POD types.
  20 template <typename T> class VectorNoCtor {
  21 public:
  22   void init(uptr InitialCapacity) {
  23     CapacityBytes = 0;
  24     Size = 0;
  25     Data = nullptr;
  26     reserve(InitialCapacity);
  27   }
  28   void destroy() {
  29     if (Data)
  30       unmap(Data, CapacityBytes);
  31   }
  32   T &operator[](uptr I) {
  33     DCHECK_LT(I, Size);
  34     return Data[I];
  35   }
  36   const T &operator[](uptr I) const {
  37     DCHECK_LT(I, Size);
  38     return Data[I];
  39   }
  40   void push_back(const T &Element) {
  41     DCHECK_LE(Size, capacity());
  42     if (Size == capacity()) {
  43       const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1);
  44       reallocate(NewCapacity);
  45     }
  46     memcpy(&Data[Size++], &Element, sizeof(T));
  47   }
  48   T &back() {
  49     DCHECK_GT(Size, 0);
  50     return Data[Size - 1];
  51   }
  52   void pop_back() {
  53     DCHECK_GT(Size, 0);
  54     Size--;
  55   }
  56   uptr size() const { return Size; }
  57   const T *data() const { return Data; }
  58   T *data() { return Data; }
  59   uptr capacity() const { return CapacityBytes / sizeof(T); }
  60   void reserve(uptr NewSize) {
  61     // Never downsize internal buffer.
  62     if (NewSize > capacity())
  63       reallocate(NewSize);
  64   }
  65   void resize(uptr NewSize) {
  66     if (NewSize > Size) {
  67       reserve(NewSize);
  68       memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
  69     }
  70     Size = NewSize;
  71   }
  72
  73   void clear() { Size = 0; }
  74   bool empty() const { return size() == 0; }
  75
  76   const T *begin() const { return data(); }
  77   T *begin() { return data(); }
  78   const T *end() const { return data() + size(); }
  79   T *end() { return data() + size(); }
  80
  81 private:
  82   void reallocate(uptr NewCapacity) {
  83     DCHECK_GT(NewCapacity, 0);
  84     DCHECK_LE(Size, NewCapacity);
  85     const uptr NewCapacityBytes =
  86         roundUpTo(NewCapacity * sizeof(T), getPageSizeCached());
  87     T *NewData = (T *)map(nullptr, NewCapacityBytes, "scudo:vector");
  88     if (Data) {
  89       memcpy(NewData, Data, Size * sizeof(T));
  90       unmap(Data, CapacityBytes);
  91     }
  92     Data = NewData;
  93     CapacityBytes = NewCapacityBytes;
  94   }
  95
  96   T *Data;
  97   uptr CapacityBytes;
  98   uptr Size;
  99 };
 100
 101 template <typename T> class Vector : public VectorNoCtor<T> {
 102 public:
 103   Vector() { VectorNoCtor<T>::init(1); }
 104   explicit Vector(uptr Count) {
 105     VectorNoCtor<T>::init(Count);
 106     this->resize(Count);
 107   }
 108   ~Vector() { VectorNoCtor<T>::destroy(); }
 109   // Disallow copies and moves.
 110   Vector(const Vector &) = delete;
 111   Vector &operator=(const Vector &) = delete;
 112   Vector(Vector &&) = delete;
 113   Vector &operator=(Vector &&) = delete;
 114 };
 115
 116 } // namespace scudo
 117
 118 #endif // SCUDO_VECTOR_H_