1 files changed, 167 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/DWARFLinker/Parallel/ArrayList.h b/contrib/llvm-project/llvm/lib/DWARFLinker/Parallel/ArrayList.h
new file mode 100644
index 000000000000..c48f828609be
--- /dev/null
+++ b/contrib/llvm-project/llvm/lib/DWARFLinker/Parallel/ArrayList.h
@@ -0,0 +1,167 @@
+//===- ArrayList.h ----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
+#define LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H
+
+#include "llvm/Support/PerThreadBumpPtrAllocator.h"
+#include <atomic>
+
+namespace llvm {
+namespace dwarf_linker {
+namespace parallel {
+
+/// This class is a simple list of T structures. It keeps elements as
+/// pre-allocated groups to save memory for each element's next pointer.
+/// It allocates internal data using specified per-thread BumpPtrAllocator.
+/// Method add() can be called asynchronously.
+template <typename T, size_t ItemsGroupSize = 512> class ArrayList {
+public:
+  ArrayList(llvm::parallel::PerThreadBumpPtrAllocator *Allocator)
+      : Allocator(Allocator) {}
+
+  /// Add specified \p Item to the list.
+  T &add(const T &Item) {
+    assert(Allocator);
+
+    // Allocate head group if it is not allocated yet.
+    while (!LastGroup) {
+      if (allocateNewGroup(GroupsHead))
+        LastGroup = GroupsHead.load();
+    }
+
+    ItemsGroup *CurGroup;
+    size_t CurItemsCount;
+    do {
+      CurGroup = LastGroup;
+      CurItemsCount = CurGroup->ItemsCount.fetch_add(1);
+
+      // Check whether current group is full.
+      if (CurItemsCount < ItemsGroupSize)
+        break;
+
+      // Allocate next group if necessary.
+      if (!CurGroup->Next)
+        allocateNewGroup(CurGroup->Next);
+
+      LastGroup.compare_exchange_weak(CurGroup, CurGroup->Next);
+    } while (true);
+
+    // Store item into the current group.
+    CurGroup->Items[CurItemsCount] = Item;
+    return CurGroup->Items[CurItemsCount];
+  }
+
+  using ItemHandlerTy = function_ref<void(T &)>;
+
+  /// Enumerate all items and apply specified \p Handler to each.
+  void forEach(ItemHandlerTy Handler) {
+    for (ItemsGroup *CurGroup = GroupsHead; CurGroup;
+         CurGroup = CurGroup->Next) {
+      for (T &Item : *CurGroup)
+        Handler(Item);
+    }
+  }
+
+  /// Check whether list is empty.
+  bool empty() { return !GroupsHead; }
+
+  /// Erase list.
+  void erase() {
+    GroupsHead = nullptr;
+    LastGroup = nullptr;
+  }
+
+  void sort(function_ref<bool(const T &LHS, const T &RHS)> Comparator) {
+    SmallVector<T> SortedItems;
+    forEach([&](T &Item) { SortedItems.push_back(Item); });
+
+    if (SortedItems.size()) {
+      std::sort(SortedItems.begin(), SortedItems.end(), Comparator);
+
+      size_t SortedItemIdx = 0;
+      forEach([&](T &Item) { Item = SortedItems[SortedItemIdx++]; });
+      assert(SortedItemIdx == SortedItems.size());
+    }
+  }
+
+  size_t size() {
+    size_t Result = 0;
+
+    for (ItemsGroup *CurGroup = GroupsHead; CurGroup != nullptr;
+         CurGroup = CurGroup->Next)
+      Result += CurGroup->getItemsCount();
+
+    return Result;
+  }
+
+protected:
+  struct ItemsGroup {
+    using ArrayTy = std::array<T, ItemsGroupSize>;
+
+    // Array of items kept by this group.
+    ArrayTy Items;
+
+    // Pointer to the next items group.
+    std::atomic<ItemsGroup *> Next = nullptr;
+
+    // Number of items in this group.
+    // NOTE: ItemsCount could be inaccurate as it might be incremented by
+    // several threads. Use getItemsCount() method to get real number of items
+    // inside ItemsGroup.
+    std::atomic<size_t> ItemsCount = 0;
+
+    size_t getItemsCount() const {
+      return std::min(ItemsCount.load(), ItemsGroupSize);
+    }
+
+    typename ArrayTy::iterator begin() { return Items.begin(); }
+    typename ArrayTy::iterator end() { return Items.begin() + getItemsCount(); }
+  };
+
+  // Allocate new group. Put allocated group into the \p AtomicGroup if
+  // it is empty. If \p AtomicGroup is filled by another thread then
+  // put allocated group into the end of groups list.
+  // \returns true if allocated group is put into the \p AtomicGroup.
+  bool allocateNewGroup(std::atomic<ItemsGroup *> &AtomicGroup) {
+    ItemsGroup *CurGroup = nullptr;
+
+    // Allocate new group.
+    ItemsGroup *NewGroup = Allocator->Allocate<ItemsGroup>();
+    NewGroup->ItemsCount = 0;
+    NewGroup->Next = nullptr;
+
+    // Try to replace current group with allocated one.
+    if (AtomicGroup.compare_exchange_weak(CurGroup, NewGroup))
+      return true;
+
+    // Put allocated group as last group.
+    while (CurGroup) {
+      ItemsGroup *NextGroup = CurGroup->Next;
+
+      if (!NextGroup) {
+        if (CurGroup->Next.compare_exchange_weak(NextGroup, NewGroup))
+          break;
+      }
+
+      CurGroup = NextGroup;
+    }
+
+    return false;
+  }
+
+  std::atomic<ItemsGroup *> GroupsHead = nullptr;
+  std::atomic<ItemsGroup *> LastGroup = nullptr;
+  llvm::parallel::PerThreadBumpPtrAllocator *Allocator = nullptr;
+};
+
+} // end of namespace parallel
+} // end of namespace dwarf_linker
+} // end of namespace llvm
+
+#endif // LLVM_LIB_DWARFLINKER_PARALLEL_ARRAYLIST_H