llvm/lib/DWARFLinker/Parallel/ArrayList.h

   1 //===- ArrayList.h ----------------------------------------------*- 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 #ifndef LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
  10 #define LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
  11
  12 #include "llvm/Support/PerThreadBumpPtrAllocator.h"
  13 #include <atomic>
  14
  15 namespace llvm {
  16 namespace dwarf_linker {
  17 namespace parallel {
  18
  19 /// This class is a simple list of T structures. It keeps elements as
  20 /// pre-allocated groups to save memory for each element's next pointer.
  21 /// It allocates internal data using specified per-thread BumpPtrAllocator.
  22 /// Method add() can be called asynchronously.
  23 template <typename T, size_t ItemsGroupSize = 512> class ArrayList {
  24 public:
  25   ArrayList(llvm::parallel::PerThreadBumpPtrAllocator *Allocator)
  26       : Allocator(Allocator) {}
  27
  28   /// Add specified \p Item to the list.
  29   T &add(const T &Item) {
  30     assert(Allocator);
  31
  32     // Allocate head group if it is not allocated yet.
  33     while (!LastGroup) {
  34       if (allocateNewGroup(GroupsHead))
  35         LastGroup = GroupsHead.load();
  36     }
  37
  38     ItemsGroup *CurGroup;
  39     size_t CurItemsCount;
  40     do {
  41       CurGroup = LastGroup;
  42       CurItemsCount = CurGroup->ItemsCount.fetch_add(1);
  43
  44       // Check whether current group is full.
  45       if (CurItemsCount < ItemsGroupSize)
  46         break;
  47
  48       // Allocate next group if necessary.
  49       if (!CurGroup->Next)
  50         allocateNewGroup(CurGroup->Next);
  51
  52       LastGroup.compare_exchange_weak(CurGroup, CurGroup->Next);
  53     } while (true);
  54
  55     // Store item into the current group.
  56     CurGroup->Items[CurItemsCount] = Item;
  57     return CurGroup->Items[CurItemsCount];
  58   }
  59
  60   using ItemHandlerTy = function_ref<void(T &)>;
  61
  62   /// Enumerate all items and apply specified \p Handler to each.
  63   void forEach(ItemHandlerTy Handler) {
  64     for (ItemsGroup *CurGroup = GroupsHead; CurGroup;
  65          CurGroup = CurGroup->Next) {
  66       for (T &Item : *CurGroup)
  67         Handler(Item);
  68     }
  69   }
  70
  71   /// Check whether list is empty.
  72   bool empty() { return !GroupsHead; }
  73
  74   /// Erase list.
  75   void erase() {
  76     GroupsHead = nullptr;
  77     LastGroup = nullptr;
  78   }
  79
  80   void sort(function_ref<bool(const T &LHS, const T &RHS)> Comparator) {
  81     SmallVector<T> SortedItems;
  82     forEach([&](T &Item) { SortedItems.push_back(Item); });
  83
  84     if (SortedItems.size()) {
  85       std::sort(SortedItems.begin(), SortedItems.end(), Comparator);
  86
  87       size_t SortedItemIdx = 0;
  88       forEach([&](T &Item) { Item = SortedItems[SortedItemIdx++]; });
  89       assert(SortedItemIdx == SortedItems.size());
  90     }
  91   }
  92
  93   size_t size() {
  94     size_t Result = 0;
  95
  96     for (ItemsGroup *CurGroup = GroupsHead; CurGroup != nullptr;
  97          CurGroup = CurGroup->Next)
  98       Result += CurGroup->getItemsCount();
  99
 100     return Result;
 101   }
 102
 103 protected:
 104   struct ItemsGroup {
 105     using ArrayTy = std::array<T, ItemsGroupSize>;
 106
 107     // Array of items kept by this group.
 108     ArrayTy Items;
 109
 110     // Pointer to the next items group.
 111     std::atomic<ItemsGroup *> Next = nullptr;
 112
 113     // Number of items in this group.
 114     // NOTE: ItemsCount could be inaccurate as it might be incremented by
 115     // several threads. Use getItemsCount() method to get real number of items
 116     // inside ItemsGroup.
 117     std::atomic<size_t> ItemsCount = 0;
 118
 119     size_t getItemsCount() const {
 120       return std::min(ItemsCount.load(), ItemsGroupSize);
 121     }
 122
 123     typename ArrayTy::iterator begin() { return Items.begin(); }
 124     typename ArrayTy::iterator end() { return Items.begin() + getItemsCount(); }
 125   };
 126
 127   // Allocate new group. Put allocated group into the \p AtomicGroup if
 128   // it is empty. If \p AtomicGroup is filled by another thread then
 129   // put allocated group into the end of groups list.
 130   // \returns true if allocated group is put into the \p AtomicGroup.
 131   bool allocateNewGroup(std::atomic<ItemsGroup *> &AtomicGroup) {
 132     ItemsGroup *CurGroup = nullptr;
 133
 134     // Allocate new group.
 135     ItemsGroup *NewGroup = Allocator->Allocate<ItemsGroup>();
 136     NewGroup->ItemsCount = 0;
 137     NewGroup->Next = nullptr;
 138
 139     // Try to replace current group with allocated one.
 140     if (AtomicGroup.compare_exchange_weak(CurGroup, NewGroup))
 141       return true;
 142
 143     // Put allocated group as last group.
 144     while (CurGroup) {
 145       ItemsGroup *NextGroup = CurGroup->Next;
 146
 147       if (!NextGroup) {
 148         if (CurGroup->Next.compare_exchange_weak(NextGroup, NewGroup))
 149           break;
 150       }
 151
 152       CurGroup = NextGroup;
 153     }
 154
 155     return false;
 156   }
 157
 158   std::atomic<ItemsGroup *> GroupsHead = nullptr;
 159   std::atomic<ItemsGroup *> LastGroup = nullptr;
 160   llvm::parallel::PerThreadBumpPtrAllocator *Allocator = nullptr;
 161 };
 162
 163 } // end of namespace parallel
 164 } // end of namespace dwarf_linker
 165 } // end of namespace llvm
 166
 167 #endif // LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H