Repository: google/filament
File: filament/src/AtlasAllocator.cpp (C++)

Code before:
        const auto [x, y] = unmorton(loc.code);
        // scale to our maximum allocation size
        const uint32_t mask = (1u << layer) - 1u;
        result.viewport.left   = int32_t(x & mask) << powerOfTwo;
        result.viewport.bottom = int32_t(y & mask) << powerOfTwo;
        result.viewport.width  = dimension;
        result.viewport.height = dimension;
        result.layer = loc.code >> (2 * layer);
    }
    return result;
}

void AtlasAllocator::clear(size_t const maxTextureSize) noexcept {
    std::fill(mQuadTree.begin(), mQuadTree.end(), Node{});
    mMaxTextureSizePot = (sizeof(maxTextureSize) * 8 - 1u) - clz(maxTextureSize);
}

AtlasAllocator::NodeId AtlasAllocator::allocateInLayer(size_t const maxHeight) noexcept {
    using namespace QuadTreeUtils;

    NodeId candidate{ -1, 0 };
    if (UTILS_UNLIKELY(maxHeight > QuadTree::height())) {
        return candidate;
    }

    const int8_t n = int8_t(maxHeight);

    QuadTree::traverse(0, 0, n,
            [this, n, &candidate](NodeId const& curr) -> QuadTree::TraversalResult {

                // we should never reach a level higher than n
                assert_invariant(curr.l <= n);

                // get the node being processed
                const size_t i = index(curr.l, curr.code);
                Node const& node = mQuadTree[i];

                // if the node is allocated, the whole tree below it is unavailable
                if (node.isAllocated()) {
                    // if a node is allocated it can't have children
                    assert_invariant(!node.hasChildren());
                    return QuadTree::TraversalResult::SKIP_CHILDREN;
                }

                // we're looking for the `deepest` unallocated node that has no children,
                // up to the depth we're trying to allocate
                if (curr.l > candidate.l && !node.hasChildren()) {
                    candidate = curr;
                    // Special case where we found a fitting node, just exit.
                    if (curr.l == n) {
                        return QuadTree::TraversalResult::EXIT;

Review comment (bug):
To be clear, this means they're filament bugs, right? (For example, users cannot double free an allocation)

Code after:
        const auto [x, y] = unmorton(loc.code);
        // scale to our maximum allocation size
        const uint32_t mask = (1u << layer) - 1u;
        result.viewport.left   = int32_t(x & mask) << powerOfTwo;
        result.viewport.bottom = int32_t(y & mask) << powerOfTwo;
        result.viewport.width  = dimension;
        result.viewport.height = dimension;
        result.layer = loc.code >> (2 * layer);
        result.code = loc.code;
        result.level = loc.l;
    }
    return result;
}

void AtlasAllocator::free(Allocation const& allocation) noexcept {
    if (UTILS_UNLIKELY(!allocation.isValid())) {
        return;
    }

    // 1. Mark the node as unallocated
    const size_t i = QuadTreeUtils::index(allocation.level, allocation.code);
    Node& node = mQuadTree[i];

    // In debug builds, ensure we are freeing something that was actually allocated
    assert_invariant(node.isAllocated());
    assert_invariant(!node.hasChildren());

    node.allocated = false;

    // 2. Coalesce up the tree
    // We walk up to the root. If a parent's children count drops to 0, it means all its children are free.
    // However, we don't mark the parent as 'allocated' (that would mean it's occupied by a larger block).
    // We just ensure the parent knows it has one less child.
    // The 'allocated' flag is only true if a specific block is claimed.
    // The 'children' count tracks how many sub-blocks are claimed or split.

    int8_t currentL = allocation.level;
    uint16_t currentCode = allocation.code;

    while (currentL > 0) {
        const size_t p = QuadTreeUtils::parent(currentL, currentCode);
        Node& parent = mQuadTree[p];

        // The parent must have children (since we just came from one)
        assert_invariant(parent.hasChildren());

        parent.children--;

        // If the parent still has children, we stop coalescing because this branch is still partially in use.
        if (parent.hasChildren()) {
            break;