5 ms·
There's no bounds testing in hget(): some valid sequences of operations will cause buffer overflows. For example, this should segfault: int (**table)[2] =
by throwaway_yy2Di 12y ago
There's no bounds testing in hget(): some valid sequences of operations will cause buffer overflows. For example, this should segfault:
int (**table)[2] = hnew();
for (int j=0; j<40; ++j) {
hset(table, (10 + j*SIZE), 0);
}
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.
- valleyer 12y agoYeah... it’s easy to write small code that doesn’t work.
- userbinator 12y agoIt's not hard to fix, however - one extra modulus, as far as I can see.
- valleyer 12y agoAnd an extra local variable. Which might take up a line of source code!
- ExpiredLink 12y agoWith two additional casts you can make it compile[1] as C++ - without the incredibly wasteful extra local variable. [1] http://codepad.org/ http://codepad.org/
- vog 12y agoYour link to "http://codepad.org/" http://codepad.org/" doesn't show any code. Did you forget some arguments in the URL?
- ExpiredLink 12y agohttp://codepad.org/LuQpUhmj http://codepad.org/LuQpUhmj
- pwr22 12y agoTechnically 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 offset You 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 fills https://gist.github.com/pwr22/a08597e475d1aa44cd96 https://gist.github.com/pwr22/a08597e475d1aa44cd96 It will still fail looking up a non-existent key, which I don't understand
- hawski 12y ago>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.
- pwr22 12y agoSorry, non-existent keys return a slot but since it isn't allocated it blew up when I was trying to print out its values :(
- pjmlp 12y ago> There's no bounds testing in hget(): some valid sequences of operations will cause buffer overflows. It wouldn't be C if that wasn't the case.
- balakc 12y agoEvery 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.
- jfoutz 12y agoInstead 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)
- crabhi 12y agoh seems to be the hash. h = k & (SIZE - 1)