10b57cec5SDimitry Andric //===-- vector.h ------------------------------------------------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric 90b57cec5SDimitry Andric #ifndef SCUDO_VECTOR_H_ 100b57cec5SDimitry Andric #define SCUDO_VECTOR_H_ 110b57cec5SDimitry Andric 120b57cec5SDimitry Andric #include "common.h" 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #include <string.h> 150b57cec5SDimitry Andric 160b57cec5SDimitry Andric namespace scudo { 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric // A low-level vector based on map. May incur a significant memory overhead for 190b57cec5SDimitry Andric // small vectors. The current implementation supports only POD types. 200b57cec5SDimitry Andric template <typename T> class VectorNoCtor { 210b57cec5SDimitry Andric public: 220b57cec5SDimitry Andric void init(uptr InitialCapacity) { 230b57cec5SDimitry Andric CapacityBytes = 0; 240b57cec5SDimitry Andric Size = 0; 250b57cec5SDimitry Andric Data = nullptr; 260b57cec5SDimitry Andric reserve(InitialCapacity); 270b57cec5SDimitry Andric } 280b57cec5SDimitry Andric void destroy() { 290b57cec5SDimitry Andric if (Data) 300b57cec5SDimitry Andric unmap(Data, CapacityBytes); 310b57cec5SDimitry Andric } 320b57cec5SDimitry Andric T &operator[](uptr I) { 330b57cec5SDimitry Andric DCHECK_LT(I, Size); 340b57cec5SDimitry Andric return Data[I]; 350b57cec5SDimitry Andric } 360b57cec5SDimitry Andric const T &operator[](uptr I) const { 370b57cec5SDimitry Andric DCHECK_LT(I, Size); 380b57cec5SDimitry Andric return Data[I]; 390b57cec5SDimitry Andric } 400b57cec5SDimitry Andric void push_back(const T &Element) { 410b57cec5SDimitry Andric DCHECK_LE(Size, capacity()); 420b57cec5SDimitry Andric if (Size == capacity()) { 430b57cec5SDimitry Andric const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1); 440b57cec5SDimitry Andric reallocate(NewCapacity); 450b57cec5SDimitry Andric } 460b57cec5SDimitry Andric memcpy(&Data[Size++], &Element, sizeof(T)); 470b57cec5SDimitry Andric } 480b57cec5SDimitry Andric T &back() { 490b57cec5SDimitry Andric DCHECK_GT(Size, 0); 500b57cec5SDimitry Andric return Data[Size - 1]; 510b57cec5SDimitry Andric } 520b57cec5SDimitry Andric void pop_back() { 530b57cec5SDimitry Andric DCHECK_GT(Size, 0); 540b57cec5SDimitry Andric Size--; 550b57cec5SDimitry Andric } 560b57cec5SDimitry Andric uptr size() const { return Size; } 570b57cec5SDimitry Andric const T *data() const { return Data; } 580b57cec5SDimitry Andric T *data() { return Data; } 590b57cec5SDimitry Andric uptr capacity() const { return CapacityBytes / sizeof(T); } 600b57cec5SDimitry Andric void reserve(uptr NewSize) { 610b57cec5SDimitry Andric // Never downsize internal buffer. 620b57cec5SDimitry Andric if (NewSize > capacity()) 630b57cec5SDimitry Andric reallocate(NewSize); 640b57cec5SDimitry Andric } 650b57cec5SDimitry Andric void resize(uptr NewSize) { 660b57cec5SDimitry Andric if (NewSize > Size) { 670b57cec5SDimitry Andric reserve(NewSize); 680b57cec5SDimitry Andric memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 690b57cec5SDimitry Andric } 700b57cec5SDimitry Andric Size = NewSize; 710b57cec5SDimitry Andric } 720b57cec5SDimitry Andric 730b57cec5SDimitry Andric void clear() { Size = 0; } 740b57cec5SDimitry Andric bool empty() const { return size() == 0; } 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric const T *begin() const { return data(); } 770b57cec5SDimitry Andric T *begin() { return data(); } 780b57cec5SDimitry Andric const T *end() const { return data() + size(); } 790b57cec5SDimitry Andric T *end() { return data() + size(); } 800b57cec5SDimitry Andric 810b57cec5SDimitry Andric private: 820b57cec5SDimitry Andric void reallocate(uptr NewCapacity) { 830b57cec5SDimitry Andric DCHECK_GT(NewCapacity, 0); 840b57cec5SDimitry Andric DCHECK_LE(Size, NewCapacity); 850b57cec5SDimitry Andric const uptr NewCapacityBytes = 860b57cec5SDimitry Andric roundUpTo(NewCapacity * sizeof(T), getPageSizeCached()); 870b57cec5SDimitry Andric T *NewData = (T *)map(nullptr, NewCapacityBytes, "scudo:vector"); 880b57cec5SDimitry Andric if (Data) { 890b57cec5SDimitry Andric memcpy(NewData, Data, Size * sizeof(T)); 900b57cec5SDimitry Andric unmap(Data, CapacityBytes); 910b57cec5SDimitry Andric } 920b57cec5SDimitry Andric Data = NewData; 930b57cec5SDimitry Andric CapacityBytes = NewCapacityBytes; 940b57cec5SDimitry Andric } 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric T *Data; 970b57cec5SDimitry Andric uptr CapacityBytes; 980b57cec5SDimitry Andric uptr Size; 990b57cec5SDimitry Andric }; 1000b57cec5SDimitry Andric 1010b57cec5SDimitry Andric template <typename T> class Vector : public VectorNoCtor<T> { 1020b57cec5SDimitry Andric public: 1030b57cec5SDimitry Andric Vector() { VectorNoCtor<T>::init(1); } 1040b57cec5SDimitry Andric explicit Vector(uptr Count) { 1050b57cec5SDimitry Andric VectorNoCtor<T>::init(Count); 1060b57cec5SDimitry Andric this->resize(Count); 1070b57cec5SDimitry Andric } 1080b57cec5SDimitry Andric ~Vector() { VectorNoCtor<T>::destroy(); } 1090b57cec5SDimitry Andric // Disallow copies and moves. 1100b57cec5SDimitry Andric Vector(const Vector &) = delete; 1110b57cec5SDimitry Andric Vector &operator=(const Vector &) = delete; 1120b57cec5SDimitry Andric Vector(Vector &&) = delete; 1130b57cec5SDimitry Andric Vector &operator=(Vector &&) = delete; 1140b57cec5SDimitry Andric }; 1150b57cec5SDimitry Andric 1160b57cec5SDimitry Andric } // namespace scudo 1170b57cec5SDimitry Andric 1180b57cec5SDimitry Andric #endif // SCUDO_VECTOR_H_ 119