1193323Sed//==- llvm/Support/Recycler.h - Recycling Allocator --------------*- C++ -*-==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the Recycler class template. See the doxygen comment for 11193323Sed// Recycler for more details. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef LLVM_SUPPORT_RECYCLER_H 16193323Sed#define LLVM_SUPPORT_RECYCLER_H 17193323Sed 18193323Sed#include "llvm/ADT/ilist.h" 19193323Sed#include "llvm/Support/AlignOf.h" 20234353Sdim#include "llvm/Support/ErrorHandling.h" 21193323Sed#include <cassert> 22193323Sed 23193323Sednamespace llvm { 24193323Sed 25249423Sdimclass BumpPtrAllocator; 26249423Sdim 27193323Sed/// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for 28193323Sed/// printing statistics. 29193323Sed/// 30193323Sedvoid PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize); 31193323Sed 32193323Sed/// RecyclerStruct - Implementation detail for Recycler. This is a 33193323Sed/// class that the recycler imposes on free'd memory to carve out 34193323Sed/// next/prev pointers. 35193323Sedstruct RecyclerStruct { 36193323Sed RecyclerStruct *Prev, *Next; 37193323Sed}; 38193323Sed 39193323Sedtemplate<> 40198090Srdivackystruct ilist_traits<RecyclerStruct> : 41198090Srdivacky public ilist_default_traits<RecyclerStruct> { 42193323Sed static RecyclerStruct *getPrev(const RecyclerStruct *t) { return t->Prev; } 43193323Sed static RecyclerStruct *getNext(const RecyclerStruct *t) { return t->Next; } 44193323Sed static void setPrev(RecyclerStruct *t, RecyclerStruct *p) { t->Prev = p; } 45193323Sed static void setNext(RecyclerStruct *t, RecyclerStruct *n) { t->Next = n; } 46193323Sed 47193323Sed mutable RecyclerStruct Sentinel; 48193323Sed RecyclerStruct *createSentinel() const { 49193323Sed return &Sentinel; 50193323Sed } 51193323Sed static void destroySentinel(RecyclerStruct *) {} 52193323Sed 53193323Sed RecyclerStruct *provideInitialHead() const { return createSentinel(); } 54193323Sed RecyclerStruct *ensureHead(RecyclerStruct*) const { return createSentinel(); } 55193323Sed static void noteHead(RecyclerStruct*, RecyclerStruct*) {} 56193323Sed 57193323Sed static void deleteNode(RecyclerStruct *) { 58234353Sdim llvm_unreachable("Recycler's ilist_traits shouldn't see a deleteNode call!"); 59193323Sed } 60193323Sed}; 61193323Sed 62193323Sed/// Recycler - This class manages a linked-list of deallocated nodes 63193323Sed/// and facilitates reusing deallocated memory in place of allocating 64193323Sed/// new memory. 65193323Sed/// 66193323Sedtemplate<class T, size_t Size = sizeof(T), size_t Align = AlignOf<T>::Alignment> 67193323Sedclass Recycler { 68193323Sed /// FreeList - Doubly-linked list of nodes that have deleted contents and 69193323Sed /// are not in active use. 70193323Sed /// 71193323Sed iplist<RecyclerStruct> FreeList; 72193323Sed 73193323Sedpublic: 74193323Sed ~Recycler() { 75193323Sed // If this fails, either the callee has lost track of some allocation, 76193323Sed // or the callee isn't tracking allocations and should just call 77193323Sed // clear() before deleting the Recycler. 78193323Sed assert(FreeList.empty() && "Non-empty recycler deleted!"); 79193323Sed } 80193323Sed 81193323Sed /// clear - Release all the tracked allocations to the allocator. The 82193323Sed /// recycler must be free of any tracked allocations before being 83193323Sed /// deleted; calling clear is one way to ensure this. 84193323Sed template<class AllocatorType> 85193323Sed void clear(AllocatorType &Allocator) { 86193323Sed while (!FreeList.empty()) { 87193323Sed T *t = reinterpret_cast<T *>(FreeList.remove(FreeList.begin())); 88193323Sed Allocator.Deallocate(t); 89193323Sed } 90193323Sed } 91193323Sed 92249423Sdim /// Special case for BumpPtrAllocator which has an empty Deallocate() 93249423Sdim /// function. 94249423Sdim /// 95249423Sdim /// There is no need to traverse the free list, pulling all the objects into 96249423Sdim /// cache. 97249423Sdim void clear(BumpPtrAllocator&) { 98249423Sdim FreeList.clearAndLeakNodesUnsafely(); 99249423Sdim } 100249423Sdim 101193323Sed template<class SubClass, class AllocatorType> 102193323Sed SubClass *Allocate(AllocatorType &Allocator) { 103193323Sed assert(sizeof(SubClass) <= Size && 104193323Sed "Recycler allocation size is less than object size!"); 105193323Sed assert(AlignOf<SubClass>::Alignment <= Align && 106193323Sed "Recycler allocation alignment is less than object alignment!"); 107193323Sed return !FreeList.empty() ? 108193323Sed reinterpret_cast<SubClass *>(FreeList.remove(FreeList.begin())) : 109193323Sed static_cast<SubClass *>(Allocator.Allocate(Size, Align)); 110193323Sed } 111193323Sed 112193323Sed template<class AllocatorType> 113193323Sed T *Allocate(AllocatorType &Allocator) { 114193323Sed return Allocate<T>(Allocator); 115193323Sed } 116193323Sed 117193323Sed template<class SubClass, class AllocatorType> 118193323Sed void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) { 119193323Sed FreeList.push_front(reinterpret_cast<RecyclerStruct *>(Element)); 120193323Sed } 121193323Sed 122193323Sed void PrintStats() { 123193323Sed PrintRecyclerStats(Size, Align, FreeList.size()); 124193323Sed } 125193323Sed}; 126193323Sed 127193323Sed} 128193323Sed 129193323Sed#endif 130