18a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen//==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==// 28a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// 38a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// 58a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// 88a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// 108a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// This file defines the ArrayRecycler class template which can recycle small 118a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// arrays allocated from one of the allocators in Allocator.h 128a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen// 138a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_SUPPORT_ARRAYRECYCLER_H 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_SUPPORT_ARRAYRECYCLER_H 178a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 188a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 198a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen#include "llvm/Support/MathExtras.h" 208a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 218a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesennamespace llvm { 228a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 238a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesenclass BumpPtrAllocator; 248a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 258a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen/// Recycle small arrays allocated from a BumpPtrAllocator. 268a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen/// 278a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen/// Arrays are allocated in a small number of fixed sizes. For each supported 288a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen/// array size, the ArrayRecycler keeps a free list of available arrays. 298a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen/// 308a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesentemplate<class T, size_t Align = AlignOf<T>::Alignment> 318a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesenclass ArrayRecycler { 328a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // The free list for a given array size is a simple singly linked list. 338a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // We can't use iplist or Recycler here since those classes can't be copied. 348a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen struct FreeList { 358a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen FreeList *Next; 368a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen }; 378a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 388a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Keep a free list for each array size. 398a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen SmallVector<FreeList*, 8> Bucket; 408a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 418a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Remove an entry from the free list in Bucket[Idx] and return it. 428a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Return NULL if no entries are available. 438a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen T *pop(unsigned Idx) { 448a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen if (Idx >= Bucket.size()) 458a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return 0; 468a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen FreeList *Entry = Bucket[Idx]; 478a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen if (!Entry) 488a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return 0; 498a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Bucket[Idx] = Entry->Next; 508a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return reinterpret_cast<T*>(Entry); 518a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 528a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 538a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Add an entry to the free list at Bucket[Idx]. 548a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen void push(unsigned Idx, T *Ptr) { 558a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen assert(Ptr && "Cannot recycle NULL pointer"); 568a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen assert(sizeof(T) >= sizeof(FreeList) && "Objects are too small"); 578a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen assert(Align >= AlignOf<FreeList>::Alignment && "Object underaligned"); 588a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen FreeList *Entry = reinterpret_cast<FreeList*>(Ptr); 598a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen if (Idx >= Bucket.size()) 608a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Bucket.resize(size_t(Idx) + 1); 618a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Entry->Next = Bucket[Idx]; 628a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Bucket[Idx] = Entry; 638a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 648a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 658a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesenpublic: 668a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// The size of an allocated array is represented by a Capacity instance. 678a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 688a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// This class is much smaller than a size_t, and it provides methods to work 698a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// with the set of legal array capacities. 708a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen class Capacity { 718a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen uint8_t Index; 728a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen explicit Capacity(uint8_t idx) : Index(idx) {} 738a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 748a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen public: 758a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Capacity() : Index(0) {} 768a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 778a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Get the capacity of an array that can hold at least N elements. 788a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen static Capacity get(size_t N) { 798a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return Capacity(N ? Log2_64_Ceil(N) : 0); 808a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 818a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 828a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Get the number of elements in an array with this capacity. 838a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen size_t getSize() const { return size_t(1u) << Index; } 848a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 858a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Get the bucket number for this capacity. 868a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen unsigned getBucket() const { return Index; } 878a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 888a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Get the next larger capacity. Large capacities grow exponentially, so 898a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// this function can be used to reallocate incrementally growing vectors 908a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// in amortized linear time. 918a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Capacity getNext() const { return Capacity(Index + 1); } 928a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen }; 938a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 948a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen ~ArrayRecycler() { 958a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // The client should always call clear() so recycled arrays can be returned 968a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // to the allocator. 978a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!"); 988a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 998a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1008a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Release all the tracked allocations to the allocator. The recycler must 1018a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// be free of any tracked allocations before being deleted. 1028a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen template<class AllocatorType> 1038a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen void clear(AllocatorType &Allocator) { 1048a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen for (; !Bucket.empty(); Bucket.pop_back()) 1058a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen while (T *Ptr = pop(Bucket.size() - 1)) 1068a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Allocator.Deallocate(Ptr); 1078a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 1088a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1098a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Special case for BumpPtrAllocator which has an empty Deallocate() 1108a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// function. 1118a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 1128a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// There is no need to traverse the free lists, pulling all the objects into 1138a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// cache. 1148a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen void clear(BumpPtrAllocator&) { 1158a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen Bucket.clear(); 1168a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 1178a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1188a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Allocate an array of at least the requested capacity. 1198a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 1208a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Return an existing recycled array, or allocate one from Allocator if 1218a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// none are available for recycling. 1228a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 1238a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen template<class AllocatorType> 1248a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen T *allocate(Capacity Cap, AllocatorType &Allocator) { 1258a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Try to recycle an existing array. 1268a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen if (T *Ptr = pop(Cap.getBucket())) 1278a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return Ptr; 1288a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen // Nope, get more memory. 1298a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align)); 1308a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 1318a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1328a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Deallocate an array with the specified Capacity. 1338a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 1348a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// Cap must be the same capacity that was given to allocate(). 1358a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen /// 1368a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen void deallocate(Capacity Cap, T *Ptr) { 1378a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen push(Cap.getBucket(), Ptr); 1388a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen } 1398a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen}; 1408a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1418a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen} // end llvm namespace 1428a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen 1438a0631a35e7719c5a3dc8678ec342fe5a83170daJakob Stoklund Olesen#endif 144