llvm/ADT/ilist_base.h

0001 //===- llvm/ADT/ilist_base.h - Intrusive List Base --------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_ILIST_BASE_H
0010 #define LLVM_ADT_ILIST_BASE_H
0011
0012 #include "llvm/ADT/ilist_node_base.h"
0013 #include <cassert>
0014
0015 namespace llvm {
0016
0017 /// Implementations of list algorithms using ilist_node_base.
0018 template <bool EnableSentinelTracking, class ParentTy> class ilist_base {
0019 public:
0020   using node_base_type = ilist_node_base<EnableSentinelTracking, ParentTy>;
0021
0022   static void insertBeforeImpl(node_base_type &Next, node_base_type &N) {
0023     node_base_type &Prev = *Next.getPrev();
0024     N.setNext(&Next);
0025     N.setPrev(&Prev);
0026     Prev.setNext(&N);
0027     Next.setPrev(&N);
0028   }
0029
0030   static void removeImpl(node_base_type &N) {
0031     node_base_type *Prev = N.getPrev();
0032     node_base_type *Next = N.getNext();
0033     Next->setPrev(Prev);
0034     Prev->setNext(Next);
0035
0036     // Not strictly necessary, but helps catch a class of bugs.
0037     N.setPrev(nullptr);
0038     N.setNext(nullptr);
0039   }
0040
0041   static void removeRangeImpl(node_base_type &First, node_base_type &Last) {
0042     node_base_type *Prev = First.getPrev();
0043     node_base_type *Final = Last.getPrev();
0044     Last.setPrev(Prev);
0045     Prev->setNext(&Last);
0046
0047     // Not strictly necessary, but helps catch a class of bugs.
0048     First.setPrev(nullptr);
0049     Final->setNext(nullptr);
0050   }
0051
0052   static void transferBeforeImpl(node_base_type &Next, node_base_type &First,
0053                                  node_base_type &Last) {
0054     if (&Next == &Last || &First == &Last)
0055       return;
0056
0057     // Position cannot be contained in the range to be transferred.
0058     assert(&Next != &First &&
0059            // Check for the most common mistake.
0060            "Insertion point can't be one of the transferred nodes");
0061
0062     node_base_type &Final = *Last.getPrev();
0063
0064     // Detach from old list/position.
0065     First.getPrev()->setNext(&Last);
0066     Last.setPrev(First.getPrev());
0067
0068     // Splice [First, Final] into its new list/position.
0069     node_base_type &Prev = *Next.getPrev();
0070     Final.setNext(&Next);
0071     First.setPrev(&Prev);
0072     Prev.setNext(&First);
0073     Next.setPrev(&Final);
0074   }
0075
0076   template <class T> static void insertBefore(T &Next, T &N) {
0077     insertBeforeImpl(Next, N);
0078   }
0079
0080   template <class T> static void remove(T &N) { removeImpl(N); }
0081   template <class T> static void removeRange(T &First, T &Last) {
0082     removeRangeImpl(First, Last);
0083   }
0084
0085   template <class T> static void transferBefore(T &Next, T &First, T &Last) {
0086     transferBeforeImpl(Next, First, Last);
0087   }
0088 };
0089
0090 } // end namespace llvm
0091
0092 #endif // LLVM_ADT_ILIST_BASE_H