[libbase][adt] Add ilist base

1 files changed, 139 insertions, 0 deletions

diff --git a/libbase/include/core/adt/ilist_base.h b/libbase/include/core/adt/ilist_base.h
new file mode 100644
index 0000000..3aa8d11
--- /dev/null
+++ b/libbase/include/core/adt/ilist_base.h
@@ -0,0 +1,139 @@
+/*
+ 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_base.h - Intrusive List Base --------------*- 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 LIBBASE_ADT_ILIST_BASE_H
+#define LIBBASE_ADT_ILIST_BASE_H
+
+#include "core/adt/ilist_node_base.h"
+#include <cassert>
+
+namespace libbase
+{
+
+/// Implementations of list algorithms using ilist_node_base.
+template <bool EnableSentinelTracking, class ParentTy> class ilist_base
+{
+public:
+  using node_base_type = ilist_node_base<EnableSentinelTracking, ParentTy>;
+
+  static void
+  insertBeforeImpl (node_base_type &Next, node_base_type &N)
+  {
+    node_base_type &Prev = *Next.getPrev ();
+    N.setNext (&Next);
+    N.setPrev (&Prev);
+    Prev.setNext (&N);
+    Next.setPrev (&N);
+  }
+
+  static void
+  removeImpl (node_base_type &N)
+  {
+    node_base_type *Prev = N.getPrev ();
+    node_base_type *Next = N.getNext ();
+    Next->setPrev (Prev);
+    Prev->setNext (Next);
+
+    // Not strictly necessary, but helps catch a class of bugs.
+    N.setPrev (nullptr);
+    N.setNext (nullptr);
+  }
+
+  static void
+  removeRangeImpl (node_base_type &First, node_base_type &Last)
+  {
+    node_base_type *Prev = First.getPrev ();
+    node_base_type *Final = Last.getPrev ();
+    Last.setPrev (Prev);
+    Prev->setNext (&Last);
+
+    // Not strictly necessary, but helps catch a class of bugs.
+    First.setPrev (nullptr);
+    Final->setNext (nullptr);
+  }
+
+  static void
+  transferBeforeImpl (node_base_type &Next, node_base_type &First,
+                      node_base_type &Last)
+  {
+    if (&Next == &Last || &First == &Last)
+    {
+      return;
+    }
+
+    // Position cannot be contained in the range to be transferred.
+    assert (&Next != &First &&
+            // Check for the most common mistake.
+            "Insertion point can't be one of the transferred nodes");
+
+    node_base_type &Final = *Last.getPrev ();
+
+    // Detach from old list/position.
+    First.getPrev ()->setNext (&Last);
+    Last.setPrev (First.getPrev ());
+
+    // Splice [First, Final] into its new list/position.
+    node_base_type &Prev = *Next.getPrev ();
+    Final.setNext (&Next);
+    First.setPrev (&Prev);
+    Prev.setNext (&First);
+    Next.setPrev (&Final);
+  }
+
+  template <class T>
+  static void
+  insertBefore (T &Next, T &N)
+  {
+    insertBeforeImpl (Next, N);
+  }
+
+  template <class T>
+  static void
+  remove (T &N)
+  {
+    removeImpl (N);
+  }
+  template <class T>
+  static void
+  removeRange (T &First, T &Last)
+  {
+    removeRangeImpl (First, Last);
+  }
+
+  template <class T>
+  static void
+  transferBefore (T &Next, T &First, T &Last)
+  {
+    transferBeforeImpl (Next, First, Last);
+  }
+};
+
+} // end namespace libbase
+
+#endif // LIBBASE_ADT_ILIST_BASE_H