Steal one bit to indicate an entry is in its perfect position.  This
means we don't have to rehash it when we are rehashing the entire
table to get rid of deleted records, and we can still use it for
comparison during lookup.

Before: $ ./speed 50000000
Initial insert:  462 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  161 ns
Initial lookup (miss):  168 ns
Initial lookup (random):  326 ns
Initial delete all:  164 ns
Details: rehashes 50000000
Initial re-inserting:  167 ns
Deleting first half:  86 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  217 ns
Details: delete markers 0, perfect 81%
Lookup after half-change (match):  169 ns
Lookup after half-change (miss):  180 ns
Details: initial churn
Churning second time:  593 ns
Churning third time:  611 ns
Churning fourth time:  619 ns
Churning fifth time:  622 ns
Details: reinserting with spread
Details: delete markers 13800468, perfect 73%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  192 ns
Lookup after churn & spread (miss):  211 ns
Lookup after churn & spread (random):  373 ns
Deleting half after churn & spread:  103 ns
Adding (a different) half after churn & spread:  102 ns
Details: delete markers 29539689, perfect 72%

After:
Initial insert:  467 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  163 ns
Initial lookup (miss):  171 ns
Initial lookup (random):  326 ns
Initial delete all:  170 ns
Details: rehashes 50000000
Initial re-inserting:  169 ns
Deleting first half:  88 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  141 ns
Details: delete markers 0, perfect 81%
Lookup after half-change (match):  166 ns
Lookup after half-change (miss):  171 ns
Details: initial churn
Churning second time:  441 ns
Churning third time:  469 ns
Churning fourth time:  466 ns
Churning fifth time:  490 ns
Details: reinserting with spread
Details: delete markers 13800468, perfect 73%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  197 ns
Lookup after churn & spread (miss):  209 ns
Lookup after churn & spread (random):  369 ns
Deleting half after churn & spread:  98 ns
Adding (a different) half after churn & spread:  100 ns
Details: delete markers 29539689, perfect 72%

Delete markers build up over time, even if we try to clean as we go.
So just garbage collect them when there are too many.

Before:
rusty@vivaldi:~/devel/cvs/ccan/ccan/htable/tools (htable)$ ./speed 50000000
Initial insert:  467 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  160 ns
Initial lookup (miss):  169 ns
Initial lookup (random):  328 ns
Initial delete all:  165 ns
Details: rehashes 50000000
Initial re-inserting:  317 ns
Deleting first half:  86 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  89 ns
Details: delete markers 18894324, perfect 76%
Lookup after half-change (match):  174 ns
Lookup after half-change (miss):  203 ns
Details: initial churn
Churning second time:  816 ns
Churning third time:  615 ns
Churning fourth time:  621 ns
Churning fifth time:  846 ns
Details: reinserting with spread
Details: delete markers 11078719, perfect 74%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  191 ns
Lookup after churn & spread (miss):  208 ns
Lookup after churn & spread (random):  374 ns
Deleting half after churn & spread:  102 ns
Adding (a different) half after churn & spread:  103 ns
Details: delete markers 27442234, perfect 73%

After:
Initial insert:  462 ns
Details: hash size 134217728, mask bits 5, perfect 81%
Initial lookup (match):  161 ns
Initial lookup (miss):  168 ns
Initial lookup (random):  326 ns
Initial delete all:  164 ns
Details: rehashes 50000000
Initial re-inserting:  167 ns
Deleting first half:  86 ns
Details: rehashes 25000000, delete markers 25000000
Adding (a different) half:  217 ns
Details: delete markers 0, perfect 81%
Lookup after half-change (match):  169 ns
Lookup after half-change (miss):  180 ns
Details: initial churn
Churning second time:  593 ns
Churning third time:  611 ns
Churning fourth time:  619 ns
Churning fifth time:  622 ns
Details: reinserting with spread
Details: delete markers 13800468, perfect 73%
Details: worst run 48 (4 deleted)
Lookup after churn & spread (match):  192 ns
Lookup after churn & spread (miss):  211 ns
Lookup after churn & spread (random):  373 ns
Deleting half after churn & spread:  103 ns
Adding (a different) half after churn & spread:  102 ns
Details: delete markers 29539689, perfect 72%

Judy.h uses "Word_t" which it defines to an "unsigned long", so just use that.

If I were writing Judy from scratch, I'd use size_t or uintptr_t.

Judy.h uses "Word_t" which it defines to an "unsigned long", so just use that.

If I were writing Judy from scratch, I'd use size_t or uintptr_t.

Broken in 5378c864: we were trying to
recompile the previous failed version.  And the message we printed out
was unclear.

For str_talloc and grab_file, avoid using ccan/str (it's just for tests).

Much easier to run just a single test across the tree.

I moved the code around and missed this.

Comments of form "// [given x] outputs y" we can check the examples do as expected.

No longer abort ccanlint because a test fails, but you will get a low
score if there are no tests.

(Note: total_score is filled in, even if it's overridden when the test is
 run.  This means that if the prereq fails, that total counts so there is
 still a penalty!)

The heuristics can be hinky, so tell people what we're doing.

A simple C program to generate config.h.  It also saves the compiler and
flags for use by ccanlint (though they have to accept -c and -o).

Warnings about ignored returns, and uninitialized len after case statement.

unsigned char * is allowed to alias, so we use that for byte reversing
rather than uint32_t.  This is portable.

Remove warnings about ignoring pread/pwrite return values.

And initialize tdb before setjmp: with optimization, gcc validly saw this
as NULL and crashed.

A void * could point to anything, but a void ** can't point to any pointer.
So we use a void * and memcpy, which I believe is safe.

Compiling with gcc -O3 added some more warnings, especially about aliasing.

By setting Word_t to size_t we fix some of them, but jmap_@name_firstval
in JMAP_DEFINE_PTRIDX_TYPE we need to use a real size_t rather than lazily
casting our index to a size_t *.

Gcc also spotted taht we used idx[NUM] in test/run-ptridx-type.c; allocate
that and make the usage explicit.

I noticed this when I straced something; we're doing 1-byte writes.
This reduced the time for "make check" from 12m37s to 11m48s.

If you've not got gcc, this is a bit of a lose.  But for everyone else,
it's far simpler.

Doing our own parsing lost a few lines of code, too.

Our coverage is over 99% now.