#include <cstdio>
using namespace std;

#include "util.h"
#include "vpr_utils.h"
#include "vpr_types.h"
#include "globals.h"
#include "route_common.h"
#include "route_tree_timing.h"
#include "route_timing.h"
#include "profile_lookahead.h"
#include <cassert>
#include <cmath>

/* This module keeps track of the partial routing tree for timing-driven     *
 * routing.  The normal traceback structure doesn't provide enough info      *
 * about the partial routing during timing-driven routing, so the routines   *
 * in this module are used to keep a tree representation of the partial      *
 * routing during timing-driven routing.  This allows rapid incremental      *
 * timing analysis.  The net_delay module does timing analysis in one step   *
 * (not incrementally as pieces of the routing are added).  I could probably *
 * one day remove a lot of net_delay.c and call the corresponding routines   *
 * here, but it's useful to have a from-scratch delay calculator to check    *
 * the results of this one.                                                  */

/********************** Variables local to this module ***********************/

/* Array below allows mapping from any rr_node to any rt_node currently in   *
 * the rt_tree.                                                              */

static t_rt_node **rr_node_to_rt_node = NULL; /* [0..num_rr_nodes-1] */

/* Frees lists for fast addition and deletion of nodes and edges. */

static t_rt_node *rt_node_free_list = NULL;
static t_linked_rt_edge *rt_edge_free_list = NULL;

/********************** Subroutines local to this module *********************/

static t_rt_node *alloc_rt_node(void);

static void free_rt_node(t_rt_node * rt_node);

static t_linked_rt_edge *alloc_linked_rt_edge(void);

static void free_linked_rt_edge(t_linked_rt_edge * rt_edge);

static t_rt_node *add_path_to_route_tree(struct s_heap *hptr,
		t_rt_node ** sink_rt_node_ptr, bool lookahead_eval, float target_criticality);

static void load_new_path_R_upstream(t_rt_node * start_of_new_path_rt_node);

static t_rt_node *update_unbuffered_ancestors_C_downstream(
		t_rt_node * start_of_new_path_rt_node);

static void load_rt_subtree_Tdel(t_rt_node * subtree_rt_root, float Tarrival);

/************************** Subroutine definitions ***************************/

void alloc_route_tree_timing_structs(void) {

	/* Allocates any structures needed to build the routing trees. */

	if (rr_node_to_rt_node != NULL || rt_node_free_list != NULL
			|| rt_node_free_list != NULL) {
			vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, 
				"in alloc_route_tree_timing_structs: old structures already exist.\n");
	}

	rr_node_to_rt_node = (t_rt_node **) my_malloc(
			num_rr_nodes * sizeof(t_rt_node *));
}

void free_route_tree_timing_structs(void) {

	/* Frees the structures needed to build routing trees, and really frees      *
	 * (i.e. calls free) all the data on the free lists.                         */

	t_rt_node *rt_node, *next_node;
	t_linked_rt_edge *rt_edge, *next_edge;

	free(rr_node_to_rt_node);
	rr_node_to_rt_node = NULL;

	rt_node = rt_node_free_list;

	while (rt_node != NULL) {
		next_node = rt_node->u.next;
		free(rt_node);
		rt_node = next_node;
	}

	rt_node_free_list = NULL;

	rt_edge = rt_edge_free_list;

	while (rt_edge != NULL) {
		next_edge = rt_edge->next;
		free(rt_edge);
		rt_edge = next_edge;
	}

	rt_edge_free_list = NULL;
}

static t_rt_node *
alloc_rt_node(void) {

	/* Allocates a new rt_node, from the free list if possible, from the free   *
	 * store otherwise.                                                         */

	t_rt_node *rt_node;

	rt_node = rt_node_free_list;

	if (rt_node != NULL) {
		rt_node_free_list = rt_node->u.next;
	} else {
		rt_node = (t_rt_node *) my_malloc(sizeof(t_rt_node));
	}

	return (rt_node);
}

