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

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

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 - type-preserving resizing circular deque
Signed-off-by: Dan Good <dan@dancancode.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

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

 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>

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>

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>

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>

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

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

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>

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>

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>

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>

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>

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

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

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.

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>

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

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>

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>

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>

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>