vector.h revision 360784 
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
16namespace 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.
20template <typename T> class VectorNoCtor {
21public:
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
81private:
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 =
88        reinterpret_cast<T *>(map(nullptr, NewCapacityBytes, "scudo:vector"));
89    if (Data) {
90      memcpy(NewData, Data, Size * sizeof(T));
91      unmap(Data, CapacityBytes);
92    }
93    Data = NewData;
94    CapacityBytes = NewCapacityBytes;
95  }
96
97  T *Data;
98  uptr CapacityBytes;
99  uptr Size;
100};
101
102template <typename T> class Vector : public VectorNoCtor<T> {
103public:
104  Vector() { VectorNoCtor<T>::init(1); }
105  explicit Vector(uptr Count) {
106    VectorNoCtor<T>::init(Count);
107    this->resize(Count);
108  }
109  ~Vector() { VectorNoCtor<T>::destroy(); }
110  // Disallow copies and moves.
111  Vector(const Vector &) = delete;
112  Vector &operator=(const Vector &) = delete;
113  Vector(Vector &&) = delete;
114  Vector &operator=(Vector &&) = delete;
115};
116
117} // namespace scudo
118
119#endif // SCUDO_VECTOR_H_
120