Commit graph

9 commits

Author SHA1 Message Date
Dan Klishch
ba24e86fdd AK: Introduce IntrusiveBinaryHeap and reimplement BinaryHeap using it
The main difference between them is that IntrusiveBinaryHeap can
optionally maintain an index inside every stored node that allows
arbitrary nodes to be deleted.
2024-02-25 17:24:36 -07:00
Linus Groh
d26aabff04 Everywhere: Run clang-format 2022-12-03 23:52:23 +00:00
Andreas Kling
ae3ffdd521 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 15:51:34 +01:00
Lenny Maiorani
ccbf240962 AK: Add nodiscard attribute to BinaryHeap functions 2022-07-04 05:53:56 +00:00
Ben Wiederhake
f8d7b4daea AK: Add missing headers
Example failure:

IDAllocator.h only pulls in AK/Hashtable.h, so any compilation unit that
includes AK/IDAllocator.h without including AK/Traits.h before it used
to be doomed to fail with the cryptic error message "In instantiation of
'AK::HashTable<T, TraitsForT, IsOrdered>::Iterator AK::HashTable<T,
TraitsForT, IsOrdered>::find(const T&) [with T = int; TraitsForT =
AK::Traits: incomplete type 'AK::Traits<int>' used in nested name
specifier".
2021-10-06 23:52:40 +01:00
Idan Horowitz
1c512a702a AK+Userland: Use idan.horowitz@serenityos.org for my copyright headers 2021-04-22 22:42:38 +02:00
Brian Gianforcaro
1682f0b760 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 11:22:27 +02:00
Idan Horowitz
3c7aa56ae8 AK: Store BinaryHeap key-value pairs together for efficient swaps
The 2 seperate key and value arrays are replaced with a single struct pair
array that allows for a 2x reduction in loads/stores during element swaps
in the common case of same-sized keys and values.
2021-03-13 23:50:07 +01:00
Idan Horowitz
168cf6fac9 AK: Implement minimum BinaryHeap
This enables efficient implementations of priority queues,
and will also be used in LibCompress for efficient huffman
tree generation.
2021-03-13 20:07:25 +01:00