News for hackers. Stuff that matters.
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:

    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.
Re:15-line hash table in C by valleyer on Friday December 12, 2014 @12:31AM (#8738707)
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.
Re:15-line hash table in C by pwr22 on Friday December 12, 2014 @02:27AM (#8738927)
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 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

It will still fail looking up a non-existent key, which I don't understand

Re:15-line hash table in C by hawski on Friday December 12, 2014 @04:01AM (#8739136)
>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.

Re:15-line hash table in C by pwr22 on Friday December 12, 2014 @04:25AM (#8739203)
Not differing types
Re:15-line hash table in C by camgunz on Friday December 12, 2014 @01:27PM (#8741818)
If you really want to, I think you might be able to declare a struct in there. A curse on your house though....
Re:15-line hash table in C by pwr22 on Friday December 12, 2014 @05:36PM (#8743135)
In the end I wanted the variable to persist beyond the end of the loop anyway
Re:15-line hash table in C by pwr22 on Friday December 12, 2014 @04:38AM (#8739244)
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 :(
Re:15-line hash table in C by valleyer on Friday December 12, 2014 @12:57AM (#8738774)
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.

[1] http://codepad.org/

Re:15-line hash table in C by vog on Friday December 12, 2014 @06:21AM (#8739487)
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)
Re:15-line hash table in C by balakc on Friday December 12, 2014 @09:44AM (#8740216)
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.
Re:15-line hash table in C by jfoutz on Friday December 12, 2014 @10:26AM (#8740501)
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)
Re:15-line hash table in C by crabhi on Friday December 12, 2014 @12:40PM (#8741501)
h seems to be the hash.

    h = k & (SIZE - 1)
Re:15-line hash table in C by pjmlp on Friday December 12, 2014 @05:28AM (#8739379)
> 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.