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 
42   _LIBCPP_HIDE_FROM_ABI bool __empty() const noexcept { return __head_ == nullptr; }
43 
44   _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 
52   _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 
62   _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 
75   _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