htable: handle v. unlikely case where entries look deleted/empty. If the hash function doesn't set any bits we use, and the common bits are all zero the slot will look empty (or, just the lower bit is set: the slow looks deleted). However, each bucket is distinct since there are no duplicates, so at worse there can be two "looks invalid but actually is valid" buckets. Keep them at the end. Lookup suffers in raw tools/speed though: -Lookup after half-change (match): 53-61(54.8+/-2.3) ns +Lookup after half-change (match): 61-113(83.3+/-17) ns -Lookup after churn & spread (match): 54-90(59.9+/-11) ns +Lookup after churn & spread (match): 70-108(85.2+/-14) ns Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: htable_pick helper to select a random entry. Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: add htable_count(). Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: reduce size of htable by storing perfect bitnum, not mask. Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: reduce size of htable by calculating max every time. Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Mark unused arguments in many modules. Either with UNNEEDED (if the module already used ccan/compiler) or with (void) casting. The only other change is in ccan/list/test/run-CCAN_LIST_DEBUG.c, because the linenumbers change and thus it needs updating. Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Remove unused main() args in many modules. This makes us closer to compiling cleanly with -Wunused (as used by -Wextra). Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: add a htable_prev method to oppose _next Useful for unwinding actions taken while iterating over a htable. Signed-off-by: Cody P Schafer <dev@codyps.com>
htable: add pre-sized option. I thought this was slowing down my program; it turned out they were all hashing to the same value. But it might be useful. Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
htable: fix bug where first entry has hash of 0 or 1. Thanks to Zoltán Lajos Kis for the bug report and test case!
htable: clean up interface, document htable_type better. We change from htable_new()/htable_free() to htable_init/htable_clear. We also change HTABLE_DEFINE_TYPE() to be the full name, without automatically prepending htable_.
htable: start empty. There's no real reason to start with 128 entries.
htable: restore perfect bit when resizing. If the lower bit differs between pointers, we can lose our "perfect" bit. Since we're rehashing the entire thing anyway, we can pick another bit when we double the hash table.
htable: first implementation