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 | |