1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H 11 #define _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H 12 13 #include <__assert> 14 #include <__config> 15 16 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 17 # pragma GCC system_header 18 #endif 19 20 _LIBCPP_BEGIN_NAMESPACE_STD 21 22 #if _LIBCPP_STD_VER >= 20 23 24 template <class _Derived> 25 struct __intrusive_node_base { 26 _Derived* __next_ = nullptr; 27 _Derived* __prev_ = nullptr; 28 }; 29 30 // This class is a view of underlying double-linked list. 31 // It does not own the nodes. It provides user-friendly 32 // operations on the linked list. 33 template <class _Node> 34 struct __intrusive_list_view { 35 _LIBCPP_HIDE_FROM_ABI __intrusive_list_view() = default; 36 _LIBCPP_HIDE_FROM_ABI __intrusive_list_view(__intrusive_list_view const&) = default; 37 _LIBCPP_HIDE_FROM_ABI __intrusive_list_view(__intrusive_list_view&&) = default; 38 _LIBCPP_HIDE_FROM_ABI __intrusive_list_view& operator=(__intrusive_list_view const&) = default; 39 _LIBCPP_HIDE_FROM_ABI __intrusive_list_view& operator=(__intrusive_list_view&&) = default; 40 _LIBCPP_HIDE_FROM_ABI ~__intrusive_list_view() = default; 41 __empty__intrusive_list_view42 _LIBCPP_HIDE_FROM_ABI bool __empty() const noexcept { return __head_ == nullptr; } 43 __push_front__intrusive_list_view44 _LIBCPP_HIDE_FROM_ABI void __push_front(_Node* __node) noexcept { 45 __node->__next_ = __head_; 46 if (__head_) { 47 __head_->__prev_ = __node; 48 } 49 __head_ = __node; 50 } 51 __pop_front__intrusive_list_view52 _LIBCPP_HIDE_FROM_ABI _Node* __pop_front() noexcept { 53 _Node* __front = __head_; 54 __head_ = __head_->__next_; 55 if (__head_) { 56 __head_->__prev_ = nullptr; 57 } 58 // OK not to set __front->__next_ = nullptr as __front is not part of the list anymore 59 return __front; 60 } 61 __remove__intrusive_list_view62 _LIBCPP_HIDE_FROM_ABI void __remove(_Node* __node) noexcept { 63 if (__node->__prev_) { 64 // prev exists, set its next to our next to skip __node 65 __node->__prev_->__next_ = __node->__next_; 66 if (__node->__next_) { 67 __node->__next_->__prev_ = __node->__prev_; 68 } 69 } else { 70 _LIBCPP_ASSERT_INTERNAL(__node == __head_, "Node to be removed has no prev node, so it has to be the head"); 71 __pop_front(); 72 } 73 } 74 __is_head__intrusive_list_view75 _LIBCPP_HIDE_FROM_ABI bool __is_head(_Node* __node) noexcept { return __node == __head_; } 76 77 private: 78 _Node* __head_ = nullptr; 79 }; 80 81 #endif // _LIBCPP_STD_VER >= 20 82 83 _LIBCPP_END_NAMESPACE_STD 84 85 #endif // _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H 86