include/llvm/Support/Recycler.h

   1 //==- llvm/Support/Recycler.h - Recycling Allocator --------------*- 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 Recycler class template.  See the doxygen comment for
  11 // Recycler for more details.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_SUPPORT_RECYCLER_H
  16 #define LLVM_SUPPORT_RECYCLER_H
  17
  18 #include "llvm/ADT/alist_node.h"
  19
  20 namespace llvm {
  21
  22 /// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for
  23 /// printing statistics.
  24 ///
  25 void PrintRecyclerStats(size_t LargestTypeSize, size_t FreeListSize);
  26
  27 /// Recycler - This class manages a linked-list of deallocated nodes
  28 /// and facilitates reusing deallocated memory in place of allocating
  29 /// new memory. The objects it allocates are stored in alist_node
  30 /// containers, so they may be used in alists.
  31 ///
  32 template<class T, class LargestT = T>
  33 class Recycler {
  34   typedef alist_node<T, LargestT> NodeTy;
  35
  36   /// FreeListTraits - ilist traits for FreeList.
  37   ///
  38   struct FreeListTraits : ilist_traits<alist_node<T, LargestT> > {
  39     NodeTy &getSentinel() { return this->Sentinel; }
  40   };
  41
  42   /// FreeList - Doubly-linked list of nodes that have deleted contents and
  43   /// are not in active use.
  44   ///
  45   iplist<NodeTy, FreeListTraits> FreeList;
  46
  47   /// CreateNewNode - Allocate a new node object and initialize its
  48   /// prev and next pointers to 0.
  49   ///
  50   template<class AllocatorType>
  51   NodeTy *CreateNewNode(AllocatorType &Allocator) {
  52     // Note that we're calling new on the *node*, to initialize its
  53     // Next/Prev pointers, not new on the end-user object.
  54     return new (Allocator.Allocate<NodeTy>()) NodeTy();
  55   }
  56
  57 public:
  58   ~Recycler() { assert(FreeList.empty()); }
  59
  60   template<class AllocatorType>
  61   void clear(AllocatorType &Allocator) {
  62     while (!FreeList.empty())
  63       Allocator.Deallocate(FreeList.remove(FreeList.begin()));
  64   }
  65
  66   template<class SubClass, class AllocatorType>
  67   SubClass *Allocate(AllocatorType &Allocator) {
  68     NodeTy *N = !FreeList.empty() ?
  69                 FreeList.remove(FreeList.front()) :
  70                 CreateNewNode(Allocator);
  71     assert(N->getPrev() == 0);
  72     assert(N->getNext() == 0);
  73     return N->getElement((SubClass*)0);
  74   }
  75
  76   template<class AllocatorType>
  77   T *Allocate(AllocatorType &Allocator) {
  78     return Allocate<T>(Allocator);
  79   }
  80
  81   template<class SubClass, class AllocatorType>
  82   void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) {
  83     NodeTy *N = NodeTy::getNode(Element);
  84     assert(N->getPrev() == 0);
  85     assert(N->getNext() == 0);
  86     FreeList.push_front(N);
  87   }
  88
  89   void PrintStats() {
  90     PrintRecyclerStats(sizeof(LargestT), FreeList.size());
  91   }
  92 };
  93
  94 }
  95
  96 #endif