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 
insertBeforeImpl(node_base_type & Next,node_base_type & N)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 
removeImpl(node_base_type & N)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 
removeRangeImpl(node_base_type & First,node_base_type & Last)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 
transferBeforeImpl(node_base_type & Next,node_base_type & First,node_base_type & Last)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 
insertBefore(T & Next,T & N)76   template <class T> static void insertBefore(T &Next, T &N) {
77     insertBeforeImpl(Next, N);
78   }
79 
remove(T & N)80   template <class T> static void remove(T &N) { removeImpl(N); }
removeRange(T & First,T & Last)81   template <class T> static void removeRange(T &First, T &Last) {
82     removeRangeImpl(First, Last);
83   }
84 
transferBefore(T & Next,T & First,T & Last)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