//===- 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_