Line data    Source code

       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   164394322 :     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   130712672 :     node_base_type *Prev = N.getPrev();
      33    59862753 :     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           1 :     node_base_type *Prev = First.getPrev();
      44           1 :     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     1259227 :   static void transferBeforeImpl(node_base_type &Next, node_base_type &First,
      54             :                                  node_base_type &Last) {
      55     5889824 :     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     4630243 :     node_base_type &Final = *Last.getPrev();
      64             : 
      65             :     // Detach from old list/position.
      66     4630579 :     First.getPrev()->setNext(&Last);
      67     4630575 :     Last.setPrev(First.getPrev());
      68             : 
      69             :     // Splice [First, Final] into its new list/position.
      70     4630241 :     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   135353303 :     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           0 :     removeRangeImpl(First, Last);
      84             :   }
      85             : 
      86             :   template <class T> static void transferBefore(T &Next, T &First, T &Last) {
      87     5889823 :     transferBeforeImpl(Next, First, Last);
      88             :   }
      89             : };
      90             : 
      91             : } // end namespace llvm
      92             : 
      93             : #endif // LLVM_ADT_ILIST_BASE_H