ThreadSafetyUtil.h revision ef8225444452a1486bd721f3285301fe84643b00
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