static void free_rt_node(t_rt_node * rt_node) {

	/* Adds rt_node to the proper free list.          */

	rt_node->u.next = rt_node_free_list;
	rt_node_free_list = rt_node;
}

static t_linked_rt_edge *
alloc_linked_rt_edge(void) {

	/* Allocates a new linked_rt_edge, from the free list if possible, from the  *
	 * free store otherwise.                                                     */

	t_linked_rt_edge *linked_rt_edge;

	linked_rt_edge = rt_edge_free_list;

	if (linked_rt_edge != NULL) {
		rt_edge_free_list = linked_rt_edge->next;
	} else {
		linked_rt_edge = (t_linked_rt_edge *) my_malloc(
				sizeof(t_linked_rt_edge));
	}

	return (linked_rt_edge);
}

static void free_linked_rt_edge(t_linked_rt_edge * rt_edge) {

	/* Adds the rt_edge to the rt_edge free list.                       */

	rt_edge->next = rt_edge_free_list;
	rt_edge_free_list = rt_edge;
}

t_rt_node *
init_route_tree_to_source(int inet) {

	/* Initializes the routing tree to just the net source, and returns the root *
	 * node of the rt_tree (which is just the net source).                       */

	t_rt_node *rt_root;
	int inode;

	rt_root = alloc_rt_node();
	rt_root->u.child_list = NULL;
	rt_root->parent_node = NULL;
	rt_root->parent_switch = OPEN;
	rt_root->re_expand = true;

	inode = net_rr_terminals[inet][0]; /* Net source */

	rt_root->inode = inode;
	rt_root->C_downstream = rr_node[inode].C;
	rt_root->R_upstream = rr_node[inode].R;
	rt_root->Tdel = 0.5 * rr_node[inode].R * rr_node[inode].C;
	rr_node_to_rt_node[inode] = rt_root;

	return (rt_root);
}

t_rt_node *
update_route_tree(struct s_heap * hptr, bool lookahead_eval, float target_criticality) {

	/* Adds the most recently finished wire segment to the routing tree, and    *
	 * updates the Tdel, etc. numbers for the rest of the routing tree.  hptr   *
	 * is the heap pointer of the SINK that was reached.  This routine returns  *
	 * a pointer to the rt_node of the SINK that it adds to the routing.        */

	t_rt_node *start_of_new_path_rt_node, *sink_rt_node;
	t_rt_node *unbuffered_subtree_rt_root, *subtree_parent_rt_node;
	float Tdel_start;
	short iswitch;

	start_of_new_path_rt_node = add_path_to_route_tree(hptr, &sink_rt_node, lookahead_eval, target_criticality);
	load_new_path_R_upstream(start_of_new_path_rt_node);
	unbuffered_subtree_rt_root = update_unbuffered_ancestors_C_downstream(
			start_of_new_path_rt_node);

	subtree_parent_rt_node = unbuffered_subtree_rt_root->parent_node;

	if (subtree_parent_rt_node != NULL) { /* Parent exists. */
		Tdel_start = subtree_parent_rt_node->Tdel;
		iswitch = unbuffered_subtree_rt_root->parent_switch;
		Tdel_start += g_rr_switch_inf[iswitch].R
				* unbuffered_subtree_rt_root->C_downstream;
		Tdel_start += g_rr_switch_inf[iswitch].Tdel;
	} else { /* Subtree starts at SOURCE */
		Tdel_start = 0.;
	}

	load_rt_subtree_Tdel(unbuffered_subtree_rt_root, Tdel_start);

	return (sink_rt_node);
}

#if LOOKAHEADBYHISTORY == 1
/*
 * util function called by add_path_to_route_tree
 */
