Simple, slow priority queue implementation.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The interfaces the lqueue module currently has implement (partial) type
safety in a somewhat clunky way - types and member names need to be passed
to a number of entry points.

This patch uses the new TCON_CONTAINER magic to stash the typing
information into the declaration of the queue object, so it no longer needs
to be explicitly passed to later calls.

This does alter the lqueue interface incompatibly.  I think the module
is young enough that we can reasonably do that.  One other module,
'aga', was using lqueue, and this also includes fixes so that it still
works.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The interfaces the lstack module currently has implement (partial) type
safety in a somewhat clunk way - types and member names need to be passed
to a number of entry points.

This patch uses the new TCON_CONTAINER magic to stash the typing
information into the declaration of the stack object, so it no longer needs
to be explicitly passed to later calls.

This does alter the lstack interface incompatibly.  I think the module
is young enough that we can reasonably do that.  One other module,
'aga', was using lstack, and this also includes fixes so that it still
works.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add "container canaries" to tcon.  This allows information about a specific
member of a container structure to be encoded with TCON or TCON_WRAP.  Once
that's done, tcon_container_of() and tcon_member_of() can be used to
translate between member and container pointers based on the canary
information, without having to repeat the type and member details.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add the ability to encode, as well as types, integer values (must be
positive, compile time constant and in the range of size_t) into TCON
constructed "type" canaries.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add a new tcon_sizeof() helper macro which returns the size of a type for
which a canary has been constructed with TCON or TCON_WRAP.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The tcon module allows you to add "type canaries" to a structures, which
can be used for later typechecks.  The canaries are implemented using
a flexible array member, to avoid them taking any actual space at runtime.
That means the canaries must go at the end of your structure.

That doesn't seem like a big limitation, except that it also means the
structure containing the canaries must be at the end of any structure it
is embedded in in turn, which is a rather more serious limitation.

This patch adds a TCON_WRAP() macro which wraps a given type in a new type
which also contains type canaries, and doesn't suffer the last member
limitation.  The drawback is that if the wrapped type has smaller size than
a pointer, the type canaries will pad the wrapped type out to the size of a
pointer.

By constructing the wrappers carefully, the existing tcon macros will work
on both wrapper types constructed with TCON_WRAP and on structures
explicitly including TCON type canaries.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The lstack and lqueue modules are entirely implemented in a single header.
However, in Makefile-ccan they're listed in MODS_WITH_SRC, instead of
MODS_NO_SRC.  This appears to be harmless, but this patch moves them to
the correct category anyway.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

By construction these functions depend only on their arguments, so declare
them as CONST_FUNCTION using the helper from ccan/compiler.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

We should be allocating them with opt's allocator (we use it to free them!).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Closes: #32
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

In commit 37825438 "order: Scalar comparison functions", I accidentally
checked in a file which didn't belong with that commit, and was actually
from a module I was experimenting with but wasn't ready to commit.

This cleans up the bogus extra file.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add a wrapper macro total_order_cmp() to more conveniently use the
total_order structures.  Add some tests for it, which also improve tests
the "fancy_cmp" function.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

It used strlen() on the source, which might not be valid.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Best of both worlds.

Before:
1: 6ns
2: 7ns
4: 7ns
8: 7ns
16: 7ns
32: 8ns
64: 9ns
128: 13ns
256: 24ns
512: 47ns
1024: 92ns
2048: 185ns
4096: 376ns
8192: 739ns
16384: 1463ns
32768: 2914ns
65536: 5800ns
2: 7ns
3: 7ns
5: 7ns
9: 7ns
17: 7ns
33: 8ns
65: 9ns
129: 20ns
257: 31ns
513: 49ns
1025: 96ns
2049: 189ns
4097: 381ns
8193: 745ns
16385: 1477ns
32769: 2930ns
65537: 5824ns
total = 599391004

