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