3 ms·

every time I write C code, I don't want to remember how to implement unordered map

kragen 2y ago
You mean enum { nb = 1024 }; struct { int k, v; } hash[nb]; // 0 is an invalid key void incr(int k) { int i = k % nb, j = i; do { int k2 = hash[i].k; if (k2 && k2 != k) { i = (i+1) % nb; continue; } hash[i].k = k; hash[i].v++; return; } while (i != j); abort(); } Apologies for the telegraphic variable names and weird control flow. I wrote this on my cellphone. Lacking these 15 lines are what keep you from writing C? There's a nice tutorial on hash tables in K&R, and I can also recommend learning about Chris Wellons's "MSI" hash table design, described in C at https://nullprogram.com/blog/2022/08/08/ https://nullprogram.com/blog/2022/08/08/. He shows a more full featured hash table in about 30 lines of code, depending on what functionality you need. It's eminently practical, and usually a lot faster than generic algorithms. That's not an exceptionally simple hash table either. One night I hurriedly wrote a rather long-winded implementation also on my cellphone (strings, with separate chaining and a djb-style hash function) and it also came to about 30 lines of code: http://canonical.org/~kragen/sw/dev3/justhash.c http://canonical.org/~kragen/sw/dev3/justhash.c
- kragen 2y ago
  In the interest of correctness, I just wrote a quick test of the above code at http://canonical.org/~kragen/sw/dev3/intcount.c http://canonical.org/~kragen/sw/dev3/intcount.c. Perhaps surprisingly, it works, including the error handling, which is not always the case when you write a bunch of untested C after midnight on your cellphone. But a hash table is evidently simple enough.
  - kragen 2y ago
    Except, you know what? It fails (corrupting memory!) for negative keys k.
uecker 2y ago
You can't use anyone else code and always delete your own previous implementation?

You mean enum { nb = 1024 }; struct { int k, v; } hash[nb]; // 0 is an invalid key void incr(int k) { int i = k % nb, j = i; do { int k2 = hash[i].k; if (k2 && k2 != k) { i = (i+1) % nb; continue; } hash[i].k = k; hash[i].v++; return; } while (i != j); abort(); } Apologies for the telegraphic variable names and weird control flow. I wrote this on my cellphone. Lacking these 15 lines are what keep you from writing C? There's a nice tutorial on hash tables in K&R, and I can also recommend learning about Chris Wellons's "MSI" hash table design, described in C at https://nullprogram.com/blog/2022/08/08/ https://nullprogram.com/blog/2022/08/08/. He shows a more full featured hash table in about 30 lines of code, depending on what functionality you need. It's eminently practical, and usually a lot faster than generic algorithms. That's not an exceptionally simple hash table either. One night I hurriedly wrote a rather long-winded implementation also on my cellphone (strings, with separate chaining and a djb-style hash function) and it also came to about 30 lines of code: http://canonical.org/~kragen/sw/dev3/justhash.c http://canonical.org/~kragen/sw/dev3/justhash.c

kragen 2y ago
In the interest of correctness, I just wrote a quick test of the above code at http://canonical.org/~kragen/sw/dev3/intcount.c http://canonical.org/~kragen/sw/dev3/intcount.c. Perhaps surprisingly, it works, including the error handling, which is not always the case when you write a bunch of untested C after midnight on your cellphone. But a hash table is evidently simple enough.
- kragen 2y ago
  Except, you know what? It fails (corrupting memory!) for negative keys k.

uecker 2y ago

You can't use anyone else code and always delete your own previous implementation?