tg.c

This program is free software you can redistribute it and/or modify it under the terms of the GN

/************************************************************************
  This program is part of the
	OpenMP Source Code Repository

	http://www.pcg.ull.es/OmpSCR/
	e-mail: [e-mail]

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  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 
  (LICENSE file) along with this program; if not, write to
  the Free Software Foundation, Inc., 59 Temple Place, Suite 330, 
  Boston, MA  02111-1307  USA
	
**************************************************************************/
/*---------------------------------------------------------------------------
 * Tg v 3.0
 *
 * tg.c	--  	Performance Evaluator
 * 		Task graph ADT definition
 * v 2.2
 *
 *		NOTE: This file has chage completly from the version 1.0
 *			'cause all the interface and ADT is different
 *
 * Copyright (C) 1999, Arturo Gonz醠ez-Escribano
 *
 * v 2.3
 *	Copyright (C) 2004, Arturo Gonz醠ez-Escribano
 *	Adapted by Arturo Gonz醠ez-Escribano for OmpSCR, Jun 2004
 *	(Portable allocation statements)
 *
 *---------------------------------------------------------------------------
 */
#define TG_C

#include <stdio.h>
#include "tg.h"
#include "AError.h"


/*---------------------------------------------------------------------------
 * 1. PUBLIC TASK INTERFACE FUNCTIONS:
 *---------------------------------------------------------------------------
 */



/* --------------------------------------------------------------------
 * INITIALIZE GRAPH
 */
tg	tg_init(int resources)
{
	tg	graph = NULL;

	/* 1. CHECKING INPUT */
	if (resources < 0)
		Asystem_error("tg_init","Improper number of resources input","");

	/* 2. CREATING SPACE FOR THE GRAPH STRUCTURE */	
	graph = (tg) malloc( sizeof(tg_graph) ); 
	if ( graph == NULL ) {
		Asystem_error("tg_init", "Not enough memory", "graph");
		}

	/* 3. FILLING FIELDS */
	graph->tasknum = 0;
	graph->root = TG_NULLID;
	graph->resnum = resources;
	graph->maxid = TG_NULLID;
	graph->idarray = NULL;

	/* 4. END */
	return graph;
}




/* --------------------------------------------------------------------
 * DELETE GRAPH
 */
void tg_delete(tg graph)
{
	int	count;

	/* 0. IF NULL POINTER, END */
	if (graph==NULL) return;

	/* 1. DELETING ALL TASK */
	for (count = 0;
		count <= tg_maxid(graph);
		count ++)
		tg_del_node(graph, count);

	/* 2. FREEING INTERNAL SPACE */
	free(graph->idarray); graph->idarray=NULL;
	free(graph); graph=NULL;

	/* 3. END */
}



/* --------------------------------------------------------------------
 * DUPLICATE THE GRAPH
 */
tg tg_dup(tg graph)
{
	tg		g2;
	int		node;
	task_list	arcs=NULL;
	int		elements, count;
	int		resource;

	/* 1. INITIALIZE THE NEW GRAPH */
	g2 = tg_init(tg_resnum(graph));

	/* 2. FOR ALL NODES ON THE OLD ONE */
	for (node = 0;
		node <= tg_maxid(graph);
		node ++ )
		{
		/* 2.1. ... THAT EXISTS ... */
		if (!tg_id(graph, node))
			continue;

		/* 2.2. CREATE NODE */
		tg_add_node(g2, node);

		/* 2.3. COPY INFORMATION */
		for (resource = 0;
			resource < tg_resnum(graph);
			resource ++ )
			{
			tg_set_resource(g2, node, resource, tg_get_resource(graph, node, resource));
			}

		/* 2.4. CREATE ARCS FOR SUCCESORS */
		elements = tg_succ_num(graph, node);
		arcs = (task_list) malloc( sizeof(tg_task) * elements); 
		if ( arcs == NULL ) { 
			Asystem_error("tg_dup", "Not enough memory", "arcs");
			}
		memcpy(arcs,tg_succ(graph,node), sizeof(tg_task)*elements );
		
		for (count = 0;
			count < elements;
			count ++ )
			{
			/* 2.4.1. IF SUCCESOR DOES NOT EXIST YET, CREATE */
			if (!tg_id(g2, arcs[count]))
				tg_add_node(g2, arcs[count]);

			/* 2.4.2. ADD ARC */
			tg_add_arc(g2, node, arcs[count]);
			}
		free(arcs); arcs=NULL;
		}

	/* 3. SET ROOT */
	tg_set_root(g2, tg_root(graph));

	/* 4. RETURN THE NEW GRAPH */
	return g2;
}


/* --------------------------------------------------------------------
 * COPY RESOURCES VALUES FROM A GRAPH TO ANOTHER
 */
