/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License version 2
 *   as published by the Free Software Foundation.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 *   Copyright (C) 2007  Benjamin Segovia <bsegovia@liris.cnrs.fr>
 */

#include "kdlib_blockifier.h"
#include "sys_mem.h"

#include <stack>

/***************************************************************************//**
 * Data for the global stack
/******************************************************************************/
struct data_t {
    uint32_t src_id, dst_id;
    data_t(uint32_t _src_id, uint32_t _dst_id) {
        src_id = _src_id;
        dst_id = _dst_id;
    }
};

/***************************************************************************//**
 * Data for the block stack
/******************************************************************************/
struct bdata_t {
    uint32_t src_id, dst_id, depth;
    bdata_t(uint32_t _src_id, uint32_t _dst_id, uint32_t _depth) {
        src_id = _src_id;
        dst_id = _dst_id;
        depth = _depth;
    }
};

/***************************************************************************//**
 * Perform the blockification of the given kd-tree descriptor
/******************************************************************************/
NOINLINE void
kdlib::do_blockify(
    kdtree::descriptor_t& dst,
    kdtree::descriptor_t& src,
    uint32_t block_depth)
{
    /* Initialize the dst descriptor */
    rt::wald_tri_t * __restrict acc = (rt::wald_tri_t *)
        sys::mem::allocate(src.tri_n * sizeof(rt::wald_tri_t));
    kdtree::node_t * __restrict root = (kdtree::node_t * __restrict)
        sys::mem::allocate(src.node_n * sizeof(kdtree::node_t));
    kdtree::tri_id_t * __restrict ids = (kdtree::tri_id_t * __restrict)
        sys::mem::allocate(src.id_n * sizeof(kdtree::tri_id_t));

    /* Now, perform the block allocation */
    uint32_t curr = 1;
    std::stack<data_t> stack;
    std::stack<bdata_t> bstack;
    stack.push(data_t(0, 0));

    /* Stack for the complete kd-tree */
    while(!stack.empty()) {
        const data_t &node = stack.top();
        stack.pop();

        /* Stack for one given block */
        bstack.push(bdata_t(node.src_id, node.dst_id, 0));
        while(!bstack.empty()) {
            const bdata_t &data = bstack.top();
            bstack.pop();
            if(data.depth == block_depth) {
                stack.push(data_t(data.src_id, data.dst_id));
                continue;
            }
            root[data.dst_id] = src.root[data.src_id];
            if(src.root[data.src_id].is_leaf()) continue;
            const uint32_t depth = data.depth + 1;
            const uint32_t bits = src.root[data.src_id].inner.dim_offset_flag;
            const uint32_t off = (bits & (uint32_t) kdtree::node_t::mask_children) >> 3;
            root[data.dst_id].inner.dim_offset_flag = curr << 3;
            root[data.dst_id].inner.dim_offset_flag |= bits & (uint32_t) kdtree::node_t::mask_axis;
            bstack.push(bdata_t(off, curr++, depth));
            bstack.push(bdata_t(off + 1, curr++, depth));
        }
    }

    /* Set the results */
    memcpy(acc, src.acc, sizeof(rt::wald_tri_t) * src.tri_n);
    memcpy(ids, src.ids, sizeof(kdtree::tri_id_t) * src.id_n);
    dst.id_n = src.id_n;
    dst.tri_n = src.tri_n;
    dst.node_n = src.node_n;
    dst.root = root;
    dst.acc = acc;
    dst.ids = ids;
}

