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