//===- Allocators.h -------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_SUPPORT_ALLOCATORS_H_
#define MCLD_SUPPORT_ALLOCATORS_H_
#include "mcld/ADT/TypeTraits.h"
#include "mcld/Support/Compiler.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>
class Chunk {
 public:
  typedef DataType value_type;

 public:
  Chunk() : next(NULL), bound(0) {}

  static size_t size() { return ChunkSize; }

  static void construct(value_type* pPtr) { new (pPtr) value_type(); }

  static void construct(value_type* pPtr, const value_type& pValue) {
    new (pPtr) value_type(pValue);
  }

  static void destroy(value_type* pPtr) {}

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

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

 public:
  Chunk() : next(NULL), bound(0) {
    if (m_Size != 0)
      data = reinterpret_cast<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; }

  static void construct(value_type* pPtr) { new (pPtr) value_type(); }

  static void construct(value_type* pPtr, const value_type& pValue) {
    new (pPtr) value_type(pValue);
  }

  static void destroy(value_type* pPtr) { pPtr->~value_type(); }

 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 {
 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(NULL), m_pCurrent(NULL), 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) {
    chunk_type::construct(pPtr, 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) { chunk_type::construct(pPtr); }

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

  /// 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 (N == 0 || 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)
      getNewChunk();
    result = 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)
      getNewChunk();
    result = 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 (N == 0 || N > chunk_type::size() || m_pCurrent->bound == 0 ||
        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 (m_pCurrent->bound == 0)
      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 (cur != 0) {
      prev = cur;
      cur = cur->next;
      for (unsigned int idx = 0; idx != prev->bound; ++idx)
        destroy(prev->data + idx);
      delete prev;
    }
    reset();
  }

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

  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* getNewChunk() {
    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;

 private:
  DISALLOW_COPY_AND_ASSIGN(LinearAllocatorBase);
};

/** \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 (reinterpret_cast<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  // MCLD_SUPPORT_ALLOCATORS_H_