contrib/llvm/include/llvm/ADT/ilist_base.h

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