Michael Ellerman noted that ccan/opt has no symlink, so add ccanlint test.

I am told that CentOS 5.3 doesn't like isblank (it's ISO C).

Delio Brignoli points out that check_type fails when HAVE_TYPEOF is 0,
so turn that off here and see what else breaks...

"C has fairly weak typing:" from check_type/_info is not a new section heading!
Enforce that each word in multi-word sections must be caps.

We used to prefer to build up examples using previous ones, but this broke
for tests which were to be executed.  But list.h relied on the buildup
behavior, so return to that unless we see "// Given" comments indicating
an execution test.

gcc with optimization complained (correctly) about this.

(nfs gives warnings on build, make ccanlint unhappy).

The long names were unwieldy in practice; at risk of clashing, replace
with shorter versions.

ccanlint won't run rpcgen, so we need the C source in the repo anyway.

rename libnfs.h to nfs.h (CCAN expects "main" header to match module name).
tools move into tools/, .x file move into rpc/
Don't sed the rpcgen files, generate headers in rpc/
Make tools use <ccan/nfs/nfs.h> as per normal ccan usage.

Another Ronnie module!

Previously each check returned a void *, but in fact most of them fell into
similar patterns.  So define 'struct score' and a helper to add files to it,
and use that.

Under these rules, you get 0/1 if you skip a test because a dependency failed
which in theory means your score (as a percentage) could drop if you fix
a test.

Make test directory correctly, and #include <ccan/...> not #include "".

I'm not a fan of the SHOUTING, but it's upstream.

With the extra bits, long runs don't hurt our cache very much on search,
so we can pack quite a few in.  Here are the runs at maximal density before
and after:

Before:
$ ./speed 3145000
Initial insert:  248 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  142 ns
Initial lookup (random):  170 ns
Initial delete all:  134 ns
Details: rehashes 3145000
Initial re-inserting:  149 ns
Deleting first half:  73 ns
Details: rehashes 1572500, delete markers 1572500
Adding (a different) half:  128 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  129 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  703 ns
Churning third time:  725 ns
Churning fourth time:  717 ns
Churning fifth time:  710 ns
Details: reinserting with spread
Details: delete markers 149261, perfect 57%
Details: worst run 254 (2 deleted)
Lookup after churn & spread (match):  132 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  184 ns
Deleting half after churn & spread:  71 ns
Adding (a different) half after churn & spread:  129 ns
Details: delete markers 0, perfect 62%

After:
$ ./speed 3145727
Initial insert:  232 ns
Details: hash size 4194304, mask bits 9, perfect 63%
Initial lookup (match):  122 ns
Initial lookup (miss):  141 ns
Initial lookup (random):  234 ns
Initial delete all:  129 ns
Details: rehashes 3145727
Initial re-inserting:  153 ns
Deleting first half:  80 ns
Details: rehashes 1572864, delete markers 1572864
Adding (a different) half:  137 ns
Details: delete markers 0, perfect 62%
Lookup after half-change (match):  125 ns
Lookup after half-change (miss):  145 ns
Details: initial churn
Churning second time:  702 ns
Churning third time:  719 ns
Churning fourth time:  712 ns
Churning fifth time:  709 ns
Details: reinserting with spread
Details: delete markers 169474, perfect 56%
Details: worst run 248 (12 deleted)
Lookup after churn & spread (match):  129 ns
Lookup after churn & spread (miss):  159 ns
Lookup after churn & spread (random):  242 ns
Deleting half after churn & spread:  70 ns
Adding (a different) half after churn & spread:  133 ns
Details: delete markers 0, perfect 62%

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.

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.