static void get_rt_subtree_bb_coord (int inode, int *bb_coord_x, int *bb_coord_y) {
    int type = rr_node[inode].type;
    int dir = rr_node[inode].get_direction();
    int xhigh = rr_node[inode].get_xhigh();
    int xlow = rr_node[inode].get_xlow();
    int yhigh = rr_node[inode].get_yhigh();
    int ylow = rr_node[inode].get_ylow();
    if (type == CHANX || type == CHANY) {
        if (dir == INC_DIRECTION) {
            *bb_coord_x = xlow;
            *bb_coord_x = ylow;
        } else if (dir == DEC_DIRECTION) {
            *bb_coord_x = xlow;
            *bb_coord_y = ylow;
        } else {
            // Bi-directional
            *bb_coord_x = (xhigh + xlow) / 2;
            *bb_coord_y = (yhigh + ylow) / 2;
        }
    } else {
        // OPIN
        *bb_coord_x = (xhigh + xlow) / 2;
        *bb_coord_y = (yhigh + ylow) / 2;
    }
}
#endif
static t_rt_node *
add_path_to_route_tree(struct s_heap *hptr, t_rt_node ** sink_rt_node_ptr, bool lookahead_eval, float target_criticality) {

	/* Adds the most recent wire segment, ending at the SINK indicated by hptr, *
	 * to the routing tree.  It returns the first (most upstream) new rt_node,  *
	 * and (via a pointer) the rt_node of the new SINK.                         */

	int inode, remaining_connections_to_sink, no_route_throughs;
	short iedge, iswitch;
	float C_downstream;
	t_rt_node *rt_node, *downstream_rt_node, *sink_rt_node;
	t_linked_rt_edge *linked_rt_edge;

	inode = hptr->index;
    int target_node = inode;
    float actual_tot_cost = 0;
    actual_tot_cost += 0;
    if (lookahead_eval) {
        assert(hptr->cost == hptr->backward_path_cost);
    }
    actual_tot_cost = hptr->backward_path_cost;
    float actual_Tdel = hptr->back_Tdel;
    actual_Tdel += 0;
#ifdef DEBUG
	if (rr_node[inode].type != SINK) {
		vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, 
			"in add_path_to_route_tree. Expected type = SINK (%d).\n"
			"Got type = %d.",  SINK, rr_node[inode].type);
	}
#endif

	remaining_connections_to_sink = rr_node_route_inf[inode].target_flag;
	sink_rt_node = alloc_rt_node();
	sink_rt_node->u.child_list = NULL;
	sink_rt_node->inode = inode;
	C_downstream = rr_node[inode].C;
	sink_rt_node->C_downstream = C_downstream;
	rr_node_to_rt_node[inode] = sink_rt_node;

	/* In the code below I'm marking SINKs and IPINs as not to be re-expanded.  *
	 * Undefine NO_ROUTE_THROUGHS if you want route-throughs or ipin doglegs.   *
	 * It makes the code more efficient (though not vastly) to prune this way   *
	 * when there aren't route-throughs or ipin doglegs.                        */

