Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//==--- 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 <cstdint>

#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);

  }

};

/// ImmutableList - This class represents an immutable (functional) list.

///  It is implemented as a smart pointer (wraps ImmutableListImpl), so it

///  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:

    iterator() = default;

    iterator(ImmutableList l) : L(l.getInternalPointer()) {}

    iterator& operator++() { L = L->getTail(); return *this; }

    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; }

  };

  /// begin - 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); }

  /// end - Returns an iterator denoting the end of the list.  This iterator

  ///  does not refer to a valid list element.

  iterator end() const { return iterator(); }

  /// isEmpty - 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;

  }

  /// isEqual - 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); }

  /// getHead - Returns the head of the list.

  const T& getHead() const {

    assert(!isEmpty() && "Cannot get the head of an empty list.");

    return X->getHead();

  }

  /// getTail - 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 inline ImmutableList<T> getEmptyKey() {

    return reinterpret_cast<ImmutableListImpl<T>*>(-1);

  }

  static inline ImmutableList<T> getTombstoneKey() {

    return reinterpret_cast<ImmutableListImpl<T>*>(-2);

  }

  static unsigned getHashValue(ImmutableList<T> X) {

    uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());

    return (unsigned((uintptr_t)PtrVal) >> 4) ^

           (unsigned((uintptr_t)PtrVal) >> 9);

  }

  static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {

    return X1 == X2;

  }

};

} // end namespace llvm

#endif // LLVM_ADT_IMMUTABLELIST_H