EIC code displayed by LXR master/​include/​llvm/​ADT/​ImmutableList.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:06

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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team