htable: Mark functions constructed by HTABLE_DEFINE_TYPE as UNNEEDED

The HTABLE_DEFINE_TYPE macro builds a type-specific hash table by
constructing a bunch of simple wrapper functions.  The user of the hash
table may not end up using all of these.  With gcc the fact that the
functions are inline stops an warnings about unused functions, but that's
not the case with clang.

Suppress these warnings by marking all the constructed functions except
for name##_add() as UNNEEDED (using the macro from ccan/compiler).  _add
is left alone on the grounds that a hash table you never add anything to
isn't much use, so this will help you to spot an entirely redundant
HTABLE_DEFINE_TYPE invocation.  *_init() would be a more obvious choice,
except that there is both *_init() and *_init_sized() and you only need
to use one of these.

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

strmap: Convert to using TCON_WRAP() instead of plain TCON()

The usual way of construction strmap objects is to use the STRMAP_MEMBERS()
macro which expands to both a raw strmap structure and a tcon type canary.
However, the tcon type canary involves a flexible array member which means
that in standard C99 STRMAP_MEMBERS() must appear only at the end of a
structure definition.  But worse, that structure can then only appear at
the end of any other structure it is included in, which is pretty
inconvenient for the intended purpose of creating type specific strmaps.

gcc extensions allow this to work (somehow), but clang complains loudly
about it.

The tcon module already includes the TCON_WRAP() mechanism, which already
provides this same sort of type-specific definitions in a more general way.
So convert strmap (and its users) to that approach.

This removes STRMAP_MEMBERS() entirely, breaking compatibility.  I'm hoping
strmap is used in few enough places that we can get away with that.

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

altstack: disable valgrind.

It does not seem to respect stack games!

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

altstack: New module

altstack - run a function with a dedicated stack, and then release the memory

Signed-off-by: Dan Good <dan@dancancode.com>

aga: Annotate unused return values

bfs_dequeue() and dfs_pop() discard the return values of lqueue_dequeue()
and lstack_pop() respectively.  This is correct, but causes warnings in
some compiler configurations (including the one currently used by
travis-ci.org).

Use the cast-to-void idiom to tell the compiler this is intentional.

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

ccanlint: Remove unused variable

The 'rest' variable in examples_run.c:find_expect() was unused.

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

configurator: Clarify empty if

configurator.c contains an if with an empty statement on the same line as
the condition.  This is very easy to misread, and also causes a warning
from clang, so move the ; onto the next line.

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

.travis.yml: Add clang builds to Travis

Still not exactly a great coverage of different C compilers, but clearly
better than *just* gcc.

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

rszshm: New module

rszshm - resizable pointer-safe shared memory

Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

tal/str: fix infinite loop of tal_fmt() with empty string.

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

pipecmd: add stderr fd arg.

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

pipecmd: fix fd leak.

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

io: io_time_override to insert fake times.

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

deque: check HAVE_STATEMENT_EXPR, tweaks from feedback

Thanks to the detailed feedback from David Gibson, I made the
following improvements:

* add missing includes
* check for statement expression support, give an error if absent
* ccanlint directive to skip "without features" steps
* add license ref to top of source files
* rename run1.c test to api1.c

Signed-off-by: Dan Good <dan@dancancode.com>

deque: New module

deque - type-preserving resizing circular deque

Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Add file describing Signed-off-by and guiding new module authors.

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

tweaks from feedback - thanks

Add xstring module - bounded string builder with three valued comparator

Makefile-web: Quote the names in the error message

 progress found but fubar in MOD

is now:

 'progress' found but 'fubar' in MOD

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

web/logo: Use a relative protocol

The webfont forces http, which results in a mixed content warning if
you're visiting the site on https. Strip the protocol so we use whatever
the user has connected with.

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Makefile-web: Download prettify from git

The SVN mirror disappeared some time ago. It now lives on Github.

Signed-off-by: Joel Stanley <joel@jms.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

pipecmd: test can't-exec case.

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

pipecmd: add pipecmdarr variant.

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

tools/namespacize: use unlink_noerr.

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

net: use close_noerr.

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

noerr: add free_noerr().

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

aga,agar: New shortcut2 sample graph and testcases based on it

This patch adds a new test graph "shortcut2" which includes a negative cost
edge.  Along with that we add a testcase for Dijkstra's algorithm checking
that it gracefully fails in this case.

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

aga,agar: New shortcut1 sample graph and testcases based on it

For all the existing test graphs, the shortest path by cost is also the
shortest path by number of edges.  This patch adds a new test graph where
that is not the case, in order to test that the Dijkstra's algorithm
implementation correctly handles that case.

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

aga,agar: Non-equal edge costs for parallel test graph

