1//===- ThreadSafetyUtil.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 defines some basic utility classes for use by ThreadSafetyTIL.h
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_THREAD_SAFETY_UTIL_H
15#define LLVM_CLANG_THREAD_SAFETY_UTIL_H
16
17#include "llvm/ADT/StringRef.h"
18#include "llvm/Support/AlignOf.h"
19#include "llvm/Support/Allocator.h"
20#include "llvm/Support/Compiler.h"
21#include "clang/AST/ExprCXX.h"
22
23#include <cassert>
24#include <cstddef>
25#include <vector>
26#include <utility>
27
28namespace clang {
29namespace threadSafety {
30namespace til {
31
32// Simple wrapper class to abstract away from the details of memory management.
33// SExprs are allocated in pools, and deallocated all at once.
34class MemRegionRef {
35private:
36  union AlignmentType {
37    double d;
38    void *p;
39    long double dd;
40    long long ii;
41  };
42
43public:
44  MemRegionRef() : Allocator(nullptr) {}
45  MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
46
47  void *allocate(size_t Sz) {
48    return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment);
49  }
50
51  template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
52
53  template <typename T> T *allocateT(size_t NumElems) {
54    return Allocator->Allocate<T>(NumElems);
55  }
56
57private:
58  llvm::BumpPtrAllocator *Allocator;
59};
60
61
62} // end namespace til
63} // end namespace threadSafety
64} // end namespace clang
65
66
67inline void *operator new(size_t Sz,
68                          clang::threadSafety::til::MemRegionRef &R) {
69  return R.allocate(Sz);
70}
71
72
73namespace clang {
74namespace threadSafety {
75
76std::string getSourceLiteralString(const clang::Expr *CE);
77
78using llvm::StringRef;
79using clang::SourceLocation;
80
81namespace til {
82
83
84// A simple fixed size array class that does not manage its own memory,
85// suitable for use with bump pointer allocation.
86template <class T> class SimpleArray {
87public:
88  SimpleArray() : Data(nullptr), Size(0), Capacity(0) {}
89  SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
90      : Data(Dat), Size(Sz), Capacity(Cp) {}
91  SimpleArray(MemRegionRef A, size_t Cp)
92      : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {}
93  SimpleArray(SimpleArray<T> &&A)
94      : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
95    A.Data = nullptr;
96    A.Size = 0;
97    A.Capacity = 0;
98  }
99
100  SimpleArray &operator=(SimpleArray &&RHS) {
101    if (this != &RHS) {
102      Data = RHS.Data;
103      Size = RHS.Size;
104      Capacity = RHS.Capacity;
105
106      RHS.Data = nullptr;
107      RHS.Size = RHS.Capacity = 0;
108    }
109    return *this;
110  }
111
112  // Reserve space for at least Ncp items, reallocating if necessary.
113  void reserve(size_t Ncp, MemRegionRef A) {
114    if (Ncp <= Capacity)
115      return;
116    T *Odata = Data;
117    Data = A.allocateT<T>(Ncp);
118    Capacity = Ncp;
119    memcpy(Data, Odata, sizeof(T) * Size);
120    return;
121  }
122
123  // Reserve space for at least N more items.
124  void reserveCheck(size_t N, MemRegionRef A) {
125    if (Capacity == 0)
126      reserve(u_max(InitialCapacity, N), A);
127    else if (Size + N < Capacity)
128      reserve(u_max(Size + N, Capacity * 2), A);
129  }
130
131  typedef T *iterator;
132  typedef const T *const_iterator;
133
134  size_t size() const { return Size; }
135  size_t capacity() const { return Capacity; }
136
137  T &operator[](unsigned i) {
138    assert(i < Size && "Array index out of bounds.");
139    return Data[i];
140  }
141  const T &operator[](unsigned i) const {
142    assert(i < Size && "Array index out of bounds.");
143    return Data[i];
144  }
145
146  iterator begin() { return Data; }
147  iterator end() { return Data + Size; }
148
149  const_iterator cbegin() const { return Data; }
150  const_iterator cend() const { return Data + Size; }
151
152  void push_back(const T &Elem) {
153    assert(Size < Capacity);
154    Data[Size++] = Elem;
155  }
156
157  void setValues(unsigned Sz, const T& C) {
158    assert(Sz <= Capacity);
159    Size = Sz;
160    for (unsigned i = 0; i < Sz; ++i) {
161      Data[i] = C;
162    }
163  }
164
165  template <class Iter> unsigned append(Iter I, Iter E) {
166    size_t Osz = Size;
167    size_t J = Osz;
168    for (; J < Capacity && I != E; ++J, ++I)
169      Data[J] = *I;
170    Size = J;
171    return J - Osz;
172  }
173
174private:
175  // std::max is annoying here, because it requires a reference,
176  // thus forcing InitialCapacity to be initialized outside the .h file.
177  size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
178
179  static const size_t InitialCapacity = 4;
180
181  SimpleArray(const SimpleArray<T> &A) LLVM_DELETED_FUNCTION;
182
183  T *Data;
184  size_t Size;
185  size_t Capacity;
186};
187
188}  // end namespace til
189
190
191// A copy on write vector.
192// The vector can be in one of three states:
193// * invalid -- no operations are permitted.
194// * read-only -- read operations are permitted.
195// * writable -- read and write operations are permitted.
196// The init(), destroy(), and makeWritable() methods will change state.
197template<typename T>
198class CopyOnWriteVector {
199  class VectorData {
200  public:
201    VectorData() : NumRefs(1) { }
202    VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { }
203
204    unsigned NumRefs;
205    std::vector<T> Vect;
206  };
207
208  // No copy constructor or copy assignment.  Use clone() with move assignment.
209  CopyOnWriteVector(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
210  void operator=(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
211
212public:
213  CopyOnWriteVector() : Data(nullptr) {}
214  CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
215  ~CopyOnWriteVector() { destroy(); }
216
217  // Returns true if this holds a valid vector.
218  bool valid() const  { return Data; }
219
220  // Returns true if this vector is writable.
221  bool writable() const { return Data && Data->NumRefs == 1; }
222
223  // If this vector is not valid, initialize it to a valid vector.
224  void init() {
225    if (!Data) {
226      Data = new VectorData();
227    }
228  }
229
230  // Destroy this vector; thus making it invalid.
231  void destroy() {
232    if (!Data)
233      return;
234    if (Data->NumRefs <= 1)
235      delete Data;
236    else
237      --Data->NumRefs;
238    Data = nullptr;
239  }
240
241  // Make this vector writable, creating a copy if needed.
242  void makeWritable() {
243    if (!Data) {
244      Data = new VectorData();
245      return;
246    }
247    if (Data->NumRefs == 1)
248      return;   // already writeable.
249    --Data->NumRefs;
250    Data = new VectorData(*Data);
251  }
252
253  // Create a lazy copy of this vector.
254  CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
255
256  CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
257    destroy();
258    Data = V.Data;
259    V.Data = nullptr;
260    return *this;
261  }
262
263  typedef typename std::vector<T>::const_iterator const_iterator;
264
265  const std::vector<T> &elements() const { return Data->Vect; }
266
267  const_iterator begin() const { return elements().cbegin(); }
268  const_iterator end() const { return elements().cend(); }
269
270  const T& operator[](unsigned i) const { return elements()[i]; }
271
272  unsigned size() const { return Data ? elements().size() : 0; }
273
274  // Return true if V and this vector refer to the same data.
275  bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
276
277  // Clear vector.  The vector must be writable.
278  void clear() {
279    assert(writable() && "Vector is not writable!");
280    Data->Vect.clear();
281  }
282
283  // Push a new element onto the end.  The vector must be writable.
284  void push_back(const T &Elem) {
285    assert(writable() && "Vector is not writable!");
286    Data->Vect.push_back(Elem);
287  }
288
289  // Gets a mutable reference to the element at index(i).
290  // The vector must be writable.
291  T& elem(unsigned i) {
292    assert(writable() && "Vector is not writable!");
293    return Data->Vect[i];
294  }
295
296  // Drops elements from the back until the vector has size i.
297  void downsize(unsigned i) {
298    assert(writable() && "Vector is not writable!");
299    Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
300  }
301
302private:
303  CopyOnWriteVector(VectorData *D) : Data(D) {
304    if (!Data)
305      return;
306    ++Data->NumRefs;
307  }
308
309  VectorData *Data;
310};
311
312
313} // end namespace threadSafety
314} // end namespace clang
315
316#endif  // LLVM_CLANG_THREAD_SAFETY_UTIL_H
317