ArrayList.h

Go to the documentation of this file.

//===- 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_DWARFLINKERPARALLEL_ARRAYLIST_H
#define LLVM_LIB_DWARFLINKERPARALLEL_ARRAYLIST_H
 
#include "llvm/Support/PerThreadBumpPtrAllocator.h"
#include <atomic>
 
namespace llvm {
namespace dwarflinker_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(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;
  parallel::PerThreadBumpPtrAllocator *Allocator = nullptr;
};
 
} // end of namespace dwarflinker_parallel
} // end namespace llvm
 
#endif // LLVM_LIB_DWARFLINKERPARALLEL_ARRAYLIST_H