At the moment the "parallel" test graph just uses the default cost of 1
for all the links between the two nodes.  This patch changes that so that
the links have cost 2, except (optionally) one with cost 1.  This provides
a useful test for the Dijkstra's algorithm implementation to ensure that
it picks the correct link for the shortest path.

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

aga,agar: Dijkstra's algorithm

Implement Dijkstra's algorithm for one-source shortest-path.

This uses the lpq module as the implementation of the priority queue.  That
means this implementation is some way behind the theoretical efficiency of
Dijkstra's algorithm.  It should be reasonably straightforward to swap out
the priority queue for a better one in the future, though.

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

aga,agar: Add edge costs

This allows the edge_info callback to supply a cost or length for an edge.
For now we only support 'long' valued costs.  If the callback doesn't
supply a cost, it's considered cost 1.

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

Makefile-ccan: add pipecmd

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

pipecmd: new module.

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

strgrp: Cache cosine popcounts to reduce computation

Neatly, this reduces some of the OpenMP-related noise in the
implementation by removing the need for the include. The loop body of
grp_for() is also clearer as a result of the change; the changes to the
function interfaces motivated a re-think of the complexity here.

strgrp: Fix indexing of per-thread storage for cosine filter

aga: Add aga_node_needs_update() internal function

There are situations where aga algorithms may want to check if a node is
up-to-date (i.e. has yet been discovered by the current algorithm) without
making it up to date if it's not.  This adds an internal function to do so.

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

strgrp: Add cosine similarity filter

The cosine similarity measure[1] (O(m + n)) contributes a decent runtime
reduction when used as a filter prior to execution of more expensive
algorithms such as LCS[2] (O(m * n)).

A private test set of 3500 strings was used to quantify the improvement.
The shape of the test set is described by Python's Pandas module as:

    >>> frames.apply(len).describe()
    count    3500.000000
    mean       47.454286
    std        14.980197
    min        10.000000
    25%        37.000000
    50%        45.000000
    75%        61.000000
    max       109.000000
    dtype: float64
    >>>

The tests were performed on a lightly loaded Lenovo X201s stocked with a
Intel Core i7 L 640 @ 2.13GHz CPU with 3.7 GiB of memory. The test was
compiled with GCC 4.9.3:

    $ gcc --version
    gcc (Gentoo 4.9.3 p1.0, pie-0.6.2) 4.9.3
    Copyright (C) 2015 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Using the test program outlined below, ten runs for input set sizes
incrementing in batches of 500 were taken prior to filtering with cosine
similarity:

    500:  0.61, 0.25, 0.08, 0.07, 0.07, 0.07, 0.09, 0.07, 0.07, 0.07
    1000: 0.33, 0.32, 0.34, 0.32, 0.32, 0.33, 0.32, 0.32, 0.34, 0.32
    1500: 0.72, 1.53, 0.72, 0.70, 0.72, 0.70, 0.72, 0.71, 1.46, 0.71
    2000: 1.22, 1.20, 1.22, 1.98, 1.20, 1.20, 1.22, 1.94, 1.20, 1.20
    2500: 1.97, 2.72, 1.94, 2.33, 2.44, 1.94, 2.82, 1.93, 1.94, 2.69
    3000: 2.69, 3.41, 2.66, 3.38, 2.67, 3.42, 2.63, 3.44, 2.65, 3.39
    3500: 4.18, 3.65, 4.21, 4.21, 3.56, 4.21, 4.16, 3.63, 4.20, 4.13

After adding the cosine similarity filter the runtimes became:

    500:  0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02, 0.02
    1000: 0.08, 0.07, 0.07, 0.07, 0.08, 0.07, 0.07, 0.08, 0.07, 0.07
    1500: 0.16, 0.16, 0.15, 0.16, 0.16, 0.15, 0.15, 0.15, 0.16, 0.16
    2000: 0.26, 0.26, 0.25, 0.26, 0.26, 0.26, 0.25, 0.26, 0.26, 0.26
    2500: 0.41, 0.41, 0.41, 0.40, 0.42, 0.42, 0.42, 0.41, 0.41, 0.41
    3000: 0.58, 0.56, 0.57, 0.56, 0.58, 0.57, 0.56, 0.56, 0.57, 0.55
    3500: 0.75, 0.74, 0.73, 0.74, 0.74, 0.73, 0.72, 0.75, 0.75, 0.75

As such, on average the runtime improvements are:

    N       Avg Pre         Avg Post        Improvement (Pre / Post)
    500     0.145           0.02            7.25
    1000    0.326           0.073           4.47
    1500    0.869           0.156           5.57
    2000    1.358           0.258           5.26
    2500    2.272           0.412           5.51
    3000    3.034           0.566           5.36
    3500    4.014           0.74            5.42

