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