#define NO_ROUTE_THROUGHS 1	/* Can't route through unused CLB outputs */
	no_route_throughs = 1;
	if (no_route_throughs == 1)
		sink_rt_node->re_expand = false;
	else {
		if (remaining_connections_to_sink == 0) { /* Usual case */
			sink_rt_node->re_expand = true;
		}

		/* Weird case.  This net connects several times to the same SINK.  Thus I   *
		 * can't re_expand this node as part of the partial routing for subsequent  *
		 * connections, since I need to reach it again via another path.            */

		else {
			sink_rt_node->re_expand = false;
		}
	}

	/* Now do it's predecessor. */
	downstream_rt_node = sink_rt_node;
	inode = hptr->u.prev_node;
	iedge = hptr->prev_edge;
	iswitch = rr_node[inode].switches[iedge];

	/* For all "new" nodes in the path */
    int new_nodes_count = 0;
    float new_nodes_dev = 0;
    new_nodes_count += 0;
    new_nodes_dev += 0;
    float new_nodes_abs_dev = 0;
    new_nodes_abs_dev += 0;

    float total_Tdel = rr_node_route_inf[inode].back_Tdel;
    total_Tdel += 0.;
    // used to get the Tdel eval for wire only
    int furthest_wire_inode = -1;
	while (rr_node_route_inf[inode].prev_node != NO_PREVIOUS) {
        if (rr_node[inode].type == CHANX
         || rr_node[inode].type == CHANY)
            furthest_wire_inode = inode;
        new_nodes_count ++;
        if (lookahead_eval) {
#if NETWISELOOKAHEADEVAL == 1 || DEPTHWISELOOKAHEADEVAL == 1
            float estimated_future_cost, c_downstream, basecost = 0;
            estimated_future_cost = get_timing_driven_future_Tdel(inode, target_node, &c_downstream, &basecost);
            float actual_future_cost = total_Tdel - rr_node_route_inf[inode].back_Tdel;
            estimated_future_cost += 0.0;
            actual_future_cost += 0.0;
#endif
#if NETWISELOOKAHEADEVAL == 1
            node_on_path ++;
            if ( actual_future_cost != 0 ) {
                estimated_cost_deviation += (estimated_future_cost / actual_future_cost - 1);
                estimated_cost_deviation_abs += abs(estimated_future_cost / actual_future_cost - 1);
            }
#endif
#if DEPTHWISELOOKAHEADEVAL == 1
            /*
            if (actual_future_cost != 0) {
                new_nodes_dev += (estimated_future_cost / total_Tdel - 1);
                new_nodes_abs_dev += abs(estimated_future_cost / total_Tdel - 1);
            }
            */
#endif
        }
		linked_rt_edge = alloc_linked_rt_edge();
		linked_rt_edge->child = downstream_rt_node;
		linked_rt_edge->iswitch = iswitch;
		linked_rt_edge->next = NULL;

		rt_node = alloc_rt_node();
		downstream_rt_node->parent_node = rt_node;
		downstream_rt_node->parent_switch = iswitch;

		rt_node->u.child_list = linked_rt_edge;
		rt_node->inode = inode;

		if (g_rr_switch_inf[iswitch].buffered == false)
			C_downstream += rr_node[inode].C;
		else
			C_downstream = rr_node[inode].C;

		rt_node->C_downstream = C_downstream;
		rr_node_to_rt_node[inode] = rt_node;

		if (no_route_throughs == 1)
			if (rr_node[inode].type == IPIN)
				rt_node->re_expand = false;
			else
				rt_node->re_expand = true;

		else {
			if (remaining_connections_to_sink == 0) { /* Normal case */
				rt_node->re_expand = true;
			} else { /* This is the IPIN before a multiply-connected SINK */
				rt_node->re_expand = false;

				/* Reset flag so wire segments get reused */

				remaining_connections_to_sink = 0;
			}
		}

		downstream_rt_node = rt_node;
		iedge = rr_node_route_inf[inode].prev_edge;
		inode = rr_node_route_inf[inode].prev_node;
		iswitch = rr_node[inode].switches[iedge];
	}
    // XXX: only print out for critical path
#if PRINTCRITICALPATH == 1
    if (target_node == DB_TARGET_NODE && itry_share == DB_ITRY) {
        int iinode = hptr->u.prev_node;
        printf("CRITICAL PATH %d: back trace start\tcrit: %fNEW NODES %d\n", target_node, target_criticality, new_nodes_count);
        while (rr_node_route_inf[iinode].prev_node != NO_PREVIOUS) {
            // this is backtrace, so print in anti-direction order
            int ix_s, ix_e, iy_s, iy_e;
            get_unidir_seg_end(iinode, &ix_s, &iy_s);
            get_unidir_seg_start(iinode, &ix_e, &iy_e);
            int prev_iinode = rr_node_route_inf[iinode].prev_node;
            float bTdel = rr_node_route_inf[iinode].back_Tdel;
            float bbTdel = rr_node_route_inf[prev_iinode].back_Tdel;
            int wire_type = rr_indexed_data[rr_node[iinode].get_cost_index()].seg_index;
            float dummy, basecost = 0;
            printf("\tid:%d - %d\tstart(%d,%d)\tend(%d,%d)\tbackTdel:%einodeTdel:%e\tactual future Tdel:%.3f\test future Tdel:%.3f\n", 
                    iinode, wire_type, ix_s, iy_s, ix_e, iy_e,
                    bTdel, (bTdel - bbTdel), 
                    (actual_Tdel - bTdel) * pow(10, 10), 
                    get_timing_driven_future_Tdel(iinode, target_node, &dummy, &basecost) * pow(10, 10));
            iinode = prev_iinode;
        }
    }
