Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/wabt/intrusive-list.h
1 /* 2 * Copyright 2017 WebAssembly Community Group participants 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef WABT_INTRUSIVE_LIST_H_ 18 #define WABT_INTRUSIVE_LIST_H_ 19 20 #include <cassert> 21 #include <iterator> 22 #include <memory> 23 24 // This uses a similar interface as std::list, but is missing the following 25 // features: 26 // 27 // * Add "extract_" functions that remove an element from the list and return 28 // it. 29 // * Only supports move-only operations 30 // * No allocator support 31 // * No initializer lists 32 // * Asserts instead of exceptions 33 // * Some functions are not implemented (merge, remove, remove_if, reverse, 34 // unique, sort, non-member comparison operators) 35 36 namespace wabt { 37 38 template <typename T> 39 class intrusive_list; 40 41 template <typename T> 42 class intrusive_list_base { 43 private: 44 friend class intrusive_list<T>; 45 46 mutable T* next_ = nullptr; 47 mutable T* prev_ = nullptr; 48 }; 49 50 template <typename T> 51 class intrusive_list { 52 public: 53 // types: 54 using value_type = T; 55 using reference = value_type&; 56 using const_reference = const value_type&; 57 class iterator; 58 class const_iterator; 59 using size_type = std::size_t; 60 using difference_type = std::ptrdiff_t; 61 using reverse_iterator = std::reverse_iterator<iterator>; 62 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 63 64 // construct/copy/destroy: 65 intrusive_list(); 66 explicit intrusive_list(std::unique_ptr<T> node); 67 explicit intrusive_list(T&& node); 68 intrusive_list(const intrusive_list&) = delete; 69 intrusive_list(intrusive_list&&); 70 ~intrusive_list(); 71 intrusive_list& operator=(const intrusive_list& other) = delete; 72 intrusive_list& operator=(intrusive_list&& other); 73 74 // iterators: 75 iterator begin() noexcept; 76 const_iterator begin() const noexcept; 77 iterator end() noexcept; 78 const_iterator end() const noexcept; 79 80 reverse_iterator rbegin() noexcept; 81 const_reverse_iterator rbegin() const noexcept; 82 reverse_iterator rend() noexcept; 83 const_reverse_iterator rend() const noexcept; 84 85 const_iterator cbegin() const noexcept; 86 const_iterator cend() const noexcept; 87 const_reverse_iterator crbegin() const noexcept; 88 const_reverse_iterator crend() const noexcept; 89 90 // capacity: 91 size_type size() const noexcept; 92 bool empty() const noexcept; 93 94 // element access: 95 reference front(); 96 const_reference front() const; 97 reference back(); 98 const_reference back() const; 99 100 // modifiers: 101 template <class... Args> 102 void emplace_front(Args&&... args); 103 template <class... Args> 104 void emplace_back(Args&&... args); 105 void push_front(std::unique_ptr<T> node); 106 void push_front(T&& node); 107 void push_back(std::unique_ptr<T> node); 108 void push_back(T&& node); 109 void pop_front(); 110 void pop_back(); 111 std::unique_ptr<T> extract_front(); 112 std::unique_ptr<T> extract_back(); 113 114 template <class... Args> 115 iterator emplace(iterator pos, Args&&... args); 116 iterator insert(iterator pos, std::unique_ptr<T> node); 117 iterator insert(iterator pos, T&& node); 118 std::unique_ptr<T> extract(iterator it); 119 120 iterator erase(iterator pos); 121 iterator erase(iterator first, iterator last); 122 void swap(intrusive_list&); 123 void clear() noexcept; 124 125 void splice(iterator pos, intrusive_list& node); 126 void splice(iterator pos, intrusive_list&& node); 127 void splice(iterator pos, intrusive_list& node, iterator it); 128 void splice(iterator pos, 129 intrusive_list& node, 130 iterator first, 131 iterator last); 132 133 private: 134 T* first_ = nullptr; 135 T* last_ = nullptr; 136 size_t size_ = 0; 137 }; 138 139 /// iterator 140 template <typename T> 141 class intrusive_list<T>::iterator { 142 public: 143 using difference_type = std::ptrdiff_t; 144 using iterator_category = std::bidirectional_iterator_tag; 145 using value_type = T; 146 using pointer = T*; 147 using reference = T&; 148 149 iterator(const intrusive_list<T>& list, T* node) 150 : list_(&list), node_(node) {} 151 152 reference operator*() const { 153 assert(node_); 154 return *node_; 155 } 156 157 pointer operator->() const { 158 assert(node_); 159 return node_; 160 } 161 162 iterator& operator++() { 163 assert(node_); 164 node_ = node_->next_; 165 return *this; 166 } 167 168 iterator operator++(int) { 169 iterator tmp = *this; 170 operator++(); 171 return tmp; 172 } 173 174 iterator& operator--() { 175 node_ = node_ ? node_->prev_ : list_->last_; 176 return *this; 177 } 178 179 iterator operator--(int) { 180 iterator tmp = *this; 181 operator--(); 182 return tmp; 183 } 184 185 bool operator==(iterator rhs) const { 186 assert(list_ == rhs.list_); 187 return node_ == rhs.node_; 188 } 189 190 bool operator!=(iterator rhs) const { 191 assert(list_ == rhs.list_); 192 return node_ != rhs.node_; 193 } 194 195 private: 196 friend class const_iterator; 197 198 const intrusive_list<T>* list_; 199 T* node_; 200 }; 201 202 /// const_iterator 203 template <typename T> 204 class intrusive_list<T>::const_iterator { 205 public: 206 using difference_type = std::ptrdiff_t; 207 using iterator_category = std::bidirectional_iterator_tag; 208 using value_type = T; 209 using pointer = const T*; 210 using reference = const T&; 211 212 const_iterator(const intrusive_list<T>& list, T* node) 213 : list_(&list), node_(node) {} 214 215 const_iterator(const iterator& other) 216 : list_(other.list_), node_(other.node_) {} 217 218 reference operator*() const { 219 assert(node_); 220 return *node_; 221 } 222 223 pointer operator->() const { 224 assert(node_); 225 return node_; 226 } 227 228 const_iterator& operator++() { 229 assert(node_); 230 node_ = node_->next_; 231 return *this; 232 } 233 234 const_iterator operator++(int) { 235 const_iterator tmp = *this; 236 operator++(); 237 return tmp; 238 } 239 240 const_iterator& operator--() { 241 node_ = node_ ? node_->prev_ : list_->last_; 242 return *this; 243 } 244 245 const_iterator operator--(int) { 246 const_iterator tmp = *this; 247 operator--(); 248 return tmp; 249 } 250 251 bool operator==(const_iterator rhs) const { 252 assert(list_ == rhs.list_); 253 return node_ == rhs.node_; 254 } 255 256 bool operator!=(const_iterator rhs) const { 257 assert(list_ == rhs.list_); 258 return node_ != rhs.node_; 259 } 260 261 private: 262 const intrusive_list<T>* list_; 263 T* node_; 264 }; 265 266 template <typename T> 267 inline intrusive_list<T>::intrusive_list() {} 268 269 template <typename T> 270 inline intrusive_list<T>::intrusive_list(std::unique_ptr<T> node) { 271 push_back(std::move(node)); 272 } 273 274 template <typename T> 275 inline intrusive_list<T>::intrusive_list(T&& node) { 276 push_back(std::move(node)); 277 } 278 279 template <typename T> 280 inline intrusive_list<T>::intrusive_list(intrusive_list&& other) 281 : first_(other.first_), last_(other.last_), size_(other.size_) { 282 other.first_ = other.last_ = nullptr; 283 other.size_ = 0; 284 } 285 286 template <typename T> 287 inline intrusive_list<T>::~intrusive_list() { 288 clear(); 289 } 290 291 template <typename T> 292 inline intrusive_list<T>& intrusive_list<T>::operator=( 293 intrusive_list<T>&& other) { 294 clear(); 295 first_ = other.first_; 296 last_ = other.last_; 297 size_ = other.size_; 298 other.first_ = other.last_ = nullptr; 299 other.size_ = 0; 300 return *this; 301 } 302 303 template <typename T> 304 inline typename intrusive_list<T>::iterator 305 intrusive_list<T>::begin() noexcept { 306 return iterator(*this, first_); 307 } 308 309 template <typename T> 310 inline typename intrusive_list<T>::const_iterator intrusive_list<T>::begin() 311 const noexcept { 312 return const_iterator(*this, first_); 313 } 314 315 template <typename T> 316 inline typename intrusive_list<T>::iterator intrusive_list<T>::end() noexcept { 317 return iterator(*this, nullptr); 318 } 319 320 template <typename T> 321 inline typename intrusive_list<T>::const_iterator intrusive_list<T>::end() 322 const noexcept { 323 return const_iterator(*this, nullptr); 324 } 325 326 template <typename T> 327 inline typename intrusive_list<T>::reverse_iterator 328 intrusive_list<T>::rbegin() noexcept { 329 return reverse_iterator(iterator(*this, nullptr)); 330 } 331 332 template <typename T> 333 inline typename intrusive_list<T>::const_reverse_iterator 334 intrusive_list<T>::rbegin() const noexcept { 335 return const_reverse_iterator(const_iterator(*this, nullptr)); 336 } 337 338 template <typename T> 339 inline typename intrusive_list<T>::reverse_iterator 340 intrusive_list<T>::rend() noexcept { 341 return reverse_iterator(iterator(*this, first_)); 342 } 343 344 template <typename T> 345 inline typename intrusive_list<T>::const_reverse_iterator 346 intrusive_list<T>::rend() const noexcept { 347 return const_reverse_iterator(const_iterator(*this, first_)); 348 } 349 350 template <typename T> 351 inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cbegin() 352 const noexcept { 353 return const_iterator(*this, first_); 354 } 355 356 template <typename T> 357 inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cend() 358 const noexcept { 359 return const_iterator(*this, nullptr); 360 } 361 362 template <typename T> 363 inline typename intrusive_list<T>::const_reverse_iterator 364 intrusive_list<T>::crbegin() const noexcept { 365 return const_reverse_iterator(const_iterator(*this, nullptr)); 366 } 367 368 template <typename T> 369 inline typename intrusive_list<T>::const_reverse_iterator 370 intrusive_list<T>::crend() const noexcept { 371 return const_reverse_iterator(const_iterator(*this, first_)); 372 } 373 374 template <typename T> 375 inline typename intrusive_list<T>::size_type intrusive_list<T>::size() 376 const noexcept { 377 return size_; 378 } 379 380 template <typename T> 381 inline bool intrusive_list<T>::empty() const noexcept { 382 return size_ == 0; 383 } 384 385 template <typename T> 386 inline typename intrusive_list<T>::reference intrusive_list<T>::front() { 387 assert(!empty()); 388 return *first_; 389 } 390 391 template <typename T> 392 inline typename intrusive_list<T>::const_reference intrusive_list<T>::front() 393 const { 394 assert(!empty()); 395 return *first_; 396 } 397 398 template <typename T> 399 inline typename intrusive_list<T>::reference intrusive_list<T>::back() { 400 assert(!empty()); 401 return *last_; 402 } 403 404 template <typename T> 405 inline typename intrusive_list<T>::const_reference intrusive_list<T>::back() 406 const { 407 assert(!empty()); 408 return *last_; 409 } 410 411 template <typename T> 412 template <class... Args> 413 inline void intrusive_list<T>::emplace_front(Args&&... args) { 414 push_front(std::make_unique<T>(std::forward<Args>(args)...)); 415 } 416 417 template <typename T> 418 template <class... Args> 419 inline void intrusive_list<T>::emplace_back(Args&&... args) { 420 push_back(std::make_unique<T>(std::forward<Args>(args)...)); 421 } 422 423 template <typename T> 424 inline void intrusive_list<T>::push_front(std::unique_ptr<T> node) { 425 assert(node->prev_ == nullptr && node->next_ == nullptr); 426 427 T* node_p = node.release(); 428 if (first_) { 429 node_p->next_ = first_; 430 first_->prev_ = node_p; 431 } else { 432 last_ = node_p; 433 } 434 first_ = node_p; 435 size_++; 436 } 437 438 template <typename T> 439 inline void intrusive_list<T>::push_front(T&& node) { 440 push_front(std::make_unique<T>(std::move(node))); 441 } 442 443 template <typename T> 444 inline void intrusive_list<T>::push_back(std::unique_ptr<T> node) { 445 assert(node->prev_ == nullptr && node->next_ == nullptr); 446 447 T* node_p = node.release(); 448 if (last_) { 449 node_p->prev_ = last_; 450 last_->next_ = node_p; 451 } else { 452 first_ = node_p; 453 } 454 last_ = node_p; 455 size_++; 456 } 457 458 template <typename T> 459 inline void intrusive_list<T>::push_back(T&& node) { 460 push_back(std::make_unique<T>(std::move(node))); 461 } 462 463 template <typename T> 464 inline void intrusive_list<T>::pop_front() { 465 extract_front(); 466 } 467 468 template <typename T> 469 inline void intrusive_list<T>::pop_back() { 470 extract_back(); 471 } 472 473 template <typename T> 474 inline std::unique_ptr<T> intrusive_list<T>::extract_front() { 475 assert(!empty()); 476 T* node = first_; 477 if (first_ == last_) { 478 first_ = last_ = nullptr; 479 } else { 480 first_ = first_->next_; 481 first_->prev_ = nullptr; 482 } 483 node->next_ = node->prev_ = nullptr; 484 size_--; 485 return std::unique_ptr<T>(node); 486 } 487 488 template <typename T> 489 inline std::unique_ptr<T> intrusive_list<T>::extract_back() { 490 assert(!empty()); 491 T* node = last_; 492 if (first_ == last_) { 493 first_ = last_ = nullptr; 494 } else { 495 last_ = last_->prev_; 496 last_->next_ = nullptr; 497 } 498 node->next_ = node->prev_ = nullptr; 499 size_--; 500 return std::unique_ptr<T>(node); 501 } 502 503 template <typename T> 504 template <class... Args> 505 inline typename intrusive_list<T>::iterator intrusive_list<T>::emplace( 506 iterator pos, 507 Args&&... args) { 508 return insert(pos, std::make_unique<T>(std::forward<Args>(args)...)); 509 } 510 511 template <typename T> 512 inline typename intrusive_list<T>::iterator intrusive_list<T>::insert( 513 iterator pos, 514 std::unique_ptr<T> node) { 515 assert(node->prev_ == nullptr && node->next_ == nullptr); 516 517 T* node_p; 518 if (pos == end()) { 519 push_back(std::move(node)); 520 node_p = &back(); 521 } else { 522 node_p = node.release(); 523 node_p->prev_ = pos->prev_; 524 node_p->next_ = &*pos; 525 if (pos->prev_) { 526 pos->prev_->next_ = node_p; 527 } else { 528 first_ = node_p; 529 } 530 pos->prev_ = node_p; 531 size_++; 532 } 533 return iterator(*this, node_p); 534 } 535 536 template <typename T> 537 inline typename intrusive_list<T>::iterator intrusive_list<T>::insert( 538 iterator pos, 539 T&& node) { 540 return insert(pos, std::make_unique<T>(std::move(node))); 541 } 542 543 template <typename T> 544 inline std::unique_ptr<T> intrusive_list<T>::extract(iterator pos) { 545 assert(!empty()); 546 assert(pos != end()); 547 T* node = &*pos; 548 if (first_ == last_) { 549 first_ = last_ = nullptr; 550 } else { 551 if (node->prev_) { 552 node->prev_->next_ = node->next_; 553 } else { 554 first_ = node->next_; 555 } 556 557 if (node->next_) { 558 node->next_->prev_ = node->prev_; 559 } else { 560 last_ = node->prev_; 561 } 562 } 563 node->next_ = node->prev_ = nullptr; 564 size_--; 565 return std::unique_ptr<T>(node); 566 } 567 568 template <typename T> 569 inline typename intrusive_list<T>::iterator intrusive_list<T>::erase( 570 iterator pos) { 571 iterator next = std::next(pos); 572 extract(pos); 573 return next; 574 } 575 576 template <typename T> 577 inline typename intrusive_list<T>::iterator intrusive_list<T>::erase( 578 iterator first, 579 iterator last) { 580 while (first != last) 581 first = erase(first); 582 return first; 583 } 584 585 template <typename T> 586 inline void intrusive_list<T>::swap(intrusive_list& other) { 587 std::swap(first_, other.first_); 588 std::swap(last_, other.last_); 589 std::swap(size_, other.size_); 590 } 591 592 template <typename T> 593 inline void intrusive_list<T>::clear() noexcept { 594 for (T* iter = first_; iter;) { 595 T* next = iter->next_; 596 delete iter; 597 iter = next; 598 } 599 first_ = last_ = nullptr; 600 size_ = 0; 601 } 602 603 template <typename T> 604 inline void intrusive_list<T>::splice(iterator pos, intrusive_list& other) { 605 splice(pos, other, other.begin(), other.end()); 606 } 607 608 template <typename T> 609 inline void intrusive_list<T>::splice(iterator pos, intrusive_list&& other) { 610 splice(pos, other, other.begin(), other.end()); 611 } 612 613 template <typename T> 614 inline void intrusive_list<T>::splice(iterator pos, 615 intrusive_list& other, 616 iterator it) { 617 insert(pos, other.extract(it)); 618 } 619 620 template <typename T> 621 inline void intrusive_list<T>::splice(iterator pos, 622 intrusive_list& other, 623 iterator first, 624 iterator last) { 625 while (first != last) 626 insert(pos, other.extract(first++)); 627 } 628 629 } // namespace wabt 630 631 #endif // WABT_INTRUSIVE_LIST_H_
