Allocators.h revision affc150dc44fab1911775a49636d0ce85333b634
1//===- Allocators.h ---------------------------------------------------------===// 2// 3// The MCLinker Project 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef LLVM_ALLOCATORS_H 11#define LLVM_ALLOCATORS_H 12#ifdef ENABLE_UNITTEST 13#include <gtest.h> 14#endif 15#include "mcld/ADT/Uncopyable.h" 16#include "mcld/ADT/TypeTraits.h" 17#include "mcld/LD/LDContext.h" 18#include <cstddef> 19#include <cstdlib> 20 21namespace mcld 22{ 23 24/** \class Chunk 25 * \brief Chunk is the basic unit of the storage of the LinearAllocator 26 * 27 * @see LinearAllocator 28 */ 29template<typename DataType, size_t ChunkSize> 30struct Chunk 31{ 32public: 33 typedef DataType value_type; 34public: 35 Chunk() 36 : next(0), bound(0) 37 { } 38 39 static size_t size() { return ChunkSize; } 40 41public: 42 Chunk* next; 43 size_t bound; 44 DataType data[ChunkSize]; 45}; 46 47template<typename DataType> 48struct Chunk<DataType, 0> 49{ 50public: 51 typedef DataType value_type; 52 53public: 54 Chunk() 55 : next(0), bound(0) { 56 if (0 != m_Size) 57 data = (DataType*)malloc(sizeof(DataType)*m_Size); 58 else 59 data = 0; 60 } 61 62 ~Chunk() { 63 if (data) 64 free(data); 65 } 66 67 static size_t size() { return m_Size; } 68 static void setSize(size_t pSize) { m_Size = pSize; } 69 70public: 71 Chunk* next; 72 size_t bound; 73 DataType *data; 74 static size_t m_Size; 75}; 76 77template<typename DataType> 78size_t Chunk<DataType, 0>::m_Size = 0; 79 80template<typename ChunkType> 81class LinearAllocatorBase : private Uncopyable 82{ 83public: 84 typedef ChunkType chunk_type; 85 typedef typename ChunkType::value_type value_type; 86 typedef typename ChunkType::value_type* pointer; 87 typedef typename ChunkType::value_type& reference; 88 typedef const typename ChunkType::value_type* const_pointer; 89 typedef const typename ChunkType::value_type& const_reference; 90 typedef size_t size_type; 91 typedef ptrdiff_t difference_type; 92 typedef unsigned char byte_type; 93 94protected: 95 LinearAllocatorBase() 96 : m_pRoot(0), 97 m_pCurrent(0), 98 m_AllocatedNum(0) { 99 } 100 101 // LinearAllocatorBase does NOT mean to destroy the allocated memory. 102 // If you want a memory allocator to release memory at destruction, please 103 // use GCFactory series. 104 virtual ~LinearAllocatorBase() 105 { } 106 107public: 108 pointer address(reference X) const 109 { return &X; } 110 111 const_pointer address(const_reference X) const 112 { return &X; } 113 114 /// standard construct - constructing an object on the location pointed by 115 // pPtr, and using its copy constructor to initialized its value to pValue. 116 // 117 // @param pPtr the address where the object to be constructed 118 // @param pValue the value to be constructed 119 void construct(pointer pPtr, const_reference pValue) 120 { new (pPtr) value_type(pValue); } 121 122 /// default construct - constructing an object on the location pointed by 123 // pPtr, and using its default constructor to initialized its value to 124 // pValue. 125 // 126 // @param pPtr the address where the object to be constructed 127 void construct(pointer pPtr) 128 { new (pPtr) value_type(); } 129 130 /// standard destroy - destroy data on arbitrary address 131 // @para pPtr the address where the data to be destruected. 132 void destroy(pointer pPtr) 133 { pPtr->~value_type(); } 134 135 /// allocate - allocate N data in order. 136 // - Disallow to allocate a chunk whose size is bigger than a chunk. 137 // 138 // @param N the number of allocated data. 139 // @return the start address of the allocated memory 140 pointer allocate(size_type N) { 141 if (0 == N || N > chunk_type::size()) 142 return 0; 143 144 if (empty()) 145 initialize(); 146 147 size_type rest_num_elem = chunk_type::size() - m_pCurrent->bound; 148 pointer result = 0; 149 if (N > rest_num_elem) 150 createChunk(); 151 result = const_cast<pointer>(&(m_pCurrent->data[m_pCurrent->bound])); 152 m_pCurrent->bound += N; 153 return result; 154 } 155 156 /// allocate - clone function of allocating one datum. 157 pointer allocate() { 158 if (empty()) 159 initialize(); 160 161 pointer result = 0; 162 if (chunk_type::size() == m_pCurrent->bound) 163 createChunk(); 164 result = const_cast<pointer>(&(m_pCurrent->data[m_pCurrent->bound])); 165 ++m_pCurrent->bound; 166 return result; 167 } 168 169 /// deallocate - deallocate N data from the pPtr 170 // - if we can simply release some memory, then do it. Otherwise, do 171 // nothing. 172 void deallocate(pointer &pPtr, size_type N) { 173 if (0 == N || 174 N > chunk_type::size() || 175 0 == m_pCurrent->bound || 176 N >= m_pCurrent->bound) 177 return; 178 if (!isAvailable(pPtr)) 179 return; 180 m_pCurrent->bound -= N; 181 pPtr = 0; 182 } 183 184 /// deallocate - clone function of deallocating one datum 185 void deallocate(pointer &pPtr) { 186 if (0 == m_pCurrent->bound) 187 return; 188 if (!isAvailable(pPtr)) 189 return; 190 m_pCurrent->bound -= 1; 191 pPtr = 0; 192 } 193 194 /// isIn - whether the pPtr is in the current chunk? 195 bool isIn(pointer pPtr) const { 196 if (pPtr >= &(m_pCurrent->data[0]) && 197 pPtr <= &(m_pCurrent->data[chunk_type::size()-1])) 198 return true; 199 return false; 200 } 201 202 /// isIn - whether the pPtr is allocated, and can be constructed. 203 bool isAvailable(pointer pPtr) const { 204 if (pPtr >= &(m_pCurrent->data[m_pCurrent->bound]) && 205 pPtr <= &(m_pCurrent->data[chunk_type::size()-1])) 206 return true; 207 return false; 208 } 209 210 void reset() { 211 m_pRoot = 0; 212 m_pCurrent = 0; 213 m_AllocatedNum = 0; 214 } 215 216 /// clear - clear all chunks 217 void clear() { 218 chunk_type *cur = m_pRoot, *prev; 219 while (0 != cur) { 220 unsigned int idx=0; 221 prev = cur; 222 cur = cur->next; 223 while (idx != prev->bound) { 224 destroy(&prev->data[idx]); 225 ++idx; 226 } 227 delete prev; 228 } 229 reset(); 230 } 231 232 // ----- observers ----- // 233 bool empty() const { 234 return (0 == m_pRoot); 235 } 236 237 size_type max_size() const 238 { return m_AllocatedNum; } 239 240protected: 241 inline void initialize() { 242 m_pRoot = new chunk_type(); 243 m_pCurrent = m_pRoot; 244 m_AllocatedNum += chunk_type::size(); 245 } 246 247 inline chunk_type *createChunk() { 248 chunk_type *result = new chunk_type(); 249 m_pCurrent->next = result; 250 m_pCurrent = result; 251 m_AllocatedNum += chunk_type::size(); 252 return result; 253 } 254 255protected: 256 chunk_type *m_pRoot; 257 chunk_type *m_pCurrent; 258 size_type m_AllocatedNum; 259}; 260 261/** \class LinearAllocator 262 * \brief LinearAllocator is another bump pointer allocator which should be 263 * limited in use of two-phase memory allocation. 264 * 265 * Two-phase memory allocation clear separates the use of memory into 'claim' 266 * and 'release' phases. There are no interleaving allocation and 267 * deallocation. Interleaving 'allocate' and 'deallocate' increases the size 268 * of allocated memory, and causes bad locality. 269 * 270 * The underlying concept of LinearAllocator is a memory pool. LinearAllocator 271 * is a simple implementation of boost::pool's ordered_malloc() and 272 * ordered_free(). 273 * 274 * template argument DataType is the DataType to be allocated 275 * template argument ChunkSize is the number of bytes of a chunk 276 */ 277template<typename DataType, size_t ChunkSize> 278class LinearAllocator : public LinearAllocatorBase<Chunk<DataType, ChunkSize> > 279{ 280public: 281 template<typename NewDataType> 282 struct rebind { 283 typedef LinearAllocator<NewDataType, ChunkSize> other; 284 }; 285 286public: 287 LinearAllocator() 288 : LinearAllocatorBase<Chunk<DataType, ChunkSize> >() { 289 } 290 291 virtual ~LinearAllocator() 292 { } 293}; 294 295template<typename DataType> 296class LinearAllocator<DataType, 0> : public LinearAllocatorBase<Chunk<DataType, 0> > 297{ 298public: 299 template<typename NewDataType> 300 struct rebind { 301 typedef LinearAllocator<NewDataType, 0> other; 302 }; 303 304public: 305 explicit LinearAllocator(size_t pNum) 306 : LinearAllocatorBase<Chunk<DataType, 0> >() { 307 Chunk<DataType, 0>::setSize(pNum); 308 } 309 310 virtual ~LinearAllocator() 311 { } 312}; 313 314template<typename DataType> 315class MallocAllocator 316{ 317public: 318 typedef size_t size_type; 319 typedef ptrdiff_t difference_type; 320 typedef DataType* pointer; 321 typedef const DataType* const_pointer; 322 typedef DataType& reference; 323 typedef const DataType& const_reference; 324 typedef DataType value_type; 325 326 template<typename OtherDataType> 327 struct rebind 328 { 329 typedef MallocAllocator<OtherDataType> other; 330 }; 331 332public: 333 MallocAllocator() throw() 334 { } 335 336 MallocAllocator(const MallocAllocator&) throw() 337 { } 338 339 ~MallocAllocator() throw() 340 { } 341 342 pointer address(reference X) const 343 { return &X; } 344 345 const_pointer address(const_reference X) const 346 { return &X; } 347 348 pointer allocate(size_type pNumOfElements, const void* = 0) 349 { 350 return static_cast<DataType*>( 351 std::malloc(pNumOfElements*sizeof(DataType))); 352 } 353 354 void deallocate(pointer pObject, size_type) 355 { std::free(static_cast<void*>(pObject)); } 356 357 size_type max_size() const throw() 358 { return size_t(-1) / sizeof(DataType); } 359 360 void construct(pointer pObject, const DataType& pValue) 361 { ::new((void *)pObject) value_type(pValue); } 362 363 void destroy(pointer pObject) 364 { pObject->~DataType(); } 365 366}; 367 368template<> 369class MallocAllocator<void> 370{ 371public: 372 typedef size_t size_type; 373 typedef ptrdiff_t difference_type; 374 typedef void* pointer; 375 typedef const void* const_pointer; 376 typedef void* reference; 377 typedef const void* const_reference; 378 typedef void* value_type; 379 380 template<typename OtherDataType> 381 struct rebind 382 { 383 typedef MallocAllocator<OtherDataType> other; 384 }; 385 386public: 387 MallocAllocator() throw() 388 { } 389 390 MallocAllocator(const MallocAllocator&) throw() 391 { } 392 393 ~MallocAllocator() throw() 394 { } 395 396 size_type max_size() const throw() 397 { return size_t(-1) / sizeof(void*); } 398 399 pointer address(reference X) const 400 { return X; } 401 402 const_pointer address(const_reference X) const 403 { return X; } 404 405 template<typename DataType> 406 DataType* allocate(size_type pNumOfElements, const void* = 0) { 407 return static_cast<DataType*>( 408 std::malloc(pNumOfElements*sizeof(DataType))); 409 } 410 411 pointer allocate(size_type pNumOfElements, const void* = 0) { 412 return std::malloc(pNumOfElements); 413 } 414 415 template<typename DataType> 416 void deallocate(DataType* pObject, size_type) 417 { std::free(static_cast<void*>(pObject)); } 418 419 void deallocate(pointer pObject, size_type) 420 { std::free(pObject); } 421 422 template<typename DataType> 423 void construct(DataType* pObject, const DataType& pValue) 424 { /* do nothing */ } 425 426 void construct(pointer pObject, const_reference pValue) 427 { /* do nothing */ } 428 429 template<typename DataType> 430 void destroy(DataType* pObject) 431 { /* do nothing */ } 432 433 void destroy(pointer pObject) 434 { /* do nothing */ } 435}; 436 437} // namespace mcld 438 439#endif 440 441