137b74a387bb3993387029859c2d9d051c41c724eStephen Hines//===- Allocators.h -------------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_SUPPORT_ALLOCATORS_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_SUPPORT_ALLOCATORS_H_ 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/TypeTraits.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Support/Compiler.h" 1322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 14f767be5432ccac097334be48698e48621d730190Shih-wei Liao#include <cstddef> 155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <cstdlib> 165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class Chunk 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief Chunk is the basic unit of the storage of the LinearAllocator 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see LinearAllocator 235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2437b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType, size_t ChunkSize> 2537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass Chunk { 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hines 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 3037b74a387bb3993387029859c2d9d051c41c724eStephen Hines Chunk() : next(NULL), bound(0) {} 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static size_t size() { return ChunkSize; } 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void construct(value_type* pPtr) { new (pPtr) value_type(); } 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3637b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void construct(value_type* pPtr, const value_type& pValue) { 3737b74a387bb3993387029859c2d9d051c41c724eStephen Hines new (pPtr) value_type(pValue); 3837b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4037b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void destroy(value_type* pPtr) {} 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4237b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk* next; 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t bound; 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DataType data[ChunkSize]; 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4837b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType> 4937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass Chunk<DataType, 0> { 5037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 5337b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 5437b74a387bb3993387029859c2d9d051c41c724eStephen Hines Chunk() : next(NULL), bound(0) { 5537b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_Size != 0) 5637b74a387bb3993387029859c2d9d051c41c724eStephen Hines data = reinterpret_cast<DataType*>(malloc(sizeof(DataType) * m_Size)); 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao data = 0; 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~Chunk() { 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (data) 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao free(data); 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static size_t size() { return m_Size; } 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static void setSize(size_t pSize) { m_Size = pSize; } 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7037b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void construct(value_type* pPtr) { new (pPtr) value_type(); } 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void construct(value_type* pPtr, const value_type& pValue) { 7337b74a387bb3993387029859c2d9d051c41c724eStephen Hines new (pPtr) value_type(pValue); 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hines static void destroy(value_type* pPtr) { pPtr->~value_type(); } 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7837b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk* next; 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t bound; 8137b74a387bb3993387029859c2d9d051c41c724eStephen Hines DataType* data; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static size_t m_Size; 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8537b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType> 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaosize_t Chunk<DataType, 0>::m_Size = 0; 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 8837b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename ChunkType> 8937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass LinearAllocatorBase { 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 9137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ChunkType chunk_type; 9237b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef typename ChunkType::value_type value_type; 9337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef typename ChunkType::value_type* pointer; 9437b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef typename ChunkType::value_type& reference; 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const typename ChunkType::value_type* const_pointer; 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const typename ChunkType::value_type& const_reference; 9737b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 9837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 9937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef unsigned char byte_type; 10037b74a387bb3993387029859c2d9d051c41c724eStephen Hines 10137b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 10237b74a387bb3993387029859c2d9d051c41c724eStephen Hines LinearAllocatorBase() : m_pRoot(NULL), m_pCurrent(NULL), m_AllocatedNum(0) {} 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // LinearAllocatorBase does NOT mean to destroy the allocated memory. 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // If you want a memory allocator to release memory at destruction, please 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // use GCFactory series. 10737b74a387bb3993387029859c2d9d051c41c724eStephen Hines virtual ~LinearAllocatorBase() {} 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 10937b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines pointer address(reference X) const { return &X; } 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11237b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_pointer address(const_reference X) const { return &X; } 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// standard construct - constructing an object on the location pointed by 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pPtr, and using its copy constructor to initialized its value to pValue. 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pPtr the address where the object to be constructed 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pValue the value to be constructed 11937b74a387bb3993387029859c2d9d051c41c724eStephen Hines void construct(pointer pPtr, const_reference pValue) { 12037b74a387bb3993387029859c2d9d051c41c724eStephen Hines chunk_type::construct(pPtr, pValue); 12137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// default construct - constructing an object on the location pointed by 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pPtr, and using its default constructor to initialized its value to 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pValue. 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pPtr the address where the object to be constructed 12837b74a387bb3993387029859c2d9d051c41c724eStephen Hines void construct(pointer pPtr) { chunk_type::construct(pPtr); } 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// standard destroy - destroy data on arbitrary address 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @para pPtr the address where the data to be destruected. 13237b74a387bb3993387029859c2d9d051c41c724eStephen Hines void destroy(pointer pPtr) { chunk_type::destroy(pPtr); } 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// allocate - allocate N data in order. 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - Disallow to allocate a chunk whose size is bigger than a chunk. 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param N the number of allocated data. 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the start address of the allocated memory 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate(size_type N) { 14037b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (N == 0 || N > chunk_type::size()) 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 1425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (empty()) 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao initialize(); 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type rest_num_elem = chunk_type::size() - m_pCurrent->bound; 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer result = 0; 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (N > rest_num_elem) 14922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao getNewChunk(); 15022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result = m_pCurrent->data + m_pCurrent->bound; 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound += N; 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// allocate - clone function of allocating one datum. 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate() { 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (empty()) 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao initialize(); 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer result = 0; 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (chunk_type::size() == m_pCurrent->bound) 16222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao getNewChunk(); 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result = m_pCurrent->data + m_pCurrent->bound; 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++m_pCurrent->bound; 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// deallocate - deallocate N data from the pPtr 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - if we can simply release some memory, then do it. Otherwise, do 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // nothing. 17137b74a387bb3993387029859c2d9d051c41c724eStephen Hines void deallocate(pointer& pPtr, size_type N) { 17237b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (N == 0 || N > chunk_type::size() || m_pCurrent->bound == 0 || 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao N >= m_pCurrent->bound) 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!isAvailable(pPtr)) 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound -= N; 1785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr = 0; 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// deallocate - clone function of deallocating one datum 18237b74a387bb3993387029859c2d9d051c41c724eStephen Hines void deallocate(pointer& pPtr) { 18337b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pCurrent->bound == 0) 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!isAvailable(pPtr)) 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound -= 1; 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr = 0; 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// isIn - whether the pPtr is in the current chunk? 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isIn(pointer pPtr) const { 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (pPtr >= &(m_pCurrent->data[0]) && 19437b74a387bb3993387029859c2d9d051c41c724eStephen Hines pPtr <= &(m_pCurrent->data[chunk_type::size() - 1])) 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// isIn - whether the pPtr is allocated, and can be constructed. 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isAvailable(pointer pPtr) const { 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (pPtr >= &(m_pCurrent->data[m_pCurrent->bound]) && 20237b74a387bb3993387029859c2d9d051c41c724eStephen Hines pPtr <= &(m_pCurrent->data[chunk_type::size() - 1])) 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void reset() { 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pRoot = 0; 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = 0; 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum = 0; 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// clear - clear all chunks 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void clear() { 21537b74a387bb3993387029859c2d9d051c41c724eStephen Hines chunk_type* cur = m_pRoot, *prev; 21637b74a387bb3993387029859c2d9d051c41c724eStephen Hines while (cur != 0) { 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao prev = cur; 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao cur = cur->next; 21922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (unsigned int idx = 0; idx != prev->bound; ++idx) 22022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao destroy(prev->data + idx); 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete prev; 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- observers ----- // 22737b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool empty() const { return (m_pRoot == 0); } 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 22937b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_type max_size() const { return m_AllocatedNum; } 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 23137b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void initialize() { 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pRoot = new chunk_type(); 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = m_pRoot; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum += chunk_type::size(); 2365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 23837b74a387bb3993387029859c2d9d051c41c724eStephen Hines inline chunk_type* getNewChunk() { 23937b74a387bb3993387029859c2d9d051c41c724eStephen Hines chunk_type* result = new chunk_type(); 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->next = result; 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = result; 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum += chunk_type::size(); 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 24637b74a387bb3993387029859c2d9d051c41c724eStephen Hines protected: 24737b74a387bb3993387029859c2d9d051c41c724eStephen Hines chunk_type* m_pRoot; 24837b74a387bb3993387029859c2d9d051c41c724eStephen Hines chunk_type* m_pCurrent; 24937b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_type m_AllocatedNum; 25037b74a387bb3993387029859c2d9d051c41c724eStephen Hines 25137b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 25237b74a387bb3993387029859c2d9d051c41c724eStephen Hines DISALLOW_COPY_AND_ASSIGN(LinearAllocatorBase); 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class LinearAllocator 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief LinearAllocator is another bump pointer allocator which should be 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * limited in use of two-phase memory allocation. 2585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * Two-phase memory allocation clear separates the use of memory into 'claim' 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * and 'release' phases. There are no interleaving allocation and 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * deallocation. Interleaving 'allocate' and 'deallocate' increases the size 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * of allocated memory, and causes bad locality. 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * The underlying concept of LinearAllocator is a memory pool. LinearAllocator 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * is a simple implementation of boost::pool's ordered_malloc() and 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * ordered_free(). 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * template argument DataType is the DataType to be allocated 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * template argument ChunkSize is the number of bytes of a chunk 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 27137b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType, size_t ChunkSize> 27237b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass LinearAllocator 27337b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public LinearAllocatorBase<Chunk<DataType, ChunkSize> > { 27437b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 27537b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename NewDataType> 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind { 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef LinearAllocator<NewDataType, ChunkSize> other; 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 28137b74a387bb3993387029859c2d9d051c41c724eStephen Hines LinearAllocator() : LinearAllocatorBase<Chunk<DataType, ChunkSize> >() {} 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28337b74a387bb3993387029859c2d9d051c41c724eStephen Hines virtual ~LinearAllocator() {} 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 28637b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType> 28737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass LinearAllocator<DataType, 0> 28837b74a387bb3993387029859c2d9d051c41c724eStephen Hines : public LinearAllocatorBase<Chunk<DataType, 0> > { 28937b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 29037b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename NewDataType> 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind { 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef LinearAllocator<NewDataType, 0> other; 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 29537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit LinearAllocator(size_t pNum) 29737b74a387bb3993387029859c2d9d051c41c724eStephen Hines : LinearAllocatorBase<Chunk<DataType, 0> >() { 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk<DataType, 0>::setSize(pNum); 2995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 30137b74a387bb3993387029859c2d9d051c41c724eStephen Hines virtual ~LinearAllocator() {} 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 30437b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <typename DataType> 30537b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass MallocAllocator { 30637b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 30737b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 30837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 30937b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef DataType* pointer; 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const DataType* const_pointer; 31137b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef DataType& reference; 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const DataType& const_reference; 31337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef DataType value_type; 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 31537b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename OtherDataType> 31637b74a387bb3993387029859c2d9d051c41c724eStephen Hines struct rebind { 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef MallocAllocator<OtherDataType> other; 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 3195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32037b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 32137b74a387bb3993387029859c2d9d051c41c724eStephen Hines MallocAllocator() throw() {} 3225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32337b74a387bb3993387029859c2d9d051c41c724eStephen Hines MallocAllocator(const MallocAllocator&) throw() {} 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32537b74a387bb3993387029859c2d9d051c41c724eStephen Hines ~MallocAllocator() throw() {} 3265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32737b74a387bb3993387029859c2d9d051c41c724eStephen Hines pointer address(reference X) const { return &X; } 3285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 32937b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_pointer address(const_reference X) const { return &X; } 3305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 33137b74a387bb3993387029859c2d9d051c41c724eStephen Hines pointer allocate(size_type pNumOfElements, const void* = 0) { 3325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return static_cast<DataType*>( 33337b74a387bb3993387029859c2d9d051c41c724eStephen Hines std::malloc(pNumOfElements * sizeof(DataType))); 3345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 33637b74a387bb3993387029859c2d9d051c41c724eStephen Hines void deallocate(pointer pObject, size_type) { 33737b74a387bb3993387029859c2d9d051c41c724eStephen Hines std::free(static_cast<void*>(pObject)); 33837b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 34037b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_type max_size() const throw() { return size_t(-1) / sizeof(DataType); } 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 34237b74a387bb3993387029859c2d9d051c41c724eStephen Hines void construct(pointer pObject, const DataType& pValue) { 34337b74a387bb3993387029859c2d9d051c41c724eStephen Hines ::new (reinterpret_cast<void*>(pObject)) value_type(pValue); 34437b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 34637b74a387bb3993387029859c2d9d051c41c724eStephen Hines void destroy(pointer pObject) { pObject->~DataType(); } 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 34937b74a387bb3993387029859c2d9d051c41c724eStephen Hinestemplate <> 35037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass MallocAllocator<void> { 35137b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 35237b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef size_t size_type; 35337b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef ptrdiff_t difference_type; 35437b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef void* pointer; 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const void* const_pointer; 35637b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef void* reference; 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const void* const_reference; 35837b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef void* value_type; 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 36037b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename OtherDataType> 36137b74a387bb3993387029859c2d9d051c41c724eStephen Hines struct rebind { 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef MallocAllocator<OtherDataType> other; 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 36537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 36637b74a387bb3993387029859c2d9d051c41c724eStephen Hines MallocAllocator() throw() {} 3675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 36837b74a387bb3993387029859c2d9d051c41c724eStephen Hines MallocAllocator(const MallocAllocator&) throw() {} 3695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 37037b74a387bb3993387029859c2d9d051c41c724eStephen Hines ~MallocAllocator() throw() {} 3715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 37237b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_type max_size() const throw() { return size_t(-1) / sizeof(void*); } 3735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 37437b74a387bb3993387029859c2d9d051c41c724eStephen Hines pointer address(reference X) const { return X; } 3755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 37637b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_pointer address(const_reference X) const { return X; } 3775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 37837b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename DataType> 3795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DataType* allocate(size_type pNumOfElements, const void* = 0) { 3805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return static_cast<DataType*>( 38137b74a387bb3993387029859c2d9d051c41c724eStephen Hines std::malloc(pNumOfElements * sizeof(DataType))); 3825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate(size_type pNumOfElements, const void* = 0) { 3855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return std::malloc(pNumOfElements); 3865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 38837b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename DataType> 38937b74a387bb3993387029859c2d9d051c41c724eStephen Hines void deallocate(DataType* pObject, size_type) { 39037b74a387bb3993387029859c2d9d051c41c724eStephen Hines std::free(static_cast<void*>(pObject)); 39137b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 39337b74a387bb3993387029859c2d9d051c41c724eStephen Hines void deallocate(pointer pObject, size_type) { std::free(pObject); } 3945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 39537b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename DataType> 39637b74a387bb3993387029859c2d9d051c41c724eStephen Hines void construct(DataType* pObject, const DataType& pValue) { /* do nothing */ 39737b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 3985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 39937b74a387bb3993387029859c2d9d051c41c724eStephen Hines void construct(pointer pObject, const_reference pValue) { /* do nothing */ 40037b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 4015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 40237b74a387bb3993387029859c2d9d051c41c724eStephen Hines template <typename DataType> 40337b74a387bb3993387029859c2d9d051c41c724eStephen Hines void destroy(DataType* pObject) { /* do nothing */ 40437b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 4055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 40637b74a387bb3993387029859c2d9d051c41c724eStephen Hines void destroy(pointer pObject) { /* do nothing */ 40737b74a387bb3993387029859c2d9d051c41c724eStephen Hines } 4085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 4095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 41037b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 411affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 41237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_SUPPORT_ALLOCATORS_H_ 413