#endif
	/* Inode is the join point to the old routing */
    if (rr_node[inode].type == CHANX
     || rr_node[inode].type == CHANY)
        furthest_wire_inode = inode;
    if (furthest_wire_inode == -1)
        furthest_wire_inode = target_node;
	rt_node = rr_node_to_rt_node[inode];

	linked_rt_edge = alloc_linked_rt_edge();
	linked_rt_edge->child = downstream_rt_node;
	linked_rt_edge->iswitch = iswitch;
	linked_rt_edge->next = rt_node->u.child_list;
	rt_node->u.child_list = linked_rt_edge;

	downstream_rt_node->parent_node = rt_node;
	downstream_rt_node->parent_switch = iswitch;

    new_nodes_count ++ ;
    // new_nodes_count ++ / node_on_path ++ accouts for the intersection node
    //if (new_nodes_count == 14)
    //    printf("TARGET NODE %d\n", target_node);

    if (lookahead_eval){
#if NETWISELOOKAHEADEVAL == 1 || DEPTHWISELOOKAHEADEVAL == 1
        /*
        float estimated_future_cost = rr_node_route_inf[inode].path_cost 
                                - rr_node_route_inf[inode].backward_path_cost;
        float actual_future_cost = actual_tot_cost 
                                - rr_node_route_inf[inode].backward_path_cost;
        */
        float estimated_future_cost, c_downstream, basecost = 0;
        estimated_future_cost = get_timing_driven_future_Tdel(furthest_wire_inode, target_node, &c_downstream, &basecost);
        float actual_future_cost = total_Tdel - rr_node_route_inf[furthest_wire_inode].back_Tdel;

#endif
#if NETWISELOOKAHEADEVAL == 1
        // netwise lookahead_eval finishing up
        node_on_path ++;
        if ( actual_future_cost != 0 ) {
            estimated_cost_deviation += (estimated_future_cost / actual_future_cost - 1);
            estimated_cost_deviation_abs += abs(estimated_future_cost / actual_future_cost - 1);
        }
#endif
#if DEPTHWISELOOKAHEADEVAL == 1
        // depthwise lookahead_eval setting up
        if (subtree_count.count(new_nodes_count) <= 0) {
            subtree_count[new_nodes_count] = 0;
            subtree_size_avg[new_nodes_count] = 0;
            subtree_est_dev_avg[new_nodes_count] = 0;
            subtree_est_dev_abs_avg[new_nodes_count] = 0;
        }
        if (actual_future_cost != 0) {
            new_nodes_dev += (estimated_future_cost / actual_future_cost - 1);
            new_nodes_abs_dev += abs(estimated_future_cost / actual_future_cost - 1);
        }
        subtree_count[new_nodes_count] ++;
        int tree_counter = subtree_count[new_nodes_count];
        // running avg
        // arithmetic avg
        //subtree_size_avg[new_nodes_count] = ((tree_counter - 1) * subtree_size_avg[new_nodes_count]
        //                                + subtree_size_avg[0]) / (float)tree_counter;
        // geometric avg
        if (subtree_size_avg[new_nodes_count] == 0) {
            subtree_size_avg[new_nodes_count] = subtree_size_avg[0];
            /*
            if (new_nodes_count == 19)
                printf("\nitry %d\tTARGET NODE %d\tsubtree count %d\tsubtree expanded nodes %f\n", itry_share, target_node, subtree_count[19], subtree_size_avg[0]);
            */
            if (target_node == DB_TARGET_NODE) {
                print_db_node_inf(DB_TARGET_NODE);
                print_db_node_inf(hptr->u.prev_node);
            }
        } else {
            float temp = pow(subtree_size_avg[new_nodes_count], (tree_counter - 1) / (float)tree_counter);
            subtree_size_avg[new_nodes_count] = temp * pow(subtree_size_avg[0], 1.0/(float)tree_counter);
        }
        float cur_dev = new_nodes_dev; // / new_nodes_count;
        /*
        if (cur_dev == -1) {
            printf("@@@@@@@\titry %d\ttarget_node %d\tnew nodes count %d\n", itry_share, target_node, new_nodes_count);
            assert(cur_dev != -1);
        }
        */
        if (cur_dev < -0.6 && new_nodes_count > 10)
            printf("\nXXXXX TARGET NODE %d\n\n", target_node);
        float cur_dev_abs = new_nodes_abs_dev / new_nodes_count;
        subtree_est_dev_avg[new_nodes_count] = ((tree_counter - 1) * subtree_est_dev_avg[new_nodes_count]
                                        + cur_dev) / (float)tree_counter;
        //subtree_est_dev_abs_avg[new_nodes_count] = ((tree_counter - 1) * subtree_est_dev_abs_avg[new_nodes_count]
        //                                + cur_dev_abs) / (float)tree_counter;
        if (subtree_est_dev_abs_avg[new_nodes_count] == 0) {
            subtree_est_dev_abs_avg[new_nodes_count] = cur_dev_abs;
        } else {
            float temp = pow(subtree_est_dev_abs_avg[new_nodes_count], (tree_counter - 1) / (float)tree_counter);
            subtree_est_dev_abs_avg[new_nodes_count] = temp * pow(cur_dev_abs, 1.0/(float)tree_counter);
        }
#endif
    }
	*sink_rt_node_ptr = sink_rt_node;
	return (downstream_rt_node);
}

