include/llvm/ADT/ilist_base.h

   1 //===- llvm/ADT/ilist_base.h - Intrusive List Base --------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_ADT_ILIST_BASE_H
  10 #define LLVM_ADT_ILIST_BASE_H
  11
  12 #include "llvm/ADT/ilist_node_base.h"
  13 #include <cassert>
  14
  15 namespace llvm {
  16
  17 /// Implementations of list algorithms using ilist_node_base.
  18 template <bool EnableSentinelTracking> class ilist_base {
  19 public:
  20   using node_base_type = ilist_node_base<EnableSentinelTracking>;
  21
  22   static void insertBeforeImpl(node_base_type &Next, node_base_type &N) {
  23     node_base_type &Prev = *Next.getPrev();
  24     N.setNext(&Next);
  25     N.setPrev(&Prev);
  26     Prev.setNext(&N);
  27     Next.setPrev(&N);
  28   }
  29
  30   static void removeImpl(node_base_type &N) {
  31     node_base_type *Prev = N.getPrev();
  32     node_base_type *Next = N.getNext();
  33     Next->setPrev(Prev);
  34     Prev->setNext(Next);
  35
  36     // Not strictly necessary, but helps catch a class of bugs.
  37     N.setPrev(nullptr);
  38     N.setNext(nullptr);
  39   }
  40
  41   static void removeRangeImpl(node_base_type &First, node_base_type &Last) {
  42     node_base_type *Prev = First.getPrev();
  43     node_base_type *Final = Last.getPrev();
  44     Last.setPrev(Prev);
  45     Prev->setNext(&Last);
  46
  47     // Not strictly necessary, but helps catch a class of bugs.
  48     First.setPrev(nullptr);
  49     Final->setNext(nullptr);
  50   }
  51
  52   static void transferBeforeImpl(node_base_type &Next, node_base_type &First,
  53                                  node_base_type &Last) {
  54     if (&Next == &Last || &First == &Last)
  55       return;
  56
  57     // Position cannot be contained in the range to be transferred.
  58     assert(&Next != &First &&
  59            // Check for the most common mistake.
  60            "Insertion point can't be one of the transferred nodes");
  61
  62     node_base_type &Final = *Last.getPrev();
  63
  64     // Detach from old list/position.
  65     First.getPrev()->setNext(&Last);
  66     Last.setPrev(First.getPrev());
  67
  68     // Splice [First, Final] into its new list/position.
  69     node_base_type &Prev = *Next.getPrev();
  70     Final.setNext(&Next);
  71     First.setPrev(&Prev);
  72     Prev.setNext(&First);
  73     Next.setPrev(&Final);
  74   }
  75
  76   template <class T> static void insertBefore(T &Next, T &N) {
  77     insertBeforeImpl(Next, N);
  78   }
  79
  80   template <class T> static void remove(T &N) { removeImpl(N); }
  81   template <class T> static void removeRange(T &First, T &Last) {
  82     removeRangeImpl(First, Last);
  83   }
  84
  85   template <class T> static void transferBefore(T &Next, T &First, T &Last) {
  86     transferBeforeImpl(Next, First, Last);
  87   }
  88 };
  89
  90 } // end namespace llvm
  91
  92 #endif // LLVM_ADT_ILIST_BASE_H