ImmutableList.h

Go to the documentation of this file.

//==--- ImmutableList.h - Immutable (functional) list interface --*- 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines the ImmutableList class.
///
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_ADT_IMMUTABLELIST_H
#define LLVM_ADT_IMMUTABLELIST_H
 
#include "llvm/ADT/FoldingSet.h"
#include "llvm/Support/Allocator.h"
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <new>
 
namespace llvm {
 
template <typename T> class ImmutableListFactory;
 
template <typename T>
class ImmutableListImpl : public FoldingSetNode {
  friend class ImmutableListFactory<T>;
 
  T Head;
  const ImmutableListImpl* Tail;
 
  template <typename ElemT>
  ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
    : Head(std::forward<ElemT>(head)), Tail(tail) {}
 
public:
  ImmutableListImpl(const ImmutableListImpl &) = delete;
  ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
 
  const T& getHead() const { return Head; }
  const ImmutableListImpl* getTail() const { return Tail; }
 
  static inline void Profile(FoldingSetNodeID& ID, const T& H,
                             const ImmutableListImpl* L){
    ID.AddPointer(L);
    ID.Add(H);
  }
 
  void Profile(FoldingSetNodeID& ID) {
    Profile(ID, Head, Tail);
  }
};
 
/// This class represents an immutable (functional) list. It is implemented as a
/// smart pointer (wraps ImmutableListImpl), so it is intended to always be
/// copied by value as if it were a pointer. This interface matches ImmutableSet
/// and ImmutableMap. ImmutableList objects should almost never be created
/// directly, and instead should be created by ImmutableListFactory objects that
/// manage the lifetime of a group of lists. When the factory object is
/// reclaimed, all lists created by that factory are released as well.
template <typename T>
class ImmutableList {
public:
  using value_type = T;
  using Factory = ImmutableListFactory<T>;
 
  static_assert(std::is_trivially_destructible<T>::value,
                "T must be trivially destructible!");
 
private:
  const ImmutableListImpl<T>* X;
 
public:
  // This constructor should normally only be called by ImmutableListFactory<T>.
  // There may be cases, however, when one needs to extract the internal pointer
  // and reconstruct a list object from that pointer.
  ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
 
  const ImmutableListImpl<T>* getInternalPointer() const {
    return X;
  }
 
  class iterator {
    const ImmutableListImpl<T>* L = nullptr;
 
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = std::remove_reference_t<T>;
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type *;
    using reference = const value_type &;
 
    iterator() = default;
    iterator(ImmutableList l) : L(l.getInternalPointer()) {}
 
    iterator& operator++() { L = L->getTail(); return *this; }
    iterator operator++(int) {
      iterator Tmp = *this;
      ++*this;
      return Tmp;
    }
    bool operator==(const iterator& I) const { return L == I.L; }
    bool operator!=(const iterator& I) const { return L != I.L; }
    const value_type& operator*() const { return L->getHead(); }
    const std::remove_reference_t<value_type> *operator->() const {
      return &L->getHead();
    }
 
    ImmutableList getList() const { return L; }
  };
 
  /// Returns an iterator referring to the head of the list, or an iterator
  /// denoting the end of the list if the list is empty.
  iterator begin() const { return iterator(X); }
 
  /// Returns an iterator denoting the end of the list. This iterator does not
  /// refer to a valid list element.
  iterator end() const { return iterator(); }
 
  /// Returns true if the list is empty.
  bool isEmpty() const { return !X; }
 
  bool contains(const T& V) const {
    for (iterator I = begin(), E = end(); I != E; ++I) {
      if (*I == V)
        return true;
    }
    return false;
  }
 
  /// Returns true if two lists are equal.  Because all lists created from the
  /// same ImmutableListFactory are uniqued, this has O(1) complexity because it
  /// the contents of the list do not need to be compared. Note that you should
  /// only compare two lists created from the same ImmutableListFactory.
  bool isEqual(const ImmutableList& L) const { return X == L.X; }
 
  bool operator==(const ImmutableList& L) const { return isEqual(L); }
 
  /// Returns the head of the list.
  const T& getHead() const {
    assert(!isEmpty() && "Cannot get the head of an empty list.");
    return X->getHead();
  }
 
  /// Returns the tail of the list, which is another (possibly empty)
  /// ImmutableList.
  ImmutableList getTail() const {
    return X ? X->getTail() : nullptr;
  }
 
  void Profile(FoldingSetNodeID& ID) const {
    ID.AddPointer(X);
  }
};
 
template <typename T>
class ImmutableListFactory {
  using ListTy = ImmutableListImpl<T>;
  using CacheTy = FoldingSet<ListTy>;
 
  CacheTy Cache;
  uintptr_t Allocator;
 
  bool ownsAllocator() const {
    return (Allocator & 0x1) == 0;
  }
 
  BumpPtrAllocator& getAllocator() const {
    return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
  }
 
public:
  ImmutableListFactory()
    : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
 
  ImmutableListFactory(BumpPtrAllocator& Alloc)
  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
 
  ~ImmutableListFactory() {
    if (ownsAllocator()) delete &getAllocator();
  }
 
  template <typename ElemT>
  [[nodiscard]] ImmutableList<T> concat(ElemT &&Head, ImmutableList<T> Tail) {
    // Profile the new list to see if it already exists in our cache.
    FoldingSetNodeID ID;
    void* InsertPos;
 
    const ListTy* TailImpl = Tail.getInternalPointer();
    ListTy::Profile(ID, Head, TailImpl);
    ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
 
    if (!L) {
      // The list does not exist in our cache.  Create it.
      BumpPtrAllocator& A = getAllocator();
      L = (ListTy*) A.Allocate<ListTy>();
      new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
 
      // Insert the new list into the cache.
      Cache.InsertNode(L, InsertPos);
    }
 
    return L;
  }
 
  template <typename ElemT>
  [[nodiscard]] ImmutableList<T> add(ElemT &&Data, ImmutableList<T> L) {
    return concat(std::forward<ElemT>(Data), L);
  }
 
  template <typename... CtorArgs>
  [[nodiscard]] ImmutableList<T> emplace(ImmutableList<T> Tail,
                                         CtorArgs &&...Args) {
    return concat(T(std::forward<CtorArgs>(Args)...), Tail);
  }
 
  ImmutableList<T> getEmptyList() const {
    return ImmutableList<T>(nullptr);
  }
 
  template <typename ElemT>
  ImmutableList<T> create(ElemT &&Data) {
    return concat(std::forward<ElemT>(Data), getEmptyList());
  }
};
 
//===----------------------------------------------------------------------===//
// Partially-specialized Traits.
//===----------------------------------------------------------------------===//
 
template <typename T> struct DenseMapInfo<ImmutableList<T>, void> {
  static unsigned getHashValue(ImmutableList<T> X) {
    return DenseMapInfo<const void *>::getHashValue(X.getInternalPointer());
  }
 
  static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
    return X1 == X2;
  }
};
 
} // end namespace llvm
 
#endif // LLVM_ADT_IMMUTABLELIST_H