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 "mem_map.h"
  13
  14 #include <string.h>
  15
  16 namespace scudo {
  17
  18 // A low-level vector based on map. It stores the contents inline up to a fixed
  19 // capacity, or in an external memory buffer if it grows bigger than that. May
  20 // incur a significant memory overhead for small vectors. The current
  21 // implementation supports only POD types.
  22 //
  23 // NOTE: This class is not meant to be used directly, use Vector<T> instead.
  24 template <typename T, size_t StaticNumEntries> class VectorNoCtor {
  25 public:
  26   T &operator[](uptr I) {
  27     DCHECK_LT(I, Size);
  28     return Data[I];
  29   }
  30   const T &operator[](uptr I) const {
  31     DCHECK_LT(I, Size);
  32     return Data[I];
  33   }
  34   void push_back(const T &Element) {
  35     DCHECK_LE(Size, capacity());
  36     if (Size == capacity()) {
  37       const uptr NewCapacity = roundUpPowerOfTwo(Size + 1);
  38       if (!reallocate(NewCapacity)) {
  39         return;
  40       }
  41     }
  42     memcpy(&Data[Size++], &Element, sizeof(T));
  43   }
  44   T &back() {
  45     DCHECK_GT(Size, 0);
  46     return Data[Size - 1];
  47   }
  48   void pop_back() {
  49     DCHECK_GT(Size, 0);
  50     Size--;
  51   }
  52   uptr size() const { return Size; }
  53   const T *data() const { return Data; }
  54   T *data() { return Data; }
  55   constexpr uptr capacity() const { return CapacityBytes / sizeof(T); }
  56   bool reserve(uptr NewSize) {
  57     // Never downsize internal buffer.
  58     if (NewSize > capacity())
  59       return reallocate(NewSize);
  60     return true;
  61   }
  62   void resize(uptr NewSize) {
  63     if (NewSize > Size) {
  64       if (!reserve(NewSize)) {
  65         return;
  66       }
  67       memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
  68     }
  69     Size = NewSize;
  70   }
  71
  72   void clear() { Size = 0; }
  73   bool empty() const { return size() == 0; }
  74
  75   const T *begin() const { return data(); }
  76   T *begin() { return data(); }
  77   const T *end() const { return data() + size(); }
  78   T *end() { return data() + size(); }
  79
  80 protected:
  81   constexpr void init(uptr InitialCapacity = 0) {
  82     Data = &LocalData[0];
  83     CapacityBytes = sizeof(LocalData);
  84     if (InitialCapacity > capacity())
  85       reserve(InitialCapacity);
  86   }
  87   void destroy() {
  88     if (Data != &LocalData[0])
  89       ExternalBuffer.unmap();
  90   }
  91
  92 private:
  93   bool reallocate(uptr NewCapacity) {
  94     DCHECK_GT(NewCapacity, 0);
  95     DCHECK_LE(Size, NewCapacity);
  96
  97     MemMapT NewExternalBuffer;
  98     NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached());
  99     if (!NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector",
 100                                MAP_ALLOWNOMEM)) {
 101       return false;
 102     }
 103     T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase());
 104
 105     memcpy(NewExternalData, Data, Size * sizeof(T));
 106     destroy();
 107
 108     Data = NewExternalData;
 109     CapacityBytes = NewCapacity;
 110     ExternalBuffer = NewExternalBuffer;
 111     return true;
 112   }
 113
 114   T *Data = nullptr;
 115   uptr CapacityBytes = 0;
 116   uptr Size = 0;
 117
 118   T LocalData[StaticNumEntries] = {};
 119   MemMapT ExternalBuffer;
 120 };
 121
 122 template <typename T, size_t StaticNumEntries>
 123 class Vector : public VectorNoCtor<T, StaticNumEntries> {
 124 public:
 125   static_assert(StaticNumEntries > 0U,
 126                 "Vector must have a non-zero number of static entries.");
 127   constexpr Vector() { VectorNoCtor<T, StaticNumEntries>::init(); }
 128   explicit Vector(uptr Count) {
 129     VectorNoCtor<T, StaticNumEntries>::init(Count);
 130     this->resize(Count);
 131   }
 132   ~Vector() { VectorNoCtor<T, StaticNumEntries>::destroy(); }
 133   // Disallow copies and moves.
 134   Vector(const Vector &) = delete;
 135   Vector &operator=(const Vector &) = delete;
 136   Vector(Vector &&) = delete;
 137   Vector &operator=(Vector &&) = delete;
 138 };
 139
 140 } // namespace scudo
 141
 142 #endif // SCUDO_VECTOR_H_