8 years agoptr_valid: test whether a ptr is valid.
Rusty Russell [Mon, 5 Dec 2011 12:16:46 +0000 (22:46 +1030)]
ptr_valid: test whether a ptr is valid.

Very slow, but sometimes you need to know without crashing.

8 years agoconfigurator: HAVE_PROC_SELF_MAPS
Rusty Russell [Mon, 5 Dec 2011 03:46:33 +0000 (14:16 +1030)]
configurator: HAVE_PROC_SELF_MAPS

8 years agoobjset: new module.
Rusty Russell [Sun, 4 Dec 2011 22:50:34 +0000 (09:20 +1030)]
objset: new module.

8 years agoccanlint.1: fix description of per-test options for tests_pass_valgrind.
Rusty Russell [Sun, 4 Dec 2011 22:49:34 +0000 (09:19 +1030)]
ccanlint.1: fix description of per-test options for tests_pass_valgrind.

8 years agodoc: man page for ccanlint.
Rusty Russell [Fri, 2 Dec 2011 03:15:08 +0000 (13:45 +1030)]
doc: man page for ccanlint.

8 years agoccanlint: remove argument to -k/--keep
Rusty Russell [Fri, 2 Dec 2011 03:37:24 +0000 (14:07 +1030)]
ccanlint: remove argument to -k/--keep

It's much easier to simply say "keep all", and it simplifies the code
quite a bit.

8 years agoccanlint: use -t for --target not --timeout
Rusty Russell [Fri, 2 Dec 2011 03:37:23 +0000 (14:07 +1030)]
ccanlint: use -t for --target not --timeout

I use --target far more than --timeout.

8 years agoccanlint: use traversal to trim tests we want to skip.
Rusty Russell [Fri, 2 Dec 2011 03:37:22 +0000 (14:07 +1030)]
ccanlint: use traversal to trim tests we want to skip.

Rather than using a separate index of tetst to skip, make sure tests
we don't want to run are removed from the graph of tests to start

This means that the "skip" field is only set when we fail a test (and
thus must be reset when we test the next module).

8 years agoccanlint: use node traverse for --target.
Rusty Russell [Fri, 2 Dec 2011 03:37:21 +0000 (14:07 +1030)]
ccanlint: use node traverse for --target.

Rather than walking the list of tests manually, use
dgraph_traverse_to() to run the tests.

8 years agoccanlint: use dgraph module.
Rusty Russell [Fri, 2 Dec 2011 03:37:21 +0000 (14:07 +1030)]
ccanlint: use dgraph module.

Instead of a linked list of tests, we use dgraph and strmap.

8 years agoccanlint: remove wart from info options.
Rusty Russell [Fri, 2 Dec 2011 03:37:20 +0000 (14:07 +1030)]
ccanlint: remove wart from info options.

Make info_exists() call add_info_options() directly, rather than detecting
that we've found _info inside the loop of tests.

It means targeting is now a global, which is a bit sucky.

8 years agodgraph: new module for directed graphs.
Rusty Russell [Fri, 2 Dec 2011 03:36:58 +0000 (14:06 +1030)]
dgraph: new module for directed graphs.

8 years agoccanlint: parse --verbose before anything else.
Rusty Russell [Fri, 2 Dec 2011 03:10:27 +0000 (13:40 +1030)]
ccanlint: parse --verbose before anything else.

