summaryrefslogtreecommitdiff
path: root/AK/Vector.h
AgeCommit message (Collapse)Author
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.
2020-07-26AK: Implement Span which represents a contiguous sequence of objects.asynts
This makes it possible to pass one object rather than pointer and length individually.
2020-07-05AK: Make Vector::unstable_remove() return the removed valueSergey Bugaev
...and rename it to unstable_take(), to align with other take...() methods.
2020-06-23AK: Inline the basics of VectorIteratorAndreas Kling
Inlining these allows the compiler to optimize out the assertions in favor of a static range check in many cases.
2020-05-20Revert "AK: Add InitializerList, an implementation of std::initializer_list"Andreas Kling
This reverts commit 0a2cab09282edf357647d2f6e61f9b0680492dca.
2020-05-20AK: Add InitializerList, an implementation of std::initializer_listAndrew Kaster
Use the AK version of std::initializer_list in AK::Vector, but only when in serenity. When building AK for a non-serenity target, the header <initializer_list> should be always available.
2020-05-12AK: Fix gcc 10.1 compiler warnings in Vector.hLinus Groh
It's complaining about "size_t >= 0" checks. Fixes #2196.
2020-05-03AK: Add Vector::resize_and_keep_capacity()Andreas Kling
This function is just like resize() except it does not deallocate the vector buffer when shrinking.
2020-05-02AK: Inline busy functions in VectorAnotherTest
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-02-25AK: Make Vector use size_t for its size and capacityAndreas Kling
2020-02-14AK: Add a forward declaration headerAndreas Kling
You can now #include <AK/Forward.h> to get most of the AK types as forward declarations. Header dependency explosion is one of the main contributors to compile times at the moment, so this is a step towards smaller include graphs.
2020-01-25AK: Vector::is_null() should always return falseAndreas Kling
This is only used by the somewhat dubious templated String::copy(). An empty Vector should generate an empty String when copied, never a null String.
2020-01-19Kernel: Optimize VM range deallocation a bitAndreas Kling
Previously, when deallocating a range of VM, we would sort and merge the range list. This was quite slow for large processes. This patch optimizes VM deallocation in the following ways: - Use binary search instead of linear scan to find the place to insert the deallocated range. - Insert at the right place immediately, removing the need to sort. - Merge the inserted range with any adjacent range(s) in-line instead of doing a separate merge pass into a list copy. - Add Traits<Range> to inform Vector that Range objects are trivial and can be moved using memmove(). I've also added an assertion that deallocated ranges are actually part of the RangeAllocator's initial address range. I've benchmarked this using g++ to compile Kernel/Process.cpp. With these changes, compilation goes from ~41 sec to ~35 sec.
2020-01-19AK: Teach Vector::insert() to use memmove() for trivial typesAndreas Kling
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.
2020-01-15AK: Add Vector::unstable_remove(index)Andreas Kling
This removes an item at an index without preserving the sort order of the Vector. This enables constant-time removal from unsorted Vectors, as it avoids shifting all of the entries following the removed one.
2020-01-04AK: Allow copying a Vector from a Vector with different inline capacityAndreas Kling
2019-12-22AK: Add Vector::remove_all_matching()Andreas Kling
2019-12-19AK: Add Vector::find_first_index(const T&)Hüseyin ASLITÜRK
2019-11-07AK: Add Vector::take(index)Andreas Kling
This removes an item from the vector and returns it.
2019-11-07AK: Add Vector::prepend(T&&)Andreas Kling
2019-08-12Vector: Use memcpy to implement remove() for trivial typesAndreas Kling
This is a lot faster than the generic code path. Also added some unit testing for this.
2019-08-07Vector: Use memcpy when dynamically growing Vectors of trivial typesAndreas Kling
2019-08-07Vector: Use TypedTransfer in more parts of VectorAndreas Kling
Make more Vector-of-trivial-type operations go fast :^)
2019-08-07Vector: Use memcmp for comparing two vectors with trivial elementsAndreas Kling
2019-08-07Vector: Use memmove() for moving trivial types around moreAndreas Kling
This can definitely be improved with better trivial type detection and by using the TypedTransfer template in more places. It's a bit annoying that we can't get <type_traits> in Vector.h since it's included in the toolchain compilation before we have libstdc++.
2019-08-04AK: Add VectorIterator::index()Andreas Kling
A simple helper function that extracts the index of an iterator. Note that the index is not valid if the iterator is end().
2019-08-04Vector: Add find() and some iterator improvementsAndreas Kling
Vector now has find() just like HashTable. I also made the iterator comparison functions const-correct.
2019-08-01AK: Add Vector::empend().Andreas Kling
This is a complement to append() that works by constructing the new element in-place via placement new and forwarded constructor arguments. The STL calls this emplace_back() which looks ugly, so I'm inventing a nice word for it instead. :^)
2019-07-24AK: Delete Vector::resize() from Nonnull{Own,Ref}PtrVector.Andreas Kling
It's not possible to grow one of these vectors beyond what's already in them since it's not possible to default-construct Nonnull{Own,Ref}Ptr. Add Vector::shrink() which can be used when you want to shrink the Vector and delete resize() from the specialized Vectors.
2019-07-21AK: Remove unused Vector::shift_left().Andreas Kling
I was using this for a makeshift queue, but now there is AK::Queue.
2019-07-21AK: Fix off-by-one in Vector::prepend(Vector&&).Andreas Kling
Caught by valgrind's uninitialized access checks on the Vector unit test. Yay for finding bugs with valgrind on the unit tests! :^)
2019-07-20AK: Add Vector::prepend(Vector&&).Andreas Kling
Also included a good boy unit test.
2019-07-11AK: Use operator== for comparison in Vector::contains_slowRobin Burchell
2019-07-11AK: Add operator== & operator!= to VectorRobin Burchell
2019-07-04AK: Add Vector::insert_before_matching(T&&, callback);Andreas Kling
This allows you to do things like: vector.insert_before_matching(value, [](auto& entry) { return value < entry; }); Basically it scans until it finds an element that matches the condition callback and then inserts the new value before the matching element.
2019-07-04Vector: Simplify functions that take both T&& and const T&.Andreas Kling
We can implement foo(const T&) by invoking foo(T&&) with a temporary T.
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-29AK: Defer to Traits<T> for equality comparison in container templates.Andreas Kling
This is prep work for supporting HashMap with NonnullRefPtr<T> as values. It's currently not possible because many HashTable functions require being able to default-construct the value type.
2019-06-28AK: We can't use std::initializer_list in LibC builds.Andreas Kling
The LibC build is a bit complicated, since the toolchain depends on it. During the toolchain bootstrap, after we've built parts of GCC, we have to stop and build Serenity's LibC, so that the rest of GCC can use it. This means that during that specific LibC build, we don't yet have access to things like std::initializer_list. For now we solve this by defining SERENITY_LIBC_BUILD during the LibC build and excluding the Vector/initializer_list support inside LibC.
2019-06-28AK: Add Vector(std::initializer_list<T>) constructor.Andreas Kling
This allows us to construct a Vector from an initializer list like so: Vector<Object> objects = { object1, object2, object3 };
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 01:29:52 +0000