#ifndef LLVM_SUPPORT_RECYCLER_H
#define LLVM_SUPPORT_RECYCLER_H
-#include "llvm/ADT/alist_node.h"
+#include "llvm/ADT/ilist.h"
+#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cassert>
namespace llvm {
/// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for
/// printing statistics.
///
-void PrintRecyclerStats(size_t LargestTypeSize, size_t FreeListSize);
+void PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize);
/// Recycler - This class manages a linked-list of deallocated nodes
/// and facilitates reusing deallocated memory in place of allocating
-/// new memory. The objects it allocates are stored in alist_node
-/// containers, so they may be used in alists.
+/// new memory.
///
-template<class T, class LargestT = T>
+template<class T, size_t Size = sizeof(T), size_t Align = AlignOf<T>::Alignment>
class Recycler {
- typedef alist_node<T, LargestT> NodeTy;
-
- /// FreeListTraits - ilist traits for FreeList.
- ///
- struct FreeListTraits : ilist_traits<alist_node<T, LargestT> > {
- NodeTy &getSentinel() { return this->Sentinel; }
+ struct FreeNode {
+ FreeNode *Next;
};
- /// FreeList - Doubly-linked list of nodes that have deleted contents and
- /// are not in active use.
- ///
- iplist<NodeTy, FreeListTraits> FreeList;
+ /// List of nodes that have deleted contents and are not in active use.
+ FreeNode *FreeList = nullptr;
- /// CreateNewNode - Allocate a new node object and initialize its
- /// prev and next pointers to 0.
- ///
- template<class AllocatorType>
- NodeTy *CreateNewNode(AllocatorType &Allocator) {
- // Note that we're calling new on the *node*, to initialize its
- // Next/Prev pointers, not new on the end-user object.
- return new (Allocator.Allocate<NodeTy>()) NodeTy();
+ FreeNode *pop_val() {
+ auto *Val = FreeList;
+ FreeList = FreeList->Next;
+ return Val;
+ }
+
+ void push(FreeNode *N) {
+ N->Next = FreeList;
+ FreeList = N;
}
public:
- ~Recycler() { assert(FreeList.empty()); }
+ ~Recycler() {
+ // If this fails, either the callee has lost track of some allocation,
+ // or the callee isn't tracking allocations and should just call
+ // clear() before deleting the Recycler.
+ assert(!FreeList && "Non-empty recycler deleted!");
+ }
+ /// clear - Release all the tracked allocations to the allocator. The
+ /// recycler must be free of any tracked allocations before being
+ /// deleted; calling clear is one way to ensure this.
template<class AllocatorType>
void clear(AllocatorType &Allocator) {
- while (!FreeList.empty())
- Allocator.Deallocate(FreeList.remove(FreeList.begin()));
+ while (FreeList) {
+ T *t = reinterpret_cast<T *>(pop_val());
+ Allocator.Deallocate(t);
+ }
}
+ /// Special case for BumpPtrAllocator which has an empty Deallocate()
+ /// function.
+ ///
+ /// There is no need to traverse the free list, pulling all the objects into
+ /// cache.
+ void clear(BumpPtrAllocator &) { FreeList = nullptr; }
+
template<class SubClass, class AllocatorType>
SubClass *Allocate(AllocatorType &Allocator) {
- NodeTy *N = !FreeList.empty() ?
- FreeList.remove(FreeList.front()) :
- CreateNewNode(Allocator);
- assert(N->getPrev() == 0);
- assert(N->getNext() == 0);
- return N->getElement((SubClass*)0);
+ static_assert(AlignOf<SubClass>::Alignment <= Align,
+ "Recycler allocation alignment is less than object align!");
+ static_assert(sizeof(SubClass) <= Size,
+ "Recycler allocation size is less than object size!");
+ return FreeList ? reinterpret_cast<SubClass *>(pop_val())
+ : static_cast<SubClass *>(Allocator.Allocate(Size, Align));
}
template<class AllocatorType>
}
template<class SubClass, class AllocatorType>
- void Deallocate(AllocatorType &Allocator, SubClass* Element) {
- NodeTy *N = NodeTy::getNode(Element);
- assert(N->getPrev() == 0);
- assert(N->getNext() == 0);
- FreeList.push_front(N);
+ void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) {
+ push(reinterpret_cast<FreeNode *>(Element));
}
- void PrintStats() {
- PrintRecyclerStats(sizeof(LargestT), FreeList.size());
- }
+ void PrintStats();
};
+template <class T, size_t Size, size_t Align>
+void Recycler<T, Size, Align>::PrintStats() {
+ size_t S = 0;
+ for (auto *I = FreeList; I; I = I->Next)
+ ++S;
+ PrintRecyclerStats(Size, Align, S);
+}
+
}
#endif