1//===-- tsan_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 a part of ThreadSanitizer (TSan), a race detector.
11//
12//===----------------------------------------------------------------------===//
13
14// Low-fat STL-like vector container.
15
16#ifndef TSAN_VECTOR_H
17#define TSAN_VECTOR_H
18
19#include "tsan_defs.h"
20#include "tsan_mman.h"
21
22namespace __tsan {
23
24template<typename T>
25class Vector {
26 public:
27  explicit Vector(MBlockType typ)
28      : typ_(typ)
29      , begin_()
30      , end_()
31      , last_() {
32  }
33
34  ~Vector() {
35    if (begin_)
36      internal_free(begin_);
37  }
38
39  void Reset() {
40    if (begin_)
41      internal_free(begin_);
42    begin_ = 0;
43    end_ = 0;
44    last_ = 0;
45  }
46
47  uptr Size() const {
48    return end_ - begin_;
49  }
50
51  T &operator[](uptr i) {
52    DCHECK_LT(i, end_ - begin_);
53    return begin_[i];
54  }
55
56  const T &operator[](uptr i) const {
57    DCHECK_LT(i, end_ - begin_);
58    return begin_[i];
59  }
60
61  T *PushBack() {
62    EnsureSize(Size() + 1);
63    T *p = &end_[-1];
64    internal_memset(p, 0, sizeof(*p));
65    return p;
66  }
67
68  T *PushBack(const T& v) {
69    EnsureSize(Size() + 1);
70    T *p = &end_[-1];
71    internal_memcpy(p, &v, sizeof(*p));
72    return p;
73  }
74
75  void PopBack() {
76    DCHECK_GT(end_, begin_);
77    end_--;
78  }
79
80  void Resize(uptr size) {
81    if (size == 0) {
82      end_ = begin_;
83      return;
84    }
85    uptr old_size = Size();
86    EnsureSize(size);
87    if (old_size < size) {
88      for (uptr i = old_size; i < size; i++)
89        internal_memset(&begin_[i], 0, sizeof(begin_[i]));
90    }
91  }
92
93 private:
94  const MBlockType typ_;
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*)internal_alloc(typ_, cap * sizeof(T));
113    if (cap0) {
114      internal_memcpy(p, begin_, cap0 * sizeof(T));
115      internal_free(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 __tsan
126
127#endif  // #ifndef TSAN_VECTOR_H
128