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