16bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===- ThreadSafetyUtil.h --------------------------------------*- C++ --*-===// 26bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 36bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The LLVM Compiler Infrastructure 46bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 56bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// This file is distributed under the University of Illinois Open Source 66bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// License. See LICENSE.TXT for details. 76bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 86bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===----------------------------------------------------------------------===// 96bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// This file defines some basic utility classes for use by ThreadSafetyTIL.h 116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===----------------------------------------------------------------------===// 136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 14176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H 15176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H 166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 170e2c34f92f00628d48968dfea096d36381f494cbStephen Hines#include "clang/AST/ExprCXX.h" 186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/ADT/StringRef.h" 196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/Support/AlignOf.h" 206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/Support/Allocator.h" 216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "llvm/Support/Compiler.h" 226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include <cassert> 236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include <cstddef> 24176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#include <ostream> 250e2c34f92f00628d48968dfea096d36381f494cbStephen Hines#include <utility> 260e2c34f92f00628d48968dfea096d36381f494cbStephen Hines#include <vector> 276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace clang { 296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace threadSafety { 306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace til { 316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Simple wrapper class to abstract away from the details of memory management. 336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// SExprs are allocated in pools, and deallocated all at once. 346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass MemRegionRef { 356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines union AlignmentType { 376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines double d; 386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void *p; 396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines long double dd; 406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines long long ii; 416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines MemRegionRef() : Allocator(nullptr) {} 456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} 466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void *allocate(size_t Sz) { 486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment); 496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } 526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines template <typename T> T *allocateT(size_t NumElems) { 546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Allocator->Allocate<T>(NumElems); 556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines llvm::BumpPtrAllocator *Allocator; 596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace til 636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace threadSafety 646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace clang 656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline void *operator new(size_t Sz, 686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines clang::threadSafety::til::MemRegionRef &R) { 696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return R.allocate(Sz); 706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace clang { 746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace threadSafety { 756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesstd::string getSourceLiteralString(const clang::Expr *CE); 776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesusing llvm::StringRef; 796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesusing clang::SourceLocation; 806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace til { 826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// A simple fixed size array class that does not manage its own memory, 856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// suitable for use with bump pointer allocation. 866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate <class T> class SimpleArray { 876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SimpleArray() : Data(nullptr), Size(0), Capacity(0) {} 896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) 906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Data(Dat), Size(Sz), Capacity(Cp) {} 916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SimpleArray(MemRegionRef A, size_t Cp) 926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} 936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SimpleArray(SimpleArray<T> &&A) 946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { 956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines A.Data = nullptr; 966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines A.Size = 0; 976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines A.Capacity = 0; 986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SimpleArray &operator=(SimpleArray &&RHS) { 1016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (this != &RHS) { 1026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = RHS.Data; 1036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Size = RHS.Size; 1046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Capacity = RHS.Capacity; 1056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RHS.Data = nullptr; 1076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines RHS.Size = RHS.Capacity = 0; 1086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return *this; 1106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 112c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Reserve space for at least Ncp items, reallocating if necessary. 1136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void reserve(size_t Ncp, MemRegionRef A) { 114c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (Ncp <= Capacity) 1156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; 1166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T *Odata = Data; 1176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = A.allocateT<T>(Ncp); 1186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Capacity = Ncp; 1196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines memcpy(Data, Odata, sizeof(T) * Size); 1206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; 1216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 123c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Reserve space for at least N more items. 124c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void reserveCheck(size_t N, MemRegionRef A) { 125c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (Capacity == 0) 126c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines reserve(u_max(InitialCapacity, N), A); 127c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines else if (Size + N < Capacity) 128c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines reserve(u_max(Size + N, Capacity * 2), A); 129c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 130c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typedef T *iterator; 1326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typedef const T *const_iterator; 1333ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar typedef std::reverse_iterator<iterator> reverse_iterator; 1343ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t size() const { return Size; } 1376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t capacity() const { return Capacity; } 1386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T &operator[](unsigned i) { 1406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(i < Size && "Array index out of bounds."); 1416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Data[i]; 1426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const T &operator[](unsigned i) const { 1446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(i < Size && "Array index out of bounds."); 1456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Data[i]; 1466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 147176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines T &back() { 148176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines assert(Size && "No elements in the array."); 149176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Data[Size - 1]; 150176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 151176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const T &back() const { 152176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines assert(Size && "No elements in the array."); 153176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Data[Size - 1]; 154176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines iterator begin() { return Data; } 157176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines iterator end() { return Data + Size; } 158176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 159176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const_iterator begin() const { return Data; } 160176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const_iterator end() const { return Data + Size; } 1616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const_iterator cbegin() const { return Data; } 163176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const_iterator cend() const { return Data + Size; } 1646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1653ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar reverse_iterator rbegin() { return reverse_iterator(end()); } 1663ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar reverse_iterator rend() { return reverse_iterator(begin()); } 1673ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar 1683ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar const_reverse_iterator rbegin() const { 1693ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return const_reverse_iterator(end()); 1703ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 1713ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar const_reverse_iterator rend() const { 1723ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return const_reverse_iterator(begin()); 1733ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 1743ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar 1756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void push_back(const T &Elem) { 1766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Size < Capacity); 1776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data[Size++] = Elem; 1786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 180176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // drop last n elements from array 181176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void drop(unsigned n = 0) { 182176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines assert(Size > n); 183176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Size -= n; 184176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 185176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void setValues(unsigned Sz, const T& C) { 1876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Sz <= Capacity); 1886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Size = Sz; 1896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines for (unsigned i = 0; i < Sz; ++i) { 1906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data[i] = C; 1916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines template <class Iter> unsigned append(Iter I, Iter E) { 1956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t Osz = Size; 1966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t J = Osz; 1976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines for (; J < Capacity && I != E; ++J, ++I) 1986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data[J] = *I; 1996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Size = J; 2006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return J - Osz; 2016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2033ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar llvm::iterator_range<reverse_iterator> reverse() { 2043ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return llvm::make_range(rbegin(), rend()); 2053ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 2063ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar llvm::iterator_range<const_reverse_iterator> reverse() const { 2073ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return llvm::make_range(rbegin(), rend()); 2083ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 209176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 2106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 211c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // std::max is annoying here, because it requires a reference, 212c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // thus forcing InitialCapacity to be initialized outside the .h file. 213c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; } 214c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 215c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines static const size_t InitialCapacity = 4; 216c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 2170e2c34f92f00628d48968dfea096d36381f494cbStephen Hines SimpleArray(const SimpleArray<T> &A) = delete; 2186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T *Data; 2206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t Size; 2216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines size_t Capacity; 2226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 2236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 224176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 2256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace til 2266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// A copy on write vector. 2296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The vector can be in one of three states: 2306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// * invalid -- no operations are permitted. 2316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// * read-only -- read operations are permitted. 2326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// * writable -- read and write operations are permitted. 2336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The init(), destroy(), and makeWritable() methods will change state. 2346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<typename T> 2356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass CopyOnWriteVector { 2366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines class VectorData { 2376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines public: 2386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VectorData() : NumRefs(1) { } 2396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { } 2406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned NumRefs; 2426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines std::vector<T> Vect; 2436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 2446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // No copy constructor or copy assignment. Use clone() with move assignment. 2460e2c34f92f00628d48968dfea096d36381f494cbStephen Hines CopyOnWriteVector(const CopyOnWriteVector &V) = delete; 2470e2c34f92f00628d48968dfea096d36381f494cbStephen Hines void operator=(const CopyOnWriteVector &V) = delete; 2486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 2506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CopyOnWriteVector() : Data(nullptr) {} 2516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } 2526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ~CopyOnWriteVector() { destroy(); } 2536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Returns true if this holds a valid vector. 2556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool valid() const { return Data; } 2566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Returns true if this vector is writable. 2586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool writable() const { return Data && Data->NumRefs == 1; } 2596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // If this vector is not valid, initialize it to a valid vector. 2616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void init() { 2626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!Data) { 2636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = new VectorData(); 2646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Destroy this vector; thus making it invalid. 2686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void destroy() { 2696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!Data) 2706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; 2716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Data->NumRefs <= 1) 2726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines delete Data; 2736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines else 2746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines --Data->NumRefs; 2756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = nullptr; 2766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Make this vector writable, creating a copy if needed. 2796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void makeWritable() { 2806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!Data) { 2816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = new VectorData(); 2826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; 2836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Data->NumRefs == 1) 2856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; // already writeable. 2866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines --Data->NumRefs; 2876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = new VectorData(*Data); 2886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Create a lazy copy of this vector. 2916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } 2926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { 2946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines destroy(); 2956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data = V.Data; 2966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines V.Data = nullptr; 2976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return *this; 2986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typedef typename std::vector<T>::const_iterator const_iterator; 3016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const std::vector<T> &elements() const { return Data->Vect; } 3036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const_iterator begin() const { return elements().cbegin(); } 3056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const_iterator end() const { return elements().cend(); } 3066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const T& operator[](unsigned i) const { return elements()[i]; } 3086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned size() const { return Data ? elements().size() : 0; } 3106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Return true if V and this vector refer to the same data. 3126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; } 3136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Clear vector. The vector must be writable. 3156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void clear() { 3166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(writable() && "Vector is not writable!"); 3176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data->Vect.clear(); 3186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Push a new element onto the end. The vector must be writable. 3216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void push_back(const T &Elem) { 3226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(writable() && "Vector is not writable!"); 3236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data->Vect.push_back(Elem); 3246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Gets a mutable reference to the element at index(i). 3276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // The vector must be writable. 3286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T& elem(unsigned i) { 3296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(writable() && "Vector is not writable!"); 3306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Data->Vect[i]; 3316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Drops elements from the back until the vector has size i. 3346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void downsize(unsigned i) { 3356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(writable() && "Vector is not writable!"); 3366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); 3376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 3406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CopyOnWriteVector(VectorData *D) : Data(D) { 3416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!Data) 3426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return; 3436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ++Data->NumRefs; 3446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VectorData *Data; 3476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 3486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 350176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesinline std::ostream& operator<<(std::ostream& ss, const StringRef str) { 351176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return ss.write(str.data(), str.size()); 352176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines} 353176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 354176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 3556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace threadSafety 3566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace clang 3576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H 359