86 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H11#define _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H12 13#include <__assert>14#include <__config>15 16#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)17# pragma GCC system_header18#endif19 20_LIBCPP_BEGIN_NAMESPACE_STD21 22#if _LIBCPP_STD_VER >= 2023 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-friendly32// 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 anymore59 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 __node65 __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 >= 2082 83_LIBCPP_END_NAMESPACE_STD84 85#endif // _LIBCPP___STOP_TOKEN_INTRUSIVE_LIST_VIEW_H86