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 ParentTy> class ilist_base { 19 public: 20 using node_base_type = ilist_node_base<EnableSentinelTracking, ParentTy>; 21 insertBeforeImpl(node_base_type & Next,node_base_type & N)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 removeImpl(node_base_type & N)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 removeRangeImpl(node_base_type & First,node_base_type & Last)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 transferBeforeImpl(node_base_type & Next,node_base_type & First,node_base_type & Last)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 insertBefore(T & Next,T & N)76 template <class T> static void insertBefore(T &Next, T &N) { 77 insertBeforeImpl(Next, N); 78 } 79 remove(T & N)80 template <class T> static void remove(T &N) { removeImpl(N); } removeRange(T & First,T & Last)81 template <class T> static void removeRange(T &First, T &Last) { 82 removeRangeImpl(First, Last); 83 } 84 transferBefore(T & Next,T & First,T & Last)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