Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

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