//===- Allocators.h ---------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ALLOCATORS_H
#define LLVM_ALLOCATORS_H
#ifdef ENABLE_UNITTEST
#include <gtest.h>
#endif
#include "mcld/ADT/Uncopyable.h"
#include "mcld/ADT/TypeTraits.h"
#include "mcld/LD/LDContext.h"

#include <cstddef>
#include <cstdlib>

namespace mcld
{

/** \class Chunk
 *  \brief Chunk is the basic unit of the storage of the LinearAllocator
 *
 *  @see LinearAllocator
 */
template<typename DataType, size_t ChunkSize>
struct Chunk
{
public:
  typedef DataType value_type;
public:
  Chunk()
  : next(0), bound(0)
  { }

  static size_t size() { return ChunkSize; }

public:
  Chunk* next;
  size_t bound;
  DataType data[ChunkSize];
};

template<typename DataType>
struct Chunk<DataType, 0>
{
public:
  typedef DataType value_type;

public:
  Chunk()
  : next(0), bound(0) {
    if (0 != m_Size)
      data = (DataType*)malloc(sizeof(DataType)*m_Size);
    else
      data = 0;
  }

  ~Chunk() {
    if (data)
      free(data);
  }

  static size_t size()              { return m_Size; }
  static void setSize(size_t pSize) { m_Size = pSize; }

public:
  Chunk* next;
  size_t bound;
  DataType *data;
  static size_t m_Size;
};

template<typename DataType>
size_t Chunk<DataType, 0>::m_Size = 0;

template<typename ChunkType>
class LinearAllocatorBase : private Uncopyable
{
public:
  typedef ChunkType                             chunk_type;
  typedef typename ChunkType::value_type        value_type;
  typedef typename ChunkType::value_type*       pointer;
  typedef typename ChunkType::value_type&       reference;
  typedef const typename ChunkType::value_type* const_pointer;
  typedef const typename ChunkType::value_type& const_reference;
  typedef size_t                                size_type;
  typedef ptrdiff_t                             difference_type;
  typedef unsigned char                         byte_type;

protected:
  LinearAllocatorBase()
    : m_pRoot(0),
      m_pCurrent(0),
      m_AllocatedNum(0) {
  }

  // LinearAllocatorBase does NOT mean to destroy the allocated memory.
  // If you want a memory allocator to release memory at destruction, please
  // use GCFactory series.
  virtual ~LinearAllocatorBase()
  { }

public:
  pointer address(reference X) const
  { return &X; }

  const_pointer address(const_reference X) const
  { return &X; }

  /// standard construct - constructing an object on the location pointed by
  //  pPtr, and using its copy constructor to initialized its value to pValue.
  //
  //  @param pPtr the address where the object to be constructed
  //  @param pValue the value to be constructed
  void construct(pointer pPtr, const_reference pValue)
  { new (pPtr) value_type(pValue); }

  /// default construct - constructing an object on the location pointed by
  //  pPtr, and using its default constructor to initialized its value to
  //  pValue.
  //
  //  @param pPtr the address where the object to be constructed
  void construct(pointer pPtr)
  { new (pPtr) value_type(); }

  /// standard destroy - destroy data on arbitrary address
  //  @para pPtr the address where the data to be destruected.
  void destroy(pointer pPtr)
  { pPtr->~value_type(); }

  /// allocate - allocate N data in order.
  //  - Disallow to allocate a chunk whose size is bigger than a chunk.
  //
  //  @param N the number of allocated data.
  //  @return the start address of the allocated memory
  pointer allocate(size_type N) {
    if (0 == N || N > chunk_type::size())
      return 0;

    if (empty())
      initialize();

    size_type rest_num_elem = chunk_type::size() - m_pCurrent->bound;
    pointer result = 0;
    if (N > rest_num_elem)
      createChunk();
    result = const_cast<pointer>(&(m_pCurrent->data[m_pCurrent->bound]));
    m_pCurrent->bound += N;
    return result;
  }

  /// allocate - clone function of allocating one datum.
  pointer allocate() {
    if (empty())
      initialize();

    pointer result = 0;
    if (chunk_type::size() == m_pCurrent->bound)
      createChunk();
    result = const_cast<pointer>(&(m_pCurrent->data[m_pCurrent->bound]));
    ++m_pCurrent->bound;
    return result;
  }

  /// deallocate - deallocate N data from the pPtr
  //  - if we can simply release some memory, then do it. Otherwise, do
  //    nothing.
  void deallocate(pointer &pPtr, size_type N) {
    if (0 == N ||
        N > chunk_type::size() ||
        0 == m_pCurrent->bound ||
        N >= m_pCurrent->bound)
      return;
    if (!isAvailable(pPtr))
      return;
    m_pCurrent->bound -= N;
    pPtr = 0;
  }

  /// deallocate - clone function of deallocating one datum
  void deallocate(pointer &pPtr) {
    if (0 == m_pCurrent->bound)
      return;
    if (!isAvailable(pPtr))
      return;
    m_pCurrent->bound -= 1;
    pPtr = 0;
  }

  /// isIn - whether the pPtr is in the current chunk?
  bool isIn(pointer pPtr) const {
    if (pPtr >= &(m_pCurrent->data[0]) &&
        pPtr <= &(m_pCurrent->data[chunk_type::size()-1]))
      return true;
    return false;
  }

  /// isIn - whether the pPtr is allocated, and can be constructed.
  bool isAvailable(pointer pPtr) const {
    if (pPtr >= &(m_pCurrent->data[m_pCurrent->bound]) &&
        pPtr <= &(m_pCurrent->data[chunk_type::size()-1]))
      return true;
    return false;
  }

  void reset() {
    m_pRoot = 0;
    m_pCurrent = 0;
    m_AllocatedNum = 0;
  }

