David Gibson [Tue, 20 Oct 2015 03:23:37 +0000 (14:23 +1100)]
tcon: Add an alternate way of building type canaries
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>
David Gibson [Sun, 25 Oct 2015 12:30:55 +0000 (23:30 +1100)]
lstack, lqueue: Move from MODS_WITH_SRC to MODS_NO_SRC
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>
David Gibson [Sun, 18 Oct 2015 10:45:01 +0000 (21:45 +1100)]
Remove stale file ccan/priority_queue/test/run.c
In commit 3782543 "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>
David Gibson [Sun, 18 Oct 2015 10:10:58 +0000 (21:10 +1100)]
order: total_order_cmp() helper and better tests
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>
Rusty Russell [Fri, 9 Oct 2015 01:43:58 +0000 (12:13 +1030)]
Travis: upgrade, try using apt dependencies.
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/1369
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Mon, 28 Sep 2015 03:14:40 +0000 (12:44 +0930)]
ccanlint: enhance and streamline "output" testing lines.
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>
David Gibson [Sat, 5 Sep 2015 04:32:24 +0000 (14:32 +1000)]
mem: Remove array_size dependency
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>
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>
Cody P Schafer [Wed, 19 Aug 2015 02:29:54 +0000 (22:29 -0400)]
pr_log: a new module that provides a simple run-time controlled logging interface
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>
Cody P Schafer [Sun, 16 Aug 2015 22:54:37 +0000 (18:54 -0400)]
configurator: hide type punning
As for the type punning: gcc-5.1 with optimization (at least) warns about type punning in
the previous example. The new usage should be exactly equivalent to the
old, but just seperates the cast and deref into 2 statements. Frankly,
I'm suprised gcc's type-punning analysis is so limited.
Signed-off-by: Cody P Schafer <dev@codyps.com> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Tue, 18 Aug 2015 23:17:02 +0000 (16:17 -0700)]
bytestring: Add rational comment to testcase
Reviewing the previous patch it took me some time to work out what the
purpose of the compile_fail-BYTESTRING-2.c test. Add a comment to avoid
that in future.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Cody P Schafer [Tue, 18 Aug 2015 00:33:31 +0000 (20:33 -0400)]
bytestring: avoid compile_fail failure due to uninitialized warning
bytestring: Module tests compile (tests_compile): FAIL
/home/x/g/ccc/ccan/ccan/bytestring/test/compile_fail-BYTESTRING-2.c:Compile gave warnings without -DFAIL:
/home/x/g/ccc/ccan/ccan/bytestring/test/compile_fail-BYTESTRING-2.c: In function ‘main’:
/home/x/g/ccc/ccan/ccan/bytestring/test/compile_fail-BYTESTRING-2.c:15:2: warning: ‘bs.len’ is used uninitialized in this function [-Wuninitialized]
printf("%zd %s\n", bs.len, x);
^
Signed-off-by: Cody P Schafer <dev@codyps.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Cody P Schafer [Sun, 16 Aug 2015 22:54:37 +0000 (18:54 -0400)]
configurator: avoid leaks that LeakSanitizer doesn't like
These leaks aren't really an issue since they are completely bounded,
but if one is building with leak sanitizer enabled (as
-fsanitize=address does in gcc-5.1), it kills the configurator, which
isn't very useful for us. Add the few free() calls it's looking for.
This is not an actual code issue, they just workaround
some optional compiler peculiarities.
Signed-off-by: Cody P Schafer <dev@codyps.com> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au> (split off leak change)
David Gibson [Mon, 11 May 2015 10:35:34 +0000 (22:35 +1200)]
aga: Add lazytrie testcase
This adds a more complex testcase to the aga module. This one is a trie
(basically a radix tree for strings).
It demonstrates different ways of constructing edge information from an
internal representation than the existing testcases. Importantly, it also
demonstrates aga's ability to cope with the edge function lazily
constructing nodes on the fly.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 7 May 2015 11:29:19 +0000 (21:29 +1000)]
aga: Testcase for attempt to run concurrent algorithms
The aga algorithms can't be run concurrently, because they store state
information in the aga_node structures. However, they are supposed to
detect an attempt to re-enter and safely report an error. This adds a
testcase for this.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 21 May 2015 09:23:19 +0000 (21:23 +1200)]
aga: Simple test graphs
This adds code for a number of example graphs for use in tests of the aga
module. They also demonstrate several different ways of constructing
graphs using the aga callbacks.
It adds one actual testcase, which just verifies that the example graph
look like what they're supposed to. Specifically it computes a set of
adjacency lists for the example graphs from the callback code, then
compares that to a canned example of what it should be.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 18 Jun 2015 09:30:18 +0000 (19:30 +1000)]
avl: Use definitions from order module
The AvlCompare type defined in the avl module is identical in signature to
the compare function used by qsort() and bsearch(). That has a common
definition in the new order module, so use that rather than defining its
own.
In addition use the standard comparison functions from order where possible
for the avl test code.
Cc: Joey Adams <joeyadams3.14159@gmail.com> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 18 Jun 2015 09:29:37 +0000 (19:29 +1000)]
asort: Use order module definitions
The asort routine takes a user-supplied comparison function. Use the
definitions from the new order module to slightly simplify the declaration
and handling of this function.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Tue, 2 Jun 2015 07:30:58 +0000 (17:30 +1000)]
order: Scalar comparison functions
Extend the order module to provide simple, standard, comparison
callbacks for scalar types (i.e. integer and floating point types).
In addition to the usual variants comparing a plain scalar, this also
provides helper macros to construct a suitably typed callback and context
pointer to order structures by a specified scalar field.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Tue, 2 Jun 2015 07:26:49 +0000 (17:26 +1000)]
order: Module for comparison callbacks
Many common algorithms take a callback for comparing items - effectively
giving the items a user defined order.
For example, the standard library qsort() and bsearch() routines take such
a callback. The ccan/avl module takes an identical one. The ccan/asort
and ccan/asearch modules use a different variant: their callback takes an
additional context parameter, and is also typed via use of macros and
typesafe_cb.
This module provides helper types and macros for easily declaring any of
the common variants on comparison functions: the 2-parameter untyped form
(as used by qsort), the 3-parameter untyped form (used by the asort back
end) and the 3-parameter typed form (used by the asort front end). It
provides a wrapper macro for doing the typesafe_cb conversion from
3-parameter typed to 3-parameter untyped.
It also provides a container struct to describe both a comparison callback
and a context value as a single structure. This also comes in both
untyped and typed variants.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 13 Jun 2015 14:24:57 +0000 (00:24 +1000)]
lqueue: Allow a queueu to be initialized from an existing back element
There are occasional cases where you might construct a valid queue, and
retain a direct pointer to the back element, but not the struct lqueue
used to build it.
This patch adds a new lqueue_init_from_back() macro to reconstruct a valid
struct lqueue from the element pointer for cases like this.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 13 Jun 2015 14:23:39 +0000 (00:23 +1000)]
lstack: Allow a stack to be initialized from an existing top element
There are occasional cases where you might construct a valid stack, and
retain a direct pointer to the top element, but not the struct lstack
used to build it.
This patch adds a new lstack_init_from_top() macro to reconstruct a valid
struct lstack from the element pointer for cases like this.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 27 May 2015 14:17:35 +0000 (00:17 +1000)]
asearch: Add context pointer to asearch comparison callback
asearch, like the standard library bsearch, takes a comparison callback.
Like bsearch() that callback doesn't include a user supplied context
pointer. As well as being generally limiting, that makes the comparison
functions used by asearch gratuitously different from those used by the
asort module.
This patch alters this. Note that this is an incompatible change to the
asearch interface. I think this is worth it to correct the oversight, but
others might disagree. At present the only user within ccan is ntdb, which
is corrected to match.
This means actually supplying a binary search implementation, rather than
relying on bsearch() from the standard library. We follow the lead of the
asort module and steal^H^H^H^H^Hadapt the implementation from glibc.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Wed, 27 May 2015 14:17:34 +0000 (00:17 +1000)]
asearch: Correct license tag to LGPL 2.1+
The _info file for asearch currently gives the license as just "LGPL".
That gives a warning from ccanlint, because it interprets that as the
latest LGPL 3 whereas asearch.h and the license link indicate it's actually
LGPL 2.1+.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
David Gibson [Tue, 26 May 2015 12:56:50 +0000 (22:56 +1000)]
ptrint: Module for encoding integers into void * pointers
For callbacks which need a void * context pointer in the general case,
there are often simpler cases where an integer would suffice. These are
often handled by casting the integer into a pointer, rather than having
to allocate that integer somewhere.
This adds a module with some helpers for this. It has some advantages over
direct casts:
* It uses pointer arithmetic against NULL instead of casts which should
make it more portable, even to weird platforms with odd representations
for NULL. I don't know the C standard well enough to know if it's
totally portable though.
* In particular it means that the truth value of the pointer
representation matches that of the encoded integer.
* The conversion functions are inlines providing more type safety than
raw casts.
* It uses a ptrint_t * type which can be used to mark such pointer
encoded integers. ptrint_t is a deliberately incomplete type so such
pointers can never be dereferenced.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
projects / ccan / log