TinyPtrVector.h revision 2edc74aa1fb541253f4286a70194960dab69506b
19d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 29d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 39d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// The LLVM Compiler Infrastructure 49d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 59d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// This file is distributed under the University of Illinois Open Source 69d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// License. See LICENSE.TXT for details. 79d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 89d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner//===----------------------------------------------------------------------===// 99d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 109d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#ifndef LLVM_ADT_TINYPTRVECTOR_H 119d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#define LLVM_ADT_TINYPTRVECTOR_H 129d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 13ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#include "llvm/ADT/ArrayRef.h" 149d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#include "llvm/ADT/SmallVector.h" 159d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#include "llvm/ADT/PointerUnion.h" 16ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#include "llvm/Support/Compiler.h" 179d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 189d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnernamespace llvm { 199d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 209d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// TinyPtrVector - This class is specialized for cases where there are 219d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// normally 0 or 1 element in a vector, but is general enough to go beyond that 229d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// when required. 239d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// 249d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// NOTE: This container doesn't allow you to store a null pointer into it. 259d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// 269d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnertemplate <typename EltTy> 279d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnerclass TinyPtrVector { 289d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnerpublic: 299d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner typedef llvm::SmallVector<EltTy, 4> VecTy; 309d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner llvm::PointerUnion<EltTy, VecTy*> Val; 319d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 329d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner TinyPtrVector() {} 339d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 349d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (VecTy *V = Val.template dyn_cast<VecTy*>()) 359d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = new VecTy(*V); 369d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 37ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 38ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 39ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer RHS.Val = (EltTy)0; 40ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer } 41ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#endif 429d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner ~TinyPtrVector() { 439d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (VecTy *V = Val.template dyn_cast<VecTy*>()) 449d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner delete V; 459d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 469d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 47266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner // implicit conversion operator to ArrayRef. 48266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner operator ArrayRef<EltTy>() const { 49266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner if (Val.isNull()) 50266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner return ArrayRef<EltTy>(); 51266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner if (Val.template is<EltTy>()) 52bb9dbb7d6b4f39b74b755795e31b219a5518dd77Eli Friedman return *Val.getAddrOfPtr1(); 53266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner return *Val.template get<VecTy*>(); 54266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner } 55266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner 569d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner bool empty() const { 5722e522e08640be459f237796009cf7666d6d75e7Chris Lattner // This vector can be empty if it contains no element, or if it 5822e522e08640be459f237796009cf7666d6d75e7Chris Lattner // contains a pointer to an empty vector. 599d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (Val.isNull()) return true; 609d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 619d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return Vec->empty(); 629d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return false; 639d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 649d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 659d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner unsigned size() const { 669d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (empty()) 679d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return 0; 6822e522e08640be459f237796009cf7666d6d75e7Chris Lattner if (Val.template is<EltTy>()) 699d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return 1; 7022e522e08640be459f237796009cf7666d6d75e7Chris Lattner return Val.template get<VecTy*>()->size(); 719d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 729d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 73e6f1355c38fb66b0bee35cb4d6ec93f07196d961Benjamin Kramer typedef const EltTy *const_iterator; 74bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis typedef EltTy *iterator; 75bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 76bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator begin() { 7779976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (empty()) 7879976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return 0; 7979976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 8079976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (Val.template is<EltTy>()) 810db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis return Val.getAddrOfPtr1(); 8279976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 8379976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return Val.template get<VecTy *>()->begin(); 8479976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 8579976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner } 86bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator end() { 8779976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (empty()) 8879976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return 0; 8979976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 9079976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (Val.template is<EltTy>()) 9179976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return begin() + 1; 9279976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 9379976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return Val.template get<VecTy *>()->end(); 9479976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner } 9579976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 96bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis const_iterator begin() const { 97bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 98bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 99bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 100bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis const_iterator end() const { 101bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 102bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 103bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 1049d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner EltTy operator[](unsigned i) const { 1059d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(!Val.isNull() && "can't index into an empty vector"); 1069d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) { 1079d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(i == 0 && "tinyvector index out of range"); 1089d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return V; 1099d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1109d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 11122e522e08640be459f237796009cf7666d6d75e7Chris Lattner assert(i < Val.template get<VecTy*>()->size() && 1129d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner "tinyvector index out of range"); 11322e522e08640be459f237796009cf7666d6d75e7Chris Lattner return (*Val.template get<VecTy*>())[i]; 1149d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1159d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1169d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner EltTy front() const { 1179d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(!empty() && "vector empty"); 1189d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) 1199d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return V; 1209d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return Val.template get<VecTy*>()->front(); 1219d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1229d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1232edc74aa1fb541253f4286a70194960dab69506bChris Lattner EltTy back() const { 1242edc74aa1fb541253f4286a70194960dab69506bChris Lattner assert(!empty() && "vector empty"); 1252edc74aa1fb541253f4286a70194960dab69506bChris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) 1262edc74aa1fb541253f4286a70194960dab69506bChris Lattner return V; 1272edc74aa1fb541253f4286a70194960dab69506bChris Lattner return Val.template get<VecTy*>()->back(); 1282edc74aa1fb541253f4286a70194960dab69506bChris Lattner } 1292edc74aa1fb541253f4286a70194960dab69506bChris Lattner 1302edc74aa1fb541253f4286a70194960dab69506bChris Lattner 1319d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner void push_back(EltTy NewVal) { 1329d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(NewVal != 0 && "Can't add a null value"); 1339d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1349d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have nothing, add something. 1359d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (Val.isNull()) { 1369d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = NewVal; 1379d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return; 1389d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1399d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1409d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a single value, convert to a vector. 14122e522e08640be459f237796009cf7666d6d75e7Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) { 1429d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = new VecTy(); 1439d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val.template get<VecTy*>()->push_back(V); 1449d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1459d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1469d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // Add the new value, we know we have a vector. 1479d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val.template get<VecTy*>()->push_back(NewVal); 1489d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1499d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1502edc74aa1fb541253f4286a70194960dab69506bChris Lattner void pop_back() { 1512edc74aa1fb541253f4286a70194960dab69506bChris Lattner // If we have a single value, convert to empty. 1522edc74aa1fb541253f4286a70194960dab69506bChris Lattner if (Val.template is<EltTy>()) 1532edc74aa1fb541253f4286a70194960dab69506bChris Lattner Val = (EltTy)0; 1542edc74aa1fb541253f4286a70194960dab69506bChris Lattner else if (VecTy *Vec = Val.template get<VecTy*>()) 1552edc74aa1fb541253f4286a70194960dab69506bChris Lattner Vec->pop_back(); 1562edc74aa1fb541253f4286a70194960dab69506bChris Lattner } 1572edc74aa1fb541253f4286a70194960dab69506bChris Lattner 1582edc74aa1fb541253f4286a70194960dab69506bChris Lattner 1599d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner void clear() { 1609d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a single value, convert to empty. 161840635741f132a9a10f052cbf3b21e14bc74835aChris Lattner if (Val.template is<EltTy>()) { 1629d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = (EltTy)0; 1639d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 1649d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a vector form, just clear it. 1659d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Vec->clear(); 1669d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 1679d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // Otherwise, we're already empty. 1689d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 169bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 170bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator erase(iterator I) { 171bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // If we have a single value, convert to empty. 172bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis if (Val.template is<EltTy>()) { 173bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis if (I == begin()) 174bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis Val = (EltTy)0; 175bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 176bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // multiple items in a vector; just do the erase, there is no 177bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // benefit to collapsing back to a pointer 178bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return Vec->erase(I); 179bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 180bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 181bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return 0; 182bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 1839d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1849d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnerprivate: 1859d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET. 186ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 187ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET. 188ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#endif 1899d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner}; 1909d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner} // end namespace llvm 1919d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 1929d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#endif 193