1//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- 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/// \file 10/// This file defines classes to implement an intrusive doubly linked list class 11/// (i.e. each node of the list must contain a next and previous field for the 12/// list. 13/// 14/// The ilist class itself should be a plug in replacement for list. This list 15/// replacement does not provide a constant time size() method, so be careful to 16/// use empty() when you really want to know if it's empty. 17/// 18/// The ilist class is implemented as a circular list. The list itself contains 19/// a sentinel node, whose Next points at begin() and whose Prev points at 20/// rbegin(). The sentinel node itself serves as end() and rend(). 21/// 22//===----------------------------------------------------------------------===// 23 24#ifndef LLVM_ADT_ILIST_H 25#define LLVM_ADT_ILIST_H 26 27#include "llvm/ADT/simple_ilist.h" 28#include <cassert> 29#include <cstddef> 30#include <iterator> 31 32namespace llvm { 33 34/// Use delete by default for iplist and ilist. 35/// 36/// Specialize this to get different behaviour for ownership-related API. (If 37/// you really want ownership semantics, consider using std::list or building 38/// something like \a BumpPtrList.) 39/// 40/// \see ilist_noalloc_traits 41template <typename NodeTy> struct ilist_alloc_traits { 42 static void deleteNode(NodeTy *V) { delete V; } 43}; 44 45/// Custom traits to do nothing on deletion. 46/// 47/// Specialize ilist_alloc_traits to inherit from this to disable the 48/// non-intrusive deletion in iplist (which implies ownership). 49/// 50/// If you want purely intrusive semantics with no callbacks, consider using \a 51/// simple_ilist instead. 52/// 53/// \code 54/// template <> 55/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {}; 56/// \endcode 57template <typename NodeTy> struct ilist_noalloc_traits { 58 static void deleteNode(NodeTy *V) {} 59}; 60 61/// Callbacks do nothing by default in iplist and ilist. 62/// 63/// Specialize this for to use callbacks for when nodes change their list 64/// membership. 65template <typename NodeTy> struct ilist_callback_traits { 66 void addNodeToList(NodeTy *) {} 67 void removeNodeFromList(NodeTy *) {} 68 69 /// Callback before transferring nodes to this list. The nodes may already be 70 /// in this same list. 71 template <class Iterator> 72 void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, 73 Iterator /*last*/) { 74 (void)OldList; 75 } 76}; 77 78/// A fragment for template traits for intrusive list that provides default 79/// node related operations. 80/// 81/// TODO: Remove this layer of indirection. It's not necessary. 82template <typename NodeTy> 83struct ilist_node_traits : ilist_alloc_traits<NodeTy>, 84 ilist_callback_traits<NodeTy> {}; 85 86/// Template traits for intrusive list. 87/// 88/// Customize callbacks and allocation semantics. 89template <typename NodeTy> 90struct ilist_traits : public ilist_node_traits<NodeTy> {}; 91 92/// Const traits should never be instantiated. 93template <typename Ty> struct ilist_traits<const Ty> {}; 94 95//===----------------------------------------------------------------------===// 96// 97/// A wrapper around an intrusive list with callbacks and non-intrusive 98/// ownership. 99/// 100/// This wraps a purely intrusive list (like simple_ilist) with a configurable 101/// traits class. The traits can implement callbacks and customize the 102/// ownership semantics. 103/// 104/// This is a subset of ilist functionality that can safely be used on nodes of 105/// polymorphic types, i.e. a heterogeneous list with a common base class that 106/// holds the next/prev pointers. The only state of the list itself is an 107/// ilist_sentinel, which holds pointers to the first and last nodes in the 108/// list. 109template <class IntrusiveListT, class TraitsT> 110class iplist_impl : public TraitsT, IntrusiveListT { 111 typedef IntrusiveListT base_list_type; 112 113public: 114 typedef typename base_list_type::pointer pointer; 115 typedef typename base_list_type::const_pointer const_pointer; 116 typedef typename base_list_type::reference reference; 117 typedef typename base_list_type::const_reference const_reference; 118 typedef typename base_list_type::value_type value_type; 119 typedef typename base_list_type::size_type size_type; 120 typedef typename base_list_type::difference_type difference_type; 121 typedef typename base_list_type::iterator iterator; 122 typedef typename base_list_type::const_iterator const_iterator; 123 typedef typename base_list_type::reverse_iterator reverse_iterator; 124 typedef 125 typename base_list_type::const_reverse_iterator const_reverse_iterator; 126 127private: 128 static bool op_less(const_reference L, const_reference R) { return L < R; } 129 static bool op_equal(const_reference L, const_reference R) { return L == R; } 130 131public: 132 iplist_impl() = default; 133 134 iplist_impl(const iplist_impl &) = delete; 135 iplist_impl &operator=(const iplist_impl &) = delete; 136 137 iplist_impl(iplist_impl &&X) 138 : TraitsT(std::move(static_cast<TraitsT &>(X))), 139 IntrusiveListT(std::move(static_cast<IntrusiveListT &>(X))) {} 140 iplist_impl &operator=(iplist_impl &&X) { 141 *static_cast<TraitsT *>(this) = std::move(static_cast<TraitsT &>(X)); 142 *static_cast<IntrusiveListT *>(this) = 143 std::move(static_cast<IntrusiveListT &>(X)); 144 return *this; 145 } 146 147 ~iplist_impl() { clear(); } 148 149 // Miscellaneous inspection routines. 150 size_type max_size() const { return size_type(-1); } 151 152 using base_list_type::begin; 153 using base_list_type::end; 154 using base_list_type::rbegin; 155 using base_list_type::rend; 156 using base_list_type::empty; 157 using base_list_type::front; 158 using base_list_type::back; 159 160 void swap(iplist_impl &RHS) { 161 assert(0 && "Swap does not use list traits callback correctly yet!"); 162 base_list_type::swap(RHS); 163 } 164 165 iterator insert(iterator where, pointer New) { 166 this->addNodeToList(New); // Notify traits that we added a node... 167 return base_list_type::insert(where, *New); 168 } 169 170 iterator insert(iterator where, const_reference New) { 171 return this->insert(where, new value_type(New)); 172 } 173 174 iterator insertAfter(iterator where, pointer New) { 175 if (empty()) 176 return insert(begin(), New); 177 else 178 return insert(++where, New); 179 } 180 181 /// Clone another list. 182 template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) { 183 clear(); 184 for (const_reference V : L2) 185 push_back(clone(V)); 186 } 187 188 pointer remove(iterator &IT) { 189 pointer Node = &*IT++; 190 this->removeNodeFromList(Node); // Notify traits that we removed a node... 191 base_list_type::remove(*Node); 192 return Node; 193 } 194 195 pointer remove(const iterator &IT) { 196 iterator MutIt = IT; 197 return remove(MutIt); 198 } 199 200 pointer remove(pointer IT) { return remove(iterator(IT)); } 201 pointer remove(reference IT) { return remove(iterator(IT)); } 202 203 // erase - remove a node from the controlled sequence... and delete it. 204 iterator erase(iterator where) { 205 this->deleteNode(remove(where)); 206 return where; 207 } 208 209 iterator erase(pointer IT) { return erase(iterator(IT)); } 210 iterator erase(reference IT) { return erase(iterator(IT)); } 211 212 /// Remove all nodes from the list like clear(), but do not call 213 /// removeNodeFromList() or deleteNode(). 214 /// 215 /// This should only be used immediately before freeing nodes in bulk to 216 /// avoid traversing the list and bringing all the nodes into cache. 217 void clearAndLeakNodesUnsafely() { base_list_type::clear(); } 218 219private: 220 // transfer - The heart of the splice function. Move linked list nodes from 221 // [first, last) into position. 222 // 223 void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) { 224 if (position == last) 225 return; 226 227 // Notify traits we moved the nodes... 228 this->transferNodesFromList(L2, first, last); 229 230 base_list_type::splice(position, L2, first, last); 231 } 232 233public: 234 //===----------------------------------------------------------------------=== 235 // Functionality derived from other functions defined above... 236 // 237 238 using base_list_type::size; 239 240 iterator erase(iterator first, iterator last) { 241 while (first != last) 242 first = erase(first); 243 return last; 244 } 245 246 void clear() { erase(begin(), end()); } 247 248 // Front and back inserters... 249 void push_front(pointer val) { insert(begin(), val); } 250 void push_back(pointer val) { insert(end(), val); } 251 void pop_front() { 252 assert(!empty() && "pop_front() on empty list!"); 253 erase(begin()); 254 } 255 void pop_back() { 256 assert(!empty() && "pop_back() on empty list!"); 257 iterator t = end(); erase(--t); 258 } 259 260 // Special forms of insert... 261 template<class InIt> void insert(iterator where, InIt first, InIt last) { 262 for (; first != last; ++first) insert(where, *first); 263 } 264 265 // Splice members - defined in terms of transfer... 266 void splice(iterator where, iplist_impl &L2) { 267 if (!L2.empty()) 268 transfer(where, L2, L2.begin(), L2.end()); 269 } 270 void splice(iterator where, iplist_impl &L2, iterator first) { 271 iterator last = first; ++last; 272 if (where == first || where == last) return; // No change 273 transfer(where, L2, first, last); 274 } 275 void splice(iterator where, iplist_impl &L2, iterator first, iterator last) { 276 if (first != last) transfer(where, L2, first, last); 277 } 278 void splice(iterator where, iplist_impl &L2, reference N) { 279 splice(where, L2, iterator(N)); 280 } 281 void splice(iterator where, iplist_impl &L2, pointer N) { 282 splice(where, L2, iterator(N)); 283 } 284 285 template <class Compare> 286 void merge(iplist_impl &Right, Compare comp) { 287 if (this == &Right) 288 return; 289 this->transferNodesFromList(Right, Right.begin(), Right.end()); 290 base_list_type::merge(Right, comp); 291 } 292 void merge(iplist_impl &Right) { return merge(Right, op_less); } 293 294 using base_list_type::sort; 295 296 /// Get the previous node, or \c nullptr for the list head. 297 pointer getPrevNode(reference N) const { 298 auto I = N.getIterator(); 299 if (I == begin()) 300 return nullptr; 301 return &*std::prev(I); 302 } 303 /// Get the previous node, or \c nullptr for the list head. 304 const_pointer getPrevNode(const_reference N) const { 305 return getPrevNode(const_cast<reference >(N)); 306 } 307 308 /// Get the next node, or \c nullptr for the list tail. 309 pointer getNextNode(reference N) const { 310 auto Next = std::next(N.getIterator()); 311 if (Next == end()) 312 return nullptr; 313 return &*Next; 314 } 315 /// Get the next node, or \c nullptr for the list tail. 316 const_pointer getNextNode(const_reference N) const { 317 return getNextNode(const_cast<reference >(N)); 318 } 319}; 320 321/// An intrusive list with ownership and callbacks specified/controlled by 322/// ilist_traits, only with API safe for polymorphic types. 323/// 324/// The \p Options parameters are the same as those for \a simple_ilist. See 325/// there for a description of what's available. 326template <class T, class... Options> 327class iplist 328 : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> { 329 using iplist_impl_type = typename iplist::iplist_impl; 330 331public: 332 iplist() = default; 333 334 iplist(const iplist &X) = delete; 335 iplist &operator=(const iplist &X) = delete; 336 337 iplist(iplist &&X) : iplist_impl_type(std::move(X)) {} 338 iplist &operator=(iplist &&X) { 339 *static_cast<iplist_impl_type *>(this) = std::move(X); 340 return *this; 341 } 342}; 343 344template <class T, class... Options> using ilist = iplist<T, Options...>; 345 346} // end namespace llvm 347 348namespace std { 349 350 // Ensure that swap uses the fast list swap... 351 template<class Ty> 352 void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { 353 Left.swap(Right); 354 } 355 356} // end namespace std 357 358#endif // LLVM_ADT_ILIST_H 359