sanitizer_vector.h revision 360784 
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() + 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      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
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