This way, we can debug really early failures (eg. during option

8 years agoccanlint: get rid of separate class of compulsory tests.
Rusty Russell [Thu, 1 Dec 2011 06:15:51 +0000 (16:45 +1030)]
ccanlint: get rid of separate class of compulsory tests.

It's reduced to a flag which means we stop processing the module.  We have
to enhance our dependencies a bit, but they've always been quite good.

This simplifies things quite a bit.

8 years agoopt: add OPT_EARLY and opt_early_parse.
Rusty Russell [Thu, 1 Dec 2011 06:14:51 +0000 (16:44 +1030)]
opt: add OPT_EARLY and opt_early_parse.

Parsing options like --verbose and --debug can be a pain.  You need to
have everything set up before invoking parse_args(), but that may be a
significant amount of work, for which you may want verbose or
debugging enabled.

Thus the concept of "early" args: you can nominate arguments to be
parse before anything else, using opt_early_parse().

8 years agostrset, strmap: invert iterator function meaning.
Rusty Russell [Thu, 1 Dec 2011 06:13:51 +0000 (16:43 +1030)]
strset, strmap: invert iterator function meaning.

Make a false return abort the iteration, not true.

The old way makes sense for search functions (true == I found it), but
other kinds of iteration are more common (brute force search is
probably dumb).

8 years agosetset: fix API to match strmap and common sense.
Rusty Russell [Thu, 1 Dec 2011 06:12:51 +0000 (16:42 +1030)]
setset: fix API to match strmap and common sense.

strset_set -> strset_add
strset_clear -> strset_del
strset_test -> strset_get
strset_destroy -> strset_clear

8 years agostrmap: allow const arguments to strset_iterate().
Rusty Russell [Thu, 1 Dec 2011 06:11:51 +0000 (16:41 +1030)]
strmap: allow const arguments to strset_iterate().

8 years agostrset: allow const arguments to strset_iterate().
Rusty Russell [Thu, 1 Dec 2011 06:10:51 +0000 (16:40 +1030)]
strset: allow const arguments to strset_iterate().

8 years agoopt: fix up outdated comments in documentation.
Rusty Russell [Thu, 1 Dec 2011 06:09:51 +0000 (16:39 +1030)]
opt: fix up outdated comments in documentation.

8 years agoopt: get rid of last remnant of getopt.
Rusty Russell [Thu, 1 Dec 2011 06:09:50 +0000 (16:39 +1030)]
opt: get rid of last remnant of getopt.

Testing code still using it.

8 years agotlist: remove type arg from tlist_top(), tlist_tail()
Rusty Russell [Thu, 1 Dec 2011 06:09:47 +0000 (16:39 +1030)]
tlist: remove type arg from tlist_top(), tlist_tail()

With the type canary, it's unnecessary.  Though the implementation is
a bit more awkward since they longer map directly through to list_top/tail.

8 years agolist: don't multiple-evaluate arguments to tlist_top and tlist_tail
Rusty Russell [Wed, 30 Nov 2011 03:02:18 +0000 (13:32 +1030)]
list: don't multiple-evaluate arguments to tlist_top and tlist_tail

8 years agocontainer_of: add container_off() helper.
Rusty Russell [Wed, 30 Nov 2011 03:02:06 +0000 (13:32 +1030)]
container_of: add container_off() helper.

Just like container_of() (with typechecking, etc), but return the offset
to the enclosing structure.

8 years agottxml: exclude license_comment check so it doesn't fail ccanlint.
Rusty Russell [Wed, 30 Nov 2011 02:41:00 +0000 (13:11 +1030)]
ttxml: exclude license_comment check so it doesn't fail ccanlint.

8 years agotdb2: display capability information in tdb_summary()
Rusty Russell [Wed, 30 Nov 2011 02:39:07 +0000 (13:09 +1030)]
tdb2: display capability information in tdb_summary()

This means we know they're there in future, and what restrictions they

8 years agotdb2: add a capability list from the header.
Rusty Russell [Wed, 30 Nov 2011 01:39:18 +0000 (12:09 +1030)]
tdb2: add a capability list from the header.

This allows even more extensibility in future: in particular, the top
bits of each capability tell us what to do if we don't understand it:
fail the open, fail to open for write, or don't try to check the

tdb_check needs to understand the capability list so it can know to
skip over it: each element in the list is prefixed with the type tag
and the length.

8 years agotdb2: provide tdb_layout_write() rather than implying it by new_tdb_layout arg.
Rusty Russell [Wed, 30 Nov 2011 00:42:22 +0000 (11:12 +1030)]
tdb2: provide tdb_layout_write() rather than implying it by new_tdb_layout arg.

Neater API.

8 years agotdb2: add an internal TDB_CANT_CHECK flag.
Rusty Russell [Wed, 30 Nov 2011 00:42:22 +0000 (11:12 +1030)]
tdb2: add an internal TDB_CANT_CHECK flag.

This will be used shortly to indicate that a TDB2 file indicates it
cannot be checked.

8 years agofailtest: do trace via a FILE, not an fd.
Rusty Russell [Wed, 30 Nov 2011 00:42:03 +0000 (11:12 +1030)]
failtest: do trace via a FILE, not an fd.

The current mix of writing to an fd doesn't mix as well with
stderr/stdout.  And writing to a FILE * is more portable.

8 years agofailtest: add --trace to replace --tracepath
Rusty Russell [Wed, 30 Nov 2011 00:40:30 +0000 (11:10 +1030)]
failtest: add --trace to replace --tracepath

This gives a much deeper insight into what failtest is doing; good for
debugging failtest itself.

8 years agofailtest: save and restore file state inside child (on-demand)
Rusty Russell [Wed, 30 Nov 2011 00:23:42 +0000 (10:53 +1030)]
failtest: save and restore file state inside child (on-demand)

We currently save all files in the parent, and restore them once
the child is gone.  That doesn't work in a case where the child
manipulates a file the parent doesn't currently have open, so
switch to a model where the child cleans itself up, using the
already-existing cleanup callbacks.

This means that we need to undo much more, especially restoring
file offsets.  We also need to handle the case where we've already
closed the file, and now we're cleaning up.  As a bonus, we now
handle open() with O_TRUNC properly.

The cleanup function now has two modes: one simply frees (so valgrind
doesn't complain about failtest leaking so the user can see real leaks
in their programs), the other restores things so the parent sees no

8 years agofailtest: add comment about limitations of untracked pointers.
Rusty Russell [Tue, 29 Nov 2011 22:48:11 +0000 (09:18 +1030)]
failtest: add comment about limitations of untracked pointers.

8 years agofailtest: fix open in tests.
Rusty Russell [Tue, 29 Nov 2011 22:47:11 +0000 (09:17 +1030)]
failtest: fix open in tests.

The argument is wrong, so the return was -1.  That currently works,
but it will beak with the next patch.  Fix the typo.

8 years agofailtest: fix failpath on open.
Rusty Russell [Tue, 29 Nov 2011 22:46:11 +0000 (09:16 +1030)]
failtest: fix failpath on open.

And separate out the code which follows --failpath so failtest_close()
can use it too.

8 years agofailtest: report failpath problems correctly.
Rusty Russell [Tue, 29 Nov 2011 22:45:11 +0000 (09:15 +1030)]
failtest: report failpath problems correctly.

It was the wrong way around, and also it's better to show the whole
remaining failpath rather than the current letter.

8 years agofailtest: stop when leak detected.
Rusty Russell [Tue, 29 Nov 2011 22:44:11 +0000 (09:14 +1030)]
failtest: stop when leak detected.

Don't continue when we report a leak: tell the parent it's a failure.

8 years agotdb2: suppress failtest more than once on mmap.
Rusty Russell [Tue, 29 Nov 2011 22:43:11 +0000 (09:13 +1030)]
tdb2: suppress failtest more than once on mmap.

Now we test failing mmap, ccanlint -v time has increased from 200 to
330 seconds.  Worse, tests no time out on my laptop.

Fix this, by preventing us from going down that particular rabbit hole.
ccanlint -v now takes 201 seconds again.

8 years agofailtest: catch mmap.
Rusty Russell [Tue, 29 Nov 2011 22:42:11 +0000 (09:12 +1030)]
failtest: catch mmap.

mmap can also fail on out-of-memory, and for the coming change to the
way we save and restore files we want to know about them anyway.

8 years agotdb2: simplify failtest helper.
Rusty Russell [Tue, 29 Nov 2011 22:41:11 +0000 (09:11 +1030)]
tdb2: simplify failtest helper.

failtest now culls duplicates for itself (and more efficiently), so
don't replicate the logic here.  It changes things a bit, because
failtest uses backtraces rather than a simple call point to find

Also, fix one case (in run-11-simple-fetch.c) where we simply exited
rather than using failtest_exit().  We got away with it before, because
we never hit that particular failure pattern.

8 years agofailtest: fix --debugpath
Rusty Russell [Tue, 29 Nov 2011 22:40:11 +0000 (09:10 +1030)]
failtest: fix --debugpath

Calling failpath_string() here leaves the final letter randomly upper or
lower-cased, since call->fail is uninitialized.  This means we sometimes
don't match the debug string.

1) Initialize call->fail here so it will match the debug string.
2) If our calls don't match --debugpath, abort.
3) Don't match the final letter (which may be upper or lower case)
   when checking we're still on the path.  We could do better, but this is
   only a sanity-check anyway.

