gs_dag_basic.c

Go to the documentation of this file.

/********************************************************************/
/*                          gs_dag_basic.c                          */
/*           the basic functions for the GridSolve DAG API          */
/*                       Yinan Li, 05/17/2007                       */
/********************************************************************/


#include "gs_dag.h"
#include "gs_sequence.h"

static int seq_id = 0;


GS_DAG_t *make_new_GS_DAG() {
    GS_DAG_t *new_dag;

    new_dag = (GS_DAG_t *) malloc(sizeof(GS_DAG_t));
    if (new_dag == NULL) return NULL;

    /* initialize the new DAG */
    new_dag->head_node = NULL;
    new_dag->tail_node = NULL;
    new_dag->head_dep = NULL;
    new_dag->tail_dep = NULL;
    new_dag->num_nodes = 0;
    new_dag->num_deps = 0;
    new_dag->max_sched_level = 0;
    new_dag->analyzed = 0;

    return new_dag;
}


int insert_node_GS_DAG(GS_DAG_t *dag, char *func_name,
    gs_va_list *arg_list, grpc_arg_stack *arg_stack) {
    GS_DAG_Node_t *new_node;
    grpc_error_t status;
    int ret_val;
    

    if (dag == NULL) return -1;

    if (func_name == NULL) return -1;

    if (arg_list == NULL && arg_stack == NULL) return -1;
    
    /* create a new DAG node */
    new_node = (GS_DAG_Node_t *) malloc(sizeof(GS_DAG_Node_t));
    if (new_node == NULL) {
        perror("malloc");
        return -1;
    }

    /* ----------------------- initialize the new node ---------------------- */
    new_node->func_name = func_name;
    new_node->server = NULL;
    new_node->state = INITIAL;
    new_node->sched_level = 0;
    new_node->arg_list = arg_list;
    new_node->arg_stack = arg_stack;

    new_node->handle = (grpc_function_handle_t *)
        malloc(sizeof(grpc_function_handle_t));
    if (new_node->handle == NULL) {
        perror("malloc");
        exit(1);
    }
    
    /* create a default function handle for the new node */
    status = grpc_function_handle_default(
    new_node->handle, new_node->func_name);
    if (status != GRPC_NO_ERROR) {
        fprintf(stderr, "ERROR: %s\n", grpc_error_string(status));
        grpc_function_handle_destruct(new_node->handle);
        if (new_node->handle != NULL) free(new_node->handle);
        grpc_finalize();
        exit(1);
    }


    /* this will compute the sizes of all the non-scalar
       arguments and setup all the data pointers */
    if (new_node->arg_list == NULL) {
        if ((ret_val = gs_sender_compute_arg_sizes(
            NULL, new_node->arg_stack->args,
            new_node->handle->problem_desc,
            grpc_sequence_language, grpc_sequence_major)) < 0) {
            fprintf(stderr, "error computing argument sizes at client side\n");
            exit(1);
        }
        new_node->handle->problem_desc->size_computed = 1;
    }
    else if (new_node->arg_stack == NULL) {
        if ((ret_val = gs_sender_compute_arg_sizes(
            new_node->arg_list, NULL,
            new_node->handle->problem_desc,
            grpc_sequence_language, grpc_sequence_major)) < 0) {
            fprintf(stderr, "error computing argument sizes at client side\n");
            exit(1);
        }
        new_node->handle->problem_desc->size_computed = 1;
        new_node->handle->problem_desc->seq_id = seq_id++;
    }

    /* ---------------------------- insert into DAG ------------------------- */
    /* if there isn't any node in the current DAG */
    if (dag->num_nodes == 0) {
        dag->head_node = new_node;
        dag->tail_node = new_node;
        new_node->prev = NULL;
        new_node->next = NULL;
    } else {
        /* add the new node to the tail of the list */
        new_node->prev = dag->tail_node;
        new_node->next = NULL;
        dag->tail_node->next = new_node;
        dag->tail_node = new_node;
    }

    dag->num_nodes++;
    
    return 0;
}


int delete_node_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *node) {
    /* no node at all*/
    if (dag->num_nodes == 0) return -1;

    if (node == NULL) return -1;

    /* only one node exist */
    if (dag->num_nodes == 1 &&
        dag->head_node == node) {
        dag->head_node = NULL;
        dag->tail_node = NULL;
        free(node);
        dag->num_nodes--;
        return 0;
    }
    
    /* at least 2 nodes */
    
    /* the node is the head */
    if (dag->head_node == node) {
        node->next->prev = NULL;
        dag->head_node = node->next;
        free(node);
        dag->num_nodes--;
        return 0;
    }

    /* the node is the tail */
    if (dag->tail_node == node) {
        node->prev->next = NULL;
        dag->tail_node = node->prev;
        free(node);
        dag->num_nodes--;
        return 0;
    }
    
    /* the node is in the middle */
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
    dag->num_nodes--;

    return 0;
}


