contrib/llvm/tools/clang/include/clang/AST/UsuallyTinyPtrVector.h

   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:
  35   UsuallyTinyPtrVector() : Storage(0) { }
  36   explicit UsuallyTinyPtrVector(T *Element)
  37     : Storage(reinterpret_cast<uintptr_t>(Element)) { }
  38
  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
  52 UsuallyTinyPtrVector<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
  62 UsuallyTinyPtrVector<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>
  75 size_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>
  84 void 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>
 106 void UsuallyTinyPtrVector<T>::Destroy() {
 107   if (Storage & 0x01)
 108     delete reinterpret_cast<vector_type *>(Storage & ~0x01);
 109
 110   Storage = 0;
 111 }
 112
 113 }
 114 #endif