00001
00002
00003
00004
00005 #include "graph_int.h"
00006 #include "graph_static_int.h"
00007
00008 #define g_field(graph) ((g_field_t *) (graph)->user_data)
00009
00010 graph_t *
00011 g_alloc_static(int ng, int nv, int ne)
00012 {
00013 graph_t *g;
00014 g_field_t *gf;;
00015
00016 g = g_alloc();
00017 gf = ALLOC(g_field_t,1);
00018 gf->num_g_slots = ng;
00019 gf->num_v_slots = nv;
00020 gf->num_e_slots = ne;
00021 gf->user_data = (gGeneric) ALLOC(gGeneric, ng);
00022
00023 g->user_data = (gGeneric) gf;
00024 return(g);
00025 }
00026
00027 void
00028 g_free_static(
00029 graph_t *g,
00030 void (*f_free_g)(gGeneric),
00031 void (*f_free_v)(gGeneric),
00032 void (*f_free_e)(gGeneric))
00033 {
00034 vertex_t *v;
00035 edge_t *e;
00036 lsGen gen;
00037 lsGeneric junk;
00038
00039 if (g == NIL(graph_t)) {
00040 return;
00041 }
00042 if (f_free_g != (void (*)(gGeneric)) NULL) {
00043 (*f_free_g)(g_field(g)->user_data);
00044 }
00045 FREE(g_field(g)->user_data);
00046 FREE(g->user_data);
00047
00048 foreach_vertex(g,gen,v) {
00049 if (f_free_v != (void (*)(gGeneric)) NULL) {
00050 (*f_free_v)(v->user_data);
00051 }
00052 FREE(v->user_data);
00053 (void) lsDestroy(g_get_in_edges(v),(void (*)(lsGeneric)) NULL);
00054 (void) lsDestroy(g_get_out_edges(v),(void (*)(lsGeneric)) NULL);
00055 (void) lsRemoveItem(((vertex_t_int *) v)->handle,&junk);
00056 FREE(v);
00057 }
00058 foreach_edge(g,gen,e) {
00059 if (f_free_e != (void (*)(gGeneric)) NULL) {
00060 (*f_free_e)(e->user_data);
00061 }
00062 FREE(e->user_data);
00063 (void) lsRemoveItem(((edge_t_int *) e)->handle,&junk);
00064 FREE(e);
00065 }
00066 g_free(g,(void (*)(gGeneric)) NULL,(void (*)(gGeneric)) NULL,
00067 (void (*)(gGeneric)) NULL);
00068 }
00069
00070 static graph_t *theGraph;
00071
00072 static gGeneric
00073 copy_v_slots(gGeneric user_data)
00074 {
00075 int i;
00076 int num_v_slots = g_field(theGraph)->num_v_slots;
00077 gGeneric *news = ALLOC(gGeneric,num_v_slots);
00078
00079 for (i = 0; i < num_v_slots; i++) {
00080 news[i] = ((gGeneric *) user_data)[i];
00081 }
00082 return((gGeneric) news);
00083 }
00084
00085 static gGeneric
00086 copy_e_slots(gGeneric user_data)
00087 {
00088 int i;
00089 int num_e_slots = g_field(theGraph)->num_e_slots;
00090 gGeneric *news = ALLOC(gGeneric,num_e_slots);
00091
00092 for (i = 0; i < num_e_slots; i++) {
00093 news[i] = ((gGeneric *) user_data)[i];
00094 }
00095 return((gGeneric) news);
00096 }
00097
00098 graph_t *
00099 g_dup_static(
00100 graph_t *g,
00101 gGeneric (*f_copy_g)(gGeneric),
00102 gGeneric (*f_copy_v)(gGeneric),
00103 gGeneric (*f_copy_e)(gGeneric))
00104 {
00105 g_field_t *gf, *gf2;
00106 graph_t *g2;
00107 gGeneric *news;
00108 int i;
00109
00110 if (f_copy_v == (gGeneric (*)(gGeneric)) NULL) {
00111 theGraph = g;
00112 f_copy_v = copy_v_slots;
00113 }
00114 if (f_copy_e == (gGeneric (*)(gGeneric)) NULL) {
00115 theGraph = g;
00116 f_copy_e = copy_e_slots;
00117 }
00118 g2 = g_dup(g,(gGeneric (*)(gGeneric)) NULL,f_copy_v,f_copy_e);
00119 if (g == NIL(graph_t)) {
00120 return(g2);
00121 }
00122
00123 gf = g_field(g);
00124 gf2 = ALLOC(g_field_t,1);
00125 gf2->num_g_slots = gf->num_g_slots;
00126 gf2->num_v_slots = gf->num_v_slots;
00127 gf2->num_e_slots = gf->num_e_slots;
00128 if (f_copy_g == (gGeneric (*)(gGeneric)) NULL) {
00129 news = ALLOC(gGeneric,gf->num_g_slots);
00130 for (i = gf->num_g_slots - 1; i >= 0; i--) {
00131 news[i] = ((gGeneric *) gf->user_data)[i];
00132 }
00133 gf2->user_data = (gGeneric) news;
00134 }
00135 else {
00136 gf2->user_data = (*f_copy_g)(gf->user_data);
00137 }
00138 g2->user_data = (gGeneric) gf2;
00139 return(g2);
00140 }
00141
00142
00143 void
00144 g_set_g_slot_static(graph_t *g, int i, gGeneric val)
00145 {
00146 if (g == NIL(graph_t)) {
00147 fail("g_set_g_slot_static: Null graph");
00148 }
00149 ((gGeneric *) g_field(g)->user_data)[i] = val;
00150 return;
00151 }
00152
00153
00154 gGeneric
00155 g_get_g_slot_static(graph_t *g, int i)
00156 {
00157 if (g == NIL(graph_t)) {
00158 fail("g_get_g_slot_static: Null graph");
00159 }
00160 return ((gGeneric *) g_field(g)->user_data)[i];
00161 }
00162
00163 void
00164 g_copy_g_slots_static(graph_t *g1, graph_t *g2, gGeneric (*f_copy_g)(gGeneric))
00165 {
00166 g_field_t *gf1,*gf2;
00167 gGeneric slots1,*slots2;
00168 int n;
00169
00170 if (g1 == NIL(graph_t) || g2 == NIL(graph_t)) {
00171 fail("g_copy_g_slots_static: Null graph");
00172 }
00173 gf1 = g_field(g1);
00174 gf2 = g_field(g2);
00175 n = gf1->num_g_slots;
00176
00177 if (n != gf2->num_g_slots) {
00178 fail("g_copy_g_slots_static: Graphs have different numbers of slots");
00179 }
00180 slots1 = gf1->user_data;
00181 slots2 = (gGeneric *) gf2->user_data;
00182 if (f_copy_g == (gGeneric (*)(gGeneric)) NULL) {
00183 for (n-- ; n >= 0; n--) {
00184 slots2[n] = ((gGeneric *) slots1)[n];
00185 }
00186 }
00187 else {
00188 FREE(slots2);
00189 gf2->user_data = (*f_copy_g)(slots1);
00190 }
00191 }
00192
00193
00194 edge_t *
00195 g_add_edge_static(vertex_t *v1, vertex_t *v2)
00196 {
00197 edge_t *e;
00198 g_field_t *gf;
00199
00200 if (v1 == NIL(vertex_t) || v2 == NIL(vertex_t)) {
00201 fail("g_add_edge_static: Null vertex");
00202 }
00203 e = g_add_edge(v1, v2);
00204 gf = g_field(g_edge_graph(e));
00205 e->user_data = (gGeneric) ALLOC(gGeneric, gf->num_e_slots);
00206 return(e);
00207 }
00208
00209
00210 void
00211 g_delete_edge_static(edge_t *e, void (*f_free_e)(gGeneric))
00212 {
00213 if (e == NIL(edge_t)) {
00214 fail("g_delete_edge_static: Null edge");
00215 }
00216 if (f_free_e != (void (*)(gGeneric)) NULL) {
00217 (*f_free_e)(e->user_data);
00218 }
00219 FREE(e->user_data);
00220 g_delete_edge(e,(void (*)(gGeneric)) NULL);
00221 }
00222
00223
00224 void
00225 g_set_e_slot_static(edge_t *e, int i, gGeneric val)
00226 {
00227 if (e == NIL(edge_t)) {
00228 fail("g_set_e_slot_static: Null edge");
00229 }
00230 ((gGeneric *) e->user_data)[i] = val;
00231 }
00232
00233
00234 gGeneric
00235 g_get_e_slot_static(edge_t *e, int i)
00236 {
00237 if (e == NIL(edge_t)) {
00238 fail("g_get_e_slot_static: Null edge");
00239 }
00240 return((gGeneric *) e->user_data)[i];
00241 }
00242
00243 void
00244 g_copy_e_slots_static(edge_t *e1, edge_t *e2, gGeneric (*f_copy_e)(gGeneric))
00245 {
00246 int n;
00247 gGeneric slots1,*slots2;
00248
00249 if (e1 == NIL(edge_t) || e2 == NIL(edge_t)) {
00250 fail("g_copy_e_slots_static: Null edge");
00251 }
00252 n = g_field(g_edge_graph(e1))->num_e_slots;
00253
00254 if (n != g_field(g_edge_graph(e2))->num_e_slots) {
00255 fail("g_copy_e_slots_static: Edges have differing numbers of slots");
00256 }
00257 slots1 = e1->user_data;
00258 slots2 = (gGeneric *) e2->user_data;
00259 if (f_copy_e == (gGeneric (*)(gGeneric)) NULL) {
00260 for (n--; n >= 0; n--) {
00261 slots2[n] = ((gGeneric *) slots1)[n];
00262 }
00263 }
00264 else {
00265 FREE(slots2);
00266 e2->user_data = (*f_copy_e)(slots1);
00267 }
00268 }
00269
00270
00271 vertex_t *
00272 g_add_vertex_static(graph_t *g)
00273 {
00274 g_field_t *gf;
00275 vertex_t *v;
00276
00277 if (g == NIL(graph_t)) {
00278 fail("g_add_vertex_static: Null graph");
00279 }
00280 gf = g_field(g);
00281 v = g_add_vertex(g);
00282 v->user_data = (gGeneric) ALLOC(gGeneric, gf->num_v_slots);
00283 return(v);
00284 }
00285
00286
00287 void
00288 g_delete_vertex_static(
00289 vertex_t *v,
00290 void (*f_free_v)(gGeneric),
00291 void (*f_free_e)(gGeneric))
00292 {
00293 edge_t *e;
00294 lsGen gen;
00295
00296 if (v == NIL(vertex_t)) {
00297 fail("g_delete_vertex_static: Null vertex");
00298 }
00299 foreach_in_edge(v, gen, e) {
00300 if (f_free_e != (void (*)(gGeneric)) NULL) {
00301 (*f_free_e)(e->user_data);
00302 }
00303 FREE(e->user_data);
00304 }
00305 foreach_out_edge(v, gen, e) {
00306 if (f_free_e != (void (*)(gGeneric)) NULL) {
00307 (*f_free_e)(e->user_data);
00308 }
00309 FREE(e->user_data);
00310 }
00311 if (f_free_v != (void (*)(gGeneric)) NULL) {
00312 (*f_free_v)(v->user_data);
00313 }
00314 FREE(v->user_data);
00315 g_delete_vertex(v, (void (*)(gGeneric)) NULL, (void (*)(gGeneric)) NULL);
00316 }
00317
00318
00319 void
00320 g_set_v_slot_static(vertex_t *v, int i, gGeneric val)
00321 {
00322 if (v == NIL(vertex_t)) {
00323 fail("g_set_v_slot_static: Null vertex");
00324 }
00325 ((gGeneric *) v->user_data)[i] = val;
00326 }
00327
00328
00329 gGeneric
00330 g_get_v_slot_static(vertex_t *v, int i)
00331 {
00332 if (v == NIL(vertex_t)) {
00333 fail("g_get_v_slot_static: Null vertex");
00334 }
00335 return ((gGeneric *) v->user_data)[i];
00336 }
00337
00338 void
00339 g_copy_v_slots_static(
00340 vertex_t *v1,
00341 vertex_t *v2,
00342 gGeneric (*f_copy_v)(gGeneric))
00343 {
00344 int n;
00345 gGeneric slots1,*slots2;
00346
00347 if (v1 == NIL(vertex_t) || v2 == NIL(vertex_t)) {
00348 fail("g_copy_v_slots_static: Null vertex");
00349 }
00350 n = g_field(g_vertex_graph(v1))->num_v_slots;
00351
00352 if (n != g_field(g_vertex_graph(v2))->num_v_slots) {
00353 fail("g_copy_v_slots_static: Vertices have differing numbers of slots");
00354 }
00355 slots1 = v1->user_data;
00356 slots2 = (gGeneric *) v2->user_data;
00357 if (f_copy_v == (gGeneric (*)(gGeneric)) NULL) {
00358 for (n--; n >= 0; n--) {
00359 slots2[n] = ((gGeneric *) slots1)[n];
00360 }
00361 }
00362 else {
00363 FREE(slots2);
00364 v2->user_data = (*f_copy_v)(slots1);
00365 }
00366 }
00367