int insert_dep_GS_DAG(GS_DAG_t *dag,
    GS_DAG_Node_t *pnode, GS_DAG_Node_t *cnode, int type, 
    gs_argument_t *largp, gs_argument_t *rargp) {
    GS_DAG_Dep_t *new_dep;

    if (dag == NULL) return -1;

    if (pnode == NULL || cnode == NULL)
        return -1;


    /* create a new DAG dependency */
    new_dep = (GS_DAG_Dep_t *) malloc(sizeof(GS_DAG_Dep_t));
    if (new_dep == NULL) {
        perror("malloc");
        return -1;
    }

    new_dep->pnode = pnode;
    new_dep->cnode = cnode;
    new_dep->dep_type = type;
    new_dep->largp = largp;
    new_dep->rargp = rargp;
    new_dep->data_size = 0;

    /* if there isn't any dependency in the current DAG */
    if (dag->num_deps == 0) {
        dag->head_dep = new_dep;
        dag->tail_dep = new_dep;
        new_dep->prev = NULL;
        new_dep->next = NULL;
    } else {
        /* add the new dependency to the tail of the list */
        new_dep->prev = dag->tail_dep;
        new_dep->next = NULL;
        dag->tail_dep->next = new_dep;
        dag->tail_dep = new_dep;
    }

    dag->num_deps++;
    
    return 0;
}


int delete_dep_GS_DAG(GS_DAG_t *dag, GS_DAG_Dep_t *dep) {
    /* no dep at all*/
    if (dag->num_deps == 0) return -1;

    if (dep == NULL) return -1;

    /* only one dependency exist */
    if (dag->num_deps == 1 &&
        dag->head_dep == dep) {
        dag->head_dep = NULL;
        dag->tail_dep = NULL;
        free(dep);
        dag->num_deps--;
        return 0;
    }
    
    /* at least 2 dependencies */
    
    /* the dependency is the head */
    if (dag->head_dep == dep) {
        dep->next->prev = NULL;
        dag->head_dep = dep->next;
        free(dep);
        dag->num_deps--;
        return 0;
    }

    /* the dependency is the tail */
    if (dag->tail_dep == dep) {
        dep->prev->next = NULL;
        dag->tail_dep = dep->prev;
        free(dep);
        dag->num_deps--;
        return 0;
    }
    
    /* the depedency is in the middle */
    dep->prev->next = dep->next;
    dep->next->prev = dep->prev;
    free(dep);
    dag->num_deps--;

    return 0;
}


GS_DAG_Node_t *find_node_sched_GS_DAG(GS_DAG_t *dag, int sched_level) {
    GS_DAG_Node_t *nptr;

    if (dag == NULL || dag->num_nodes == 0) return NULL;

    for(nptr = dag->head_node; nptr != NULL; nptr = nptr->next) {
        /* the first node with specified 
           scheduling level is found */
        if (nptr->sched_level == sched_level)
            return nptr;
    }

    /* not found */
    return NULL;
}


GS_DAG_Node_t *find_node_pnode_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *pnode) {
    GS_DAG_Dep_t *dptr;
    
    if (dag == NULL || dag->num_deps == 0) return NULL;

    for(dptr = dag->head_dep; dptr != NULL; dptr = dptr->next) {
        /* the first dependency with 
           specified parent node is found */
        if (dptr->pnode == pnode)
            return dptr->cnode;
    }

    /* not found */
    return NULL;
}


GS_DAG_Dep_t *find_dep_pnode_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *pnode) {
    GS_DAG_Dep_t *dptr;
    
    if (dag == NULL || dag->num_deps == 0) return NULL;

    for(dptr = dag->head_dep; dptr != NULL; dptr = dptr->next) {
        /* the first dependency with 
           specified parent node is found */
        if (dptr->pnode == pnode)
            return dptr;
    }

    /* not found */
    return NULL;
}


int count_node_GS_DAG(GS_DAG_t *dag, int sched_level) {
    GS_DAG_Node_t *nptr;
    int count;

    if (dag == NULL || dag->num_nodes == 0) return 0;

    count = 0;
    for(nptr = dag->head_node; nptr != NULL; nptr = nptr->next) {
        if (nptr->sched_level == sched_level)
            count++;
    }
    
    return count;
}


int free_GS_DAG(GS_DAG_t *dag) {
    GS_DAG_Node_t *node;
    GS_DAG_Dep_t *dep;
    
    /* null or empty DAG */
    if (dag == NULL) return -1;

    node = dag->head_node;
    dep = dag->head_dep;
    
    /* delete each node */
    while (dag->num_nodes > 0) {
        delete_node_GS_DAG(dag, node);
        node = dag->head_node;
    }
    /* delete each dependency */
    while (dag->num_deps > 0) {
        delete_dep_GS_DAG(dag, dep);
        dep = dag->head_dep;
    }

    free(dag);

  return 0;
}