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