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