static void load_new_path_R_upstream(t_rt_node * start_of_new_path_rt_node) {

	/* Sets the R_upstream values of all the nodes in the new path to the       *
	 * correct value.                                                           */

	float R_upstream;
	int inode;
	short iswitch;
	t_rt_node *rt_node, *parent_rt_node;
	t_linked_rt_edge *linked_rt_edge;

	rt_node = start_of_new_path_rt_node;
	iswitch = rt_node->parent_switch;
	inode = rt_node->inode;
	parent_rt_node = rt_node->parent_node;

	R_upstream = g_rr_switch_inf[iswitch].R + rr_node[inode].R;

	if (g_rr_switch_inf[iswitch].buffered == false)
		R_upstream += parent_rt_node->R_upstream;

	rt_node->R_upstream = R_upstream;

	/* Note:  the traversal below makes use of the fact that this new path      *
	 * really is a path (not a tree with branches) to do a traversal without    *
	 * recursion, etc.                                                          */

	linked_rt_edge = rt_node->u.child_list;

	while (linked_rt_edge != NULL) { /* While SINK not reached. */

#ifdef DEBUG
		if (linked_rt_edge->next != NULL) {
			vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, 
				"in load_new_path_R_upstream: new routing addition is a tree (not a path).\n");
		}
#endif

		rt_node = linked_rt_edge->child;
		iswitch = linked_rt_edge->iswitch;
		inode = rt_node->inode;

		if (g_rr_switch_inf[iswitch].buffered)
			R_upstream = g_rr_switch_inf[iswitch].R + rr_node[inode].R;
		else
			R_upstream += g_rr_switch_inf[iswitch].R + rr_node[inode].R;

		rt_node->R_upstream = R_upstream;
		linked_rt_edge = rt_node->u.child_list;
	}
}

