//===-- UsuallyTinyPtrVector.h - Pointer vector class -----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines the UsuallyTinyPtrVector class, which is a vector that
//  optimizes the case where there is only one element.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_AST_USUALLY_TINY_PTR_VECTOR_H
#define LLVM_CLANG_AST_USUALLY_TINY_PTR_VECTOR_H

#include <vector>

namespace clang {

/// \brief A vector class template that is optimized for storing a single 
/// pointer element.
template<typename T>
class UsuallyTinyPtrVector {
  /// \brief Storage for the vector.
  ///
  /// When the low bit is zero, this is a T *. When the
  /// low bit is one, this is a std::vector<T *> *.
  mutable uintptr_t Storage;

  typedef std::vector<T*> vector_type;

public:
  UsuallyTinyPtrVector() : Storage(0) { }
  explicit UsuallyTinyPtrVector(T *Element) 
    : Storage(reinterpret_cast<uintptr_t>(Element)) { }
  
  bool empty() const { return !Storage; }

  typedef const T **iterator;
  iterator begin() const;
  iterator end() const;
  size_t size() const;

  void push_back(T *Method);
  void Destroy();
};

template<typename T>
typename UsuallyTinyPtrVector<T>::iterator 
UsuallyTinyPtrVector<T>::begin() const {
  if ((Storage & 0x01) == 0)
    return reinterpret_cast<iterator>(&Storage);

  vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01);
  return &Vec->front();
}

template<typename T>
typename UsuallyTinyPtrVector<T>::iterator 
UsuallyTinyPtrVector<T>::end() const {
  if ((Storage & 0x01) == 0) {
    if (Storage == 0)
      return reinterpret_cast<iterator>(&Storage);

    return reinterpret_cast<iterator>(&Storage) + 1;
  }

  vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01);
  return &Vec->front() + Vec->size();
}

template<typename T>
size_t UsuallyTinyPtrVector<T>::size() const {
  if ((Storage & 0x01) == 0)
    return (Storage == 0) ? 0 : 1;

  vector_type *Vec = reinterpret_cast<vector_type *>(Storage & ~0x01);
  return Vec->size();
}

template<typename T>
void UsuallyTinyPtrVector<T>::push_back(T *Element) {
  if (Storage == 0) {
    // 0 -> 1 element.
    Storage = reinterpret_cast<uintptr_t>(Element);
    return;
  }

  vector_type *Vec;
  if ((Storage & 0x01) == 0) {
    // 1 -> 2 elements. Allocate a new vector and push the element into that
    // vector.
    Vec = new vector_type;
    Vec->push_back(reinterpret_cast<T *>(Storage));
    Storage = reinterpret_cast<uintptr_t>(Vec) | 0x01;
  } else
    Vec = reinterpret_cast<vector_type *>(Storage & ~0x01);

  // Add the new element to the vector.
  Vec->push_back(Element);
}

template<typename T>
void UsuallyTinyPtrVector<T>::Destroy() {
  if (Storage & 0x01)
    delete reinterpret_cast<vector_type *>(Storage & ~0x01);
  
  Storage = 0;
}

}
#endif