8 years agofailtest: internally eliminate duplicate calls.
Rusty Russell [Tue, 29 Nov 2011 22:39:11 +0000 (09:09 +1030)]
failtest: internally eliminate duplicate calls.

If we can get a backtrace, we can automatically eliminate identical
failures.  Surprisingly backtrace() is quite fast, but the savings for
the (naively-written) rbtree tests are impressive.  ccanlint -v time
drops from 43 seconds to 6 seconds.

8 years agoconfigurator: HAVE_BACKTRACE
Rusty Russell [Tue, 29 Nov 2011 22:38:11 +0000 (09:08 +1030)]
configurator: HAVE_BACKTRACE

8 years agofailtest: simplify FAIL_PROBE.
Rusty Russell [Tue, 29 Nov 2011 22:37:11 +0000 (09:07 +1030)]
failtest: simplify FAIL_PROBE.

When a failtest_hook returns fail_probe(), we start a counter to
continue for a little way.  Replace this hack with a simple flag,
which disables further failures.

Interestingly, this doesn't reduce coverage on the current modules
which use failtest.

8 years agofailtest: report errors in children directly to original stderr.
Rusty Russell [Tue, 29 Nov 2011 22:36:11 +0000 (09:06 +1030)]
failtest: report errors in children directly to original stderr.