The test driver is as below, where both it and its dependencies were
compiled with 'CFLAGS=-O2 -fopenmp' and linked with 'LDFLAGS=-fopenmp',
'LDLIBS=-lm':

    $ cat test.c
    #include "config.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "ccan/strgrp/strgrp.h"

    int main(void) {
        FILE *f;
        char *buf;
        struct strgrp *ctx;
        f = fdopen(0, "r");
    #define BUF_SIZE 512
        buf = malloc(BUF_SIZE);
        ctx = strgrp_new(0.85);
        while(fgets(buf, BUF_SIZE, f)) {
            buf[strcspn(buf, "\r\n")] = '\0';
            if (!strgrp_add(ctx, buf, NULL)) {
                printf("Failed to classify %s\n", buf);
            }
        }
        strgrp_free(ctx);
        free(buf);
        fclose(f);
        return 0;
    }

[1] https://en.wikipedia.org/wiki/Cosine_similarity
[2] https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

aga: Error codes

Add an enum to record error codes for aga routines.  The current
algorithms, dfs and bfs don't have any error conditions except those
reported by callbacks.  So, for now, the only code is "no error", but this
will be expanded in future.

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

aga: Fix initialization bug in aga_for_each_edge_info

The aga_for_each_edge_info macro is constructed so that if the edge_info
callback returns an error, the for loop terminates early and leaves the
_err parameter set to the error.  On successful completion of the loop,
_err should be zero.

However, on a node with no edges, _err will not be initialized, meaning
that it could be non-zero even on successful (trivial) completion of the
loop.  This fixes the bug.

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

aga: Add function block comments

Add block comments in the usual ccan format describing a number of the
important functions in the aga module.

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

lpq: New module

Simple, slow priority queue implementation.

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

lqueue: Streamline interface with TCON_CONTAINER

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>

lstack: Streamline interface with TCON_CONTAINER

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>

tcon: Encode information on container members in "type" canaries

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>

tcon: Encode integer values into "type" canaries

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>

tcon: Add tcon_sizeof() helper

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>

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>

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>

ptrint: ptr2int and int2ptr are constant functions

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>

Fixing odd formatting of info caused by unnecessary indentations.

opt: don't use raw malloc for errors.

We should be allocating them with opt's allocator (we use it to free them!).

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

mem: switch descriptions for memeqzero/memeqstr

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

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>

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>

tal/str: fix error in tal_strndup()

It used strlen() on the source, which might not be valid.

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

mem: get clever with memeqzero().

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>

mem: optimize.

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>

mem: add memzero benchmark.

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

mem: add memeqzero.

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

Travis: do make in parallel to test if that gives slight speedup.

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>

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>

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>

permutation: Generate permutations of arrays

New module.

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

mem: add memcheck() for valgrind.

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

configurator: check for valgrind/memcheck.h

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

strgrp: Fix compile errors in example

Commit 63f13d6 "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>

mem: Add memswap() function

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>

mem: Add function to check whether memory ranges overlap

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>

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>

strgrp: Tidy up kerneldoc in _info

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

strgrp: Optionally include OpenMP pragma

ccanlint: Add cflags support to _info

configurator: Add OpenMP detection

strgrp: new module

mem: add memends_str() helper for symmetry

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

mem: mark all functions as PURE

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>

bytestring: use newly added mem helpers

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>

mem: add mem helper functions

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

array_size: fix spurious test fail with gcc-5

It now warns about sizeof(function-param-not-really-an-array).

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

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>

list: suppress unused argument warnings

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: avoid potential unused parameter warnings hosing our config.h

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

configurator: sometimes _GNU_SOURCE is already defined, in those cases avoid redefinition

Config defines are disabled if a warning is emitted (we may want to
reconsider that), and warnings are emitted for define redefinition.

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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>

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>

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>

talloc: avoid a comparison mismatch & at the same time switch to non-legacy sysconf()

Without this, gcc warns about a sign mismatch in the comparison.

Signed-off-by: Cody P Schafer <dev@codyps.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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)

cpuid: update inline docs

Signed-off-by: A. Samy <f.fallen45@gmail.com>

cpuid: use a hardcoded constant when comparing CPU names

Signed-off-by: A. Samy <f.fallen45@gmail.com>

cpuid: fix test.

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

cpuid: namespacize some functions and define them as null if unsupported

cpuid: cpuid_write_info(): have outfile a file pointer instead

cpuid: rename ___cpuid to get_cpuid

cpuid: minor clean up

Makefile-ccan: add new modules.

I really need to get rid of this...

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

agar: Re-entrant Abstract Graph Algorithms

New module

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

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>

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>

aga: Breadth first search

This implements breadth first search for the abstract graph algorithms
module.

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