From 4ca723bc9dc1b9db1bd03e3b3db0c58079c3f3c4 Mon Sep 17 00:00:00 2001 From: Richard Qin Date: Fri, 6 Nov 2026 00:03:17 +0800 Subject: [libbase][adt] Add ilist --- libbase/include/core/adt/ilist.h | 546 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 546 insertions(+) create mode 100644 libbase/include/core/adt/ilist.h (limited to 'libbase/include/core/adt') 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 + . +*/ + +//==-- 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 +#include +#include + +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 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 : ilist_noalloc_traits {}; +/// \endcode +template 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 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 + 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 +struct ilist_node_traits : ilist_alloc_traits, + ilist_callback_traits +{ +}; + +/// Template traits for intrusive list. +/// +/// Customize callbacks and allocation semantics. +template +struct ilist_traits : public ilist_node_traits +{ +}; + +/// Const traits should never be instantiated. +template struct ilist_traits +{ +}; + +//===----------------------------------------------------------------------===// +// +/// 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 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 (X))), + IntrusiveListT (std::move (static_cast (X))) + { + } + iplist_impl & + operator= (iplist_impl &&X) + { + *static_cast (this) = std::move (static_cast (X)); + *static_cast (this) = + std::move (static_cast (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 + 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 + 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 + 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 (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 (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 iplist : public iplist_impl, ilist_traits> +{ + 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 (this) = std::move (X); + return *this; + } +}; + +template using ilist = iplist; + +} // end namespace libbase + +namespace std +{ + +// Ensure that swap uses the fast list swap... +template +void +swap (libbase::iplist &Left, libbase::iplist &Right) +{ + Left.swap (Right); +} + +} // end namespace std + +#endif // LIBBASE_ADT_ILIST_H -- cgit v1.2.3