xref: /freebsd/contrib/llvm-project/llvm/lib/DWARFLinker/Parallel/ArrayList.h (revision 2f9966ff63d65bd474478888c9088eeae3f9c669)
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
168