1249259Sdim//==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file defines the ArrayRecycler class template which can recycle small 11249259Sdim// arrays allocated from one of the allocators in Allocator.h 12249259Sdim// 13249259Sdim//===----------------------------------------------------------------------===// 14249259Sdim 15249259Sdim#ifndef LLVM_SUPPORT_ARRAYRECYCLER_H 16249259Sdim#define LLVM_SUPPORT_ARRAYRECYCLER_H 17249259Sdim 18249259Sdim#include "llvm/ADT/SmallVector.h" 19249259Sdim#include "llvm/Support/MathExtras.h" 20249259Sdim 21249259Sdimnamespace llvm { 22249259Sdim 23249259Sdimclass BumpPtrAllocator; 24249259Sdim 25249259Sdim/// Recycle small arrays allocated from a BumpPtrAllocator. 26249259Sdim/// 27249259Sdim/// Arrays are allocated in a small number of fixed sizes. For each supported 28249259Sdim/// array size, the ArrayRecycler keeps a free list of available arrays. 29249259Sdim/// 30249259Sdimtemplate<class T, size_t Align = AlignOf<T>::Alignment> 31249259Sdimclass ArrayRecycler { 32249259Sdim // The free list for a given array size is a simple singly linked list. 33249259Sdim // We can't use iplist or Recycler here since those classes can't be copied. 34249259Sdim struct FreeList { 35249259Sdim FreeList *Next; 36249259Sdim }; 37249259Sdim 38249259Sdim // Keep a free list for each array size. 39249259Sdim SmallVector<FreeList*, 8> Bucket; 40249259Sdim 41249259Sdim // Remove an entry from the free list in Bucket[Idx] and return it. 42249259Sdim // Return NULL if no entries are available. 43249259Sdim T *pop(unsigned Idx) { 44249259Sdim if (Idx >= Bucket.size()) 45249259Sdim return 0; 46249259Sdim FreeList *Entry = Bucket[Idx]; 47249259Sdim if (!Entry) 48249259Sdim return 0; 49249259Sdim Bucket[Idx] = Entry->Next; 50249259Sdim return reinterpret_cast<T*>(Entry); 51249259Sdim } 52249259Sdim 53249259Sdim // Add an entry to the free list at Bucket[Idx]. 54249259Sdim void push(unsigned Idx, T *Ptr) { 55249259Sdim assert(Ptr && "Cannot recycle NULL pointer"); 56249259Sdim assert(sizeof(T) >= sizeof(FreeList) && "Objects are too small"); 57249259Sdim assert(Align >= AlignOf<FreeList>::Alignment && "Object underaligned"); 58249259Sdim FreeList *Entry = reinterpret_cast<FreeList*>(Ptr); 59249259Sdim if (Idx >= Bucket.size()) 60249259Sdim Bucket.resize(size_t(Idx) + 1); 61249259Sdim Entry->Next = Bucket[Idx]; 62249259Sdim Bucket[Idx] = Entry; 63249259Sdim } 64249259Sdim 65249259Sdimpublic: 66249259Sdim /// The size of an allocated array is represented by a Capacity instance. 67249259Sdim /// 68249259Sdim /// This class is much smaller than a size_t, and it provides methods to work 69249259Sdim /// with the set of legal array capacities. 70249259Sdim class Capacity { 71249259Sdim uint8_t Index; 72249259Sdim explicit Capacity(uint8_t idx) : Index(idx) {} 73249259Sdim 74249259Sdim public: 75249259Sdim Capacity() : Index(0) {} 76249259Sdim 77249259Sdim /// Get the capacity of an array that can hold at least N elements. 78249259Sdim static Capacity get(size_t N) { 79249259Sdim return Capacity(N ? Log2_64_Ceil(N) : 0); 80249259Sdim } 81249259Sdim 82249259Sdim /// Get the number of elements in an array with this capacity. 83249259Sdim size_t getSize() const { return size_t(1u) << Index; } 84249259Sdim 85249259Sdim /// Get the bucket number for this capacity. 86249259Sdim unsigned getBucket() const { return Index; } 87249259Sdim 88249259Sdim /// Get the next larger capacity. Large capacities grow exponentially, so 89249259Sdim /// this function can be used to reallocate incrementally growing vectors 90249259Sdim /// in amortized linear time. 91249259Sdim Capacity getNext() const { return Capacity(Index + 1); } 92249259Sdim }; 93249259Sdim 94249259Sdim ~ArrayRecycler() { 95249259Sdim // The client should always call clear() so recycled arrays can be returned 96249259Sdim // to the allocator. 97249259Sdim assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!"); 98249259Sdim } 99249259Sdim 100249259Sdim /// Release all the tracked allocations to the allocator. The recycler must 101249259Sdim /// be free of any tracked allocations before being deleted. 102249259Sdim template<class AllocatorType> 103249259Sdim void clear(AllocatorType &Allocator) { 104249259Sdim for (; !Bucket.empty(); Bucket.pop_back()) 105249259Sdim while (T *Ptr = pop(Bucket.size() - 1)) 106249259Sdim Allocator.Deallocate(Ptr); 107249259Sdim } 108249259Sdim 109249259Sdim /// Special case for BumpPtrAllocator which has an empty Deallocate() 110249259Sdim /// function. 111249259Sdim /// 112249259Sdim /// There is no need to traverse the free lists, pulling all the objects into 113249259Sdim /// cache. 114249259Sdim void clear(BumpPtrAllocator&) { 115249259Sdim Bucket.clear(); 116249259Sdim } 117249259Sdim 118249259Sdim /// Allocate an array of at least the requested capacity. 119249259Sdim /// 120249259Sdim /// Return an existing recycled array, or allocate one from Allocator if 121249259Sdim /// none are available for recycling. 122249259Sdim /// 123249259Sdim template<class AllocatorType> 124249259Sdim T *allocate(Capacity Cap, AllocatorType &Allocator) { 125249259Sdim // Try to recycle an existing array. 126249259Sdim if (T *Ptr = pop(Cap.getBucket())) 127249259Sdim return Ptr; 128249259Sdim // Nope, get more memory. 129249259Sdim return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align)); 130249259Sdim } 131249259Sdim 132249259Sdim /// Deallocate an array with the specified Capacity. 133249259Sdim /// 134249259Sdim /// Cap must be the same capacity that was given to allocate(). 135249259Sdim /// 136249259Sdim void deallocate(Capacity Cap, T *Ptr) { 137249259Sdim push(Cap.getBucket(), Ptr); 138249259Sdim } 139249259Sdim}; 140249259Sdim 141249259Sdim} // end llvm namespace 142249259Sdim 143249259Sdim#endif 144