TinyPtrVector.h revision 2edc74aa1fb541253f4286a70194960dab69506b
1afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 2afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg// 3afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg// The LLVM Compiler Infrastructure 4e9bf776711b22ce336cd462adf534ad3e2d61eecKeith Whitwell// 5afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg// This file is distributed under the University of Illinois Open Source 671dea349d2be623b7819389428b0d6a124e8d184Brian Paul// License. See LICENSE.TXT for details. 7afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg// 8afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg//===----------------------------------------------------------------------===// 9afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 10afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#ifndef LLVM_ADT_TINYPTRVECTOR_H 11afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define LLVM_ADT_TINYPTRVECTOR_H 12afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 13afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#include "llvm/ADT/ArrayRef.h" 14afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#include "llvm/ADT/SmallVector.h" 15afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#include "llvm/ADT/PointerUnion.h" 16afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#include "llvm/Support/Compiler.h" 17afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 18afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgnamespace llvm { 19afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 20afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// TinyPtrVector - This class is specialized for cases where there are 21afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// normally 0 or 1 element in a vector, but is general enough to go beyond that 22afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// when required. 23afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// 24afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// NOTE: This container doesn't allow you to store a null pointer into it. 25afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/// 26afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgtemplate <typename EltTy> 27afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgclass TinyPtrVector { 28afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgpublic: 29afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg typedef llvm::SmallVector<EltTy, 4> VecTy; 30afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg llvm::PointerUnion<EltTy, VecTy*> Val; 31b5b5c52034840dbfcd3f76a9e7cde8b379e7d517Jouk Jansen 32b5b5c52034840dbfcd3f76a9e7cde8b379e7d517Jouk Jansen TinyPtrVector() {} 33b5b5c52034840dbfcd3f76a9e7cde8b379e7d517Jouk Jansen TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 34afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (VecTy *V = Val.template dyn_cast<VecTy*>()) 353c63452e64df7e10aa073c6c3b9492b1d7dabbb8Brian Paul Val = new VecTy(*V); 36374e7fd6cc95d3d91629a6e1c951d77e8a29c31cBrian Paul } 37374e7fd6cc95d3d91629a6e1c951d77e8a29c31cBrian Paul#if LLVM_USE_RVALUE_REFERENCES 3871dea349d2be623b7819389428b0d6a124e8d184Brian Paul TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 39afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg RHS.Val = (EltTy)0; 4071dea349d2be623b7819389428b0d6a124e8d184Brian Paul } 41afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#endif 42afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg ~TinyPtrVector() { 43afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (VecTy *V = Val.template dyn_cast<VecTy*>()) 44afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg delete V; 45afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 46afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 47afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg // implicit conversion operator to ArrayRef. 48afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg operator ArrayRef<EltTy>() const { 49afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (Val.isNull()) 50afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return ArrayRef<EltTy>(); 51afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (Val.template is<EltTy>()) 5249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return *Val.getAddrOfPtr1(); 53afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return *Val.template get<VecTy*>(); 5449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 5549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 5649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul bool empty() const { 5749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // This vector can be empty if it contains no element, or if it 58afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg // contains a pointer to an empty vector. 59afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (Val.isNull()) return true; 60afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 6149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return Vec->empty(); 62afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return false; 6349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 6449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 6549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul unsigned size() const { 6649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (empty()) 6749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return 0; 6849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (Val.template is<EltTy>()) 6949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return 1; 7049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return Val.template get<VecTy*>()->size(); 7149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 7249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 73afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg typedef const EltTy *const_iterator; 7449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul typedef EltTy *iterator; 75afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 7649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul iterator begin() { 7749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (empty()) 7849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return 0; 79afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 80afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (Val.template is<EltTy>()) 81afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return Val.getAddrOfPtr1(); 82afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 8349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return Val.template get<VecTy *>()->begin(); 84afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 8549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 8649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul iterator end() { 8749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (empty()) 8849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return 0; 8949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 9049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (Val.template is<EltTy>()) 9149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return begin() + 1; 9249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 9349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return Val.template get<VecTy *>()->end(); 9449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 9549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 9649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul const_iterator begin() const { 9749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 98afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 9949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 10049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul const_iterator end() const { 10149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 102afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 103afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 104afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg EltTy operator[](unsigned i) const { 105afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(!Val.isNull() && "can't index into an empty vector"); 106afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (EltTy V = Val.template dyn_cast<EltTy>()) { 107afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(i == 0 && "tinyvector index out of range"); 108afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return V; 109afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 110afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 111afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(i < Val.template get<VecTy*>()->size() && 112afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg "tinyvector index out of range"); 113afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return (*Val.template get<VecTy*>())[i]; 114afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 115afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 116afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg EltTy front() const { 117afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(!empty() && "vector empty"); 118afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (EltTy V = Val.template dyn_cast<EltTy>()) 119afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return V; 120afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return Val.template get<VecTy*>()->front(); 121afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 122afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 123afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg EltTy back() const { 124afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(!empty() && "vector empty"); 125afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (EltTy V = Val.template dyn_cast<EltTy>()) 126afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return V; 127afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg return Val.template get<VecTy*>()->back(); 128afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 129afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 130afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 131afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg void push_back(EltTy NewVal) { 132afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg assert(NewVal != 0 && "Can't add a null value"); 13349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 13449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // If we have nothing, add something. 13549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (Val.isNull()) { 136afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg Val = NewVal; 13749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return; 13849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 13949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 14049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // If we have a single value, convert to a vector. 14149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (EltTy V = Val.template dyn_cast<EltTy>()) { 14249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val = new VecTy(); 14349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val.template get<VecTy*>()->push_back(V); 14449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 14549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 14649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // Add the new value, we know we have a vector. 14749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val.template get<VecTy*>()->push_back(NewVal); 14849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 14949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 15049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul void pop_back() { 15149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // If we have a single value, convert to empty. 15249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (Val.template is<EltTy>()) 15349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val = (EltTy)0; 15449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul else if (VecTy *Vec = Val.template get<VecTy*>()) 15549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Vec->pop_back(); 15649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 15749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 15849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 15949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul void clear() { 16049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // If we have a single value, convert to empty. 16149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (Val.template is<EltTy>()) { 16249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val = (EltTy)0; 16349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 164afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg // If we have a vector form, just clear it. 165afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg Vec->clear(); 166afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 167afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg // Otherwise, we're already empty. 168afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg } 169afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 17049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul iterator erase(iterator I) { 17149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // If we have a single value, convert to empty. 172afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg if (Val.template is<EltTy>()) { 17349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul if (I == begin()) 17449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul Val = (EltTy)0; 17549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 17649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // multiple items in a vector; just do the erase, there is no 17749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul // benefit to collapsing back to a pointer 17849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return Vec->erase(I); 17949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 18049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 18149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul return 0; 18249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul } 18349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 18449bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paulprivate: 18549bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET. 18649bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul#if LLVM_USE_RVALUE_REFERENCES 18749bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET. 18849bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul#endif 18949bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul}; 19049bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul} // end namespace llvm 19149bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul 19249bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul#endif 19349bef526fde084b3ab20e9ff19bb89ecc31d4e55Brian Paul