This is useful for debugging failtest itself, as well as for things
like tracing.

8 years agofailtest: use high-numbers file descriptors to stay out of the way.
Rusty Russell [Tue, 29 Nov 2011 22:35:11 +0000 (09:05 +1030)]
failtest: use high-numbers file descriptors to stay out of the way.

We use file descriptors inside failtest; use dup2 to try to avoid
changing the file descriptor numbers used in the program (particularly
when programs mess with invalid file descriptors, they're likely to
still be invalid).

8 years agofailtest: use a linked list for history, not an array.
Rusty Russell [Tue, 29 Nov 2011 22:34:11 +0000 (09:04 +1030)]
failtest: use a linked list for history, not an array.

This avoids a silly realloc, but more importantly it gets us closer to
being runtime extensible, as each history element can be a different

8 years agotlist: implement tlist_for_each_rev
Rusty Russell [Tue, 29 Nov 2011 22:33:11 +0000 (09:03 +1030)]
tlist: implement tlist_for_each_rev

8 years agolist: implement list_for_each_rev()
Rusty Russell [Tue, 29 Nov 2011 22:32:11 +0000 (09:02 +1030)]
list: implement list_for_each_rev()

8 years agotdb2: consolidate testing failtest suppression routines.
Rusty Russell [Tue, 29 Nov 2011 22:31:11 +0000 (09:01 +1030)]
tdb2: consolidate testing failtest suppression routines.

Less cut & paste means less patching as failtest changes.

8 years agofailtest: fix internal cut & paste bug
Rusty Russell [Tue, 29 Nov 2011 22:30:11 +0000 (09:00 +1030)]
failtest: fix internal cut & paste bug

failtest_malloc should use p->u.malloc not p->u.calloc.  The layouts
are identical, so it doesn't matter, but it's confusing and leaves us
open to weird bugs in future should one change.

8 years agoccanlint: fix depends_build_without_features
Rusty Russell [Tue, 29 Nov 2011 22:29:11 +0000 (08:59 +1030)]
ccanlint: fix depends_build_without_features

This depends on reduce_features; currently it tends to run before
that, so it doesn't think there are any features to reduce and doesn't
build or run the tests with reduced features.

8 years agoMakefile-web: push to github repo too.
Rusty Russell [Wed, 23 Nov 2011 02:36:00 +0000 (13:06 +1030)]
Makefile-web: push to github repo too.

Saves me doing it manually.

