htable: use "perfect" bit to reduce rehashes.

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%

htable: rehash to clear delete markers

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%

htable: speed benchmark

htable: first implementation

jmap: a speed benchmark

jmap: fix incorrect prototype in header documentation.

jmap: just use unsigned long, not size_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.

jbitset: just use unsigned long, not size_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.

ccanlint: fix compilation of chained examples.

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

antithread, foreach, grab_file, hashtable, str_talloc: fix _info depends.

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

ccanlint: add --target

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

ccanlint: add test to look for modules we use but don't list in _info.

ccanlint: fix wrong initialization in example compilation.

I moved the code around and missed this.

Makefile: make non-optimized variant comment a bit clearer.

alignof, array_size, crc: provide comments to allow testing examples.

ccanlint: try running example code.

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

opt: fix junk after string in opt_show_charp.

cleanup: get rid of unwanted tap/ toplevel which crept in.

web: point to the configurator to generate config.h

.gitignore: ignore configurator

makefiles: add "scores" target.

alloc: fix missing header in compilation of example.

ccanlint: make tests non-compulsory, always print score.

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!)

ccanlint: with -vv, give details on attempts to compile examples.

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

tools: new "configurator" tool.

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).

tdb2: fix gcc -O3 warnings on test/layout.c

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

tdb: fix warnings with gcc -O3, and one test crash.

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.

talloc: fix gcc -O3 aliasing warnings

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.

opt: fix gcc -O3 warnings.

jmap: fix aliasing issues, one real testcase bug

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.

foreach: new module

Merge branch 'judy'

jmap: new module

jbitset: new module.

web: don't try to link to old bzr repository, use git.

tap: restore buffering to stdout

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

gitify the tree, especially the web makefile.

web: clean up directory

ilog: rework to reduce interface.

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

opt: wean off getopt_long, beef up tests.

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

Our coverage is over 99% now.

tdb2: extend test/layout to be able to place in file.

This was for lockcheck, but that didn't work very well.  Seems like a useful
addition nonetheless.

tdb2: fix intermittent test fail.

With correct seed, we could expand hash and break test.

opt: change / separator to |

Paul Wayper points out that "or" has a better mental mapping, and more
importantly that this is how Perl's Getopt::Long does it.

I'm still leaving the - and -- in there, for reasons previously articulated
(grep-friendly and harder to get wrong).

avl: I attached a patch changing the AVL module to the MIT license.

license: more changing of licence -> license.

webpages: make sure target of licence links is included in tarballs.

avl: new module

tdb2: 64 bit fixes.

typesafe_cb: 64 bit fixes.

In particular, gcc warns about cast from int to pointer.

tdb: 64-bit fixes.

tally: fixes for 64 bit machines.

read_write_all: don't rely on write to pipe blocking in tests.

Instead, directly control write().

opt: 64-bit compile fixes

%.* => unsigned, not size_t.

ccan_tokenizer: 64-bit compile fixes.

%zu for size_t printf.

alloc: fix 64-bit

Make sure we use 1UL to bitshift, not 1.

tools: fixes for 64-bit.

printf's %.* means an unsigned arg, not a size_t.

tdb2: fix infinite loop in tdb_check

check_free_list returns a length, not bool.

tdb2: add tdb_attribute_seed for setting hash seed.

Particularly useful for reproduction, like tdbtorture.

licence->license: US English is the standard for code.

If a Swedish-speaking Finn writes code in English, why should I complain about
a few weird spellings?

tdb2: clarify locking heirarchy; hashes, freelist, then expand lock.

tdb2: fix run-summary test

(Was succeeding in finding "Free bucket 8" string, because of "Free bucket 80:".

opt: list ccan/typesafe_cb as a dependency.

ccanlint: use opt package.

Now we get long options!

opt: add opt_log_stderr_exit helper, and opt_usage NULL option.

The former encapsulates a common "just exit on error" case, the latter
avoids having to repeat the extra usage string.

(We actually would have crashed before if someone passed NULL there, even
 though the documentation said you could).

opt: fix example to compile.

opt: remove gratuitous { } in initializers.

A little less typing for users.

compiler, list, noerr, sparse_bsearch, str, str_talloc, stringmap, talloc_link, tdb, tdb2, typesafe_cb: fix examples

Phew, now they call compile!

ccanlint: yet more modifications to example extraction and compile.

Now (with fixes) every ccanlint example compiles!

ccanlint: rename files on collision even with keep=true.

tools: fix bug in doc-extract, handle spaces in summary line

      /**
       * struct foo - some description

So, <identifier> here can have a space in it.

compiler, talloc: warn if return from realloc-like functions isn't used.

This hit my doc extraction tool, so fix it!

tdb: fixed unitialized vars.

tdb2: fix uninitialized var.

modules: update documentation examples so they compile under ccanlint.

This is everything up to the list module... now it's time for sleep.

ccanlint: yet more heuristics for compiling examples.

Including intuiting ccan depends based on headers...

array: fix example compile.

hash: fix examples so they compile.

talloc: fix examples so they compile.

opt: fix examples so they compile.

alloc: fix examples so they compile.

tap: make examples compilable by ccanlint.

In particular, we can assume "somefunc()" exists in our examples.

ccanlint: more heuristics for compiling examples.

Try to glue consecutive examples together if all else fails (works well for
ccan/alloc/alloc.h).  This means we should put examples into list in order.

tools: "See Also:" can be a section in documentation, so allow it.

ccanlint: more heuristics for compiling examples.

These are from hash: the entire example is indented, there is no main(), and
there are unused static functions.

ccanlint: really fix failing test logic.

Some of the compulsory tests don't have a total_score; treat that as "1".
And don't print out a score if the total is <= 1.

ccanlint: link api tests against compiled objects

Don't assume that ../modulename.o already built!

ccanlint: add somefunc() to help examples compile.

And don't require the module.o to already exist: link against generated .o files.

ccanlint: actually try to compile examples.

Includes primitive attempt to place fragments into appropriate framework to
compile them.

ccanlint: load file contents on demand, fix names for extracted examples.

We had example names like "example-opt.h-opt_parse", which got trimmed to
"example-opt".  By using a basename of example-opt.h-opt_parse.c, we only
strip the final ".c" not the middle ".h".

ccanlint: make sure we stop on failure of compulsory test.

ccanlint: fix -k has_examples

opt: fix warnings with gcc and -O.

opt: minor API tweaks.

Don't allow NULL descs, and put them in macro.  Users can use "", but make
sure it's explicit, not an accidental omission.
Use errx() instead of assert() for API usage errors.
Rename opt_flags to opt_type.

opt: allow parameter names in arguments.

opt: remove unused debug function and code, test a few more corner cases.

opt: clarify option iteration a little.

I still don't like the duplication, but it's clearer and not much longer.

opt: fix reporting of arguments when multiple arguments exist.

longidx is not updated in this case.  We should open-code option parsing.

opt: Put actual options inside names.

This is more explicit than separate short and long (great for grep!) and
simpler.

opt: add support for showing default value.

opt: new module to parse commandline options.