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