| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
|
|
Double the capacity when used+deleted buckets crosses 60% of capacity.
This appears to be a sweet spot for performance based on some ad-hoc
testing with test-js. :^)
|
|
Instead of each hash bucket being a SinglyLinkedList, switch to using
closed hashing (open addressing). Buckets are chained together via
double hashing (hashing the hash until we find an unused bucket.)
This greatly reduces malloc traffic, since each added element no longer
allocates a new linked list node.
Appears performance neutral on test-js. Can definitely be tuned and
could use proper management of load factor, etc.
|
|
in CppLexer. (#3147)
1. Add general utility to get array number of elements.
2. Add Needed API to AK::HashTable
3. Refactor CppLexer initialization
|
|
This allows performing an action based on whether something
was actually added or removed without having to look it up
prior to calling set() or remove().
|
|
This commit replaces SinglyLinkedListIterator::universal_end() with an
empty SinglyLinkedListIterator(). Piano needs this in order to
initialize a member array of iterators without 84 lines of
universal_end().
|
|
|
|
|
|
This was only used by HashTable::dump() which I used when doing the
first HashTable implementation. Removing this allows us to also remove
most includes of <AK/kstdio.h>.
|
|
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.
|
|
|
|
This is just for consistency, and we might want to switch to another
bucket type some day.
|
|
It doesn't seem sane to try to iterate over a HashTable while it's in
the middle of being cleared. Since this might cause strange problems,
this patch adds an assertion if an iterator is constructed during
clear() or rehash() of a HashTable.
|
|
Solve this by adding find() overloads to HashTable and SinglyLinkedList
that take a templated functor for comparing the values.
This allows HashMap to call HashTable::find() without having to create
a temporary Entry for use as the table key. :^)
|
|
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.
|
|
|
|
We were using a DoublyLinkedList<T> simply because it supported remove().
This patch consolidates the SinglyLinkedList iterators and adds remove().
|
|
Get rid of the ConstIterator classes for these containers and use templated
FooIterator<T, ...> and FooIterator<const T, ...> helpers.
This makes the HashTable class a lot easier to read.
|
|
Previously it was only possible to move them, but we should allow copying
as well, since it's gonna be useful for many things.
|
|
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.
|
|
These functions make sure that the underlying table can accomodate at least
'capacity' entries before needing a rehash.
|
|
|
|
|
|
A GIcon can contain any number of bitmaps internally, and will give you
the best fitting icon when you call bitmap_for_size().
|
|
|
|
We forgot to clear the m_buckets pointer. This meant that multiple calls to
clear() would cause trouble.
|
|
|
|
|
|
|
|
Also teach /bin/id to print the user's supplemental groups.
|
|
Refactored SyntheticFileSystem to maintain an arbitrary directory structure.
ProcFileSystem creates a directory entry in /proc for each new process.
|
|
This would be a lot better as an LRU. Right now it's a 32-slot
hash table with random eviction.
|
|
|
|
|
|
|
|
|
|
|
