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
15namespace llvm {
16namespace dwarf_linker {
17namespace 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.
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 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