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 = 0) {
23     Data = reinterpret_cast<T *>(&LocalData[0]);
24     CapacityBytes = sizeof(LocalData);
25     reserve(InitialCapacity);
26   }
27   void destroy() {
28     if (Data != reinterpret_cast<T *>(&LocalData[0]))
29       unmap(Data, CapacityBytes);
30   }
31   T &operator[](uptr I) {
32     DCHECK_LT(I, Size);
33     return Data[I];
34   }
35   const T &operator[](uptr I) const {
36     DCHECK_LT(I, Size);
37     return Data[I];
38   }
39   void push_back(const T &Element) {
40     DCHECK_LE(Size, capacity());
41     if (Size == capacity()) {
42       const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1);
43       reallocate(NewCapacity);
44     }
45     memcpy(&Data[Size++], &Element, sizeof(T));
46   }
47   T &back() {
48     DCHECK_GT(Size, 0);
49     return Data[Size - 1];
50   }
51   void pop_back() {
52     DCHECK_GT(Size, 0);
53     Size--;
54   }
55   uptr size() const { return Size; }
56   const T *data() const { return Data; }
57   T *data() { return Data; }
58   uptr capacity() const { return CapacityBytes / sizeof(T); }
59   void reserve(uptr NewSize) {
60     // Never downsize internal buffer.
61     if (NewSize > capacity())
62       reallocate(NewSize);
63   }
64   void resize(uptr NewSize) {
65     if (NewSize > Size) {
66       reserve(NewSize);
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 private:
81   void reallocate(uptr NewCapacity) {
82     DCHECK_GT(NewCapacity, 0);
83     DCHECK_LE(Size, NewCapacity);
84     NewCapacity = roundUpTo(NewCapacity * sizeof(T), getPageSizeCached());
85     T *NewData =
86         reinterpret_cast<T *>(map(nullptr, NewCapacity, "scudo:vector"));
87     memcpy(NewData, Data, Size * sizeof(T));
88     destroy();
89     Data = NewData;
90     CapacityBytes = NewCapacity;
91   }
92 
93   T *Data = nullptr;
94   u8 LocalData[256] = {};
95   uptr CapacityBytes = 0;
96   uptr Size = 0;
97 };
98 
99 template <typename T> class Vector : public VectorNoCtor<T> {
100 public:
101   Vector() { VectorNoCtor<T>::init(); }
102   explicit Vector(uptr Count) {
103     VectorNoCtor<T>::init(Count);
104     this->resize(Count);
105   }
106   ~Vector() { VectorNoCtor<T>::destroy(); }
107   // Disallow copies and moves.
108   Vector(const Vector &) = delete;
109   Vector &operator=(const Vector &) = delete;
110   Vector(Vector &&) = delete;
111   Vector &operator=(Vector &&) = delete;
112 };
113 
114 } // namespace scudo
115 
116 #endif // SCUDO_VECTOR_H_
117