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-exception
6//
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_H
16#define SANITIZER_VECTOR_H
17
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: 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: 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% growth
105 if (cap == 0)
106 cap = 16;
107 if (cap < size)
108 cap = size;
109 T *p = (T*)InternalAlloc(size: 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 __sanitizer
123
124#endif // #ifndef SANITIZER_VECTOR_H
125