[DWARFLinkerParallel] Add simple list with thread safe insertions.

[avl]

Summary

This patch is extracted from D96035. It adds simple non-allocating list class.
The list allows thread safe insertions. List items should be allocated
and deleted outside the list.

[tschuett]

llvm/include/llvm/DWARFLinkerNext/List.h

24 ↗

(On Diff #485731)

not atomic?

45 ↗

(On Diff #485731)

not atomic?

[avl]

llvm/include/llvm/DWARFLinkerNext/List.h

24 ↗

(On Diff #485731)

only "Head" requires std::atomic. as only "Head" field is changed by different threads.

45 ↗

(On Diff #485731)

CurHead is not visible or changed by other threads, thus not necessarily to make it atomic.

[avl]

renamed AddItem to AddAtFront. Cured test.

[avl]

rebased.

[avl]

ping.

[avl]

friendly ping.

[JDevlieghere]

The implementation looks good. I left some inline comments with suggestions for names that more closely match that of the STL containers to make the class feel more familiar to those who are used to them.

llvm/include/llvm/DWARFLinkerParallel/NonAllocatingList.h

38

front

42

empty

45

pushFront

76

clear

79

sort

98

reverse

[avl]

addressed comments(renamed class methods).

[JDevlieghere]

LGTM

[avl]

cancel this patch in favor of another solution used by D153268

llvm/include/llvm/DWARFLinkerParallel/DWARFLinker.h

 //===- DWARFLinker.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_DWARFLINKERPARALLEL_DWARFLINKER_H
 #define LLVM_DWARFLINKERPARALLEL_DWARFLINKER_H
 
+#include "llvm/DWARFLinkerParallel/NonAllocatingList.h"
+
 namespace llvm {
 namespace dwarflinker_parallel {} // end namespace dwarflinker_parallel
 } // end namespace llvm
 
 #endif // LLVM_DWARFLINKERPARALLEL_DWARFLINKER_H

llvm/include/llvm/DWARFLinkerParallel/NonAllocatingList.h

+//===- NonAllocatingList.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_DWARFLINKERPARALLEL_NONALLOCATINGLIST_H
+#define LLVM_DWARFLINKERPARALLEL_NONALLOCATINGLIST_H
+
+#include "llvm/ADT/STLFunctionalExtras.h"
+#include <algorithm>
+#include <atomic>
+#include <type_traits>
+#include <vector>
+
+namespace llvm {
+namespace dwarflinker_parallel {
+
+/// Mixin adding "Next" field for the list entry.
+template <class T> class NonAllocatingListItemMixin {
+public:
+  T *Next = nullptr;
+};
+
+/// Simple list with lock free insertions. Other methods are not thread-safe.
+/// ASSUMPTION: nodes are allocated and deallocated outside the list.
+template <class T> class NonAllocatingList {
+public:
+  NonAllocatingList() {
+    static_assert(
+        std::is_base_of<NonAllocatingListItemMixin<T>, T>::value,
+        "type parameter of List must derive from NonAllocatingListItemMixin");
+  }
+
+  /// \returns current head of the list.
+  T *getHead() { return Head; }
+  const T *getHead() const { return Head; }
+
+  /// \returns true if the list is empty.
+  bool isEmpty() const { return Head == nullptr; }
+
+  /// Adds \p NewItem into the list. Item added at front of the list.
+  void addAtFront(T *NewItem) {
+    T *CurHead = nullptr;
+    do {
+      CurHead = Head;
+      NewItem->Next = CurHead;
+    } while (!Head.compare_exchange_weak(CurHead, NewItem));
+  }
+
+  /// Enumerates the items in the list and calls the \p Handler for each item.
+  void enumerateItems(function_ref<void(T &Item)> Handler) {
+    T *CurItem = Head;
+    while (CurItem != nullptr) {
+      T *NextItem = CurItem->Next;
+      Handler(*CurItem);
+
+      CurItem = NextItem;
+    }
+  }
+
+  /// Enumerates the items in the list and calls the \p handler for each item.
+  void enumerateItems(function_ref<void(const T &Item)> Handler) const {
+    T *CurItem = Head;
+    while (CurItem != nullptr) {
+      T *NextItem = CurItem->Next;
+      Handler(*CurItem);
+
+      CurItem = NextItem;
+    }
+  }
+
+  /// Sets list head to null.
+  void erase() { Head = nullptr; }
+
+  /// Sorts list items according to the \p Comparator.
+  void sortItems(function_ref<bool(T *LHS, T *RHS)> Comparator) {
+    // TODO: It might be beneficial to implement sorting of items
+    // using merge sort.
+    std::vector<T *> Types;
+    enumerateItems([&](T &Type) { Types.push_back(&Type); });
+
+    if (Types.size()) {
+      std::sort(Types.begin(), Types.end(), Comparator);
+
+      Head = *Types.begin();
+      Types.back()->Next = nullptr;
+
+      for (size_t CurIdx = 1; CurIdx < Types.size(); CurIdx++) {
+        Types[CurIdx - 1]->Next = Types[CurIdx];
+      }
+    }
+  }
+
+  /// Reverse list items.
+  void reverseItems() {
+    T *nextItem = nullptr;
+    enumerateItems([&](T &Type) {
+      Type.Next = nextItem;
+      nextItem = &Type;
+    });
+    Head = nextItem;
+  }
+
+protected:
+  std::atomic<T *> Head = {nullptr};
+};
+
+} // end of namespace dwarflinker_parallel
+} // end namespace llvm
+
+#endif // LLVM_DWARFLINKERPARALLEL_NONALLOCATINGLIST_H

llvm/unittests/DWARFLinkerParallel/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   DWARFLinkerParallel
   )
 
 add_llvm_unittest(DWARFLinkerParallelTests
   DWARFLinkerTest.cpp
+  NonAllocatingListTest.cpp
   )
 
 target_link_libraries(DWARFLinkerParallelTests PRIVATE LLVMTestingSupport)
 
 add_dependencies(DWARFLinkerParallelTests intrinsics_gen)

llvm/unittests/DWARFLinkerParallel/NonAllocatingListTest.cpp

+//===- llvm/unittest/DWARFLinkerParallel/NonAllocatingListTest.cpp --------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DWARFLinkerParallel/NonAllocatingList.h"
+#include "llvm/Support/Parallel.h"
+#include "gtest/gtest.h"
+#include <cstdlib>
+
+using namespace llvm;
+using namespace dwarflinker_parallel;
+
+namespace {
+
+struct Number : public NonAllocatingListItemMixin<Number> {
+  int Num = 0;
+};
+
+inline bool operator==(const Number &LHS, const Number &RHS) {
+  return LHS.Num == RHS.Num;
+}
+
+TEST(NonAllocatingListTest, TestList) {
+
+  Number N1;
+  N1.Num = 1;
+
+  NonAllocatingList<Number> L;
+
+  EXPECT_TRUE(L.isEmpty());
+  EXPECT_TRUE(L.getHead() == nullptr);
+
+  // Add first item.
+  L.addAtFront(&N1);
+  EXPECT_FALSE(L.isEmpty());
+  EXPECT_TRUE(L.getHead() == &N1);
+
+  Number N2;
+  N2.Num = 2;
+
+  // Add second item.
+  L.addAtFront(&N2);
+  EXPECT_FALSE(L.isEmpty());
+  EXPECT_TRUE(L.getHead() == &N2);
+  EXPECT_TRUE(L.getHead()->Next == &N1);
+
+  Number N3;
+  N3.Num = 3;
+
+  // Add third item.
+  L.addAtFront(&N3);
+  EXPECT_FALSE(L.isEmpty());
+  EXPECT_TRUE(L.getHead() == &N3);
+  EXPECT_TRUE(L.getHead()->Next == &N2);
+  EXPECT_TRUE(L.getHead()->Next->Next == &N1);
+
+  // Check sorting.
+  L.sortItems(
+      [](Number *LHS, Number *RHS) -> bool { return LHS->Num < RHS->Num; });
+
+  EXPECT_TRUE(L.getHead()->Num == 1);
+  EXPECT_TRUE(L.getHead()->Next->Num == 2);
+  EXPECT_TRUE(L.getHead()->Next->Next->Num == 3);
+
+  // Check reverse items.
+  L.reverseItems();
+
+  EXPECT_TRUE(L.getHead()->Num == 3);
+  EXPECT_TRUE(L.getHead()->Next->Num == 2);
+  EXPECT_TRUE(L.getHead()->Next->Next->Num == 1);
+
+  // Check items enumerations.
+  L.enumerateItems(
+      [](Number &N) { EXPECT_TRUE(N.Num == 1 || N.Num == 2 || N.Num == 3); });
+
+  // Check cleanup.
+  L.erase();
+  EXPECT_TRUE(L.isEmpty());
+  EXPECT_TRUE(L.getHead() == nullptr);
+}
+
+TEST(NonAllocatingListTest, TestListParallel) {
+  std::vector<Number> Data;
+
+  // Create data.
+  for (int Idx = 10; Idx < 1000; Idx++) {
+    Number N;
+    N.Num = Idx;
+    Data.push_back(N);
+  }
+
+  NonAllocatingList<Number> L;
+
+  // Add data into the list.
+  parallelFor(0, Data.size(), [&](size_t Idx) { L.addAtFront(&Data[Idx]); });
+
+  EXPECT_FALSE(L.isEmpty());
+
+  // Check that list contains exactly source data.
+  size_t NumElements = 0;
+  L.enumerateItems([&](const Number &N) {
+    NumElements++;
+
+    EXPECT_TRUE(std::find(Data.begin(), Data.end(), N) != Data.end());
+  });
+  EXPECT_TRUE(NumElements == Data.size());
+}
+
+} // anonymous namespace