| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
While it was cargo-culted from many other projects, allowing people to
lose the Makefile regeneration rules is a recipe for disaster. autotools
is apparently discouraging the presence of AM_MAINTAINER_MODE, in a
shocking bout of sanity.
|
|
This is entirely written by myself, with the exception of the
hash_sizes[] contents which come from the hash_table implementation in
nickle, which I decided to not use.
|
