(Taken from PR for lightning)

Patch-from: https://github.com/conanocSigned-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>

It's significantly faster because it assumes no deletion:

10000000,critbit iteration (nsec),316
10000000,critbit callback iteration (nsec),90
...
10000000,critbit consecutive iteration (nsec),308
10000000,critbit consecutive callback iteration (nsec),78
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

We can't do the full range, but we can for a handful of bits (8).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

Because intmap_after_() would simply examine the critbits to walk the
tree, it wouldn't realize that it might be in the completely wrong tree.

In this case:

         Bit 4:
         0   1
        /     \
       /       \
  100000011  100001011

When we ask for intmap_after_(011111111) we would check the critbit, it's
a 1, so we end up on the right leaf instead of the left.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

A critbit tree is a binary tree which keeps branches for each bit
which differs in the leaves.  It's a simple data structure, but not
entirely simple to implement the primitives people expect, as this bus
shows.

The bug: I added an open iterator, and intmap_after_ for a random
value would sometimes return the wrong node.

Cause: we don't know what the prefix is as we iterate, so by only
testing the critbits in the tree, we can end up in the wrong place.
This is only a problem if the value isn't in the (sub)tree, but this
can easily happen even with contiguous trees should deletion occur.
You can see an example in the next patch, which adds a test.

After finding a bug in my intmap_after() routine, I went searching for
other implementations to see how they handled it.  Most didn't provide
an open-ended iterator like this, relying on callback iterators which
don't allow deletion.  Gah!

The exception was https://github.com/blynn/blt/blob/master/blt.c#L179
which implements blt_ceil() which does this (if you add one to the
key, at least).  However, it does it by effectively finding a node,
using that to derive the prefix, then walking down the tree again.
That's pretty suboptimal.

There are basically two choices if you want an efficient after()
operation: to reimplement this approach with some optimizations
(ie. keep branches as we descend, and when we get to the bottom and
know the prefix, we know which branch to go down), or keep the bits
which got to each node.

The latter is more optimal, but less generally useful: for bit
strings, for example, we could keep the bits in common on each node,
rather than storing the entire string at the bottom.  But in practice
you'd be doing allocations to re-create the index if the caller wanted
it.

However, in this implementation our keys are 64 bits only, and we
already use a u8 for the bit number: using a 64-bit value there
consumes no more space (thanks to alignment).  We can store the
critbit by using the prefix capped by a bit: 0b10000...0000 means
no prefix and highest bit is the critbit, and 0bxxxxx1000...000
means the prefix is xxxxxx and the critbit is the 6th highest bit.

The penalty is that iteration 70% slower.  It's still pretty fast
though.

Before:
$ for i in `seq 5`; do ./speed 10000000; done | stats
10000000,random generation (nsec),3-4(3.2+/-0.4)
10000000,critbit insert (nsec),1530-1751(1633.2+/-80)
10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97)
10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02)
10000000,critbit iteration (nsec),208-266(242.2+/-19)
10000000,critbit memory (bytes),48
10000000,critbit delete (nsec),1747-1861(1803.8+/-42)
10000000,critbit consecutive iteration (nsec),182-228(210+/-18)

After:
10000000,random generation (nsec),3-4(3.2+/-0.4)
10000000,critbit insert (nsec),1533-1699(1628+/-65)
10000000,critbit successful lookup (nsec),1831-2104(1972.4+/-1e+02)
10000000,critbit failed lookup (nsec),1850-2152(2008.2+/-1.1e+02)
10000000,critbit iteration (nsec),304-324(312.8+/-7.5)
10000000,critbit memory (bytes),48
10000000,critbit delete (nsec),1617-1872(1752+/-99)
10000000,critbit consecutive iteration (nsec),303-318(311+/-5.4)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

I wrote these a while ago, dig them out.

On my laptop, min-max(avg+/-stdev) of 5 runs:

make && for i in `seq 5`; do ./speed 10000000; done | stats
make: Nothing to be done for 'all'.
10000000,random generation (nsec),3-4(3.2+/-0.4)
10000000,critbit insert (nsec),1530-1751(1633.2+/-80)
10000000,critbit successful lookup (nsec),1723-1993(1806.8+/-97)
10000000,critbit failed lookup (nsec),1763-2104(1933.6+/-1.3e+02)
10000000,critbit iteration (nsec),208-266(242.2+/-19)
10000000,critbit memory (bytes),48
10000000,critbit delete (nsec),1747-1861(1803.8+/-42)
10000000,critbit consecutive iteration (nsec),182-228(210+/-18)
10000000,hash insert (nsec),396-424(412+/-9.6)
10000000,hash successful lookup (nsec),150-164(157.4+/-5.5)
10000000,hash failed lookup (nsec),163-178(170+/-5.5)
10000000,hash iteration (nsec),21-26(23.2+/-1.7)
10000000,hash memory (bytes),45
10000000,hash delete (nsec),179-194(183.6+/-5.3)
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>

