Re:15-line hash table in C
by throwaway_yy2Di on Thursday December 11, 2014 @10:48PM
(#8738482)
There's no bounds testing in hget(): some valid sequences of operations will cause buffer overflows. For example, this should segfault:
The problem is, the probing function doesn't wrap (the "t += h" part), so if you have have several colliding keys, it will probe for them past the end of the table.
[ Parent
| on HN ]
Yeah... it’s easy to write small code that doesn’t work.
Re:15-line hash table in C
by userbinator on Friday December 12, 2014 @12:52AM
(#8738762)
It's not hard to fix, however - one extra modulus, as far as I can see.
Technically there is bounds checking
... & (SIZE - 1)
but it looks broken because t does the C-ish mutating accumulator thing rather than acting as a base and using h as an offsetYou need a temporary variable of
int (**)[2]
to avoid doing two additions per iter, though maybe the compiler can pick that up and do it for you. Anyway, this no longer crashes but it now runs forever if the hash fillshttps://gist.github.com/pwr22/a08597e475d1aa44cd96
It will still fail looking up a non-existent key, which I don't understand
>Due to C there is no way to declare both an int and that in the loop preamble so you'd need at least one more line
In C99 it's allowed to declare in the loop preamble. True for ANSI-C.
Not differing types
If you really want to, I think you might be able to declare a struct in there. A curse on your house though....
In the end I wanted the variable to persist beyond the end of the loop anyway
Sorry, non-existent keys return a slot but since it isn't allocated it blew up when I was trying to print out its values :(
And an extra local variable. Which might take up a line of source code!
Re:15-line hash table in C
by ExpiredLink on Friday December 12, 2014 @04:56AM
(#8739294)
With two additional casts you can make it compile[1] as C++ - without the incredibly wasteful extra local variable.
Your link to "http://codepad.org/" doesn't show any code. Did you forget some arguments in the URL?
Re:15-line hash table in C
by ExpiredLink on Friday December 12, 2014 @11:24AM
(#8740913)
Every time a lookup is performed, isn't it linearly looking through the table to find that key... That doesn't sound like a hash! Maybe am missing something here.
Instead of a linked list to store hash collisions, it's using linear probing, which just uses the next open spot in the table. (Maybe I'm misunderstanding the question, it looks like they're indexing into the table correctly to me)
h seems to be the hash.
h = k & (SIZE - 1)