10b57cec5SDimitry Andric //===-- sanitizer_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 // This file is shared between sanitizers run-time libraries. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric // Low-fat STL-like vector container. 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric #ifndef SANITIZER_VECTOR_H 160b57cec5SDimitry Andric #define SANITIZER_VECTOR_H 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric #include "sanitizer_common/sanitizer_allocator_internal.h" 190b57cec5SDimitry Andric #include "sanitizer_common/sanitizer_libc.h" 200b57cec5SDimitry Andric 210b57cec5SDimitry Andric namespace __sanitizer { 220b57cec5SDimitry Andric 230b57cec5SDimitry Andric template<typename T> 240b57cec5SDimitry Andric class Vector { 250b57cec5SDimitry Andric public: Vector()2668d75effSDimitry Andric Vector() : begin_(), end_(), last_() {} 270b57cec5SDimitry Andric ~Vector()280b57cec5SDimitry Andric ~Vector() { 290b57cec5SDimitry Andric if (begin_) 300b57cec5SDimitry Andric InternalFree(begin_); 310b57cec5SDimitry Andric } 320b57cec5SDimitry Andric Reset()330b57cec5SDimitry Andric void Reset() { 340b57cec5SDimitry Andric if (begin_) 350b57cec5SDimitry Andric InternalFree(begin_); 360b57cec5SDimitry Andric begin_ = 0; 370b57cec5SDimitry Andric end_ = 0; 380b57cec5SDimitry Andric last_ = 0; 390b57cec5SDimitry Andric } 400b57cec5SDimitry Andric Size()410b57cec5SDimitry Andric uptr Size() const { 420b57cec5SDimitry Andric return end_ - begin_; 430b57cec5SDimitry Andric } 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric T &operator[](uptr i) { 460b57cec5SDimitry Andric DCHECK_LT(i, end_ - begin_); 470b57cec5SDimitry Andric return begin_[i]; 480b57cec5SDimitry Andric } 490b57cec5SDimitry Andric 500b57cec5SDimitry Andric const T &operator[](uptr i) const { 510b57cec5SDimitry Andric DCHECK_LT(i, end_ - begin_); 520b57cec5SDimitry Andric return begin_[i]; 530b57cec5SDimitry Andric } 540b57cec5SDimitry Andric PushBack()550b57cec5SDimitry Andric T *PushBack() { 560b57cec5SDimitry Andric EnsureSize(Size() + 1); 570b57cec5SDimitry Andric T *p = &end_[-1]; 580b57cec5SDimitry Andric internal_memset(p, 0, sizeof(*p)); 590b57cec5SDimitry Andric return p; 600b57cec5SDimitry Andric } 610b57cec5SDimitry Andric PushBack(const T & v)620b57cec5SDimitry Andric T *PushBack(const T& v) { 630b57cec5SDimitry Andric EnsureSize(Size() + 1); 640b57cec5SDimitry Andric T *p = &end_[-1]; 650b57cec5SDimitry Andric internal_memcpy(p, &v, sizeof(*p)); 660b57cec5SDimitry Andric return p; 670b57cec5SDimitry Andric } 680b57cec5SDimitry Andric PopBack()690b57cec5SDimitry Andric void PopBack() { 700b57cec5SDimitry Andric DCHECK_GT(end_, begin_); 710b57cec5SDimitry Andric end_--; 720b57cec5SDimitry Andric } 730b57cec5SDimitry Andric Resize(uptr size)740b57cec5SDimitry Andric void Resize(uptr size) { 750b57cec5SDimitry Andric if (size == 0) { 760b57cec5SDimitry Andric end_ = begin_; 770b57cec5SDimitry Andric return; 780b57cec5SDimitry Andric } 790b57cec5SDimitry Andric uptr old_size = Size(); 800b57cec5SDimitry Andric if (size <= old_size) { 810b57cec5SDimitry Andric end_ = begin_ + size; 820b57cec5SDimitry Andric return; 830b57cec5SDimitry Andric } 840b57cec5SDimitry Andric EnsureSize(size); 850b57cec5SDimitry Andric if (old_size < size) { 86*753f127fSDimitry Andric internal_memset(&begin_[old_size], 0, 87*753f127fSDimitry Andric sizeof(begin_[old_size]) * (size - old_size)); 880b57cec5SDimitry Andric } 890b57cec5SDimitry Andric } 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric private: 920b57cec5SDimitry Andric T *begin_; 930b57cec5SDimitry Andric T *end_; 940b57cec5SDimitry Andric T *last_; 950b57cec5SDimitry Andric EnsureSize(uptr size)960b57cec5SDimitry Andric void EnsureSize(uptr size) { 970b57cec5SDimitry Andric if (size <= Size()) 980b57cec5SDimitry Andric return; 990b57cec5SDimitry Andric if (size <= (uptr)(last_ - begin_)) { 1000b57cec5SDimitry Andric end_ = begin_ + size; 1010b57cec5SDimitry Andric return; 1020b57cec5SDimitry Andric } 1030b57cec5SDimitry Andric uptr cap0 = last_ - begin_; 1040b57cec5SDimitry Andric uptr cap = cap0 * 5 / 4; // 25% growth 1050b57cec5SDimitry Andric if (cap == 0) 1060b57cec5SDimitry Andric cap = 16; 1070b57cec5SDimitry Andric if (cap < size) 1080b57cec5SDimitry Andric cap = size; 1090b57cec5SDimitry Andric T *p = (T*)InternalAlloc(cap * sizeof(T)); 1100b57cec5SDimitry Andric if (cap0) { 1110b57cec5SDimitry Andric internal_memcpy(p, begin_, cap0 * sizeof(T)); 1120b57cec5SDimitry Andric InternalFree(begin_); 1130b57cec5SDimitry Andric } 1140b57cec5SDimitry Andric begin_ = p; 1150b57cec5SDimitry Andric end_ = begin_ + size; 1160b57cec5SDimitry Andric last_ = begin_ + cap; 1170b57cec5SDimitry Andric } 1180b57cec5SDimitry Andric 1190b57cec5SDimitry Andric Vector(const Vector&); 1200b57cec5SDimitry Andric void operator=(const Vector&); 1210b57cec5SDimitry Andric }; 1220b57cec5SDimitry Andric } // namespace __sanitizer 1230b57cec5SDimitry Andric 1240b57cec5SDimitry Andric #endif // #ifndef SANITIZER_VECTOR_H 125