static t_rt_node *
update_unbuffered_ancestors_C_downstream(t_rt_node * start_of_new_path_rt_node) {

	/* Updates the C_downstream values for the ancestors of the new path.  Once *
	 * a buffered switch is found amongst the ancestors, no more ancestors are  *
	 * affected.  Returns the root of the "unbuffered subtree" whose Tdel       *
	 * values are affected by the new path's addition.                          */

	t_rt_node *rt_node, *parent_rt_node;
	short iswitch;
	float C_downstream_addition;

	rt_node = start_of_new_path_rt_node;
	C_downstream_addition = rt_node->C_downstream;
	parent_rt_node = rt_node->parent_node;
	iswitch = rt_node->parent_switch;

	while (parent_rt_node != NULL && g_rr_switch_inf[iswitch].buffered == false) {
		rt_node = parent_rt_node;
		rt_node->C_downstream += C_downstream_addition;
		parent_rt_node = rt_node->parent_node;
		iswitch = rt_node->parent_switch;
	}

	return (rt_node);
}

static void load_rt_subtree_Tdel(t_rt_node * subtree_rt_root, float Tarrival) {

	/* Updates the Tdel values of the subtree rooted at subtree_rt_root by      *
	 * by calling itself recursively.  The C_downstream values of all the nodes *
	 * must be correct before this routine is called.  Tarrival is the time at  *
	 * at which the signal arrives at this node's *input*.                      */

	int inode;
	short iswitch;
	t_rt_node *child_node;
	t_linked_rt_edge *linked_rt_edge;
	float Tdel, Tchild;

	inode = subtree_rt_root->inode;

	/* Assuming the downstream connections are, on average, connected halfway    *
	 * along a wire segment's length.  See discussion in net_delay.c if you want *
	 * to change this.                                                           */

	Tdel = Tarrival + 0.5 * subtree_rt_root->C_downstream * rr_node[inode].R;
	subtree_rt_root->Tdel = Tdel;

	/* Now expand the children of this node to load their Tdel values (depth-   *
	 * first pre-order traversal).                                              */

	linked_rt_edge = subtree_rt_root->u.child_list;

	while (linked_rt_edge != NULL) {
		iswitch = linked_rt_edge->iswitch;
		child_node = linked_rt_edge->child;

		Tchild = Tdel + g_rr_switch_inf[iswitch].R * child_node->C_downstream;
		Tchild += g_rr_switch_inf[iswitch].Tdel; /* Intrinsic switch delay. */
		load_rt_subtree_Tdel(child_node, Tchild);

		linked_rt_edge = linked_rt_edge->next;
	}
}

void free_route_tree(t_rt_node * rt_node) {

	/* Puts the rt_nodes and edges in the tree rooted at rt_node back on the    *
	 * free lists.  Recursive, depth-first post-order traversal.                */

	t_rt_node *child_node;
	t_linked_rt_edge *rt_edge, *next_edge;

	rt_edge = rt_node->u.child_list;

	while (rt_edge != NULL) { /* For all children */
		child_node = rt_edge->child;
		free_route_tree(child_node);
		next_edge = rt_edge->next;
		free_linked_rt_edge(rt_edge);
		rt_edge = next_edge;
	}

	free_rt_node(rt_node);
}

void update_net_delays_from_route_tree(float *net_delay,
		t_rt_node ** rt_node_of_sink, int inet) {

	/* Goes through all the sinks of this net and copies their delay values from *
	 * the route_tree to the net_delay array.                                    */

	unsigned int isink;
	t_rt_node *sink_rt_node;

	for (isink = 1; isink < g_clbs_nlist.net[inet].pins.size(); isink++) {
		sink_rt_node = rt_node_of_sink[isink];
		net_delay[isink] = sink_rt_node->Tdel;
	}
}