beenull/ladybird
1
0
Fork 0
mirror of https://github.com/LadybirdBrowser/ladybird.git synced 2024-11-21 15:10:19 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions 6
ladybird/AK/IntrusiveList.h

454 lines
15 KiB
C
Raw Permalink Normal View History

Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
/*
Meta: Update my e-mail address everywhere
2024-10-04 11:19:50 +00:00
* Copyright (c) 2018-2020, Andreas Kling <andreas@ladybird.org>
Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
*
Everything: Move to SPDX license identifiers in all files. SPDX License Identifiers are a more compact / standardized way of representing file license information. See: https://spdx.dev/resources/use/#identifiers This was done with the `ambr` search and replace tool. ambr --no-parent-ignore --key-from-file --rep-from-file key.txt rep.txt *
2021-04-22 08:24:48 +00:00
* SPDX-License-Identifier: BSD-2-Clause
Meta: Add license header to source files As suggested by Joshua, this commit adds the 2-clause BSD license as a comment block to the top of every source file. For the first pass, I've just added myself for simplicity. I encourage everyone to add themselves as copyright holders of any file they've added or modified in some significant way. If I've added myself in error somewhere, feel free to replace it with the appropriate copyright holder instead. Going forward, all new source files should include a license header.
2020-01-18 08:38:21 +00:00
*/
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
#pragma once
LibCore: Add a forward declaration header This patch adds <LibCore/Forward.h> and uses it in various places to shrink the header dependency graph.
2020-02-14 21:29:06 +00:00
#include <AK/Assertions.h>
AK: Avoid the unnecessarily confusing bunch of casts in IntrusiveList And use bit_cast instead. Also explain what it does, because it's not at all trivial to understand :^)
2021-04-16 12:00:20 +00:00
#include <AK/BitCast.h>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
#include <AK/Forward.h>
AK: Make IntrusiveRedBlackTree capable of holding non-raw pointers This is completely based on e4412f1f599bea034dea608b8c7dcc4408d90066 and will allow us to convert some AK::HashMap users in the kernel.
2021-09-07 22:57:49 +00:00
#include <AK/IntrusiveDetails.h>
AK: Mark AK::IntrusiveList Non copyable and movable
2021-07-17 09:24:02 +00:00
#include <AK/Noncopyable.h>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
#include <AK/StdLibExtras.h>
LibCore: Add a forward declaration header This patch adds <LibCore/Forward.h> and uses it in various places to shrink the header dependency graph.
2020-02-14 21:29:06 +00:00
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
namespace AK::Detail {
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
template<typename T, typename Container = RawPtr<T>>
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
class IntrusiveListNode;
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
struct ExtractIntrusiveListTypes {
template<typename V, typename Container, typename T>
static V value(IntrusiveListNode<V, Container> T::*x);
template<typename V, typename Container, typename T>
static Container container(IntrusiveListNode<V, Container> T::*x);
};
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
template<typename T, typename Container = RawPtr<T>>
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
using SubstitutedIntrusiveListNode = IntrusiveListNode<T, typename Detail::SubstituteIntrusiveContainerType<T, Container>::Type>;
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
template<typename T, typename Container>
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
class IntrusiveListStorage {
private:
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
friend class IntrusiveListNode<T, Container>;
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T_, typename Container_, SubstitutedIntrusiveListNode<T_, Container_> T_::*member>
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
friend class IntrusiveList;
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
SubstitutedIntrusiveListNode<T, Container>* m_first { nullptr };
SubstitutedIntrusiveListNode<T, Container>* m_last { nullptr };
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
};
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
class IntrusiveList {
AK: Mark AK::IntrusiveList Non copyable and movable
2021-07-17 09:24:02 +00:00
AK_MAKE_NONCOPYABLE(IntrusiveList);
AK_MAKE_NONMOVABLE(IntrusiveList);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
public:
IntrusiveList: Remove redundant constructor Problem: - The constructor is defined to be the default constructor. Solution: - Let the compiler generate the destructor by setting it to the default.
2021-05-21 23:08:04 +00:00
IntrusiveList() = default;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
~IntrusiveList();
void clear();
AK: Annotate IntrusiveList functions as [[nodiscard]]
2021-04-11 08:25:58 +00:00
[[nodiscard]] bool is_empty() const;
AK: Add IntrusiveList::size_slow() to match InlineLinkedList The functionality is needed to replace InlineLinkedList with IntrusiveList in the Kernel Process class.
2021-06-06 21:13:10 +00:00
[[nodiscard]] size_t size_slow() const;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
void append(T& n);
void prepend(T& n);
AK+Tests: Add IntrusiveList<T,...>::insert_before(..) method The insert_before method on AK::InlineLinkedList is used, so in order to achieve feature parity, we need to implement it for AK::IntrusiveList as well.
2021-06-15 09:33:59 +00:00
void insert_before(T&, T&);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
void remove(T& n);
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
[[nodiscard]] bool contains(T const&) const;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
[[nodiscard]] Container first() const;
[[nodiscard]] Container last() const;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
[[nodiscard]] Container take_first();
[[nodiscard]] Container take_last();
AK: Add IntrusiveList::take_first()
2019-12-22 11:23:30 +00:00
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
class Iterator {
public:
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
Iterator() = default;
Iterator(T* value)
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
: m_value(move(value))
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
{
}
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const& operator*() const { return *m_value; }
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
auto operator->() const { return m_value; }
T& operator*() { return *m_value; }
auto operator->() { return m_value; }
Everywhere: Run clang-format
2022-04-01 17:58:27 +00:00
bool operator==(Iterator const& other) const { return other.m_value == m_value; }
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
Iterator& operator++()
{
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
m_value = IntrusiveList<T, Container, member>::next(m_value);
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
return *this;
}
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
Iterator& erase();
private:
T* m_value { nullptr };
};
Iterator begin();
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
Iterator end() { return Iterator {}; }
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
class ReverseIterator {
public:
ReverseIterator() = default;
ReverseIterator(T* value)
: m_value(move(value))
{
}
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const& operator*() const { return *m_value; }
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
auto operator->() const { return m_value; }
T& operator*() { return *m_value; }
auto operator->() { return m_value; }
Everywhere: Run clang-format
2022-04-01 17:58:27 +00:00
bool operator==(ReverseIterator const& other) const { return other.m_value == m_value; }
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
ReverseIterator& operator++()
{
m_value = IntrusiveList<T, Container, member>::prev(m_value);
return *this;
}
private:
T* m_value { nullptr };
};
ReverseIterator rbegin();
ReverseIterator rend() { return ReverseIterator {}; }
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
class ConstIterator {
public:
ConstIterator() = default;
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
ConstIterator(T const* value)
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
: m_value(value)
{
}
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const& operator*() const { return *m_value; }
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
auto operator->() const { return m_value; }
Everywhere: Run clang-format
2022-04-01 17:58:27 +00:00
bool operator==(ConstIterator const& other) const { return other.m_value == m_value; }
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
ConstIterator& operator++()
{
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
m_value = IntrusiveList<T, Container, member>::next(m_value);
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
return *this;
}
private:
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const* m_value { nullptr };
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
};
ConstIterator begin() const;
ConstIterator end() const { return ConstIterator {}; }
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
private:
static T* next(T* current);
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
static T* prev(T* current);
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
static T const* next(T const* current);
static T const* prev(T const* current);
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
static T* node_to_value(SubstitutedIntrusiveListNode<T, Container>& node);
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
IntrusiveListStorage<T, Container> m_storage;
};
template<typename T, typename Container>
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
class IntrusiveListNode {
public:
~IntrusiveListNode();
void remove();
bool is_in_list() const;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
static constexpr bool IsRaw = IsPointer<Container>;
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
// Note: For some reason, clang does not consider `member` as declared here, and as declared above (`SubstitutedIntrusiveListNode<T, Container> T::*`)
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
// to be of equal types. so for now, just make the members public on clang.
AK+Everywhere: Add AK_COMPILER_{GCC,CLANG} and use them most places Doesn't use them in libc headers so that those don't have to pull in AK/Platform.h. AK_COMPILER_GCC is set _only_ for gcc, not for clang too. (__GNUC__ is defined in clang builds as well.) Using AK_COMPILER_GCC simplifies things some. AK_COMPILER_CLANG isn't as much of a win, other than that it's consistent with AK_COMPILER_GCC.
2022-10-04 19:04:13 +00:00
#if !defined(AK_COMPILER_CLANG)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
private:
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T_, typename Container_, SubstitutedIntrusiveListNode<T_, Container_> T_::*member>
friend class ::AK::Detail::IntrusiveList;
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
#endif
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
IntrusiveListStorage<T, Container>* m_storage = nullptr;
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
SubstitutedIntrusiveListNode<T, Container>* m_next = nullptr;
SubstitutedIntrusiveListNode<T, Container>* m_prev = nullptr;
AK: Enable IntrusiveList self reference to be optimized out when empty If a member is an empty class, the standard normally stats that it needs to have a size of at least 1 byte in order to guarantee that the addresses of distinct objects of the same type are always distinct. However as of c++20, we can use [[no_unique_address]] to instruct the compiler that if the member has an empty type, it may optimize it to occupy no space.
2021-08-19 00:07:05 +00:00
[[no_unique_address]] SelfReferenceIfNeeded<Container, IsRaw> m_self;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
};
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline typename IntrusiveList<T, Container, member>::Iterator& IntrusiveList<T, Container, member>::Iterator::erase()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
auto old = m_value;
m_value = IntrusiveList<T, Container, member>::next(m_value);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
(old->*member).remove();
return *this;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline IntrusiveList<T, Container, member>::~IntrusiveList()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
clear();
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline void IntrusiveList<T, Container, member>::clear()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
while (m_storage.m_first)
m_storage.m_first->remove();
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline bool IntrusiveList<T, Container, member>::is_empty() const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
return m_storage.m_first == nullptr;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK: Add IntrusiveList::size_slow() to match InlineLinkedList The functionality is needed to replace InlineLinkedList with IntrusiveList in the Kernel Process class.
2021-06-06 21:13:10 +00:00
inline size_t IntrusiveList<T, Container, member>::size_slow() const
{
size_t size = 0;
auto it_end = end();
for (auto it = begin(); it != it_end; ++it) {
++size;
}
return size;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline void IntrusiveList<T, Container, member>::append(T& n)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
remove(n);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
auto& nnode = n.*member;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
nnode.m_storage = &m_storage;
nnode.m_prev = m_storage.m_last;
nnode.m_next = nullptr;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
if constexpr (!RemoveReference<decltype(nnode)>::IsRaw)
nnode.m_self.reference = &n; // Note: Self-reference ensures that the object will keep a ref to itself when the Container is a smart pointer.
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
if (m_storage.m_last)
m_storage.m_last->m_next = &nnode;
m_storage.m_last = &nnode;
if (!m_storage.m_first)
m_storage.m_first = &nnode;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline void IntrusiveList<T, Container, member>::prepend(T& n)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK: Use IntrusiveList::remove() in the IntrusiveList::prepend() prolog All other functions use the functionality for removal, use it in the prepend function as well for consistency.
2021-06-15 09:31:58 +00:00
remove(n);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
AK: Use IntrusiveList::remove() in the IntrusiveList::prepend() prolog All other functions use the functionality for removal, use it in the prepend function as well for consistency.
2021-06-15 09:31:58 +00:00
auto& nnode = n.*member;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
nnode.m_storage = &m_storage;
nnode.m_prev = nullptr;
nnode.m_next = m_storage.m_first;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
if constexpr (!RemoveReference<decltype(nnode)>::IsRaw)
nnode.m_self.reference = &n;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
if (m_storage.m_first)
m_storage.m_first->m_prev = &nnode;
m_storage.m_first = &nnode;
if (!m_storage.m_last)
m_storage.m_last = &nnode;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Tests: Add IntrusiveList<T,...>::insert_before(..) method The insert_before method on AK::InlineLinkedList is used, so in order to achieve feature parity, we need to implement it for AK::IntrusiveList as well.
2021-06-15 09:33:59 +00:00
inline void IntrusiveList<T, Container, member>::insert_before(T& bn, T& n)
{
remove(n);
auto& new_node = n.*member;
auto& before_node = bn.*member;
new_node.m_storage = &m_storage;
new_node.m_next = &before_node;
new_node.m_prev = before_node.m_prev;
if (before_node.m_prev)
before_node.m_prev->m_next = &new_node;
before_node.m_prev = &new_node;
if (m_storage.m_first == &before_node) {
m_storage.m_first = &new_node;
}
if constexpr (!RemoveReference<decltype(new_node)>::IsRaw)
new_node.m_self.reference = &n;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline void IntrusiveList<T, Container, member>::remove(T& n)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
auto& nnode = n.*member;
if (nnode.m_storage)
nnode.remove();
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
inline bool IntrusiveList<T, Container, member>::contains(T const& n) const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
auto& nnode = n.*member;
return nnode.m_storage == &m_storage;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline Container IntrusiveList<T, Container, member>::first() const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
return m_storage.m_first ? node_to_value(*m_storage.m_first) : nullptr;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline Container IntrusiveList<T, Container, member>::take_first()
AK: Add IntrusiveList::take_first()
2019-12-22 11:23:30 +00:00
{
AK: Fix IntrusvieList::take_first/last() actually compile with RefPtr<T> PR #6376 made IntrusiveList capable of holding RefPtr<T>, etc. however there was a latent bug where take_first() / take_last() would fail to compile because they weren't being converted to their container type.
2021-04-20 06:27:26 +00:00
if (Container ptr = first()) {
AK: Add IntrusiveList::take_first()
2019-12-22 11:23:30 +00:00
remove(*ptr);
return ptr;
}
return nullptr;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline Container IntrusiveList<T, Container, member>::take_last()
AK: Add IntrusiveList::take_last()
2020-11-24 15:37:55 +00:00
{
AK: Fix IntrusvieList::take_first/last() actually compile with RefPtr<T> PR #6376 made IntrusiveList capable of holding RefPtr<T>, etc. however there was a latent bug where take_first() / take_last() would fail to compile because they weren't being converted to their container type.
2021-04-20 06:27:26 +00:00
if (Container ptr = last()) {
AK: Add IntrusiveList::take_last()
2020-11-24 15:37:55 +00:00
remove(*ptr);
return ptr;
}
return nullptr;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline Container IntrusiveList<T, Container, member>::last() const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
return m_storage.m_last ? node_to_value(*m_storage.m_last) : nullptr;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
inline T const* IntrusiveList<T, Container, member>::next(T const* current)
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
{
auto& nextnode = (current->*member).m_next;
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const* nextstruct = nextnode ? node_to_value(*nextnode) : nullptr;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
return nextstruct;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
inline T const* IntrusiveList<T, Container, member>::prev(T const* current)
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
{
auto& prevnode = (current->*member).m_prev;
Kernel: Make self-contained locking smart pointers their own classes Until now, our kernel has reimplemented a number of AK classes to provide automatic internal locking: - RefPtr - NonnullRefPtr - WeakPtr - Weakable This patch renames the Kernel classes so that they can coexist with the original AK classes: - RefPtr => LockRefPtr - NonnullRefPtr => NonnullLockRefPtr - WeakPtr => LockWeakPtr - Weakable => LockWeakable The goal here is to eventually get rid of the Lock* classes in favor of using external locking.
2022-08-19 18:53:40 +00:00
T const* prevstruct = prevnode ? node_to_value(*prevnode) : nullptr;
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
return prevstruct;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline T* IntrusiveList<T, Container, member>::next(T* current)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
auto& nextnode = (current->*member).m_next;
T* nextstruct = nextnode ? node_to_value(*nextnode) : nullptr;
return nextstruct;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
inline T* IntrusiveList<T, Container, member>::prev(T* current)
{
auto& prevnode = (current->*member).m_prev;
T* prevstruct = prevnode ? node_to_value(*prevnode) : nullptr;
return prevstruct;
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline typename IntrusiveList<T, Container, member>::Iterator IntrusiveList<T, Container, member>::begin()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
return m_storage.m_first ? Iterator(node_to_value(*m_storage.m_first)) : Iterator();
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK: Add reverse iterator support to AK::IntrusiveList In order for IntrusiveList to be capable of replacing InlineLinkedList, it needs to support reverse iteration. InlineLinkedList currently supports manual reverse iteration by calling list->last() followed by node->prev().
2021-06-03 10:14:56 +00:00
inline typename IntrusiveList<T, Container, member>::ReverseIterator IntrusiveList<T, Container, member>::rbegin()
{
return m_storage.m_last ? ReverseIterator(node_to_value(*m_storage.m_last)) : ReverseIterator();
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
inline typename IntrusiveList<T, Container, member>::ConstIterator IntrusiveList<T, Container, member>::begin() const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK: Add basic const iteration to IntrusiveList
2021-03-11 13:12:33 +00:00
return m_storage.m_first ? ConstIterator(node_to_value(*m_storage.m_first)) : ConstIterator();
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, typename Container, SubstitutedIntrusiveListNode<T, Container> T::*member>
inline T* IntrusiveList<T, Container, member>::node_to_value(SubstitutedIntrusiveListNode<T, Container>& node)
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK: Accomodate always-32-bit data member pointers in IntrusiveList This only exists on windows, but we've made an effort to keep jakt working on windows, so let's support this silliness.
2023-04-30 15:10:07 +00:00
// Note: A data member pointer is a 32-bit offset in the Windows ABI (both x86 and x86_64),
// whereas it is an appropriately sized ptrdiff_t in the Itanium ABI, the following ensures
// that we always use the correct type for the subtraction.
using EquivalentNumericTypeForDataMemberPointer = Conditional<sizeof(member) == sizeof(ptrdiff_t), ptrdiff_t, u32>;
static_assert(sizeof(EquivalentNumericTypeForDataMemberPointer) == sizeof(member),
"The equivalent numeric type for the data member pointer must have the same size as the data member pointer itself.");
AK: Avoid the unnecessarily confusing bunch of casts in IntrusiveList And use bit_cast instead. Also explain what it does, because it's not at all trivial to understand :^)
2021-04-16 12:00:20 +00:00
// Note: Since this might seem odd, here's an explanation on what this function actually does:
// `node` is a reference that resides in some part of the actual value (of type T), the
// placement (i.e. offset) of which is described by the pointer-to-data-member parameter
// named `member`.
// This function effectively takes in the address of the data member, and returns the address
// of the value (of type T) holding that member.
AK: Accomodate always-32-bit data member pointers in IntrusiveList This only exists on windows, but we've made an effort to keep jakt working on windows, so let's support this silliness.
2023-04-30 15:10:07 +00:00
return bit_cast<T*>(bit_cast<unsigned char*>(&node) - bit_cast<EquivalentNumericTypeForDataMemberPointer>(member));
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
}
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
template<typename T, typename Container>
inline IntrusiveListNode<T, Container>::~IntrusiveListNode()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
AK: Don't unlink intrusive list elements in the destructor Removing the element from the intrusive linked list might not be safe if doing so requires a lock. Instead this is something the caller should have done so let's verify instead that we're not on any lists.
2021-05-19 21:42:28 +00:00
VERIFY(!is_in_list());
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
}
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
template<typename T, typename Container>
inline void IntrusiveListNode<T, Container>::remove()
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
Everywhere: Rename ASSERT => VERIFY (...and ASSERT_NOT_REACHED => VERIFY_NOT_REACHED) Since all of these checks are done in release builds as well, let's rename them to VERIFY to prevent confusion, as everyone is used to assertions being compiled out in release. We can introduce a new ASSERT macro that is specifically for debug checks, but I'm doing this wholesale conversion first since we've accumulated thousands of these already, and it's not immediately obvious which ones are suitable for ASSERT.
2021-02-23 19:42:32 +00:00
VERIFY(m_storage);
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
if (m_storage->m_first == this)
m_storage->m_first = m_next;
if (m_storage->m_last == this)
m_storage->m_last = m_prev;
if (m_prev)
m_prev->m_next = m_next;
if (m_next)
m_next->m_prev = m_prev;
m_prev = nullptr;
m_next = nullptr;
m_storage = nullptr;
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
if constexpr (!IsRaw)
m_self.reference = nullptr;
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
}
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
template<typename T, typename Container>
inline bool IntrusiveListNode<T, Container>::is_in_list() const
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
{
return m_storage != nullptr;
}
AK: Make IntrusiveList work with NonnullRefPtr's
2021-04-20 08:31:27 +00:00
// Specialise IntrusiveList for NonnullRefPtr
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
// By default, intrusive lists cannot contain null entries anyway, so switch to RefPtr
// and just make the user-facing functions deref the pointers.
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
template<class T, SubstitutedIntrusiveListNode<T, NonnullRefPtr<T>> T::*member>
AK+Kernel: Make IntrusiveList capable of holding non-raw pointers This should allow creating intrusive lists that have smart pointers, while remaining free (compared to the impl before this commit) when holding raw pointers :^) As a sidenote, this also adds a `RawPtr<T>` type, which is just equivalent to `T*`. Note that this does not actually use such functionality, but is only expected to pave the way for #6369, to replace NonnullRefPtrVector<T> with intrusive lists. As it is with zero-cost things, this makes the interface a bit less nice by requiring the type name of what an `IntrusiveListNode` holds (and optionally its container, if not RawPtr), and also requiring the type of the container (normally `RawPtr`) on the `IntrusiveList` instance.
2021-04-16 12:03:24 +00:00
class IntrusiveList<T, NonnullRefPtr<T>, member> : public IntrusiveList<T, RefPtr<T>, member> {
public:
[[nodiscard]] NonnullRefPtr<T> first() const { return *IntrusiveList<T, RefPtr<T>, member>::first(); }
[[nodiscard]] NonnullRefPtr<T> last() const { return *IntrusiveList<T, RefPtr<T>, member>::last(); }
[[nodiscard]] NonnullRefPtr<T> take_first() { return *IntrusiveList<T, RefPtr<T>, member>::take_first(); }
[[nodiscard]] NonnullRefPtr<T> take_last() { return *IntrusiveList<T, RefPtr<T>, member>::take_last(); }
};
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
}
AK+Everywhere: Reduce the number of template parameters of IntrusiveList This makes the user-facing type only take the node member pointer, and lets the compiler figure out the other needed types from that.
2021-09-09 12:00:59 +00:00
namespace AK {
template<typename T, typename Container = RawPtr<T>>
using IntrusiveListNode = Detail::SubstitutedIntrusiveListNode<T, Container>;
template<auto member>
using IntrusiveList = Detail::IntrusiveList<
decltype(Detail::ExtractIntrusiveListTypes::value(member)),
decltype(Detail::ExtractIntrusiveListTypes::container(member)),
member>;
}
AK: Make it possible to not `using` AK classes into the global namespace This patch adds the `USING_AK_GLOBALLY` macro which is enabled by default, but can be overridden by build flags. This is a step towards integrating Jakt and AK types.
2022-11-26 11:18:30 +00:00
#if USING_AK_GLOBALLY
AK: Introduce IntrusiveList And use it in the scheduler. IntrusiveList is similar to InlineLinkedList, except that rather than making assertions about the type (and requiring inheritance), it provides an IntrusiveListNode type that can be used to put an instance into many different lists at once. As a proof of concept, port the scheduler over to use it. The only downside here is that the "list" global needs to know the position of the IntrusiveListNode member, so we have to position things a little awkwardly to make that happen. We also move the runnable lists to Thread, to avoid having to publicize the node.
2019-07-19 11:04:42 +00:00
using AK::IntrusiveList;
using AK::IntrusiveListNode;
AK: Make it possible to not `using` AK classes into the global namespace This patch adds the `USING_AK_GLOBALLY` macro which is enabled by default, but can be overridden by build flags. This is a step towards integrating Jakt and AK types.
2022-11-26 11:18:30 +00:00
#endif
Reference in a new issue Copy permalink