summaryrefslogtreecommitdiff
path: root/AK/Bitmap.h
AgeCommit message (Collapse)Author
2023-03-09AK: Replace C-style castsSam Atkins
2022-12-22AK+Everywhere: Replace all Bitmap::must_create() uses with ::create()Sam Atkins
Well, *someone* has to add some more FIXMEs to keep FIXME Roulette going. :^)
2022-12-22AK: Rename Bitmap::try_create() to ::create()Sam Atkins
This is step 1 to removing `must_create()`.
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-02-11AK: Make Bitmap construction OOM-fallibleIdan Horowitz
2022-02-05AK: Remove commented-out code from Bitmap containerLiav A
Instead, add a note to explain that there's a const variant of data() method in the parent BitmapView class.
2021-11-28AK: Remove unused static member of BitmapBen Wiederhake
This is a remnant of the Bitmap/BitmapView split.
2021-11-14AK: Resolve clang-tidy readability-const-return-type warning in BitmapAndrew Kaster
Returning a const BitmapView doesn't make much sense :^)
2021-11-14AK: Resolve clang-tidy readability-qualified-auto warningsAndrew Kaster
... In files included by Kernel/Process.cpp and Kernel/Thread.cpp
2021-11-14AK: Resolve clang-tidy readability-bool-conversion warningsAndrew Kaster
... In files included by Kernel/Process.cpp and Kernel/Thread.cpp
2021-11-10AK: Properly declare inheritance of Bitmap from BitmapViewBen Wiederhake
All the read-only methods of Bitmap simply defer to BitmapView. Let's make this relationship official by using class inheritance. This might even shave off a few instructions, although any sufficiently optimizing compiler probably already optimized them away.
2021-11-10AK+Kernel: Make BitmapView read-onlyBen Wiederhake
2021-07-21AK: Sprinkle [[nodiscard]] on AK::BitmapAndreas Kling
2021-07-13AK: Make Bitmap::set() non-constAndreas Kling
2021-07-11AK: Use kfree_sized() in AK::BitmapAndreas Kling
2021-05-19Bitmap: De-duplicate bitmasksLenny Maiorani
Problem: - Bitmasks are duplicated. - Bitmasks are C-style arrays. Solution: - Move bitmasks to BitmapView.h. - Change C-style arrays to be AK::Array for added safety.
2021-05-18BitmapView: Disable mutations of the underlying BitmapLenny Maiorani
Problem: - `BitmapView` permits changing the underlying `Bitmap`. This violates the idea of a "view" since views are simply overlays which can themselves change but do not change the underlying data. Solution: - Migrate all non-`const` member functions to Bitmap.
2021-05-17Revert "BitmapView: Disable mutations of the underlying Bitmap"Andreas Kling
This reverts commit f25209113fcd15df5778938c4accf13c5139d278.
2021-05-17BitmapView: Disable mutations of the underlying BitmapLenny Maiorani
Problem: - `BitmapView` permits changing the underlying `Bitmap`. This violates the idea of a "view" since views are simply overlays which can themselves change but do not change the underlying data. Solution: - Migrate all non-`const` member functions to Bitmap.
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-09AK: Add BitmapView::set_range_and_verify_that_all_bits_flip()Andreas Kling
This function sets a range of bits to the same value while also verifying that all bits in the range get flipped in the process.
2021-03-04AK: Simplify Bitmap and implement in terms of BitmapViewAndreas Kling
Add Bitmap::view() and forward most of the calls to BitmapView since the code was identical. Bitmap is now primarily concerned with its dynamically allocated backing store and BitmapView deals with the rest.
2021-03-04AK: Add Bitmap::is_null()Andreas Kling
This class has a null state but there was no API to check for it.
2021-02-23Everywhere: Rename ASSERT => VERIFYAndreas Kling
(...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-14AK: Make the Bitmap::size_in_bytes() member function publicAnotherTest
It's annoying to calculate it when it's already a member function.
2021-02-08Everywhere: Remove unnecessary headers 4/4Ben Wiederhake
Arbitrarily split up to make git bisect easier. These unnecessary #include's were found by combining an automated tool (which determined likely candidates) and some brain power (which decided whether the #include is also semantically superfluous).
2020-10-03Everywhere: Fix more typosLinus Groh
2020-09-09AK: Add Bitmap::find_one_anywhere and optimize Bitmap::find_firstTom
Leverage constexpr and __builtin_ffs for Bitmap::find_first. Also add a variant Bitmap::find_one_anywhere that can start scanning at a provided hint. Also, merge Bitmap::fill_range into the already existing Bitmap::set_range
2020-09-06AK: Add Bitmap::count_in_range and Bitmap::fill_rangeTom
2020-08-27Meta: Force semi-colon after MAKE_AK_NONXXXABLE()Ben Wiederhake
Before, we had about these occurrence counts: COPY: 13 without, 33 with MOVE: 12 without, 28 with Clearly, 'with' was the preferred way. However, this introduced double-semicolons all over the place, and caused some warnings to trigger. This patch *forces* the usage of a semi-colon when calling the macro, by removing the semi-colon within the macro. (And thus also gets rid of the double-semicolon.)
2020-05-06AK: Fix Bitmap not finding unset ranges at the end of the mapAndreas Kling
When we switched the Bitmap code to operating 32 bits at a time, we neglected to look in the trailing remainder bits after the last full 32-bit word. This patch fixes that and adds a couple of tests for Bitmap that I hacked up while tracking down this bug. I found this bug when noticing that the kernel would OOM while there were still some pages left in the physical page allocator.
2020-04-06Kernel: Support best fit allocation policy in kmalloc()nimelehin
Add find_best_fit() which implements best fit allocation algorithm. Kmalloc now uses a best fit allocation policy for large allocations.
2020-04-06Bitmap: Add Bitmap::find_next_range_of_unset_bits()nimelehin
AK::Bitmap is extended with find_next_range_of_unset_bits(). The function is implemented using count_trailing_zeroes_32(), which is optimized on many platforms, that gives a huge performance boost. Functions find_longest_range_of_unset_bits() and find_first_fit() are implemented with find_next_range_of_unset_bits(). According to benchmarks, they are 60-100% faster.
2020-04-06AK: Add Bitmap::find_first_fit()nimelehin
Add find_first_fit() which implements first fit algorithm.
2020-04-06AK: Add Bitmap::set_range()nimelehin
Add set_range() which sets a range of bits to requested value. Fix code style.
2020-03-08AK: Use default constructor of Optional if an unset bit is not foundLiav A
2020-03-08AK: Use __builtin_memset() and such to reduce header dependenciesAndreas Kling
We can use __builtin_memset() without including <string.h>. This is pretty neat, as it will allow us to reduce the header deps of AK templates a bit, if applied consistently. Note that this is an enabling change for an upcoming #include removal.
2020-03-06AK: Remove Optional::operator bool()Andreas Kling
This was causing some obvious-in-hindsight but hard to spot bugs where we'd implicitly convert the bool to an integer type and carry on with the number 1 instead of the actual value().
2020-03-02AK: Remove superfluous explicit in Bitmap (#1337)howar6hill
2020-02-25AK: Some more int => size_t in BitmapAndreas Kling
2020-02-24AK: Make Bitmap use size_t for its sizeAndreas Kling
Also rework its API's to return Optional<size_t> instead of int with -1 as the error value.
2020-01-26Ext2FS: allocate_blocks allocates contiguous blocks (#1095)Marios Prokopakis
This implementation uses the new helper method of Bitmap called find_longest_range_of_unset_bits. This method looks for the biggest range of contiguous bits unset in the bitmap and returns the start of the range back to the caller.
2020-01-18Meta: Add license header to source filesAndreas Kling
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.
2019-10-01AK: Make Bitmap constructors public to allow make<Bitmap>()Andreas Kling
I don't love this, but I also don't love the Bitmap class in general.
2019-08-01AK: Make Bitmap movable but not copyable.Andreas Kling
We were falling back to an incorrect compiler-generated copy ctor for this class, and let's not do that. Found by PVS-Studio.
2019-07-03AK: Rename the common integer typedefs to make it obvious what they are.Andreas Kling
These types can be picked up by including <AK/Types.h>: * u8, u16, u32, u64 (unsigned) * i8, i16, i32, i64 (signed)
2019-06-12AK: Add find_first_{set,unset} and grow methods to BitmapConrad Pankoff
2019-05-28Add clang-format fileRobin Burchell
Also run it across the whole tree to get everything using the One True Style. We don't yet run this in an automated fashion as it's a little slow, but there is a snippet to do so in makeall.sh.
2019-05-14Kernel: Encapsulate the Region's COW map a bit better.Andreas Kling
2019-02-25More moving towards using signed types.Andreas Kling
I'm still feeling this out, but I am starting to like the general idea.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-17 05:51:19 +0000