8 years agolist: fix list element counting in provided example inside _info file
Vladimir Zapolskiy [Tue, 22 Nov 2011 23:58:15 +0000 (01:58 +0200)]
list: fix list element counting in provided example inside _info file

This change initializes a counter of children, otherwise is may contain
arbitrary value.

Signed-off-by: Vladimir Zapolskiy <>
8 years agocast: fix warnings with -Wextra (specifically -Wmissing-field-initializers)
Rusty Russell [Mon, 21 Nov 2011 05:17:00 +0000 (15:47 +1030)]
cast: fix warnings with -Wextra (specifically -Wmissing-field-initializers)

As noted by Jan Engelhardt; libHX fixed this already.

8 years agolist: simplify tests a little.
Rusty Russell [Mon, 21 Nov 2011 02:02:30 +0000 (12:32 +1030)]
list: simplify tests a little.

The two tests are identical with one line different, so make it clear.

8 years agoccanlint: fix --test-dep-graph
Rusty Russell [Wed, 16 Nov 2011 07:44:56 +0000 (18:14 +1030)]
ccanlint: fix --test-dep-graph

Broken by 758ab1f402b4 "ccanlint: drop -d, interpret any arguments as
directories, and allow multiple."

8 years agoccanlint: make fewer tests compulsory.
Rusty Russell [Tue, 15 Nov 2011 02:12:25 +0000 (12:42 +1030)]
ccanlint: make fewer tests compulsory.

Compulsory means "malformed", we might get rid of it altogether, since
any test can mark "fail" and make ccanlint exit with non-zero status.

Now we only have four compulsory tests:
   info_exists               Module has _info file
   depends_exist             Module's CCAN dependencies can be found
   objects_build             Module object files can be built
   module_builds             Module can be built from object files

8 years agoccanlint: fix ccanlint -l
Rusty Russell [Tue, 15 Nov 2011 02:10:37 +0000 (12:40 +1030)]
ccanlint: fix ccanlint -l

8 years agotdb2: don't be fascist when TDB_VERSION1 is specified.
Rusty Russell [Tue, 1 Nov 2011 23:38:32 +0000 (10:08 +1030)]
tdb2: don't be fascist when TDB_VERSION1 is specified.

We currently insist that a tdb file be a version1 file if tdb_open() is
passed the TDB_VERSION1 flag; we fail if it's actually a tdb2.

But that makes generic wrappers harder, and is unlikely to be what the
user wants: if they do, they can check tdb_get_flags() & TDB_VERSION1
after opening.

8 years agostrset: set errno to ENOENT even if we return NULL.
Rusty Russell [Tue, 1 Nov 2011 23:06:29 +0000 (09:36 +1030)]
strset: set errno to ENOENT even if we return NULL.

It seems redundant: strset_test() and strset_clear() can only return NULL
when the string is not a member.  However, it became clear in writing
ccan/tsort that it's much more convenient for callers if we set errno
in this case too, so they can pass it up.

8 years agostrmap: set errno to ENOENT even if we return NULL.
Rusty Russell [Tue, 1 Nov 2011 23:05:29 +0000 (09:35 +1030)]
strmap: set errno to ENOENT even if we return NULL.

It seems redundant: strmap_get() and strmap_del() can only return NULL
when the string is not a member.  However, it became clear in writing
ccan/tsort that it's much more convenient for callers if we set errno
in this case too, so they can pass it up.

8 years agoccanlint: fix uninitialized variables in tests_pass_valgrind.
Rusty Russell [Tue, 1 Nov 2011 23:04:29 +0000 (09:34 +1030)]
ccanlint: fix uninitialized variables in tests_pass_valgrind.

We weren't initializing the leak_info field when the test was marked
FAIL in _info (as in tdb2).

8 years agoccanlint: fix test link when given no arguments.
Rusty Russell [Tue, 1 Nov 2011 23:01:25 +0000 (09:31 +1030)]
ccanlint: fix test link when given no arguments.

Fallout from commit 758ab1f402b4af3cccac09548b709deca17ef930
(ccanlint: drop -d, interpret any arguments as directories...)

