1351282Sdim//===-- vector.h ------------------------------------------------*- C++ -*-===// 2351282Sdim// 3351282Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351282Sdim// See https://llvm.org/LICENSE.txt for license information. 5351282Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351282Sdim// 7351282Sdim//===----------------------------------------------------------------------===// 8351282Sdim 9351282Sdim#ifndef SCUDO_VECTOR_H_ 10351282Sdim#define SCUDO_VECTOR_H_ 11351282Sdim 12351282Sdim#include "common.h" 13351282Sdim 14351282Sdim#include <string.h> 15351282Sdim 16351282Sdimnamespace scudo { 17351282Sdim 18351282Sdim// A low-level vector based on map. May incur a significant memory overhead for 19351282Sdim// small vectors. The current implementation supports only POD types. 20351282Sdimtemplate <typename T> class VectorNoCtor { 21351282Sdimpublic: 22351282Sdim void init(uptr InitialCapacity) { 23351282Sdim CapacityBytes = 0; 24351282Sdim Size = 0; 25351282Sdim Data = nullptr; 26351282Sdim reserve(InitialCapacity); 27351282Sdim } 28351282Sdim void destroy() { 29351282Sdim if (Data) 30351282Sdim unmap(Data, CapacityBytes); 31351282Sdim } 32351282Sdim T &operator[](uptr I) { 33351282Sdim DCHECK_LT(I, Size); 34351282Sdim return Data[I]; 35351282Sdim } 36351282Sdim const T &operator[](uptr I) const { 37351282Sdim DCHECK_LT(I, Size); 38351282Sdim return Data[I]; 39351282Sdim } 40351282Sdim void push_back(const T &Element) { 41351282Sdim DCHECK_LE(Size, capacity()); 42351282Sdim if (Size == capacity()) { 43351282Sdim const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1); 44351282Sdim reallocate(NewCapacity); 45351282Sdim } 46351282Sdim memcpy(&Data[Size++], &Element, sizeof(T)); 47351282Sdim } 48351282Sdim T &back() { 49351282Sdim DCHECK_GT(Size, 0); 50351282Sdim return Data[Size - 1]; 51351282Sdim } 52351282Sdim void pop_back() { 53351282Sdim DCHECK_GT(Size, 0); 54351282Sdim Size--; 55351282Sdim } 56351282Sdim uptr size() const { return Size; } 57351282Sdim const T *data() const { return Data; } 58351282Sdim T *data() { return Data; } 59351282Sdim uptr capacity() const { return CapacityBytes / sizeof(T); } 60351282Sdim void reserve(uptr NewSize) { 61351282Sdim // Never downsize internal buffer. 62351282Sdim if (NewSize > capacity()) 63351282Sdim reallocate(NewSize); 64351282Sdim } 65351282Sdim void resize(uptr NewSize) { 66351282Sdim if (NewSize > Size) { 67351282Sdim reserve(NewSize); 68351282Sdim memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 69351282Sdim } 70351282Sdim Size = NewSize; 71351282Sdim } 72351282Sdim 73351282Sdim void clear() { Size = 0; } 74351282Sdim bool empty() const { return size() == 0; } 75351282Sdim 76351282Sdim const T *begin() const { return data(); } 77351282Sdim T *begin() { return data(); } 78351282Sdim const T *end() const { return data() + size(); } 79351282Sdim T *end() { return data() + size(); } 80351282Sdim 81351282Sdimprivate: 82351282Sdim void reallocate(uptr NewCapacity) { 83351282Sdim DCHECK_GT(NewCapacity, 0); 84351282Sdim DCHECK_LE(Size, NewCapacity); 85351282Sdim const uptr NewCapacityBytes = 86351282Sdim roundUpTo(NewCapacity * sizeof(T), getPageSizeCached()); 87360784Sdim T *NewData = 88360784Sdim reinterpret_cast<T *>(map(nullptr, NewCapacityBytes, "scudo:vector")); 89351282Sdim if (Data) { 90351282Sdim memcpy(NewData, Data, Size * sizeof(T)); 91351282Sdim unmap(Data, CapacityBytes); 92351282Sdim } 93351282Sdim Data = NewData; 94351282Sdim CapacityBytes = NewCapacityBytes; 95351282Sdim } 96351282Sdim 97351282Sdim T *Data; 98351282Sdim uptr CapacityBytes; 99351282Sdim uptr Size; 100351282Sdim}; 101351282Sdim 102351282Sdimtemplate <typename T> class Vector : public VectorNoCtor<T> { 103351282Sdimpublic: 104351282Sdim Vector() { VectorNoCtor<T>::init(1); } 105351282Sdim explicit Vector(uptr Count) { 106351282Sdim VectorNoCtor<T>::init(Count); 107351282Sdim this->resize(Count); 108351282Sdim } 109351282Sdim ~Vector() { VectorNoCtor<T>::destroy(); } 110351282Sdim // Disallow copies and moves. 111351282Sdim Vector(const Vector &) = delete; 112351282Sdim Vector &operator=(const Vector &) = delete; 113351282Sdim Vector(Vector &&) = delete; 114351282Sdim Vector &operator=(Vector &&) = delete; 115351282Sdim}; 116351282Sdim 117351282Sdim} // namespace scudo 118351282Sdim 119351282Sdim#endif // SCUDO_VECTOR_H_ 120