LLVM: lib/DWARFLinker/Parallel/ArrayList.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9#ifndef LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
10#define LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
11
13#include
14
15namespace llvm {
18
19
20
21
22
23template <typename T, size_t ItemsGroupSize = 512> class ArrayList {
24public:
27
28
31
32
36 }
37
39 size_t CurItemsCount;
40 do {
42 CurItemsCount = CurGroup->ItemsCount.fetch_add(1);
43
44
45 if (CurItemsCount < ItemsGroupSize)
46 break;
47
48
49 if (!CurGroup->Next)
51
52 LastGroup.compare_exchange_weak(CurGroup, CurGroup->Next);
53 } while (true);
54
55
56 CurGroup->Items[CurItemsCount] = Item;
57 return CurGroup->Items[CurItemsCount];
58 }
59
61
62
65 CurGroup = CurGroup->Next) {
66 for (T &Item : *CurGroup)
67 Handler(Item);
68 }
69 }
70
71
73
74
79
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
94 size_t Result = 0;
95
97 CurGroup = CurGroup->Next)
98 Result += CurGroup->getItemsCount();
99
100 return Result;
101 }
102
103protected:
105 using ArrayTy = std::array<T, ItemsGroupSize>;
106
107
109
110
111 std::atomic<ItemsGroup *> Next = nullptr;
112
113
114
115
116
118
120 return std::min(ItemsCount.load(), ItemsGroupSize);
121 }
122
123 typename ArrayTy::iterator begin() { return Items.begin(); }
125 };
126
127
128
129
130
133
134
137 NewGroup->Next = nullptr;
138
139
140 if (AtomicGroup.compare_exchange_strong(CurGroup, NewGroup))
141 return true;
142
143
144 while (CurGroup) {
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
159 std::atomic<ItemsGroup *> LastGroup = nullptr;
161};
162
163}
164}
165}
166
167#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
T & add(const T &Item)
Add specified Item to the list.
Definition ArrayList.h:29
std::atomic< ItemsGroup * > LastGroup
Definition ArrayList.h:159
bool empty()
Check whether list is empty.
Definition ArrayList.h:72
llvm::parallel::PerThreadBumpPtrAllocator * Allocator
Definition ArrayList.h:160
bool allocateNewGroup(std::atomic< ItemsGroup * > &AtomicGroup)
Definition ArrayList.h:131
size_t size()
Definition ArrayList.h:93
void forEach(ItemHandlerTy Handler)
Enumerate all items and apply specified Handler to each.
Definition ArrayList.h:63
std::atomic< ItemsGroup * > GroupsHead
Definition ArrayList.h:158
void erase()
Erase list.
Definition ArrayList.h:75
function_ref< void(T &)> ItemHandlerTy
Definition ArrayList.h:60
void sort(function_ref< bool(const T &LHS, const T &RHS)> Comparator)
Definition ArrayList.h:80
ArrayList(llvm::parallel::PerThreadBumpPtrAllocator *Allocator)
Definition ArrayList.h:25
An efficient, type-erasing, non-owning reference to a callable.
PerThreadAllocator< BumpPtrAllocator > PerThreadBumpPtrAllocator
This is an optimization pass for GlobalISel generic memory operations.
Definition ArrayList.h:104
ArrayTy Items
Definition ArrayList.h:108
std::array< T, ItemsGroupSize > ArrayTy
Definition ArrayList.h:105
std::atomic< size_t > ItemsCount
Definition ArrayList.h:117
std::atomic< ItemsGroup * > Next
Definition ArrayList.h:111
ArrayTy::iterator end()
Definition ArrayList.h:124
ArrayTy::iterator begin()
Definition ArrayList.h:123
size_t getItemsCount() const
Definition ArrayList.h:119