8 years agocompiler, ilog: IDEMPOTENT "idempotent does not mean what you think it means"
Rusty Russell [Wed, 26 Oct 2011 06:26:22 +0000 (16:56 +1030)]
compiler, ilog: IDEMPOTENT "idempotent does not mean what you think it means"

Actually, I don't even think it means that.  But rename it to something
which is sane.

Thanks to David Gibson for reporting.

8 years agostrset: set errno on strset_add failures.
Rusty Russell [Wed, 26 Oct 2011 06:25:50 +0000 (16:55 +1030)]
strset: set errno on strset_add failures.

8 years agostrmap: set errno on strmap_add() failures.
Rusty Russell [Wed, 26 Oct 2011 06:25:38 +0000 (16:55 +1030)]
strmap: set errno on strmap_add() failures.

8 years agoccanlint: fix creation of example test/run.c
Rusty Russell [Mon, 24 Oct 2011 23:50:18 +0000 (10:20 +1030)]
ccanlint: fix creation of example test/run.c

Hasn't worked for a while now.  Oops.

8 years agoccanlint: drop -d, interpret any arguments as directories, and allow multiple.
Rusty Russell [Wed, 5 Oct 2011 05:23:35 +0000 (15:53 +1030)]
ccanlint: drop -d, interpret any arguments as directories, and allow multiple.

This gets us closer to 'ccanlint *' rather than relying on Makefiles
to test all modules.  Unfortunately, because of limited parallelism, it's
currently slower than make -j.

8 years agoccanlint: fix spurious warning errors.
Rusty Russell [Wed, 5 Oct 2011 03:40:29 +0000 (14:10 +1030)]
ccanlint: fix spurious warning errors.

Because we fork children to do compilations, and we use stdio, we need
to flush stdout before the fork otherwise the child will flush
afterwards.  The compile tests interpret this output as a compiler

This shows up if you redirect ccanlint output to a file.

8 years agotdb2: fix valgrind suppression in _info.
Rusty Russell [Tue, 4 Oct 2011 01:40:09 +0000 (12:10 +1030)]
tdb2: fix valgrind suppression in _info.

Commit c4ca9f54301c0367 renamed run-83-openhook.c to
api-83-openhook.c, but didn't update the suppression in _info.  My
system runs a patched valgrind, which doesn't have this problem.

8 years agoshort_types: fix example for 64 bit platforms
Rusty Russell [Tue, 4 Oct 2011 01:40:08 +0000 (12:10 +1030)]
short_types: fix example for 64 bit platforms

Use correct printf string.

8 years agoopt: increase testing coverage on 64 bit platforms
Rusty Russell [Tue, 4 Oct 2011 01:40:08 +0000 (12:10 +1030)]
opt: increase testing coverage on 64 bit platforms

Help the compiler eliminate untestable code.

8 years agonet: fix tests for systems without IPv6 entries in /etc/hosts.
Rusty Russell [Tue, 4 Oct 2011 01:40:08 +0000 (12:10 +1030)]
net: fix tests for systems without IPv6 entries in /etc/hosts.

We fake up a dual IPv4/IPv6 response to localhost for testing, but it
assumed localhost6 or ip6-localhost entries.  Fall back to "::1" which
should always work.

8 years agojmap: fix _info example for 64 bit systems.
Rusty Russell [Tue, 4 Oct 2011 01:40:08 +0000 (12:10 +1030)]
jmap: fix _info example for 64 bit systems.

8 years agoforeach: make test more accurate, fix for 64-bit gcc 4.4.3
Rusty Russell [Tue, 4 Oct 2011 01:39:45 +0000 (12:09 +1030)]
foreach: make test more accurate, fix for 64-bit gcc 4.4.3

gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3 on x86_64 uses a different stack
offset for the second call to test_ptr_recursion(), meaning it sees
new iterators.  Put it inside a loop to reduce the chance of that

8 years agoasearch: fix example on 64 bit platforms.
Rusty Russell [Tue, 4 Oct 2011 01:38:45 +0000 (12:08 +1030)]
asearch: fix example on 64 bit platforms.

8 years agoalloc: fix memory leak in tests.
Rusty Russell [Tue, 4 Oct 2011 01:37:45 +0000 (12:07 +1030)]
alloc: fix memory leak in tests.

