/* To avoid warnings, libm's log2 can’t be used, because it takes a double,
 * and a long int could be larger than a dobole. Therefore, inline assembly
 * and the bsr instruction are used, which computes an integer's log2. */
static inline long int log2_i(const long int x)
{
    long int y;
    asm("bsr %1, %0\n" : "=r"(y) : "r"(x));
    return y;
}

long int get_children(struct heap *h, int index)
{
    long int size = array_size(h->array);

    if (size == 0)
        return 0;

    int end_level     = 1 + (int)log2_i(size);
    int level         = (index == 0) ? 1 : 1 + (int)log2_i(index);
    int between       = level - end_level;
    long int children = (1 << between) - 2;

    /* Move the index to the left deepest child,
     * This is repeated application of 2 * i + 1,
     * which turns, at n times, into 2**n * i + 2**n - 1. */

    index = (index << between) + (1 << between) - 1;

    int begin = index;
    int end   = index + ((1 << between) - 1);

    if (size > end)
        children += (end - begin) + 1;
    else if (size > begin)
        children += (size - begin) + 1;

    return children;
}