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