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 #include <cstddef> 16 #include <type_traits> 17 18 namespace llvm { 19 20 /// Implementations of list algorithms using ilist_node_base. 21 template <bool EnableSentinelTracking> class ilist_base { 22 public: 23 typedef ilist_node_base<EnableSentinelTracking> node_base_type; 24 25 static void insertBeforeImpl(node_base_type &Next, node_base_type &N) { 26 node_base_type &Prev = *Next.getPrev(); 27 N.setNext(&Next); 28 N.setPrev(&Prev); 29 Prev.setNext(&N); 30 Next.setPrev(&N); 31 } 32 33 static void removeImpl(node_base_type &N) { 34 node_base_type *Prev = N.getPrev(); 35 node_base_type *Next = N.getNext(); 36 Next->setPrev(Prev); 37 Prev->setNext(Next); 38 39 // Not strictly necessary, but helps catch a class of bugs. 40 N.setPrev(nullptr); 41 N.setNext(nullptr); 42 } 43 44 static void removeRangeImpl(node_base_type &First, node_base_type &Last) { 45 node_base_type *Prev = First.getPrev(); 46 node_base_type *Final = Last.getPrev(); 47 Last.setPrev(Prev); 48 Prev->setNext(&Last); 49 50 // Not strictly necessary, but helps catch a class of bugs. 51 First.setPrev(nullptr); 52 Final->setNext(nullptr); 53 } 54 55 static void transferBeforeImpl(node_base_type &Next, node_base_type &First, 56 node_base_type &Last) { 57 if (&Next == &Last || &First == &Last) 58 return; 59 60 // Position cannot be contained in the range to be transferred. 61 assert(&Next != &First && 62 // Check for the most common mistake. 63 "Insertion point can't be one of the transferred nodes"); 64 65 node_base_type &Final = *Last.getPrev(); 66 67 // Detach from old list/position. 68 First.getPrev()->setNext(&Last); 69 Last.setPrev(First.getPrev()); 70 71 // Splice [First, Final] into its new list/position. 72 node_base_type &Prev = *Next.getPrev(); 73 Final.setNext(&Next); 74 First.setPrev(&Prev); 75 Prev.setNext(&First); 76 Next.setPrev(&Final); 77 } 78 79 template <class T> static void insertBefore(T &Next, T &N) { 80 insertBeforeImpl(Next, N); 81 } 82 83 template <class T> static void remove(T &N) { removeImpl(N); } 84 template <class T> static void removeRange(T &First, T &Last) { 85 removeRangeImpl(First, Last); 86 } 87 88 template <class T> static void transferBefore(T &Next, T &First, T &Last) { 89 transferBeforeImpl(Next, First, Last); 90 } 91 }; 92 93 } // end namespace llvm 94 95 #endif // LLVM_ADT_ILIST_BASE_H 96
