[libbase][adt] Add ilistHEADmaster

1 files changed, 546 insertions, 0 deletions

diff --git a/libbase/include/core/adt/ilist.h b/libbase/include/core/adt/ilist.h
new file mode 100644
index 0000000..c3c769a
--- /dev/null
+++ b/libbase/include/core/adt/ilist.h
@@ -0,0 +1,546 @@
+/*
+ RCC-Project
+
+ Copyright (C) 2026 Richard Qin
+
+ This file is part of RCC-Project.
+
+ RCC-Project is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your option) any
+ later version.
+
+ RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ RCC-Project; see the file COPYING. If not see
+ <http://www.gnu.org/licenses/>.
+*/
+
+//==-- core/adt/ilist.h - Intrusive Linked List Template ---------*- 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 classes to implement an intrusive doubly linked list class
+/// (i.e. each node of the list must contain a next and previous field for the
+/// list.
+///
+/// The ilist class itself should be a plug in replacement for list.  This list
+/// replacement does not provide a constant time size() method, so be careful to
+/// use empty() when you really want to know if it's empty.
+///
+/// The ilist class is implemented as a circular list.  The list itself contains
+/// a sentinel node, whose Next points at begin() and whose Prev points at
+/// rbegin().  The sentinel node itself serves as end() and rend().
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBBASE_ADT_ILIST_H
+#define LIBBASE_ADT_ILIST_H
+
+#include "core/adt/simple_ilist.h"
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+
+namespace libbase
+{
+
+/// Use delete by default for iplist and ilist.
+///
+/// Specialize this to get different behaviour for ownership-related API.  (If
+/// you really want ownership semantics, consider using std::list or building
+/// something like \a BumpPtrList.)
+///
+/// \see ilist_noalloc_traits
+template <typename NodeTy> struct ilist_alloc_traits
+{
+  static void
+  deleteNode (NodeTy *V)
+  {
+    delete V;
+  }
+};
+
+/// Custom traits to do nothing on deletion.
+///
+/// Specialize ilist_alloc_traits to inherit from this to disable the
+/// non-intrusive deletion in iplist (which implies ownership).
+///
+/// If you want purely intrusive semantics with no callbacks, consider using \a
+/// simple_ilist instead.
+///
+/// \code
+/// template <>
+/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
+/// \endcode
+template <typename NodeTy> struct ilist_noalloc_traits
+{
+  static void
+  deleteNode (NodeTy *V)
+  {
+  }
+};
+
+/// Callbacks do nothing by default in iplist and ilist.
+///
+/// Specialize this for to use callbacks for when nodes change their list
+/// membership.
+template <typename NodeTy> struct ilist_callback_traits
+{
+  void
+  addNodeToList (NodeTy *)
+  {
+  }
+  void
+  removeNodeFromList (NodeTy *)
+  {
+  }
+
+  /// Callback before transferring nodes to this list. The nodes may already be
+  /// in this same list.
+  template <class Iterator>
+  void
+  transferNodesFromList (ilist_callback_traits &OldList, Iterator /*first*/,
+                         Iterator /*last*/)
+  {
+    (void)OldList;
+  }
+};
+
+/// A fragment for template traits for intrusive list that provides default
+/// node related operations.
+///
+/// TODO: Remove this layer of indirection.  It's not necessary.
+template <typename NodeTy>
+struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
+                           ilist_callback_traits<NodeTy>
+{
+};
+
+/// Template traits for intrusive list.
+///
+/// Customize callbacks and allocation semantics.
+template <typename NodeTy>
+struct ilist_traits : public ilist_node_traits<NodeTy>
+{
+};
+
+/// Const traits should never be instantiated.
+template <typename Ty> struct ilist_traits<const Ty>
+{
+};
+
+//===----------------------------------------------------------------------===//
+//
+/// A wrapper around an intrusive list with callbacks and non-intrusive
+/// ownership.
+///
+/// This wraps a purely intrusive list (like simple_ilist) with a configurable
+/// traits class.  The traits can implement callbacks and customize the
+/// ownership semantics.
+///
+/// This is a subset of ilist functionality that can safely be used on nodes of
+/// polymorphic types, i.e. a heterogeneous list with a common base class that
+/// holds the next/prev pointers.  The only state of the list itself is an
+/// ilist_sentinel, which holds pointers to the first and last nodes in the
+/// list.
+template <class IntrusiveListT, class TraitsT>
+class iplist_impl : public TraitsT, IntrusiveListT
+{
+  using base_list_type = IntrusiveListT;
+
+public:
+  using pointer = typename base_list_type::pointer;
+  using const_pointer = typename base_list_type::const_pointer;
+  using reference = typename base_list_type::reference;
+  using const_reference = typename base_list_type::const_reference;
+  using value_type = typename base_list_type::value_type;
+  using size_type = typename base_list_type::size_type;
+  using difference_type = typename base_list_type::difference_type;
+  using iterator = typename base_list_type::iterator;
+  using const_iterator = typename base_list_type::const_iterator;
+  using reverse_iterator = typename base_list_type::reverse_iterator;
+  using const_reverse_iterator =
+      typename base_list_type::const_reverse_iterator;
+
+private:
+  static bool
+  op_less (const_reference L, const_reference R)
+  {
+    return L < R;
+  }
+  static bool
+  op_equal (const_reference L, const_reference R)
+  {
+    return L == R;
+  }
+
+public:
+  iplist_impl () = default;
+
+  iplist_impl (const iplist_impl &) = delete;
+  iplist_impl &
+  operator= (const iplist_impl &) = delete;
+
+  iplist_impl (iplist_impl &&X)
+      : TraitsT (std::move (static_cast<TraitsT &> (X))),
+        IntrusiveListT (std::move (static_cast<IntrusiveListT &> (X)))
+  {
+  }
+  iplist_impl &
+  operator= (iplist_impl &&X)
+  {
+    *static_cast<TraitsT *> (this) = std::move (static_cast<TraitsT &> (X));
+    *static_cast<IntrusiveListT *> (this) =
+        std::move (static_cast<IntrusiveListT &> (X));
+    return *this;
+  }
+
+  ~iplist_impl ()
+  {
+    clear ();
+  }
+
+  // Miscellaneous inspection routines.
+  size_type
+  max_size () const
+  {
+    return size_type (-1);
+  }
+
+  using base_list_type::back;
+  using base_list_type::begin;
+  using base_list_type::empty;
+  using base_list_type::end;
+  using base_list_type::front;
+  using base_list_type::rbegin;
+  using base_list_type::rend;
+
+  void
+  swap (iplist_impl &RHS)
+  {
+    assert (0 && "Swap does not use list traits callback correctly yet!");
+    base_list_type::swap (RHS);
+  }
+
+  iterator
+  insert (iterator where, pointer New)
+  {
+    this->addNodeToList (New); // Notify traits that we added a node...
+    return base_list_type::insert (where, *New);
+  }
+
+  iterator
+  insert (iterator where, const_reference New)
+  {
+    return this->insert (where, new value_type (New));
+  }
+
+  iterator
+  insertAfter (iterator where, pointer New)
+  {
+    if (empty ())
+    {
+      return insert (begin (), New);
+    }
+    else
+    {
+      return insert (++where, New);
+    }
+  }
+
+  /// Clone another list.
+  template <class Cloner>
+  void
+  cloneFrom (const iplist_impl &L2, Cloner clone)
+  {
+    clear ();
+    for (const_reference V : L2)
+    {
+      push_back (clone (V));
+    }
+  }
+
+  pointer
+  remove (iterator &IT)
+  {
+    pointer Node = &*IT++;
+    this->removeNodeFromList (Node); // Notify traits that we removed a node...
+    base_list_type::remove (*Node);
+    return Node;
+  }
+
+  pointer
+  remove (const iterator &IT)
+  {
+    iterator MutIt = IT;
+    return remove (MutIt);
+  }
+
+  pointer
+  remove (pointer IT)
+  {
+    return remove (iterator (IT));
+  }
+  pointer
+  remove (reference IT)
+  {
+    return remove (iterator (IT));
+  }
+
+  // erase - remove a node from the controlled sequence... and delete it.
+  iterator
+  erase (iterator where)
+  {
+    this->deleteNode (remove (where));
+    return where;
+  }
+
+  iterator
+  erase (pointer IT)
+  {
+    return erase (iterator (IT));
+  }
+  iterator
+  erase (reference IT)
+  {
+    return erase (iterator (IT));
+  }
+
+  /// Remove all nodes from the list like clear(), but do not call
+  /// removeNodeFromList() or deleteNode().
+  ///
+  /// This should only be used immediately before freeing nodes in bulk to
+  /// avoid traversing the list and bringing all the nodes into cache.
+  void
+  clearAndLeakNodesUnsafely ()
+  {
+    base_list_type::clear ();
+  }
+
+private:
+  // transfer - The heart of the splice function.  Move linked list nodes from
+  // [first, last) into position.
+  //
+  void
+  transfer (iterator position, iplist_impl &L2, iterator first, iterator last)
+  {
+    if (position == last)
+    {
+      return;
+    }
+
+    // Notify traits we moved the nodes...
+    this->transferNodesFromList (L2, first, last);
+
+    base_list_type::splice (position, L2, first, last);
+  }
+
+public:
+  //===----------------------------------------------------------------------===
+  // Functionality derived from other functions defined above...
+  //
+
+  using base_list_type::size;
+
+  iterator
+  erase (iterator first, iterator last)
+  {
+    while (first != last)
+    {
+      first = erase (first);
+    }
+    return last;
+  }
+
+  void
+  clear ()
+  {
+    erase (begin (), end ());
+  }
+
+  // Front and back inserters...
+  void
+  push_front (pointer val)
+  {
+    insert (begin (), val);
+  }
+  void
+  push_back (pointer val)
+  {
+    insert (end (), val);
+  }
+  void
+  pop_front ()
+  {
+    assert (!empty () && "pop_front() on empty list!");
+    erase (begin ());
+  }
+  void
+  pop_back ()
+  {
+    assert (!empty () && "pop_back() on empty list!");
+    iterator t = end ();
+    erase (--t);
+  }
+
+  // Special forms of insert...
+  template <class InIt>
+  void
+  insert (iterator where, InIt first, InIt last)
+  {
+    for (; first != last; ++first)
+    {
+      insert (where, *first);
+    }
+  }
+
+  // Splice members - defined in terms of transfer...
+  void
+  splice (iterator where, iplist_impl &L2)
+  {
+    if (!L2.empty ())
+    {
+      transfer (where, L2, L2.begin (), L2.end ());
+    }
+  }
+  void
+  splice (iterator where, iplist_impl &L2, iterator first)
+  {
+    iterator last = first;
+    ++last;
+    if (where == first || where == last)
+    {
+      return; // No change
+    }
+    transfer (where, L2, first, last);
+  }
+  void
+  splice (iterator where, iplist_impl &L2, iterator first, iterator last)
+  {
+    if (first != last)
+    {
+      transfer (where, L2, first, last);
+    }
+  }
+  void
+  splice (iterator where, iplist_impl &L2, reference N)
+  {
+    splice (where, L2, iterator (N));
+  }
+  void
+  splice (iterator where, iplist_impl &L2, pointer N)
+  {
+    splice (where, L2, iterator (N));
+  }
+
+  template <class Compare>
+  void
+  merge (iplist_impl &Right, Compare comp)
+  {
+    if (this == &Right)
+    {
+      return;
+    }
+    this->transferNodesFromList (Right, Right.begin (), Right.end ());
+    base_list_type::merge (Right, comp);
+  }
+  void
+  merge (iplist_impl &Right)
+  {
+    return merge (Right, op_less);
+  }
+
+  using base_list_type::sort;
+
+  /// Get the previous node, or \c nullptr for the list head.
+  pointer
+  getPrevNode (reference N) const
+  {
+    auto I = N.getIterator ();
+    if (I == begin ())
+    {
+      return nullptr;
+    }
+    return &*std::prev (I);
+  }
+  /// Get the previous node, or \c nullptr for the list head.
+  const_pointer
+  getPrevNode (const_reference N) const
+  {
+    return getPrevNode (const_cast<reference> (N));
+  }
+
+  /// Get the next node, or \c nullptr for the list tail.
+  pointer
+  getNextNode (reference N) const
+  {
+    auto Next = std::next (N.getIterator ());
+    if (Next == end ())
+    {
+      return nullptr;
+    }
+    return &*Next;
+  }
+  /// Get the next node, or \c nullptr for the list tail.
+  const_pointer
+  getNextNode (const_reference N) const
+  {
+    return getNextNode (const_cast<reference> (N));
+  }
+};
+
+/// An intrusive list with ownership and callbacks specified/controlled by
+/// ilist_traits, only with API safe for polymorphic types.
+///
+/// The \p Options parameters are the same as those for \a simple_ilist.  See
+/// there for a description of what's available.
+template <class T, class... Options>
+class iplist : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>>
+{
+  using iplist_impl_type = typename iplist::iplist_impl;
+
+public:
+  iplist () = default;
+
+  iplist (const iplist &X) = delete;
+  iplist &
+  operator= (const iplist &X) = delete;
+
+  iplist (iplist &&X) : iplist_impl_type (std::move (X))
+  {
+  }
+  iplist &
+  operator= (iplist &&X)
+  {
+    *static_cast<iplist_impl_type *> (this) = std::move (X);
+    return *this;
+  }
+};
+
+template <class T, class... Options> using ilist = iplist<T, Options...>;
+
+} // end namespace libbase
+
+namespace std
+{
+
+// Ensure that swap uses the fast list swap...
+template <class Ty>
+void
+swap (libbase::iplist<Ty> &Left, libbase::iplist<Ty> &Right)
+{
+  Left.swap (Right);
+}
+
+} // end namespace std
+
+#endif // LIBBASE_ADT_ILIST_H