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 
21 namespace __sanitizer {
22 
23 template<typename T>
24 class Vector {
25  public:
Vector()26   Vector() : begin_(), end_(), last_() {}
27 
~Vector()28   ~Vector() {
29     if (begin_)
30       InternalFree(begin_);
31   }
32 
Reset()33   void Reset() {
34     if (begin_)
35       InternalFree(begin_);
36     begin_ = 0;
37     end_ = 0;
38     last_ = 0;
39   }
40 
Size()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 
PushBack()55   T *PushBack() {
56     EnsureSize(Size() + 1);
57     T *p = &end_[-1];
58     internal_memset(p, 0, sizeof(*p));
59     return p;
60   }
61 
PushBack(const T & v)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 
PopBack()69   void PopBack() {
70     DCHECK_GT(end_, begin_);
71     end_--;
72   }
73 
Resize(uptr size)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       for (uptr i = old_size; i < size; i++)
87         internal_memset(&begin_[i], 0, sizeof(begin_[i]));
88     }
89   }
90 
91  private:
92   T *begin_;
93   T *end_;
94   T *last_;
95 
EnsureSize(uptr size)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(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