Error I experienced on Alpine Linux without this patch:

    In file included from ccan/generator/generator.c:8:0:
    ./ccan/generator/generator.h:23:2: error: #error Generators require coroutines
     #error Generators require coroutines
      ^~~~~
    make: *** [Makefile:32: ccan/generator/generator.o] Error 1

From 32f86c701ab0e0ad0ad6981314a9bff2dc5ebb74 Mon Sep 17 00:00:00 2001
From: Yubin Ruan <ablacktshirt@gmail.com>
Date: Wed, 14 Mar 2018 11:14:54 +0800
Subject: [PATCH] fix misuse of typesafe_cb_cast() in example
Signed-off-by: Yubin Ruan <ablacktshirt@gmail.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

From 47c92fe951545e780ca31c598bbcbe5347059b27 Mon Sep 17 00:00:00 2001
From: Yubin Ruan <ablacktshirt@gmail.com>
Date: Mon, 12 Mar 2018 11:22:35 +0800
Subject: [PATCH] fix misspelling in the example of container_of
Signed-off-by: Yubin Ruan <ablacktshirt@gmail.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

We already handle normal free traversal loops, just not ones caused by a
direct tal_free() call, such a calling tal_free() on one's own parent.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

This is for cross-configuring, where we might want to run
`qemu-user-... gcc` or even more exotic things.
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>

It seems most sensible to make it a noop, but it definitely shouldn't
access out of bounds as it does.

Reported-by: Russ Dill
Fixes: #61
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

For lightning, we want to hand the socket off to another daemon, but we need
to be on a packet boundary.  This lets us check if we've part-read or
part-written.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

If io_read is always called, we don't know that it will actually read,
so it might not notice error.  In that case, safest to fail immediately.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

So many bugs in one example program!

There was an unrelated but which strace revealed (trying to write -7
bytes), but I think your issue was more prosaic: failing to zero the
from buffer.
Reported-by: Ian Zimmerman <itz@very.loosely.org>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

An application built using glibc would expect __BYTE_ORDER to tell if
it should be compiled for BIG_ENDIAN or LITTLE_ENDIAN, whereas ccan uses
HAVE_LITTLE_ENDIAN and HAVE_BIG_ENDIAN for the same purpose.

Hence setting __BYTE_ORDER based on what CCAN provides will no longer
break the applications which check endianness the glibc way.
Signed-off-by: Akshay Adiga <akshay.adiga@linux.vnet.ibm.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

I had a case where I was handing a sub-object (not a tal object!) to
tal_steal() and it wasn't detected, because the pointers looked correct.

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

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

The memmove() call should be using the index argument to determine the
number of bytes to copy. To be consistent with the rest of the code,
we should also not evaluate the index parameter multiple
times. Calling this with rand() % arr.size would otherwise generally
segfault.

Finally, we want to avoid using "index" as an identifier so as to not
shadow index(3) in the C library.
Signed-off-by: Damien Grassart <damien@grassart.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

Identifiers starting with underscores are technically reserved for
system use, so rename all of them to end with one instead.
Signed-off-by: Damien Grassart <damien@grassart.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

This module currently supports removing but not inserting at a
specified index, so this adds that along with some tests. Inserting a
value moves all existing data beyond index over one element.
Signed-off-by: Damien Grassart <damien@grassart.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

You can use SHACHAIN_BITS to contrain the size.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension.  TCON_WRAP() avoids this and so
is more portable.

This doesn't change the objset interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension.  TCON_WRAP() avoids this and so
is more portable.

This doesn't change the jmap interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension.  TCON_WRAP() avoids this and so
is more portable.

This doesn't change the jset interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

TCON() uses flexible-array members which aren't allowed in the middle
of structures, except as a gcc extension.  TCON_WRAP() avoids this and so
is more portable.

This doesn't change the tlist interface, only its internals.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

It's a common thing to want to do, so add helper here.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

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

If we're duplex and one io_always callback makes the other io_always,
we screwed up and hit an assertion later when the conn was in the
always list but didn't actually want to be.

io_wake() uses io_always(), so this is how it happened.  Writing a
test case for this was a bit fun, too.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

At this point the construction of the function above means that nn cannot
be NULL.

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