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>

eg. asort depends on order, but order testdepends on asort.

Probably not the greatest thing to do, but don't barf because of it.
Reported-by: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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>

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>

I've been using opt_usage_and_exit() but that exits status 0.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Currently, if allocation fails, inside bitmap_alloc0(), we'll continue
to use bitmap=NULL pointer and pass it to bitmap_zero() which will
SIGSEGV.

Cc: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Kirill Smelkov <kirr@nexedi.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

This may have been causing a travis failure.  Let's see!
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

It's a bit too powerful, if you just want to memdup one thing, it's
hard to remember what the extra args are for.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

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>

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>

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>

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

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

I misused it by accident: the implied sizeof() is too tricky.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Otherwise their web pages don't get built.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

For ccan core maintainers only, but useful.
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>

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 is still pretty stupid, but greatly reduces my routing-sim time.
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>

We fill the upper buckets after we've moved on from the first bucket
in this layer.  This means two things:
1) If we have to look at an upper layer, we need to look at the next bucket,
   unless offset is 0.
2) We need to keep looking up layers in the corner case, too.
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>

I thought this was slowing down my program; it turned out they were
all hashing to the same value.  But it might be useful.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

This enables building of the CCAN and running of all the tests on
https://travis-ci.org/Signed-off-by: Joel Stanley <joel@jms.id.au>
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>

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>