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   constexpr void init(uptr InitialCapacity = 0) {
23     Data = &LocalData[0];
24     CapacityBytes = sizeof(LocalData);
25     if (InitialCapacity > capacity())
26       reserve(InitialCapacity);
27   }
28   void destroy() {
29     if (Data != &LocalData[0])
30       unmap(Data, CapacityBytes, 0, &MapData);
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 = roundUpPowerOfTwo(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   constexpr 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     NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached());
86     T *NewData = reinterpret_cast<T *>(
87         map(nullptr, NewCapacity, "scudo:vector", 0, &MapData));
88     memcpy(NewData, Data, Size * sizeof(T));
89     destroy();
90     Data = NewData;
91     CapacityBytes = NewCapacity;
92   }
93 
94   T *Data = nullptr;
95   T LocalData[256 / sizeof(T)] = {};
96   uptr CapacityBytes = 0;
97   uptr Size = 0;
98   [[no_unique_address]] MapPlatformData MapData = {};
99 };
100 
101 template <typename T> class Vector : public VectorNoCtor<T> {
102 public:
103   constexpr Vector() { VectorNoCtor<T>::init(); }
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_
119