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
16namespace llvm {
17
18/// Implementations of list algorithms using ilist_node_base.
19template <bool EnableSentinelTracking> class ilist_base {
20public:
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
94