gs_dag_basic.c

Go to the documentation of this file.
00001 /********************************************************************/
00002 /*                          gs_dag_basic.c                          */
00003 /*           the basic functions for the GridSolve DAG API          */
00004 /*                       Yinan Li, 05/17/2007                       */
00005 /********************************************************************/
00006 
00007 
00008 #include "gs_dag.h"
00009 #include "gs_sequence.h"
00010 
00011 static int seq_id = 0;
00012 
00013 
00021 GS_DAG_t *make_new_GS_DAG() {
00022     GS_DAG_t *new_dag;
00023 
00024     new_dag = (GS_DAG_t *) malloc(sizeof(GS_DAG_t));
00025     if (new_dag == NULL) return NULL;
00026 
00027     /* initialize the new DAG */
00028     new_dag->head_node = NULL;
00029     new_dag->tail_node = NULL;
00030     new_dag->head_dep = NULL;
00031     new_dag->tail_dep = NULL;
00032     new_dag->num_nodes = 0;
00033     new_dag->num_deps = 0;
00034     new_dag->max_sched_level = 0;
00035     new_dag->analyzed = 0;
00036 
00037     return new_dag;
00038 }
00039 
00040 
00053 int insert_node_GS_DAG(GS_DAG_t *dag, char *func_name,
00054     gs_va_list *arg_list, grpc_arg_stack *arg_stack) {
00055     GS_DAG_Node_t *new_node;
00056     grpc_error_t status;
00057     int ret_val;
00058     
00059 
00060     if (dag == NULL) return -1;
00061 
00062     if (func_name == NULL) return -1;
00063 
00064     if (arg_list == NULL && arg_stack == NULL) return -1;
00065     
00066     /* create a new DAG node */
00067     new_node = (GS_DAG_Node_t *) malloc(sizeof(GS_DAG_Node_t));
00068     if (new_node == NULL) {
00069         perror("malloc");
00070         return -1;
00071     }
00072 
00073     /* ----------------------- initialize the new node ---------------------- */
00074     new_node->func_name = func_name;
00075     new_node->server = NULL;
00076     new_node->state = INITIAL;
00077     new_node->sched_level = 0;
00078     new_node->arg_list = arg_list;
00079     new_node->arg_stack = arg_stack;
00080 
00081     new_node->handle = (grpc_function_handle_t *)
00082         malloc(sizeof(grpc_function_handle_t));
00083     if (new_node->handle == NULL) {
00084         perror("malloc");
00085         exit(1);
00086     }
00087     
00088     /* create a default function handle for the new node */
00089     status = grpc_function_handle_default(
00090     new_node->handle, new_node->func_name);
00091     if (status != GRPC_NO_ERROR) {
00092         fprintf(stderr, "ERROR: %s\n", grpc_error_string(status));
00093         grpc_function_handle_destruct(new_node->handle);
00094         if (new_node->handle != NULL) free(new_node->handle);
00095         grpc_finalize();
00096         exit(1);
00097     }
00098 
00099 
00100     /* this will compute the sizes of all the non-scalar
00101        arguments and setup all the data pointers */
00102     if (new_node->arg_list == NULL) {
00103         if ((ret_val = gs_sender_compute_arg_sizes(
00104             NULL, new_node->arg_stack->args,
00105             new_node->handle->problem_desc,
00106             grpc_sequence_language, grpc_sequence_major)) < 0) {
00107             fprintf(stderr, "error computing argument sizes at client side\n");
00108             exit(1);
00109         }
00110         new_node->handle->problem_desc->size_computed = 1;
00111     }
00112     else if (new_node->arg_stack == NULL) {
00113         if ((ret_val = gs_sender_compute_arg_sizes(
00114             new_node->arg_list, NULL,
00115             new_node->handle->problem_desc,
00116             grpc_sequence_language, grpc_sequence_major)) < 0) {
00117             fprintf(stderr, "error computing argument sizes at client side\n");
00118             exit(1);
00119         }
00120         new_node->handle->problem_desc->size_computed = 1;
00121         new_node->handle->problem_desc->seq_id = seq_id++;
00122     }
00123 
00124     /* ---------------------------- insert into DAG ------------------------- */
00125     /* if there isn't any node in the current DAG */
00126     if (dag->num_nodes == 0) {
00127         dag->head_node = new_node;
00128         dag->tail_node = new_node;
00129         new_node->prev = NULL;
00130         new_node->next = NULL;
00131     } else {
00132         /* add the new node to the tail of the list */
00133         new_node->prev = dag->tail_node;
00134         new_node->next = NULL;
00135         dag->tail_node->next = new_node;
00136         dag->tail_node = new_node;
00137     }
00138 
00139     dag->num_nodes++;
00140     
00141     return 0;
00142 }
00143 
00144 
00151 int delete_node_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *node) {
00152     /* no node at all*/
00153     if (dag->num_nodes == 0) return -1;
00154 
00155     if (node == NULL) return -1;
00156 
00157     /* only one node exist */
00158     if (dag->num_nodes == 1 &&
00159         dag->head_node == node) {
00160         dag->head_node = NULL;
00161         dag->tail_node = NULL;
00162         free(node);
00163         dag->num_nodes--;
00164         return 0;
00165     }
00166     
00167     /* at least 2 nodes */
00168     
00169     /* the node is the head */
00170     if (dag->head_node == node) {
00171         node->next->prev = NULL;
00172         dag->head_node = node->next;
00173         free(node);
00174         dag->num_nodes--;
00175         return 0;
00176     }
00177 
00178     /* the node is the tail */
00179     if (dag->tail_node == node) {
00180         node->prev->next = NULL;
00181         dag->tail_node = node->prev;
00182         free(node);
00183         dag->num_nodes--;
00184         return 0;
00185     }
00186     
00187     /* the node is in the middle */
00188     node->prev->next = node->next;
00189     node->next->prev = node->prev;
00190     free(node);
00191     dag->num_nodes--;
00192 
00193     return 0;
00194 }
00195 
00196 
00211 int insert_dep_GS_DAG(GS_DAG_t *dag,
00212     GS_DAG_Node_t *pnode, GS_DAG_Node_t *cnode, int type, 
00213     gs_argument_t *largp, gs_argument_t *rargp) {
00214     GS_DAG_Dep_t *new_dep;
00215 
00216     if (dag == NULL) return -1;
00217 
00218     if (pnode == NULL || cnode == NULL)
00219         return -1;
00220 
00221 
00222     /* create a new DAG dependency */
00223     new_dep = (GS_DAG_Dep_t *) malloc(sizeof(GS_DAG_Dep_t));
00224     if (new_dep == NULL) {
00225         perror("malloc");
00226         return -1;
00227     }
00228 
00229     new_dep->pnode = pnode;
00230     new_dep->cnode = cnode;
00231     new_dep->dep_type = type;
00232     new_dep->largp = largp;
00233     new_dep->rargp = rargp;
00234     new_dep->data_size = 0;
00235 
00236     /* if there isn't any dependency in the current DAG */
00237     if (dag->num_deps == 0) {
00238         dag->head_dep = new_dep;
00239         dag->tail_dep = new_dep;
00240         new_dep->prev = NULL;
00241         new_dep->next = NULL;
00242     } else {
00243         /* add the new dependency to the tail of the list */
00244         new_dep->prev = dag->tail_dep;
00245         new_dep->next = NULL;
00246         dag->tail_dep->next = new_dep;
00247         dag->tail_dep = new_dep;
00248     }
00249 
00250     dag->num_deps++;
00251     
00252     return 0;
00253 }
00254 
00255 
00264 int delete_dep_GS_DAG(GS_DAG_t *dag, GS_DAG_Dep_t *dep) {
00265     /* no dep at all*/
00266     if (dag->num_deps == 0) return -1;
00267 
00268     if (dep == NULL) return -1;
00269 
00270     /* only one dependency exist */
00271     if (dag->num_deps == 1 &&
00272         dag->head_dep == dep) {
00273         dag->head_dep = NULL;
00274         dag->tail_dep = NULL;
00275         free(dep);
00276         dag->num_deps--;
00277         return 0;
00278     }
00279     
00280     /* at least 2 dependencies */
00281     
00282     /* the dependency is the head */
00283     if (dag->head_dep == dep) {
00284         dep->next->prev = NULL;
00285         dag->head_dep = dep->next;
00286         free(dep);
00287         dag->num_deps--;
00288         return 0;
00289     }
00290 
00291     /* the dependency is the tail */
00292     if (dag->tail_dep == dep) {
00293         dep->prev->next = NULL;
00294         dag->tail_dep = dep->prev;
00295         free(dep);
00296         dag->num_deps--;
00297         return 0;
00298     }
00299     
00300     /* the depedency is in the middle */
00301     dep->prev->next = dep->next;
00302     dep->next->prev = dep->prev;
00303     free(dep);
00304     dag->num_deps--;
00305 
00306     return 0;
00307 }
00308 
00309 
00320 GS_DAG_Node_t *find_node_sched_GS_DAG(GS_DAG_t *dag, int sched_level) {
00321     GS_DAG_Node_t *nptr;
00322 
00323     if (dag == NULL || dag->num_nodes == 0) return NULL;
00324 
00325     for(nptr = dag->head_node; nptr != NULL; nptr = nptr->next) {
00326         /* the first node with specified 
00327            scheduling level is found */
00328         if (nptr->sched_level == sched_level)
00329             return nptr;
00330     }
00331 
00332     /* not found */
00333     return NULL;
00334 }
00335 
00336 
00347 GS_DAG_Node_t *find_node_pnode_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *pnode) {
00348     GS_DAG_Dep_t *dptr;
00349     
00350     if (dag == NULL || dag->num_deps == 0) return NULL;
00351 
00352     for(dptr = dag->head_dep; dptr != NULL; dptr = dptr->next) {
00353         /* the first dependency with 
00354            specified parent node is found */
00355         if (dptr->pnode == pnode)
00356             return dptr->cnode;
00357     }
00358 
00359     /* not found */
00360     return NULL;
00361 }
00362 
00363 
00374 GS_DAG_Dep_t *find_dep_pnode_GS_DAG(GS_DAG_t *dag, GS_DAG_Node_t *pnode) {
00375     GS_DAG_Dep_t *dptr;
00376     
00377     if (dag == NULL || dag->num_deps == 0) return NULL;
00378 
00379     for(dptr = dag->head_dep; dptr != NULL; dptr = dptr->next) {
00380         /* the first dependency with 
00381            specified parent node is found */
00382         if (dptr->pnode == pnode)
00383             return dptr;
00384     }
00385 
00386     /* not found */
00387     return NULL;
00388 }
00389 
00390 
00400 int count_node_GS_DAG(GS_DAG_t *dag, int sched_level) {
00401     GS_DAG_Node_t *nptr;
00402     int count;
00403 
00404     if (dag == NULL || dag->num_nodes == 0) return 0;
00405 
00406     count = 0;
00407     for(nptr = dag->head_node; nptr != NULL; nptr = nptr->next) {
00408         if (nptr->sched_level == sched_level)
00409             count++;
00410     }
00411     
00412     return count;
00413 }
00414 
00415 
00423 int free_GS_DAG(GS_DAG_t *dag) {
00424     GS_DAG_Node_t *node;
00425     GS_DAG_Dep_t *dep;
00426     
00427     /* null or empty DAG */
00428     if (dag == NULL) return -1;
00429 
00430     node = dag->head_node;
00431     dep = dag->head_dep;
00432     
00433     /* delete each node */
00434     while (dag->num_nodes > 0) {
00435         delete_node_GS_DAG(dag, node);
00436         node = dag->head_node;
00437     }
00438     /* delete each dependency */
00439     while (dag->num_deps > 0) {
00440         delete_dep_GS_DAG(dag, dep);
00441         dep = dag->head_dep;
00442     }
00443 
00444     free(dag);
00445 
00446   return 0;
00447 }
00448 
00449 
00450