168 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H10#define LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H11 12#include "llvm/Support/PerThreadBumpPtrAllocator.h"13#include <atomic>14 15namespace llvm {16namespace dwarf_linker {17namespace parallel {18 19/// This class is a simple list of T structures. It keeps elements as20/// 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.23template <typename T, size_t ItemsGroupSize = 512> class ArrayList {24public: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 103protected: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 by115 // several threads. Use getItemsCount() method to get real number of items116 // 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 if128 // it is empty. If \p AtomicGroup is filled by another thread then129 // 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_strong(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 parallel164} // end of namespace dwarf_linker165} // end of namespace llvm166 167#endif // LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H168