  /// clear - clear all chunks
  void clear() {
    chunk_type *cur = m_pRoot, *prev;
    while (0 != cur) {
      unsigned int idx=0;
      prev = cur;
      cur = cur->next;
      while (idx != prev->bound) {
        destroy(&prev->data[idx]);
        ++idx;
      }
      delete prev;
    }
    reset();
  }

  // -----  observers  ----- //
  bool empty() const {
    return (0 == m_pRoot);
  }

  size_type max_size() const
  { return m_AllocatedNum; }

protected:
  inline void initialize() {
    m_pRoot = new chunk_type();
    m_pCurrent = m_pRoot;
    m_AllocatedNum += chunk_type::size();
  }

  inline chunk_type *createChunk() {
    chunk_type *result = new chunk_type();
    m_pCurrent->next = result;
    m_pCurrent = result;
    m_AllocatedNum += chunk_type::size();
    return result;
  }

protected:
  chunk_type *m_pRoot;
  chunk_type *m_pCurrent;
  size_type   m_AllocatedNum;
};

/** \class LinearAllocator
 *  \brief LinearAllocator is another bump pointer allocator which should be
 *  limited in use of two-phase memory allocation.
 *
 *  Two-phase memory allocation clear separates the use of memory into 'claim'
 *  and 'release' phases. There are no interleaving allocation and
 *  deallocation. Interleaving 'allocate' and 'deallocate' increases the size
 *  of allocated memory, and causes bad locality.
 *
 *  The underlying concept of LinearAllocator is a memory pool. LinearAllocator
 *  is a simple implementation of boost::pool's ordered_malloc() and
 *  ordered_free().
 *
 *  template argument DataType is the DataType to be allocated
 *  template argument ChunkSize is the number of bytes of a chunk
 */
template<typename DataType, size_t ChunkSize>
class LinearAllocator : public LinearAllocatorBase<Chunk<DataType, ChunkSize> >
{
public:
  template<typename NewDataType>
  struct rebind {
    typedef LinearAllocator<NewDataType, ChunkSize> other;
  };

public:
  LinearAllocator()
    : LinearAllocatorBase<Chunk<DataType, ChunkSize> >() {
  }

  virtual ~LinearAllocator()
  { }
};

template<typename DataType>
class LinearAllocator<DataType, 0> : public LinearAllocatorBase<Chunk<DataType, 0> >
{
public:
  template<typename NewDataType>
  struct rebind {
    typedef LinearAllocator<NewDataType, 0> other;
  };

public:
  explicit LinearAllocator(size_t pNum)
    : LinearAllocatorBase<Chunk<DataType, 0> >() {
    Chunk<DataType, 0>::setSize(pNum);
  }

  virtual ~LinearAllocator()
  { }
};

template<typename DataType>
class MallocAllocator
{
public:
  typedef size_t          size_type;
  typedef ptrdiff_t       difference_type;
  typedef DataType*       pointer;
  typedef const DataType* const_pointer;
  typedef DataType&       reference;
  typedef const DataType& const_reference;
  typedef DataType        value_type;

  template<typename OtherDataType>
  struct rebind
  {
    typedef MallocAllocator<OtherDataType> other;
  };

public:
  MallocAllocator() throw()
  { }

  MallocAllocator(const MallocAllocator&) throw()
  { }

  ~MallocAllocator() throw()
  { }

  pointer address(reference X) const
  { return &X; }

  const_pointer address(const_reference X) const
  { return &X; }

  pointer allocate(size_type pNumOfElements, const void* = 0)
  {
    return static_cast<DataType*>(
                       std::malloc(pNumOfElements*sizeof(DataType)));
  }

  void deallocate(pointer pObject, size_type)
  { std::free(static_cast<void*>(pObject)); }

  size_type max_size() const throw()
  { return size_t(-1) / sizeof(DataType); }

  void construct(pointer pObject, const DataType& pValue)
  { ::new((void *)pObject) value_type(pValue); }

  void destroy(pointer pObject)
  { pObject->~DataType(); }

};

template<>
class MallocAllocator<void>
{
public:
  typedef size_t      size_type;
  typedef ptrdiff_t   difference_type;
  typedef void*       pointer;
  typedef const void* const_pointer;
  typedef void*       reference;
  typedef const void* const_reference;
  typedef void*       value_type;

  template<typename OtherDataType>
  struct rebind
  {
    typedef MallocAllocator<OtherDataType> other;
  };

public:
  MallocAllocator() throw()
  { }

  MallocAllocator(const MallocAllocator&) throw()
  { }

  ~MallocAllocator() throw()
  { }

  size_type max_size() const throw()
  { return size_t(-1) / sizeof(void*); }

  pointer address(reference X) const
  { return X; }

  const_pointer address(const_reference X) const
  { return X; }

  template<typename DataType>
  DataType* allocate(size_type pNumOfElements, const void* = 0) {
    return static_cast<DataType*>(
                       std::malloc(pNumOfElements*sizeof(DataType)));
  }

  pointer allocate(size_type pNumOfElements, const void* = 0) {
    return std::malloc(pNumOfElements);
  }

  template<typename DataType>
  void deallocate(DataType* pObject, size_type)
  { std::free(static_cast<void*>(pObject)); }

  void deallocate(pointer pObject, size_type)
  { std::free(pObject); }

  template<typename DataType>
  void construct(DataType* pObject, const DataType& pValue)
  { /* do nothing */ }

  void construct(pointer pObject, const_reference pValue)
  { /* do nothing */ }

  template<typename DataType>
  void destroy(DataType* pObject)
  { /* do nothing */ }

  void destroy(pointer pObject)
  { /* do nothing */ }
};

} // namespace mcld

#endif