summaryrefslogtreecommitdiff
path: root/AK/IntrusiveRedBlackTree.h
AgeCommit message (Collapse)Author
2022-12-09Everywhere: Remove unnecessary AK and Detail namespace scopingMoustafa Raafat
2022-12-03Everywhere: Run clang-formatLinus Groh
2022-11-26AK: Make it possible to not `using` AK classes into the global namespaceAndreas Kling
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-10-04AK+Everywhere: Add AK_COMPILER_{GCC,CLANG} and use them most placesNico Weber
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-04-21AK: Expose RedBlackTree::find_smallest_not_below()Tim Schumacher
2022-04-04AK: Add begin_from(V&) APIs to IntrusiveRedBlackTreeIdan Horowitz
This method exploits the fact that the values themselves hold the tree pointers, and as a result this let's us skip the O(logn) traversal down to the matching Node for a Key-Value pair.
2022-04-01Everywhere: Run clang-formatIdan Horowitz
2021-09-10AK+Kernel: Reduce the number of template parameters of IntrusiveRBTreeAli Mohammad Pur
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-08AK: Add key getter to IntrusiveRedBlackTreeNodeIdan Horowitz
2021-09-08AK: Set IntrusiveRBTree Node key on insertion instead of constructionIdan Horowitz
This makes the API look much nicer.
2021-09-08AK: Make IntrusiveRedBlackTree capable of holding non-raw pointersIdan Horowitz
This is completely based on e4412f1f599bea034dea608b8c7dcc4408d90066 and will allow us to convert some AK::HashMap users in the kernel.
2021-08-13IntrusiveRedBlackTree: Remove redundant subtraction of 0Lenny Maiorani
Problem: - ToT clang will not build due to casting `nullptr` to `u8*`. This is redundant because it casts to get a `0` then subtracts it. Solution: - Remove it since subtracting `0` doesn't do anything.
2021-07-17AK: Mark RedBlackTree functions as [[nodiscard]]Brian Gianforcaro
2021-07-17AK: Mark AK::IntrusiveRedBlackTree as finalBrian Gianforcaro
2021-04-23Revert "AK: Remove virtual destructors from non-virtual classes"Idan Horowitz
This reverts commit 4378d36f6701e0f4efe71ff1a301e3cd0776d5bf.
2021-04-23AK: Remove virtual destructors from non-virtual classesLenny Maiorani
Problem: - Some classes have `virtual` destructors despite not having any virtual functions. This causes the classes to have a v-table and perform extra jumps at destruction time when there is no need. Solution: - Remove `virtual` keyword from destructors where there are no other virtual functions. - Remove the destructor completely when the default destructor can be used.
2021-04-22AK+Userland: Use idan.horowitz@serenityos.org for my copyright headersIdan Horowitz
2021-04-22Everything: Move to SPDX license identifiers in all files.Brian Gianforcaro
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-12AK: Implement IntrusiveRedBlackTree containerIdan Horowitz
This container is similar to the RedBlackTree container, but instead of transparently allocating tree nodes on insertion and freeing on removal this container piggybacks on intrusive node fields in the stored class