125 lines · c
1//===-- sanitizer_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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is shared between sanitizers run-time libraries.10//11//===----------------------------------------------------------------------===//12 13// Low-fat STL-like vector container.14 15#ifndef SANITIZER_VECTOR_H16#define SANITIZER_VECTOR_H17 18#include "sanitizer_common/sanitizer_allocator_internal.h"19#include "sanitizer_common/sanitizer_libc.h"20 21namespace __sanitizer {22 23template<typename T>24class Vector {25 public:26 Vector() : begin_(), end_(), last_() {}27 28 ~Vector() {29 if (begin_)30 InternalFree(begin_);31 }32 33 void Reset() {34 if (begin_)35 InternalFree(begin_);36 begin_ = 0;37 end_ = 0;38 last_ = 0;39 }40 41 uptr Size() const {42 return end_ - begin_;43 }44 45 T &operator[](uptr i) {46 DCHECK_LT(i, end_ - begin_);47 return begin_[i];48 }49 50 const T &operator[](uptr i) const {51 DCHECK_LT(i, end_ - begin_);52 return begin_[i];53 }54 55 T *PushBack() {56 EnsureSize(Size() + 1);57 T *p = &end_[-1];58 internal_memset(p, 0, sizeof(*p));59 return p;60 }61 62 T *PushBack(const T& v) {63 EnsureSize(Size() + 1);64 T *p = &end_[-1];65 internal_memcpy(p, &v, sizeof(*p));66 return p;67 }68 69 void PopBack() {70 DCHECK_GT(end_, begin_);71 end_--;72 }73 74 void Resize(uptr size) {75 if (size == 0) {76 end_ = begin_;77 return;78 }79 uptr old_size = Size();80 if (size <= old_size) {81 end_ = begin_ + size;82 return;83 }84 EnsureSize(size);85 if (old_size < size) {86 internal_memset(&begin_[old_size], 0,87 sizeof(begin_[old_size]) * (size - old_size));88 }89 }90 91 private:92 T *begin_;93 T *end_;94 T *last_;95 96 void EnsureSize(uptr size) {97 if (size <= Size())98 return;99 if (size <= (uptr)(last_ - begin_)) {100 end_ = begin_ + size;101 return;102 }103 uptr cap0 = last_ - begin_;104 uptr cap = cap0 * 5 / 4; // 25% growth105 if (cap == 0)106 cap = 16;107 if (cap < size)108 cap = size;109 T *p = (T*)InternalAlloc(cap * sizeof(T));110 if (cap0) {111 internal_memcpy(p, begin_, cap0 * sizeof(T));112 InternalFree(begin_);113 }114 begin_ = p;115 end_ = begin_ + size;116 last_ = begin_ + cap;117 }118 119 Vector(const Vector&);120 void operator=(const Vector&);121};122} // namespace __sanitizer123 124#endif // #ifndef SANITIZER_VECTOR_H125