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