Function node

src/e9patch/e9alloc.cpp:429–474

* Allocate and initialize a new interval tree node. */

 * Allocate and initialize a new interval tree node.
 */
static Node *node(Node *parent, intptr_t lb, intptr_t ub, size_t size,
    uint32_t flags)
{
    bool alloc_left = ((flags & FLAG_RIGHT) != 0? false:
        ((flags & FLAG_LB) != 0 || (flags & FLAG_UB) == 0));
    intptr_t LB, UB;
    if (alloc_left)
    {
        LB = lb;
        UB = lb + size;
    }
    else
    {
        LB = ub - size;
        UB = ub;
    }

    bool same_page   = ((flags & FLAG_SAME_PAGE) != 0);
    bool spans_pages = (LB / PAGE_SIZE != (UB-1) / PAGE_SIZE);
    if (same_page && spans_pages)
    {
        off_t offset = (alloc_left?
            (off_t)PAGE_SIZE - std::abs((intptr_t)(lb % PAGE_SIZE)):
            -std::abs((intptr_t)(ub % PAGE_SIZE)));
        LB += offset;
        UB += offset;
        assert(LB / PAGE_SIZE == (UB-1) / PAGE_SIZE);
        if (LB < lb || UB > ub)
        {
            // Cannot fit into the current page == fail.
            return nullptr;
        }
    }

    Node *n = alloc();
    n->alloc.lb     = LB;
    n->alloc.ub     = UB;
    n->lb           = LB;
    n->ub           = UB;
    n->entry.parent = parent;
    n->entry.left   = nullptr;
    n->entry.right  = nullptr;
    n->color        = RB_RED;
    n->gap          = 0;
    return n;
}

/*
 * Insert left-child helper.