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