8 years agotdb2: fix test printf for 64 bit.
Rusty Russell [Tue, 4 Oct 2011 01:36:45 +0000 (12:06 +1030)]
tdb2: fix test printf for 64 bit.

Very minor fix, since this won't happen unless the test fails.

8 years agoweb: add pointer to wiki/Contribute.
Rusty Russell [Thu, 29 Sep 2011 03:20:16 +0000 (12:50 +0930)]
web: add pointer to wiki/Contribute.

8 years agoNote new URL:, and point to new wiki on GitHub.
Rusty Russell [Thu, 29 Sep 2011 03:08:06 +0000 (12:38 +0930)]
Note new URL:, and point to new wiki on GitHub.

8 years agostrmap: new module for ordered map of strings using a critbit tree.
Rusty Russell [Wed, 28 Sep 2011 02:37:35 +0000 (12:07 +0930)]
strmap: new module for ordered map of strings using a critbit tree.

8 years agotcon: more help, for making strmap.
Rusty Russell [Wed, 28 Sep 2011 02:36:35 +0000 (12:06 +0930)]
tcon: more help, for making strmap.

8 years agohtable: benchmark against hsearch(3)
Rusty Russell [Tue, 27 Sep 2011 06:28:44 +0000 (15:58 +0930)]
htable: benchmark against hsearch(3)

Since that has a fixed hash table size and doesn't support delete, we can't
do a thorough comparison, but we can insert and search.

8 years agolikely: use htable_type
Rusty Russell [Tue, 27 Sep 2011 06:28:43 +0000 (15:58 +0930)]
likely: use htable_type

Also general cleanups:
(1) Don't assume that strings are folded by the compiler.
(2) Implement likely_stats_reset().
(3) Return non-const string from likely_stats(), as caller must free it.
(4) Don't use struct info indirection (that was from when we used callbacks?)
(5) Close memory leak in run-debug.c

8 years agohtable: HTABLE_INITIALIZER() for static initialization.
Rusty Russell [Tue, 27 Sep 2011 06:28:41 +0000 (15:58 +0930)]
htable: HTABLE_INITIALIZER() for static initialization.

Unfortunately it's a bit of a pain to use for typed hashtables, but it

8 years agohtable: clean up interface, document htable_type better.
Rusty Russell [Tue, 27 Sep 2011 05:07:01 +0000 (14:37 +0930)]
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_.

8 years agohtable: start empty.
Rusty Russell [Tue, 27 Sep 2011 04:56:59 +0000 (14:26 +0930)]
htable: start empty.

There's no real reason to start with 128 entries.

8 years agotap: fix exit status when we have exactly 256 errors.
Rusty Russell [Tue, 27 Sep 2011 04:55:59 +0000 (14:25 +0930)]
tap: fix exit status when we have exactly 256 errors.

8 years agotcon: update and enhance documentation.
Rusty Russell [Tue, 27 Sep 2011 03:38:16 +0000 (13:08 +0930)]
tcon: update and enhance documentation.

8 years agohtable, strset: benchmarking tools.
Rusty Russell [Mon, 26 Sep 2011 11:10:42 +0000 (20:40 +0930)]
htable, strset: benchmarking tools.

This lets us compare hash table vs. strset vs. the example
implementation of critbit trees.

cbspeed 100 runs, min-max(avg):
#01: Initial insert:   236-245(237)
#02: Initial lookup (match):   180-186(180)
#03: Initial lookup (miss):   171-185(172)
#04: Initial lookup (random):   441-457(444)
#05: Initial delete all:   127-132(128)
#06: Initial re-inserting:   219-225(220)
#07: Deleting first half:   101-104(102)
#08: Adding (a different) half:   158-162(159)
#09: Lookup after half-change (match):   202-207(203)
#10: Lookup after half-change (miss):   217-222(218)
#11: Churn 1:   297-302(299)
#12: Churn 2:   297-305(300)
#13: Churn 3:   301-308(303)
#14: Post-Churn lookup (match):   189-195(190)
#15: Post-Churn lookup (miss):   189-193(190)
#16: Post-Churn lookup (random):   499-513(503)

