summaryrefslogtreecommitdiff
path: root/AK/Vector.h
AgeCommit message (Collapse)Author
2022-04-06AK: Add const version of Vector::first_matchingkleines Filmröllchen
2022-04-04AK: Make Vector<T>::{first,last}_matching() return Optional<T&>Ali Mohammad Pur
These functions are _very_ misleading, as `first()` and `last()` return references, but `{first,last}_matching()` return copies of the values. This commit makes it so that they now return Optional<T&>, eliminating the copy and the confusion.
2022-03-28AK: Make Vector capable of holding forward-declared typesAli Mohammad Pur
This is pretty useful for making trees.
2022-03-18AK: Add const variant of Vector::in_reverse()Andreas Kling
2022-03-14AK: Allow creating a Vector from any Span of the same underlying typeTimothy Flynn
This allows, for example, to create a Vector from a subset of another Vector.
2022-03-09AK: Add reverse iterator as memberFederico Guerinoni
2022-03-09AK: Implement reverse iterator for Vector classFederico Guerinoni
2022-02-05AK: Make Vector::data() ALWAYS_INLINEIdan Horowitz
This was showing up in profiles of Browser, and it really shouldn't be.
2022-01-16AK: Make Vector more const-correct by using RemoveReference<T>creator1creeper1
Methods marked as const should always only return Foo const&, never Foo&. Previously, this only worked correctly with Foo, but not with Foo&: If someone fetched a T const&, this would have been expanded to Foo& const& which is just Foo&. Therefore, they were able to modify the elements of the Vector, even though it was marked as const. This commit fixes that by introducing VisibleType as an alias for RemoveReference<T> and using it throughout Vector. There are also other cases where we don't require a mutable reference to the underlying type, only a const reference (for example in a find operation). In these cases, we now also correctly expand the type to Foo const&.
2022-01-05AK: Make Vector::remove_all_matching() return removal successAndreas Kling
This matches the behavior of other remove_*_matching() functions.
2022-01-05AK: Disable Vector insert/empend/prepend + a append overload in KernelBrian Gianforcaro
We have whittled away at the usages of these AK::Vector APIs in the Kernel. This change disables them from being visible when building the Kernel to make sure no new usages get added.
2021-11-28AK: Stop Vector::extend from unnecessary reallocationkleines Filmröllchen
Previously, Vector::extend for a moved vector would move the other vector into this vector if this vector was empty, thereby throwing away existing allocated capacity. Therefore, this commit allows the move to only happen if this vector's capacity is too small to fit the other vector. This will also alleviate bugs where callers relied on the capacity to never shrink with calls to unchecked_append, extend and the like.
2021-11-28AK: Add Vector::unchecked_append for data pointerskleines Filmröllchen
This mirrors the existence of append() for data pointers and is very useful when the program needs to have a guarantee of no allocations, as is necessary for real-time audio.
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: Make Vector::try_* functions return ErrorOr<void>Andreas Kling
Instead of signalling allocation failure with a bool return value (false), we now use ErrorOr<void> and return ENOMEM as appropriate. This allows us to use TRY() and MUST() with Vector. :^)
2021-09-20AK: Remove unnecessary include of <new> for non-`__serenity__` buildsAndrew Kaster
We already include `<new>` in AK/kmalloc.h when KERNEL is not defined, which applies to all non-`__serenity__` builds.
2021-09-20AK+LibC: Remove SERENITY_LIBC_BUILD guard around `<initializer_list>`Andrew Kaster
This was required before commit 5f724b6ca1aae3a5a8c7189069649e8a9347cca2 when we were building LibC before libstdc++ headers were available in the sysroot. However as noted in that commit, we never actually needed to be building LibC before libstdc++, so we can go ahead and remove this ancient hack.
2021-09-17AK/Vector: Add `Vector::reverse()` methodMustafa Quraish
This reverses the contents of the vector in-place.
2021-08-08AK: Use kmalloc_array() where appropriateAndreas Kling
2021-07-22AK: Add a deduction guide to VectorAli Mohammad Pur
Note that this does not generate a vector with inline capacity.
2021-07-13Vector: Homogenize type and parameter names for predicatesngc6302h
2021-07-11AK: Use kfree_sized() in AK::VectorAndreas Kling
2021-06-12AK: Rename Vector::append(Vector) => Vector::extend(Vector)Andreas Kling
Let's make it a bit more clear when we're appending the elements from one vector to the end of another vector.
2021-06-09AK: Make Vector::take_last() ALWAYS_INLINEAli Mohammad Pur
This function doesn't do a whole lot, but is called quite a bit.
2021-06-08AK: Make Vector capable of holding reference typesAli Mohammad Pur
This commit makes it possible to instantiate `Vector<T&>` and use it to store references to `T` in a vector. All non-pointer observers are made to return the reference, and the pointer observers simply yield the underlying pointer. Note that the 'find_*' methods act on the values and not the pointers that are stored in the vector. This commit also makes errors in various vector methods much more readable by directly using requires-clauses on them. And finally, it should be noted that Vector cannot hold temporaries :^)
2021-06-08AK: Switch to east const in Vector.hAli Mohammad Pur
Let's get this out of the way before touching the file.
2021-06-08AK: Reorder Vector methods to place similar methods next to each otherAli Mohammad Pur
The methods of this class were all over the place, this commit reorders them to place them in a more logical order: - Constructors/Destructor - Observers - Comparisons and const existence checks - Mutators: insert - Mutators: append - Mutators: prepend - Mutators: assignment - Mutators: remove - OOM-safe mutators: insert - OOM-safe mutators: append - OOM-safe mutators: prepend - OOM-safe size management - Size management - Iterators
2021-06-08AK: Rename Vector::{value_type => ValueType}Ali Mohammad Pur
2021-05-22AK/Vector: Constify find_first_index()Jelle Raaijmakers
2021-05-20LibCore: Let IODevice::can_read_line() buffer until \n or EOFr-paiva
If a line was larger than 1024 bytes or the file ended without a newline character, can_read_line would return false. IODevice::can_read_line() now reads until a newline is found or EOF is reached. fixes #5907
2021-05-20AK: Added contains_in_range to Vectorr-paiva
Vector::contains_in_range() allows the search of an element in a given range on a vector object. Also added testcases for the new Vector method.
2021-05-16AK+Userland: Remove nullability feature for the ByteBuffer typeGunnar Beutner
Nobody seems to use this particular feature, in fact there were some bugs which were uncovered by removing operator bool.
2021-05-15AK+LibC: Implement malloc_good_size() and use it for Vector/HashTableGunnar Beutner
This implements the macOS API malloc_good_size() which returns the true allocation size for a given requested allocation size. This allows us to make use of all the available memory in a malloc chunk. For example, for a malloc request of 35 bytes our malloc would internally use a chunk of size 64, however the remaining 29 bytes would be unused. Knowing the true allocation size allows us to request more usable memory that would otherwise be wasted and make that available for Vector, HashTable and potentially other callers in the future.
2021-05-14AK: Vector::resize() should initialize new slots for primitive typesGunnar Beutner
We call placement new for the newly added slots. However, we should also specify an initializer so primitive data types like u64 are initialized appropriately.
2021-04-29AK: Make AK::Vector expose allocation failures in APISahan Fernando
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-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-01-31Vector: Correctly pass args to insert, insert_before_matching, prependLenny Maiorani
Problem: - Using regular functions rather than function templates results in the arguments not being deduced. This then requires the same function to be written multiple times and for `move` to be used rather than `forward`. Solution: - Collapse multiple function overloads to a single function template with a deduced argument. This allows the argument to be a forwarding reference and bind to either an l-value or r-value and forward the value. Note: - `append` is not being changed because there are several overloads for appending single values and concatenating vectors. This conflation needs to be addressed first.
2021-01-17AK: Add Vector::remove overload for removing entire rangesTom
2021-01-11Vector: Implement `find`, `find_if`, `find_first_matching` in terms of ↵Lenny Maiorani
`AK::find*` Problem: - The implementation of `find` is coupled to the implementation of `Vector`. - `Vector::find` takes the predicate by value which might be expensive. Solution: - Decouple the implementation of `find` from `Vector` by using a generic `find` algorithm. - Change the name of `find` with a predicate to `find_if` so that a binding reference can be used and the predicate can be forwarded to avoid copies. - Change all the `find(pred)` call sites to use `find_if`.
2020-12-27AK: Use direct-list-initialization for Vector::empend() (#4564)Nathan Lanza
clang trunk with -std=c++20 doesn't seem to properly look for an aggregate initializer here when the type being constructed is a simple aggregate (e.g. `struct Thing { int a; int b; };`). This template fails to compile in a usage added 12/16/2020 in `AK/Trie.h`. Both forms of initialization are supposed to call the aggregate-initializers but direct-list-initialization delegating to aggregate initializers is a new addition in c++20 that might not be implemented yet.
2020-11-23AK: Add Vector::prepend() overload for multiple itemsSergey Bugaev
Much like with Vector::append(), you may want to append multiple items in one go. It's actually more important to do this for prepending, because you don't want to copy the rest of items further each time.
2020-11-22AK: Add first_matching and last_matching to VectorLuke
first_matching returns the first item in the vector that matches the given condition. last_matching returns the last item in the vector that matches the given condition.
2020-11-16Vector: C++20 equality operatorsLenny Maiorani
Problem: - C++20 changes the way equality operators are generated. This results in overload ambiguity as reported by clang. Solution: - Remove `AK::Vector::operator!=` because it will be automatically generated in terms of `AK::Vector::operator==`. - Change `AK::Vector::operator==` to be a function template so that overload resolution is not confused about `a == b` vs `b == a`. - Add tests to ensure the behavior works. Notes: - There is more info available at https://brevzin.github.io/c++/2019/07/28/comparisons-cpp20/ for deeper discussion about overload resolution, operator rewriting, and generated functions.
2020-10-06AK: Make Vector::remove_first_matching() signal if anything was removedAndreas Kling
2020-09-09AK: Moved TypedTransfer into it's own header.asynts
2020-09-08AK: Add generic SimpleIterator class to replace VectorIterator.asynts
2020-09-06AK: Vector use Traits<T>::equals in findMuhammad Zahalqa
Use Traits<T>::equals for equality checking in search functions instead of operator==
2020-08-15AK: Rename span() to bytes() when appropriate.asynts
I originally defined the bytes() method for the String class, because it made it obvious that it's a span of bytes instead of span of characters. This commit makes this more consistent by defining a bytes() method when the type of the span is known to be u8. Additionaly, the cast operator to Bytes is overloaded for ByteBuffer and such.
2020-08-10disasm: Insert symbol names in disassembly streamNico Weber
The symbol name insertion scheme is different from objdump -d's. Compare the output on Build/Userland/id: * disasm: ... _start (08048305-0804836b): 08048305 push ebp ... 08048366 call 0x0000df56 0804836b o16 nop 0804836d o16 nop 0804836f nop (deregister_tm_clones (08048370-08048370)) 08048370 mov eax, 0x080643e0 ... _ZN2AK8Utf8ViewC1ERKNS_6StringE (0805d9b2-0805d9b7): _ZN2AK8Utf8ViewC2ERKNS_6StringE (0805d9b2-0805d9b7): 0805d9b2 jmp 0x00014ff2 0805d9b7 nop * objdump -d: 08048305 <_start>: 8048305: 55 push %ebp ... 8048366: e8 9b dc 00 00 call 8056006 <exit> 804836b: 66 90 xchg %ax,%ax 804836d: 66 90 xchg %ax,%ax 804836f: 90 nop 08048370 <deregister_tm_clones>: 8048370: b8 e0 43 06 08 mov $0x80643e0,%eax ... 0805d9b2 <_ZN2AK8Utf8ViewC1ERKNS_6StringE>: 805d9b2: e9 eb f6 ff ff jmp 805d0a2 <_ZN2AK10StringViewC1ERKNS_6StringE> 805d9b7: 90 nop Differences: 1. disasm can show multiple symbols that cover the same instructions. I've only seen this happen for C1/C2 (and D1/D2) ctor/dtor pairs, but it could conceivably happen with ICF as well. 2. disasm separates instructions that do not belong to a symbol with a newline, so that nop padding isn't shown as part of a function when it technically isn't. 3. disasm shows symbols that are skipped (due to having size 0) in parenthesis, separated from preceding and following instructions.
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 10:48:29 +0000