| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
I expect people to generally want static libs, but if a shared build
is done, it's not really useful without installing.
|
|
This will let them get used as a meson subproject.
|
|
This follows the same pattern as in the hash_table.
(taken from Mesa commit 03e37ec6d720bb5d416e98d6f6d9663086939e4d and
extended to the other loop as well, by anholt)
|
|
This was in the Mesa implementation but not upstream.
|
|
|
|
|
|
|
|
|
|
Previously, the hash_table_insert or set_add functions would bail
early if it found a deleted slot that it could re-use. However, this
is a problem if the key being inserted is already in the hash table
but further down the list. If this happens, the element ends up
getting inserted in the hash table twice. This commit makes it so
that we walk over all of the possible entries for the given key and
then, if we don't find the key, place it in the available free entry
we found.
v2: Fold in Connor Abbot's fix to not check keys in deleted entries.
v3: Propagate this change to int-set, too (change by anholt).
Reviewed-by: Eric Anholt <eric@anholt.net>
|
|
Caught while writing tests for the next bugfix.
|
|
This tree doesn't have the bug, but I'd like to bring the change that
was buggy over.
|
|
|
|
This fixes warnings when building the testsuite, due to char * vs void
* in prototypes.
|
|
Mesa was using this for hashing various key structures.
|
|
FNV-1 has the XOR and the MUL in the opposite order.
|
|
The interface was already using "set" for the primary identifier, but
the implementation still had "ht" as the identifier and various uses
of "hash table" or "table" in the documentation comments where "set"
makes more sense.
v2: Rebase on change in previous commit's v2 (by anholt)
|
|
Here, we change 'create' to accept the hash function.
This simplifies the interface for 'insert', 'search', 'contains', and
'remove' which no longer need to pass a hash value, making them more
convenient to use.
To avoid any reduction in performance, the previous interfaces for
'insert' and 'search' are still available as 'insert_pre_hashed' and
'search_pre_hashed'. This avoids redundant hashing in cases where the
caller already has a hash value. (The common case is to has once
before 'search_pre_hashed' and then reuse that value for
'insert_pre_hashed'.)
The implementation takes advantage of the 'insert_pre_hashed' version
when performing hash_rehash as part of resizing the table.
Note that 'remove' does not need a pre_hashed variant since 'remove'
is already a convenience function on top of 'remove_entry', and
'remove_entry' already has access to the hash value inside of the
entry.
Similarly, 'contains' does not need a pre_hashed variant since it is a
convnience function on top of 'search' which already has a
'search_pre_hashed' variant.
In this commit, the tests are modified such that roughly half of the
previous callers of 'search' and 'insert' are changed to the new
interface and the other half remain with the old interface (now named
'search_pre_hashed' and 'insert_pre_hashed').
v2: Make the new method call style consistent with the key equality
method (change by anholt).
|
|
|
|
These are convenience functions on top of set_search and
int_set_search. With a set, containment is often the most important
notion of interest, and it helps to be able to query this without
needing to declare a local struct set_entry*.
v2: Whitespace consistency (changes by anholt)
|
|
The new 'remove' function provides a parallel interface to that of
search, (removing an entry matching the provided data). The former
remove function (which accepts a pointer to a known entry) is renamed
to 'remove_entry'.
This new 'remove' is a simple convenience function which calls
'search' and then 'remove_entry'. As can be seen in the updates to the
test suite, there are cases where the caller was already doing exactly
that, so the new interface simplifies such uses.
v2: Whitespace consistency change (by anholt)
|
|
Much like the motivation for the original set.c, this int-set.c code
is not difficult, but it makes sense to do this up-front in the
original hash_table module (with testing) rather than expecting users
to repeat this work.
|
|
As is standard practice.
|
|
This extends the language from the source files into the Makefiles as well.
The most significant change is from "ADAM JACKSON" to "THE AUTHORS OR
COPYRIGHT HOLDERS". While I'm sure that Adam would appreciate any
reduction in liability, the intent of this language is to disclaim
liability for the actual authors and copyright holders.
(I don't know that Adam actually has any copyright interest in this
implementation, but if he does, he's still covered by the wider
language.)
|
|
Just enough to keep "git status" clean after running "make check".
|
|
It's so much easier to find function names in the header file when
they are in column 0 where they belong.
|
|
|
|
|
|
Based on a comment by Chad Versace.
|
|
Noted by Brian Paul in review for Mesa.
|
|
I think I may have made them public thinking of reaching over for them
in testcases for poking at deleted key behavior, but this makes more
sense. Noted by Chad Versace.
|
|
|
|
|
|
I kept rewriting this in an user of this code.
|
|
While it was easy to produce, it's easier to do it once and maintain it than
leave this up to every possible user. Plus, it means it gets testing.
|
|
|
|
|
|
Because of the double_hash == 0 check, the step size of 1 would have
twice the frequency of any other. With the table size being prime
numbers, any integer is co-prime with the table size, so any nonzero
step number will end up hitting every element of the hash table.
Based on a patch by Andrea Canciani to the X Server.
|
|
|
|
|
|
Reported by: Chris Wilson
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This avoids re-hashing the key for the common use case of searching for the
key's presence, then creating the entry if it isn't.
|
|
|
|
|
|
|
