contrib/llvm/include/llvm/Support/ArrayRecycler.h

   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)> class ArrayRecycler {
  30   // The free list for a given array size is a simple singly linked list.
  31   // We can't use iplist or Recycler here since those classes can't be copied.
  32   struct FreeList {
  33     FreeList *Next;
  34   };
  35
  36   static_assert(Align >= alignof(FreeList), "Object underaligned");
  37   static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
  38
  39   // Keep a free list for each array size.
  40   SmallVector<FreeList*, 8> Bucket;
  41
  42   // Remove an entry from the free list in Bucket[Idx] and return it.
  43   // Return NULL if no entries are available.
  44   T *pop(unsigned Idx) {
  45     if (Idx >= Bucket.size())
  46       return nullptr;
  47     FreeList *Entry = Bucket[Idx];
  48     if (!Entry)
  49       return nullptr;
  50     __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
  51     Bucket[Idx] = Entry->Next;
  52     __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
  53     return reinterpret_cast<T*>(Entry);
  54   }
  55
  56   // Add an entry to the free list at Bucket[Idx].
  57   void push(unsigned Idx, T *Ptr) {
  58     assert(Ptr && "Cannot recycle NULL pointer");
  59     FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
  60     if (Idx >= Bucket.size())
  61       Bucket.resize(size_t(Idx) + 1);
  62     Entry->Next = Bucket[Idx];
  63     Bucket[Idx] = Entry;
  64     __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
  65   }
  66
  67 public:
  68   /// The size of an allocated array is represented by a Capacity instance.
  69   ///
  70   /// This class is much smaller than a size_t, and it provides methods to work
  71   /// with the set of legal array capacities.
  72   class Capacity {
  73     uint8_t Index;
  74     explicit Capacity(uint8_t idx) : Index(idx) {}
  75
  76   public:
  77     Capacity() : Index(0) {}
  78
  79     /// Get the capacity of an array that can hold at least N elements.
  80     static Capacity get(size_t N) {
  81       return Capacity(N ? Log2_64_Ceil(N) : 0);
  82     }
  83
  84     /// Get the number of elements in an array with this capacity.
  85     size_t getSize() const { return size_t(1u) << Index; }
  86
  87     /// Get the bucket number for this capacity.
  88     unsigned getBucket() const { return Index; }
  89
  90     /// Get the next larger capacity. Large capacities grow exponentially, so
  91     /// this function can be used to reallocate incrementally growing vectors
  92     /// in amortized linear time.
  93     Capacity getNext() const { return Capacity(Index + 1); }
  94   };
  95
  96   ~ArrayRecycler() {
  97     // The client should always call clear() so recycled arrays can be returned
  98     // to the allocator.
  99     assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
 100   }
 101
 102   /// Release all the tracked allocations to the allocator. The recycler must
 103   /// be free of any tracked allocations before being deleted.
 104   template<class AllocatorType>
 105   void clear(AllocatorType &Allocator) {
 106     for (; !Bucket.empty(); Bucket.pop_back())
 107       while (T *Ptr = pop(Bucket.size() - 1))
 108         Allocator.Deallocate(Ptr);
 109   }
 110
 111   /// Special case for BumpPtrAllocator which has an empty Deallocate()
 112   /// function.
 113   ///
 114   /// There is no need to traverse the free lists, pulling all the objects into
 115   /// cache.
 116   void clear(BumpPtrAllocator&) {
 117     Bucket.clear();
 118   }
 119
 120   /// Allocate an array of at least the requested capacity.
 121   ///
 122   /// Return an existing recycled array, or allocate one from Allocator if
 123   /// none are available for recycling.
 124   ///
 125   template<class AllocatorType>
 126   T *allocate(Capacity Cap, AllocatorType &Allocator) {
 127     // Try to recycle an existing array.
 128     if (T *Ptr = pop(Cap.getBucket()))
 129       return Ptr;
 130     // Nope, get more memory.
 131     return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
 132   }
 133
 134   /// Deallocate an array with the specified Capacity.
 135   ///
 136   /// Cap must be the same capacity that was given to allocate().
 137   ///
 138   void deallocate(Capacity Cap, T *Ptr) {
 139     push(Cap.getBucket(), Ptr);
 140   }
 141 };
 142
 143 } // end llvm namespace
 144
 145 #endif