speed 100 runs, min-max(avg):
#01: Initial insert:   211-218(212)
#02: Initial lookup (match):   161-166(162)
#03: Initial lookup (miss):   157-162(158)
#04: Initial lookup (random):   452-460(454)
#05: Initial delete all:   126-135(127)
#06: Initial re-inserting:   193-201(194)
#07: Deleting first half:   99-107(99)
#08: Adding (a different) half:   143-190(144)
#09: Lookup after half-change (match):   183-195(184)
#10: Lookup after half-change (miss):   197-203(198)
#11: Churn 1:   271-278(274)
#12: Churn 2:   280-287(282)
#13: Churn 3:   277-285(279)
#14: Post-Churn lookup (match):   171-175(171)
#15: Post-Churn lookup (miss):   174-178(175)
#16: Post-Churn lookup (random):   525-552(528)

stringspeed 100 runs, min-max(avg):
#01: Initial insert:   300-343(308)
#02: Initial lookup (match):   98-136(99)
#03: Initial lookup (miss):   73-102(75)
#04: Initial lookup (random):   230-282(233)
#05: Initial delete all:   66-102(69)
#06: Initial re-inserting:   62-99(64)
#07: Deleting first half:   43-52(43)
#08: Adding (a different) half:   101-156(106)
#09: Lookup after half-change (match):   114-156(120)
#10: Lookup after half-change (miss):   94-103(95)
#11: Churn 1:   98-105(99)
#12: Churn 2:   96-104(98)
#13: Churn 3:   174-184(176)
#14: Post-Churn lookup (match):   93-112(94)
#15: Post-Churn lookup (miss):   77-107(79)
#16: Post-Churn lookup (random):   229-265(232)

8 years agostrset: new module using critbit trees.
Rusty Russell [Mon, 26 Sep 2011 11:01:17 +0000 (20:31 +0930)]
strset: new module using critbit trees.

Not as fast as using htable, but simple and provides order and prefix

8 years agostr: fix warnings.
Rusty Russell [Mon, 26 Sep 2011 10:43:07 +0000 (20:13 +0930)]
str: fix warnings.

Firstly, -Wwrite-strings makes string literals const, secondly, we mustn't
define str_strstr etc in terms of themselves!

8 years agostr: relicense to public domain.
Rusty Russell [Mon, 26 Sep 2011 10:42:15 +0000 (20:12 +0930)]
str: relicense to public domain.

LGPL is overkill for trivial wrappers like this.

8 years agoccanlint: more tweaks to example mangling.
Rusty Russell [Mon, 26 Sep 2011 09:53:36 +0000 (19:23 +0930)]
ccanlint: more tweaks to example mangling.

Note where previous analysis said the code was outside a function, and
fix double new-line.  Also, treat end of comment as end of statement.

8 years agotypesafe_cb: fix example macro ordering in typesafe_cb_preargs documentation.
Rusty Russell [Sat, 24 Sep 2011 04:31:19 +0000 (14:01 +0930)]
typesafe_cb: fix example macro ordering in typesafe_cb_preargs documentation.

9 years agojmap: use ccan/tcon and always be typesafe.
Rusty Russell [Fri, 23 Sep 2011 02:30:49 +0000 (12:00 +0930)]
jmap: use ccan/tcon and always be typesafe.

This handles both pointer and integer types using ccan/tcon.

9 years agojbitset: rename to jset, use ccan/tcon
Rusty Russell [Fri, 23 Sep 2011 02:29:49 +0000 (11:59 +0930)]
jbitset: rename to jset, use ccan/tcon

It's now a completely generic set implementation, and uses ccan/tcon
to always be typesafe.  It handles both integer and pointer types.

9 years agotlist: use ccan/tcon
Rusty Russell [Fri, 23 Sep 2011 02:28:52 +0000 (11:58 +0930)]
tlist: use ccan/tcon

No real change for users.

9 years agotcon: routines for creating typesafe generic containers
Rusty Russell [Thu, 22 Sep 2011 06:30:30 +0000 (16:00 +0930)]
tcon: routines for creating typesafe generic containers