LLVM  6.0.0svn
ilist_base.h
Go to the documentation of this file.
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 
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:
22 
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 
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static void insertBefore(T &Next, T &N)
Definition: ilist_base.h:77
static void transferBefore(T &Next, T &First, T &Last)
Definition: ilist_base.h:86
static void removeImpl(node_base_type &N)
Definition: ilist_base.h:31
static void insertBeforeImpl(node_base_type &Next, node_base_type &N)
Definition: ilist_base.h:23
Base class for ilist nodes.
static void transferBeforeImpl(node_base_type &Next, node_base_type &First, node_base_type &Last)
Definition: ilist_base.h:53
static void removeRange(T &First, T &Last)
Definition: ilist_base.h:82
Implementations of list algorithms using ilist_node_base.
Definition: ilist_base.h:19
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void removeRangeImpl(node_base_type &First, node_base_type &Last)
Definition: ilist_base.h:42