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