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
24template <class _Derived>
25struct __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.
33template <class _Node>
34struct __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
77private:
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