Home | History | Annotate | Line # | Download | only in ADT 
      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
     93