143 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SCUDO_VECTOR_H_10#define SCUDO_VECTOR_H_11 12#include "mem_map.h"13 14#include <string.h>15 16namespace scudo {17 18// A low-level vector based on map. It stores the contents inline up to a fixed19// capacity, or in an external memory buffer if it grows bigger than that. May20// incur a significant memory overhead for small vectors. The current21// implementation supports only POD types.22//23// NOTE: This class is not meant to be used directly, use Vector<T> instead.24template <typename T, size_t StaticNumEntries> class VectorNoCtor {25public: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 80protected: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 92private: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 122template <typename T, size_t StaticNumEntries>123class Vector : public VectorNoCtor<T, StaticNumEntries> {124public: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 scudo141 142#endif // SCUDO_VECTOR_H_143