1 //===-- UsuallyTinyPtrVector.h - Pointer vector class -----------*- 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 the UsuallyTinyPtrVector class, which is a vector that 11 // optimizes the case where there is only one element. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CLANG_AST_USUALLY_TINY_PTR_VECTOR_H 16 #define LLVM_CLANG_AST_USUALLY_TINY_PTR_VECTOR_H 17 18 #include <vector> 19 20 namespace clang { 21 22 /// \brief A vector class template that is optimized for storing a single 23 /// pointer element. 24 template<typename T> 25 class UsuallyTinyPtrVector { 26 /// \brief Storage for the vector. 27 /// 28 /// When the low bit is zero, this is a T *. When the 29 /// low bit is one, this is a std::vector<T *> *. 30 mutable uintptr_t Storage; 31 32 typedef std::vector<T*> vector_type; 33 34 public: UsuallyTinyPtrVector()35 UsuallyTinyPtrVector() : Storage(0) { } UsuallyTinyPtrVector(T * Element)36 explicit UsuallyTinyPtrVector(T *Element) 37 : Storage(reinterpret_cast<uintptr_t>(Element)) { } 38 empty()39 bool empty() const { return !Storage; } 40 41 typedef const T **iterator; 42 iterator begin() const; 43 iterator end() const; 44 size_t size() const; 45 46 void push_back(T *Method); 47 void Destroy(); 48 }; 49 50 template<typename T> 51 typename UsuallyTinyPtrVector<T>::iterator begin()52UsuallyTinyPtrVector<T>::begin() const { 53 if ((Storage & 0x01) == 0) 54 return reinterpret_cast<iterator>(&Storage); 55 56 vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01); 57 return &Vec->front(); 58 } 59 60 template<typename T> 61 typename UsuallyTinyPtrVector<T>::iterator end()62UsuallyTinyPtrVector<T>::end() const { 63 if ((Storage & 0x01) == 0) { 64 if (Storage == 0) 65 return reinterpret_cast<iterator>(&Storage); 66 67 return reinterpret_cast<iterator>(&Storage) + 1; 68 } 69 70 vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01); 71 return &Vec->front() + Vec->size(); 72 } 73 74 template<typename T> size()75size_t UsuallyTinyPtrVector<T>::size() const { 76 if ((Storage & 0x01) == 0) 77 return (Storage == 0) ? 0 : 1; 78 79 vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01); 80 return Vec->size(); 81 } 82 83 template<typename T> push_back(T * Element)84void UsuallyTinyPtrVector<T>::push_back(T *Element) { 85 if (Storage == 0) { 86 // 0 -> 1 element. 87 Storage = reinterpret_cast<uintptr_t>(Element); 88 return; 89 } 90 91 vector_type *Vec; 92 if ((Storage & 0x01) == 0) { 93 // 1 -> 2 elements. Allocate a new vector and push the element into that 94 // vector. 95 Vec = new vector_type; 96 Vec->push_back(reinterpret_cast<T *>(Storage)); 97 Storage = reinterpret_cast<uintptr_t>(Vec) | 0x01; 98 } else 99 Vec = reinterpret_cast<vector_type *>(Storage & ~0x01); 100 101 // Add the new element to the vector. 102 Vec->push_back(Element); 103 } 104 105 template<typename T> Destroy()106void UsuallyTinyPtrVector<T>::Destroy() { 107 if (Storage & 0x01) 108 delete reinterpret_cast<vector_type *>(Storage & ~0x01); 109 110 Storage = 0; 111 } 112 113 } 114 #endif 115