alt Hacker NewsI recently coded a linear-probing hash map in C and I highly recommend you to use fuzz tests. These evolve naturally from unit tests: next step table unit tests, next step property test, next step fuzzing, all steps are incremental, hence easy.
Having a fuzz test was in-va-lu-ab-le. I caught several bugs right there. The delete function was particularly tricky.
I ended up with two fuzz tests as my hash table has a key feature: convergence. Having same contents, it would have exactly same bits in the buffer. In other words, it is independent of the insertion/deletion order. For this, I added another fuzz test. I would add a third one if I realize there is an important invariant I did not fuzz test. That is not much work, but so much useful!
https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASH....
https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASHd...
P.S. In your case, I recommend clang's libfuzzer with ASAN.
Replies
fuzz testing vs HN-popular-post testing, go!
Here's another example of unit tests for hash tables (and RB-trees and skiplists and…)
https://github.com/FRRouting/frr/blob/master/tests/lib/test_...
(this file is #include'd from another, with some #define set up:)
https://github.com/FRRouting/frr/blob/master/tests/lib/test_...
The "tribe" of C developers with distaste for the preprocessor will absolutely hate how this is written. But it works and caught real issues. It doesn't use an external fuzzing tool but rather a deterministic PRNG (see prng_* calls) to get a good mix of call combinations. Coverage analysis was done to make sure it reaches everywhere.
(disclaimer: I wrote this. And it did catch bugs. Also it really should have a lot of comments.)