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 125f757f3fSDimitry Andric #include "mem_map.h" 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #include <string.h> 150b57cec5SDimitry Andric 160b57cec5SDimitry Andric namespace scudo { 170b57cec5SDimitry Andric 185f757f3fSDimitry Andric // A low-level vector based on map. It stores the contents inline up to a fixed 195f757f3fSDimitry Andric // capacity, or in an external memory buffer if it grows bigger than that. May 205f757f3fSDimitry Andric // incur a significant memory overhead for small vectors. The current 215f757f3fSDimitry Andric // implementation supports only POD types. 225f757f3fSDimitry Andric // 235f757f3fSDimitry Andric // NOTE: This class is not meant to be used directly, use Vector<T> instead. 240b57cec5SDimitry Andric template <typename T> class VectorNoCtor { 250b57cec5SDimitry Andric public: 260b57cec5SDimitry Andric T &operator[](uptr I) { 270b57cec5SDimitry Andric DCHECK_LT(I, Size); 280b57cec5SDimitry Andric return Data[I]; 290b57cec5SDimitry Andric } 300b57cec5SDimitry Andric const T &operator[](uptr I) const { 310b57cec5SDimitry Andric DCHECK_LT(I, Size); 320b57cec5SDimitry Andric return Data[I]; 330b57cec5SDimitry Andric } push_back(const T & Element)340b57cec5SDimitry Andric void push_back(const T &Element) { 350b57cec5SDimitry Andric DCHECK_LE(Size, capacity()); 360b57cec5SDimitry Andric if (Size == capacity()) { 3706c3fb27SDimitry Andric const uptr NewCapacity = roundUpPowerOfTwo(Size + 1); 380b57cec5SDimitry Andric reallocate(NewCapacity); 390b57cec5SDimitry Andric } 400b57cec5SDimitry Andric memcpy(&Data[Size++], &Element, sizeof(T)); 410b57cec5SDimitry Andric } back()420b57cec5SDimitry Andric T &back() { 430b57cec5SDimitry Andric DCHECK_GT(Size, 0); 440b57cec5SDimitry Andric return Data[Size - 1]; 450b57cec5SDimitry Andric } pop_back()460b57cec5SDimitry Andric void pop_back() { 470b57cec5SDimitry Andric DCHECK_GT(Size, 0); 480b57cec5SDimitry Andric Size--; 490b57cec5SDimitry Andric } size()500b57cec5SDimitry Andric uptr size() const { return Size; } data()510b57cec5SDimitry Andric const T *data() const { return Data; } data()520b57cec5SDimitry Andric T *data() { return Data; } capacity()53349cc55cSDimitry Andric constexpr uptr capacity() const { return CapacityBytes / sizeof(T); } reserve(uptr NewSize)540b57cec5SDimitry Andric void reserve(uptr NewSize) { 550b57cec5SDimitry Andric // Never downsize internal buffer. 560b57cec5SDimitry Andric if (NewSize > capacity()) 570b57cec5SDimitry Andric reallocate(NewSize); 580b57cec5SDimitry Andric } resize(uptr NewSize)590b57cec5SDimitry Andric void resize(uptr NewSize) { 600b57cec5SDimitry Andric if (NewSize > Size) { 610b57cec5SDimitry Andric reserve(NewSize); 620b57cec5SDimitry Andric memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 630b57cec5SDimitry Andric } 640b57cec5SDimitry Andric Size = NewSize; 650b57cec5SDimitry Andric } 660b57cec5SDimitry Andric clear()670b57cec5SDimitry Andric void clear() { Size = 0; } empty()680b57cec5SDimitry Andric bool empty() const { return size() == 0; } 690b57cec5SDimitry Andric begin()700b57cec5SDimitry Andric const T *begin() const { return data(); } begin()710b57cec5SDimitry Andric T *begin() { return data(); } end()720b57cec5SDimitry Andric const T *end() const { return data() + size(); } end()730b57cec5SDimitry Andric T *end() { return data() + size(); } 740b57cec5SDimitry Andric 755f757f3fSDimitry Andric protected: 765f757f3fSDimitry Andric constexpr void init(uptr InitialCapacity = 0) { 775f757f3fSDimitry Andric Data = &LocalData[0]; 785f757f3fSDimitry Andric CapacityBytes = sizeof(LocalData); 795f757f3fSDimitry Andric if (InitialCapacity > capacity()) 805f757f3fSDimitry Andric reserve(InitialCapacity); 815f757f3fSDimitry Andric } destroy()825f757f3fSDimitry Andric void destroy() { 835f757f3fSDimitry Andric if (Data != &LocalData[0]) 845f757f3fSDimitry Andric ExternalBuffer.unmap(ExternalBuffer.getBase(), 855f757f3fSDimitry Andric ExternalBuffer.getCapacity()); 865f757f3fSDimitry Andric } 875f757f3fSDimitry Andric 880b57cec5SDimitry Andric private: reallocate(uptr NewCapacity)890b57cec5SDimitry Andric void reallocate(uptr NewCapacity) { 900b57cec5SDimitry Andric DCHECK_GT(NewCapacity, 0); 910b57cec5SDimitry Andric DCHECK_LE(Size, NewCapacity); 925f757f3fSDimitry Andric 935f757f3fSDimitry Andric MemMapT NewExternalBuffer; 9406c3fb27SDimitry Andric NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached()); 955f757f3fSDimitry Andric NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector"); 965f757f3fSDimitry Andric T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase()); 975f757f3fSDimitry Andric 985f757f3fSDimitry Andric memcpy(NewExternalData, Data, Size * sizeof(T)); 99fe6060f1SDimitry Andric destroy(); 1005f757f3fSDimitry Andric 1015f757f3fSDimitry Andric Data = NewExternalData; 102fe6060f1SDimitry Andric CapacityBytes = NewCapacity; 1035f757f3fSDimitry Andric ExternalBuffer = NewExternalBuffer; 1040b57cec5SDimitry Andric } 1050b57cec5SDimitry Andric 106fe6060f1SDimitry Andric T *Data = nullptr; 107fe6060f1SDimitry Andric uptr CapacityBytes = 0; 108fe6060f1SDimitry Andric uptr Size = 0; 1095f757f3fSDimitry Andric 1105f757f3fSDimitry Andric T LocalData[256 / sizeof(T)] = {}; 1115f757f3fSDimitry Andric MemMapT ExternalBuffer; 1120b57cec5SDimitry Andric }; 1130b57cec5SDimitry Andric 1140b57cec5SDimitry Andric template <typename T> class Vector : public VectorNoCtor<T> { 1150b57cec5SDimitry Andric public: Vector()116349cc55cSDimitry Andric constexpr Vector() { VectorNoCtor<T>::init(); } Vector(uptr Count)1170b57cec5SDimitry Andric explicit Vector(uptr Count) { 1180b57cec5SDimitry Andric VectorNoCtor<T>::init(Count); 1190b57cec5SDimitry Andric this->resize(Count); 1200b57cec5SDimitry Andric } ~Vector()1210b57cec5SDimitry Andric ~Vector() { VectorNoCtor<T>::destroy(); } 1220b57cec5SDimitry Andric // Disallow copies and moves. 1230b57cec5SDimitry Andric Vector(const Vector &) = delete; 1240b57cec5SDimitry Andric Vector &operator=(const Vector &) = delete; 1250b57cec5SDimitry Andric Vector(Vector &&) = delete; 1260b57cec5SDimitry Andric Vector &operator=(Vector &&) = delete; 1270b57cec5SDimitry Andric }; 1280b57cec5SDimitry Andric 1290b57cec5SDimitry Andric } // namespace scudo 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric #endif // SCUDO_VECTOR_H_ 132