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>

Hi Rusty,

Thanks for reviewing the patch. V2 is attached, see my comments below.

> On 31 Mar 2015, at 02:36, Rusty Russell <rusty@rustcorp.com.au> wrote:
>
> Delio Brignoli <brignoli.delio@gmail.com> writes:
>> Hi All,
>>
>> tal_stack implements a (trivial) stack of tal contexts. Would this be a worthy addition to CCAN? (not necessarily in its current form).

[…]

>        This is cute; I’ve seen similar used in Samba.  It's

Indeed, it was inspired by talloc_stack.h ;-)

[…]

> You are missing a _info file: I would create that, and put your example
> in an Example: section there.

I moved the module and tests under can/tal/stack and added a LICENSE and _info.

> Other random advice:
> 1) You should also document the tal_newframe function (particularly note
>   that you're expected to tal_free the result, and that it will free
>   any future unfreed frames).  And note that it’s not threadsafe.

Done.

> 2) You probably want tal_newframe to be a macro, and hand file and line
>   thought to the tal_alloc_ call.  That makes debugging nicer when
>   you iterate the tree.

Done. The macro is calling a tal_newframe_() function because I’d rather not make the module’s stack variable ‘public’.

> 3) Consider whether you want to declare a dummy type 'struct tal_stack'.
>   Probably pretty unnecessary since it’s quite clear.

Skipped this one. We can declare it later if we change our minds.

Thanks
—
Delio

From c2ceb9258d97b0dcb72e7b6986cfd2bd394b254e Mon Sep 17 00:00:00 2001
From: Delio Brignoli <dbrignoli@audioscience.com>
Date: Sun, 15 Mar 2015 13:26:40 +0100
Subject: [PATCH] tal_stack: new module - V2
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>