void tg_dup_resources(tg g1, tg g2)
{
	int	count, resource;

	/* 0. CHECK THE RESOURCE NUMBERS ON THE GRAPHS */
	if (tg_resnum(g1) != tg_resnum(g2))
		Asystem_error("tg_dup_resources","Different resnum","");

	/* 1. FOR ALL TASKS ON THE ORIGIN GRAPH */
	for (count = 0;
		count <= tg_maxid(g1);
		count ++ )
		{
		/* 1.1. ... THAT EXISTS ON THE TWO GRAPHS ... */
		if (!tg_id(g1, count) || !tg_id(g2,count))
			continue;

		/* 1.2. COPY RESOURCE VALUES */
		for (resource = 0;
			resource < tg_resnum(g1);
			resource ++ )
			{
			tg_set_resource(g2, count, resource, tg_get_resource(g1, count, resource));
			}
		}

	/* 2. END */	
}



/* --------------------------------------------------------------------
 * ADD NODE
 */
Bool tg_add_node(tg graph, tg_task id)
{
	tg_ptask	ptask=NULL;
	int		count;

	/* 0. CHECKING THE IDENTIFIER */
	if (tg_id(graph, id))
		return FALSE;

	/* 1. CREATING SPACE FOR THE TASK */
	ptask = (tg_ptask) malloc( sizeof(tg_tsk) ); 
	if ( ptask == NULL ) { 
		Asystem_error("tg_add_node", "Not enough memory", "ptask");
		}

	/* 2.1. ADDING ONE TO THE NUMBER OF TASKS */
	graph->tasknum ++;

	/* 2.2. IF id IS GREATER THAN maxid */
	if (id > graph->maxid)
		{
 		/* 2.1. ASK FOR MORE SPACE */
		graph->idarray = (ptask_list) realloc(graph->idarray, sizeof(tg_ptask)*(id+1));
		if ( graph->idarray == NULL ) {
			Asystem_error("tg_add_node","Not enough memory", "idarray" );
			}

		/* 2.2. INITIALIZE THE NEW POSITIONS */
		for (count = graph->maxid + 1;
			count < id;
			count ++ )
			{
			graph->idarray[count] = NULL;
			}

		/* 2.3. CHANGE TO THE NEW maxid */
		graph->maxid = id;
		}
	graph->idarray[id] = ptask;

	/* 3. SETTING THE TASK IDENTIFICATION */
	ptask->tid = id;

	/* 5. INITIALIZING TASK FIELDS */
	ptask->resour = NULL;
	ptask->resour = (double *) malloc( sizeof(double) * ( graph->resnum ));
	if ( ptask->resour == NULL ) { 
		Asystem_error("tg_add_node", "Not enough memory", "resour");
		}
	for (count = 0;
		count < graph->resnum;
		count++ )
		{
		ptask->resour[ count ] = 0.0;
		}
	ptask->prenum = 0;
	ptask->pred = NULL;
	ptask->succnum = 0;
	ptask->succ = NULL;

	return TRUE;
}






/* --------------------------------------------------------------------
 * DELETE NODE
 */
void tg_del_node(tg graph, tg_task task)
{
	int		count;
	task_list	todelete=NULL;
	int		elements;

	/* 0. CHECKING IDENTIFICATION */
	if (!tg_id(graph, task))
		return;

	/* 1. DELETING ARCS */
	elements = tg_pred_num(graph,task);
	todelete = (task_list) malloc( sizeof(tg_task) * elements ); 
	if ( todelete == NULL ) { 
		Asystem_error("tg_del_node", "Not enough memory", "todelete 1");
		}
	memcpy(todelete, tg_pred(graph,task), sizeof(tg_task)*elements);

	for (count=0;
		count < elements;
		count ++ )
		{
		tg_del_arc(graph, todelete[count], task);
		}
	free(todelete); todelete=NULL;

	elements = tg_succ_num(graph,task);
	todelete = (task_list) malloc( sizeof(tg_task) * elements ); 
	if ( todelete == NULL ) { 
		Asystem_error("tg_del_node", "Not enough memory", "todelete 2");
		}
	memcpy(todelete, tg_succ(graph,task), sizeof(tg_task)*elements);

	for (count=0;
		count < elements;
		count ++ )
		{
		tg_del_arc(graph, task, todelete[count]);
		}
	free(todelete); todelete=NULL;

	/* 2. FREEING INTERNAL SPACE */
	free(tgp(graph,task)->resour); tgp(graph,task)->resour = NULL;

	/* 3. FREEING TASK SPACE */
	free(tgp(graph,task)); tgp(graph,task) = NULL;

	/* 4. CHANGING GRAPH STRUCTURE */
	graph->tasknum --;
	graph->idarray[task] = NULL;
	if (task == graph->maxid)
		graph->maxid --;	/* Innecesary reallocate */

	/* 5. END */
}


/* --------------------------------------------------------------------
 * ADD ARC
 */
