1 //==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the ArrayRecycler class template which can recycle small 11 // arrays allocated from one of the allocators in Allocator.h 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_SUPPORT_ARRAYRECYCLER_H 16 #define LLVM_SUPPORT_ARRAYRECYCLER_H 17 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/Support/Allocator.h" 20 #include "llvm/Support/MathExtras.h" 21 22 namespace llvm { 23 24 /// Recycle small arrays allocated from a BumpPtrAllocator. 25 /// 26 /// Arrays are allocated in a small number of fixed sizes. For each supported 27 /// array size, the ArrayRecycler keeps a free list of available arrays. 28 /// 29 template<class T, size_t Align = AlignOf<T>::Alignment> 30 class ArrayRecycler { 31 // The free list for a given array size is a simple singly linked list. 32 // We can't use iplist or Recycler here since those classes can't be copied. 33 struct FreeList { 34 FreeList *Next; 35 }; 36 37 static_assert(Align >= AlignOf<FreeList>::Alignment, "Object underaligned"); 38 static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small"); 39 40 // Keep a free list for each array size. 41 SmallVector<FreeList*, 8> Bucket; 42 43 // Remove an entry from the free list in Bucket[Idx] and return it. 44 // Return NULL if no entries are available. pop(unsigned Idx)45 T *pop(unsigned Idx) { 46 if (Idx >= Bucket.size()) 47 return nullptr; 48 FreeList *Entry = Bucket[Idx]; 49 if (!Entry) 50 return nullptr; 51 Bucket[Idx] = Entry->Next; 52 return reinterpret_cast<T*>(Entry); 53 } 54 55 // Add an entry to the free list at Bucket[Idx]. push(unsigned Idx,T * Ptr)56 void push(unsigned Idx, T *Ptr) { 57 assert(Ptr && "Cannot recycle NULL pointer"); 58 FreeList *Entry = reinterpret_cast<FreeList*>(Ptr); 59 if (Idx >= Bucket.size()) 60 Bucket.resize(size_t(Idx) + 1); 61 Entry->Next = Bucket[Idx]; 62 Bucket[Idx] = Entry; 63 } 64 65 public: 66 /// The size of an allocated array is represented by a Capacity instance. 67 /// 68 /// This class is much smaller than a size_t, and it provides methods to work 69 /// with the set of legal array capacities. 70 class Capacity { 71 uint8_t Index; Capacity(uint8_t idx)72 explicit Capacity(uint8_t idx) : Index(idx) {} 73 74 public: Capacity()75 Capacity() : Index(0) {} 76 77 /// Get the capacity of an array that can hold at least N elements. get(size_t N)78 static Capacity get(size_t N) { 79 return Capacity(N ? Log2_64_Ceil(N) : 0); 80 } 81 82 /// Get the number of elements in an array with this capacity. getSize()83 size_t getSize() const { return size_t(1u) << Index; } 84 85 /// Get the bucket number for this capacity. getBucket()86 unsigned getBucket() const { return Index; } 87 88 /// Get the next larger capacity. Large capacities grow exponentially, so 89 /// this function can be used to reallocate incrementally growing vectors 90 /// in amortized linear time. getNext()91 Capacity getNext() const { return Capacity(Index + 1); } 92 }; 93 ~ArrayRecycler()94 ~ArrayRecycler() { 95 // The client should always call clear() so recycled arrays can be returned 96 // to the allocator. 97 assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!"); 98 } 99 100 /// Release all the tracked allocations to the allocator. The recycler must 101 /// be free of any tracked allocations before being deleted. 102 template<class AllocatorType> clear(AllocatorType & Allocator)103 void clear(AllocatorType &Allocator) { 104 for (; !Bucket.empty(); Bucket.pop_back()) 105 while (T *Ptr = pop(Bucket.size() - 1)) 106 Allocator.Deallocate(Ptr); 107 } 108 109 /// Special case for BumpPtrAllocator which has an empty Deallocate() 110 /// function. 111 /// 112 /// There is no need to traverse the free lists, pulling all the objects into 113 /// cache. clear(BumpPtrAllocator &)114 void clear(BumpPtrAllocator&) { 115 Bucket.clear(); 116 } 117 118 /// Allocate an array of at least the requested capacity. 119 /// 120 /// Return an existing recycled array, or allocate one from Allocator if 121 /// none are available for recycling. 122 /// 123 template<class AllocatorType> allocate(Capacity Cap,AllocatorType & Allocator)124 T *allocate(Capacity Cap, AllocatorType &Allocator) { 125 // Try to recycle an existing array. 126 if (T *Ptr = pop(Cap.getBucket())) 127 return Ptr; 128 // Nope, get more memory. 129 return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align)); 130 } 131 132 /// Deallocate an array with the specified Capacity. 133 /// 134 /// Cap must be the same capacity that was given to allocate(). 135 /// deallocate(Capacity Cap,T * Ptr)136 void deallocate(Capacity Cap, T *Ptr) { 137 push(Cap.getBucket(), Ptr); 138 } 139 }; 140 141 } // end llvm namespace 142 143 #endif 144