15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- 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//===----------------------------------------------------------------------===// 922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#ifndef MCLD_SUPPORT_ALLOCATORS_H 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#define MCLD_SUPPORT_ALLOCATORS_H 1122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/Uncopyable.h> 1222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/TypeTraits.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 */ 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType, size_t ChunkSize> 2522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Chunk 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk() 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : next(0), bound(0) 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static size_t size() { return ChunkSize; } 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void construct(value_type* pPtr) 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { new (pPtr) value_type(); } 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void construct(value_type* pPtr, const value_type& pValue) 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { new (pPtr) value_type(pValue); } 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void destroy(value_type* pPtr) 4322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { } 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk* next; 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t bound; 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DataType data[ChunkSize]; 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Chunk<DataType, 0> 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk() 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : next(0), bound(0) { 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 != m_Size) 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao data = (DataType*)malloc(sizeof(DataType)*m_Size); 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao data = 0; 645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~Chunk() { 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (data) 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao free(data); 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static size_t size() { return m_Size; } 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static void setSize(size_t pSize) { m_Size = pSize; } 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void construct(value_type* pPtr) 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { new (pPtr) value_type(); } 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void construct(value_type* pPtr, const value_type& pValue) 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { new (pPtr) value_type(pValue); } 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao static void destroy(value_type* pPtr) 8222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { pPtr->~value_type(); } 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk* next; 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_t bound; 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DataType *data; 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static size_t m_Size; 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaosize_t Chunk<DataType, 0>::m_Size = 0; 935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename ChunkType> 955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass LinearAllocatorBase : private Uncopyable 965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ChunkType chunk_type; 995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename ChunkType::value_type value_type; 1005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename ChunkType::value_type* pointer; 1015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef typename ChunkType::value_type& reference; 1025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const typename ChunkType::value_type* const_pointer; 1035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const typename ChunkType::value_type& const_reference; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 1065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef unsigned char byte_type; 1075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 1095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao LinearAllocatorBase() 1105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : m_pRoot(0), 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent(0), 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum(0) { 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // LinearAllocatorBase does NOT mean to destroy the allocated memory. 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // If you want a memory allocator to release memory at destruction, please 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // use GCFactory series. 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~LinearAllocatorBase() 1195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 1205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer address(reference X) const 1235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return &X; } 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_pointer address(const_reference X) const 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return &X; } 1275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// standard construct - constructing an object on the location pointed by 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pPtr, and using its copy constructor to initialized its value to pValue. 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pPtr the address where the object to be constructed 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pValue the value to be constructed 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void construct(pointer pPtr, const_reference pValue) 13422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { chunk_type::construct(pPtr, pValue); } 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// default construct - constructing an object on the location pointed by 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pPtr, and using its default constructor to initialized its value to 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // pValue. 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param pPtr the address where the object to be constructed 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void construct(pointer pPtr) 14222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { chunk_type::construct(pPtr); } 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// standard destroy - destroy data on arbitrary address 1455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @para pPtr the address where the data to be destruected. 1465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void destroy(pointer pPtr) 14722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { chunk_type::destroy(pPtr); } 1485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// allocate - allocate N data in order. 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - Disallow to allocate a chunk whose size is bigger than a chunk. 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // 1525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @param N the number of allocated data. 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // @return the start address of the allocated memory 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate(size_type N) { 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == N || N > chunk_type::size()) 1565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return 0; 1575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (empty()) 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao initialize(); 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type rest_num_elem = chunk_type::size() - m_pCurrent->bound; 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer result = 0; 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (N > rest_num_elem) 16422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao getNewChunk(); 16522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result = m_pCurrent->data + m_pCurrent->bound; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound += N; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// allocate - clone function of allocating one datum. 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate() { 1725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (empty()) 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao initialize(); 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer result = 0; 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (chunk_type::size() == m_pCurrent->bound) 17722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao getNewChunk(); 17822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao result = m_pCurrent->data + m_pCurrent->bound; 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ++m_pCurrent->bound; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// deallocate - deallocate N data from the pPtr 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // - if we can simply release some memory, then do it. Otherwise, do 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // nothing. 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void deallocate(pointer &pPtr, size_type N) { 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == N || 1885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao N > chunk_type::size() || 1895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 0 == m_pCurrent->bound || 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao N >= m_pCurrent->bound) 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!isAvailable(pPtr)) 1935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 1945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound -= N; 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr = 0; 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// deallocate - clone function of deallocating one datum 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void deallocate(pointer &pPtr) { 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (0 == m_pCurrent->bound) 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (!isAvailable(pPtr)) 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return; 2045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->bound -= 1; 2055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr = 0; 2065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// isIn - whether the pPtr is in the current chunk? 2095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isIn(pointer pPtr) const { 2105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (pPtr >= &(m_pCurrent->data[0]) && 2115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr <= &(m_pCurrent->data[chunk_type::size()-1])) 2125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 2135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 2145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// isIn - whether the pPtr is allocated, and can be constructed. 2175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isAvailable(pointer pPtr) const { 2185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao if (pPtr >= &(m_pCurrent->data[m_pCurrent->bound]) && 2195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pPtr <= &(m_pCurrent->data[chunk_type::size()-1])) 2205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return true; 2215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return false; 2225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void reset() { 2255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pRoot = 0; 2265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = 0; 2275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum = 0; 2285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao /// clear - clear all chunks 2315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void clear() { 2325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chunk_type *cur = m_pRoot, *prev; 2335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao while (0 != cur) { 2345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao prev = cur; 2355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao cur = cur->next; 23622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao for (unsigned int idx = 0; idx != prev->bound; ++idx) 23722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao destroy(prev->data + idx); 2385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao delete prev; 2395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao reset(); 2415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- observers ----- // 2445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool empty() const { 2455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return (0 == m_pRoot); 2465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type max_size() const 2495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return m_AllocatedNum; } 2505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 2525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao inline void initialize() { 2535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pRoot = new chunk_type(); 2545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = m_pRoot; 2555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum += chunk_type::size(); 2565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 25822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao inline chunk_type *getNewChunk() { 2595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chunk_type *result = new chunk_type(); 2605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent->next = result; 2615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_pCurrent = result; 2625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao m_AllocatedNum += chunk_type::size(); 2635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return result; 2645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 2655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprotected: 2675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chunk_type *m_pRoot; 2685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao chunk_type *m_pCurrent; 2695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type m_AllocatedNum; 2705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 2715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class LinearAllocator 2735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief LinearAllocator is another bump pointer allocator which should be 2745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * limited in use of two-phase memory allocation. 2755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * Two-phase memory allocation clear separates the use of memory into 'claim' 2775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * and 'release' phases. There are no interleaving allocation and 2785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * deallocation. Interleaving 'allocate' and 'deallocate' increases the size 2795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * of allocated memory, and causes bad locality. 2805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * The underlying concept of LinearAllocator is a memory pool. LinearAllocator 2825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * is a simple implementation of boost::pool's ordered_malloc() and 2835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * ordered_free(). 2845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 2855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * template argument DataType is the DataType to be allocated 2865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * template argument ChunkSize is the number of bytes of a chunk 2875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 2885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType, size_t ChunkSize> 2895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass LinearAllocator : public LinearAllocatorBase<Chunk<DataType, ChunkSize> > 2905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 2915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename NewDataType> 2935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind { 2945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef LinearAllocator<NewDataType, ChunkSize> other; 2955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 2965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 2985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao LinearAllocator() 2995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : LinearAllocatorBase<Chunk<DataType, ChunkSize> >() { 3005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~LinearAllocator() 3035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 3075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass LinearAllocator<DataType, 0> : public LinearAllocatorBase<Chunk<DataType, 0> > 3085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename NewDataType> 3115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind { 3125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef LinearAllocator<NewDataType, 0> other; 3135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 3145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit LinearAllocator(size_t pNum) 3175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : LinearAllocatorBase<Chunk<DataType, 0> >() { 3185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Chunk<DataType, 0>::setSize(pNum); 3195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~LinearAllocator() 3225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename DataType> 3265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass MallocAllocator 3275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 3305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 3315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType* pointer; 3325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const DataType* const_pointer; 3335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType& reference; 3345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const DataType& const_reference; 3355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef DataType value_type; 3365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename OtherDataType> 3385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind 3395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 3405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef MallocAllocator<OtherDataType> other; 3415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 3425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao MallocAllocator() throw() 3455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao MallocAllocator(const MallocAllocator&) throw() 3485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~MallocAllocator() throw() 3515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 3525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer address(reference X) const 3545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return &X; } 3555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_pointer address(const_reference X) const 3575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return &X; } 3585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate(size_type pNumOfElements, const void* = 0) 3605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 3615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return static_cast<DataType*>( 3625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao std::malloc(pNumOfElements*sizeof(DataType))); 3635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 3645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void deallocate(pointer pObject, size_type) 3665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { std::free(static_cast<void*>(pObject)); } 3675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type max_size() const throw() 3695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return size_t(-1) / sizeof(DataType); } 3705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void construct(pointer pObject, const DataType& pValue) 3725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { ::new((void *)pObject) value_type(pValue); } 3735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void destroy(pointer pObject) 3755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { pObject->~DataType(); } 3765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 3785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<> 3805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass MallocAllocator<void> 3815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef size_t size_type; 3845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef ptrdiff_t difference_type; 3855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef void* pointer; 3865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const void* const_pointer; 3875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef void* reference; 3885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef const void* const_reference; 3895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef void* value_type; 3905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename OtherDataType> 3925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao struct rebind 3935460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { 3945460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef MallocAllocator<OtherDataType> other; 3955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 3965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 3975460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 3985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao MallocAllocator() throw() 3995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 4005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao MallocAllocator(const MallocAllocator&) throw() 4025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 4035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao ~MallocAllocator() throw() 4055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { } 4065460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4075460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao size_type max_size() const throw() 4085460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return size_t(-1) / sizeof(void*); } 4095460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4105460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer address(reference X) const 4115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X; } 4125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_pointer address(const_reference X) const 4145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { return X; } 4155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename DataType> 4175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao DataType* allocate(size_type pNumOfElements, const void* = 0) { 4185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return static_cast<DataType*>( 4195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao std::malloc(pNumOfElements*sizeof(DataType))); 4205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 4215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pointer allocate(size_type pNumOfElements, const void* = 0) { 4235460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return std::malloc(pNumOfElements); 4245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 4255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename DataType> 4275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void deallocate(DataType* pObject, size_type) 4285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { std::free(static_cast<void*>(pObject)); } 4295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void deallocate(pointer pObject, size_type) 4315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { std::free(pObject); } 4325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename DataType> 4345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void construct(DataType* pObject, const DataType& pValue) 4355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { /* do nothing */ } 4365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void construct(pointer pObject, const_reference pValue) 4385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { /* do nothing */ } 4395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<typename DataType> 4415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void destroy(DataType* pObject) 4425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { /* do nothing */ } 4435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao void destroy(pointer pObject) 4455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao { /* do nothing */ } 4465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 4475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace mcld 4495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 4505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 451affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 452