void tg_add_arc(tg graph, tg_task task_from, tg_task task_to)
{
	tg_ptask	pfrom, pto;

	/* 1. CHECK TASKS IDENTIFIERS */
	if (!tg_id(graph, task_from) || !tg_id(graph,task_to)) 
		Asystem_error("tg_add_arc","Unknown task","Cheking task ids");

	/* 2. OBTAINING POINTERS */
	pfrom = tgp(graph, task_from);
	pto = tgp(graph, task_to);

	/* 3. IF ARC ALREADY EXISTS, RETURN */
	if (tg_arc(graph, task_from, task_to))
		return;

	/* 4. CREATING SPACE IN NODES */
	pfrom->succnum ++;
	pto->prenum ++;

	pfrom->succ = (task_list)realloc(pfrom->succ, sizeof(tg_task)*(pfrom->succnum));
	if ( pfrom->succ == NULL ) { 
		Asystem_error("tg_add_arc", "Not enough memory", "pfrom->succ");
		}
	pto->pred = (task_list)realloc(pto->pred, sizeof(tg_task)*(pto->prenum));
	if ( pto->pred == NULL ) { 
		Asystem_error("tg_add_arc", "Not enough memory", "pto->pred");
		}

	/* 5. INITIALIZATING POINTERS */
	pfrom->succ[ pfrom->succnum -1 ] = task_to;
	pto->pred[ pto->prenum -1 ] = task_from;
}



/* --------------------------------------------------------------------
 * DELETE ARC
 */
void tg_del_arc(tg graph, tg_task task_from, tg_task task_to)
{
	int	count;
	Bool	deleted;
	tg_ptask	pfrom, pto;

	/* 0. OBTAINING POINTERS */
	pfrom = tgp(graph, task_from);
	pto = tgp(graph, task_to);

	/* 1. IF ARC DOES NOT EXIST, RETURN */
	if (!tg_arc(graph, task_from, task_to))
		return;

	/* 2. CHANGING TO NODE STRUCTURE */
	/* 2.1. FOR ALL PRED, COMPARE UNTIL FIND THE ONE THAT MUST BE DELETED */
	for ( deleted = FALSE, count=0 ;
		count < pto->prenum;
		count ++ )
		{
		if ( ! deleted)
			{
			if ( task_from == pto->pred[count] )
				{
		/* 2.1.1. FINDED, CHANGE FLAG */
				deleted = TRUE;	
				}	
			}
		else
			{
		/* 2.1.2. MOVE ALL THE REST POINTERS BACK */
			pto->pred[count - 1] = pto->pred[count];
			}
		}
	
	/* 2.2. REALLOCATING IN FEW SPACE */
	pto->prenum --;
	pto->pred = (task_list)realloc(pto->pred, sizeof(tg_task)*(pto->prenum));
	if ( pto->pred == NULL ) { 
		Asystem_error("tg_del_arc", "Not enough memory", "pto->pred");
		}

	/* 3. CHANGING FROM NODE STRUCTURE */
	/* 3.1. FOR ALL SUCC, COMPARE UNTIL FIND THE ONE THAT MUST BE DELETED */
	for ( deleted = FALSE, count=0 ;
		count < pfrom->succnum;
		count ++ )
		{
		if ( ! deleted)
			{
			if ( task_to == pfrom->succ[count] )
				{
		/* 3.1.1. FINDED, CHANGE FLAG */
				deleted = TRUE;	
				}	
			}
		else
			{
		/* 3.1.2. MOVE ALL THE REST POINTERS BACK */
			pfrom->succ[count - 1] = pfrom->succ[count];
			}
		}

	/* 3.2. REALLOCATING IN FEW SPACE */
	pfrom->succnum --;
	pfrom->succ = (task_list)realloc(pfrom->succ, sizeof(tg_task)*(pfrom->succnum));
	if ( pfrom->succ == NULL ) { 
		Asystem_error("tg_del_arc", "Not enough memory", "pfrom->succ");
		}


	/* 4. END */
}



/* --------------------------------------------------------------------
 * CHANGES TASK IDENTIFICATION
 */
Bool tg_change_id(tg graph, tg_task task, tg_task id)
{
	tg_task		target;
	int 		count, count2;

	/* 1. IF id EXISTS OR task DOES NOT, RETURN FALSE */
	if (tg_id(graph,id) || !tg_id(graph,task))
		return FALSE;

	/* 2. IF id IS GREATER THAN maxid */
	if (id > graph->maxid)
		{
 		/* 2.1. ASK FOR MORE SPACE */
		graph->idarray = (ptask_list)realloc(graph->idarray, sizeof(tg_ptask)*(id+1));
		if ( graph->idarray == NULL ) { 
			Asystem_error("tg_change_id","Not enough memory", "idarray");
			}

		/* 2.2. INITIALIZE THE NEW POSITIONS */
		for (count = graph->maxid + 1;
			count < id;
			count ++ )
			{
			graph->idarray[count] = NULL;
			}