After:
1: 3ns
2: 3ns
4: 4ns
8: 5ns
16: 12ns
32: 13ns
64: 15ns
128: 19ns
256: 25ns
512: 35ns
1024: 57ns
2048: 105ns
4096: 183ns
8192: 324ns
16384: 607ns
32768: 1317ns
65536: 2774ns
2: 3ns
3: 3ns
5: 4ns
9: 6ns
17: 11ns
33: 13ns
65: 14ns
129: 19ns
257: 24ns
513: 35ns
1025: 57ns
2049: 106ns
4097: 183ns
8193: 324ns
16385: 607ns
32769: 1315ns
65537: 2773ns
total = 599391004
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Better for larger, worse for smaller compares.

Before:
1: 3ns
2: 3ns
4: 5ns
8: 9ns
16: 11ns
32: 33ns
64: 45ns
128: 87ns
256: 157ns
512: 296ns
1024: 579ns
2048: 1139ns
4096: 2251ns
8192: 4505ns
16384: 9704ns
32768: 18482ns
65536: 36144ns
2: 4ns
3: 6ns
5: 8ns
9: 9ns
17: 12ns
33: 22ns
65: 45ns
129: 90ns
257: 175ns
513: 357ns
1025: 607ns
2049: 1204ns
4097: 2278ns
8193: 4552ns
16385: 9011ns
32769: 18405ns
65537: 36153ns
total = 599391004

After:
1: 6ns
2: 7ns
4: 7ns
8: 7ns
16: 7ns
32: 8ns
64: 9ns
128: 13ns
256: 24ns
512: 47ns
1024: 92ns
2048: 185ns
4096: 376ns
8192: 739ns
16384: 1463ns
32768: 2914ns
65536: 5800ns
2: 7ns
3: 7ns
5: 7ns
9: 7ns
17: 7ns
33: 8ns
65: 9ns
129: 20ns
257: 31ns
513: 49ns
1025: 96ns
2049: 189ns
4097: 381ns
8193: 745ns
16385: 1477ns
32769: 2930ns
65537: 5824ns
total = 599391004
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Seems to.  Numbers are noisy, but before was 5 min 32 sec, after this
commit was 3 min 42 sec.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

I've filed bugs to get those dev packages whitelisted:
  https://github.com/travis-ci/apt-package-whitelist/issues/1366
  https://github.com/travis-ci/apt-package-whitelist/issues/1367
  https://github.com/travis-ci/apt-package-whitelist/issues/1368
  https://github.com/travis-ci/apt-package-whitelist/issues/1369Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

1) Require "" around input
2) Make them optional around output: if not there, loose match whitespace
3) Handle \n in output.
4) Document that "Given xxx" is optional.
5) Reject any non-matching comment lines starting with "given" or "outputs"
6) Fix missed test in ccan/cast
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

New module.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Commit 63f13d64 "strgrp: Tidy up kerneldoc in _info" introduced some compile
errors into the example in strgrp/_info.  This fixes them.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add a memswap() function to the mem module, which exchanges two (equal
sized, non-overlapping) memory regions.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The test is simple, but every time I do it by hand, I always spend ages
convincing myself it's actually correct.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The mem module declares array_size as a test dependency, and includes it in
test/api.c, but doesn't actually use it.  This removes the unneeded
dependency.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

The documentation as it stood rendered badly in HTML due to a lack of
knowledge of kerneldoc formatting.

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

This might allow compilers that support the anotation to make better
choices when optimizing, and all these functions meet the requirements
for being marked pure.
Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Reviwed-by: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

It now warns about sizeof(function-param-not-really-an-array).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

A simple printf logging infra where levels are determined by the
value of the "DEBUG" environment variable.

This is loosely based on the interfaces & functionality of Linux's
printk() and pr_*() wrapper macros.

Note that the current implementation uses "<N>" prefixes (where N is a
syslog level in ascii), allowing other programs that parse log output
(like systemd's journald) to know what the priority level is.
Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>