1 /* SCCS-info %W% %E% */
2
3 /*--------------------------------------------------------------------*/
4 /* */
5 /* VCG : Visualization of Compiler Graphs */
6 /* -------------------------------------- */
7 /* */
8 /* file: alloc.c */
9 /* version: 1.00.00 */
10 /* creation: 14.4.1993 */
11 /* author: I. Lemke (...-Version 0.99.99) */
12 /* G. Sander (Version 1.00.00-...) */
13 /* Universitaet des Saarlandes, 66041 Saarbruecken */
14 /* ESPRIT Project #5399 Compare */
15 /* description: Memory Management */
16 /* status: in work */
17 /* */
18 /*--------------------------------------------------------------------*/
19
20 #ifndef lint
21 static char *id_string="$Id: alloc.c,v 3.9 1995/02/08 11:11:14 sander Exp $";
22 #endif
23
24 /*
25 * Copyright (C) 1993-2005 Saarland University
26 *
27 * This program and documentation is free software; you can redistribute
28 * it under the terms of the GNU General Public License as published by
29 * the Free Software Foundation; either version 2 of the License, or
30 * (at your option) any later version.
31 *
32 * This program is distributed in the hope that it will be useful,
33 * but WITHOUT ANY WARRANTY; without even the implied warranty of
34 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
35 * GNU General Public License for more details.
36 *
37 * You should have received a copy of the GNU General Public License
38 * along with this program; if not, write to the Free Software
39 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
40 *
41 * The software is available per anonymous ftp at ftp.cs.uni-sb.de.
42 * Contact sander@cs.uni-sb.de for additional information.
43 */
44
45
46 /*
47 * $Log: alloc.c,v $
48 * Revision 3.9 1995/02/08 11:11:14 sander
49 * Distribution version 1.3.
50 *
51 * Revision 3.8 1994/12/23 18:12:45 sander
52 * Manhatten layout added.
53 * Option interface cleared.
54 *
55 * Revision 3.7 1994/08/03 13:58:44 sander
56 * Horizontal order mechanism changed.
57 * Attribute horizontal_order for edges added.
58 *
59 * Revision 3.6 1994/05/17 16:37:18 sander
60 * attribute node_align added to allow nodes to be centered in the levels.
61 *
62 * Revision 3.5 1994/05/16 08:56:03 sander
63 * shape attribute (boxes, rhombs, ellipses, triangles) added.
64 *
65 * Revision 3.4 1994/05/05 08:20:30 sander
66 * dllist_free_all added for the local optimization of crossings.
67 *
68 * Revision 3.3 1994/04/27 16:05:19 sander
69 * Some general changes for the PostScript driver.
70 * Horizontal order added. Bug fixes of the folding phases:
71 * Folding of nested graphs works now.
72 *
73 * Revision 3.2 1994/03/04 19:11:24 sander
74 * Specification of levels per node added.
75 * X11 geometry behaviour (option -geometry) changed such
76 * that the window is now opened automatically.
77 *
78 * Revision 3.1 1994/03/01 10:59:55 sander
79 * Copyright and Gnu Licence message added.
80 * Problem with "nearedges: no" and "selfloops" solved.
81 *
82 * Revision 2.2 1994/01/21 19:33:46 sander
83 * VCG Version tested on Silicon Graphics IRIX, IBM R6000 AIX and Sun 3/60.
84 * Option handling improved. Option -grabinputfocus installed.
85 * X11 Font selection scheme implemented. The user can now select a font
86 * during installation.
87 * Sun K&R C (a nonansi compiler) tested. Some portabitility problems solved.
88 *
89 * Revision 2.1 1993/12/08 21:20:09 sander
90 * Reasonable fast and stable version
91 *
92 */
93
94
95 /****************************************************************************
96 * This file is a collection of auxiliary functions that implement the
97 * memory management. It provides the following functions:
98 *
99 * myalloc allocates memory from the internal memory management.
100 * free_memory gives the complete memory free.
101 *
102 * nodealloc allocates a GNODE object (node), adds it to nodelist
103 * graphalloc allocates a GNODE object (graph), adds it to graphlist
104 * tmpnodealloc allocates a temporary GNODE object
105 * free_node deallocate a nontemporary GNODE object
106 *
107 * nodelist_alloc allocates a stable node list element (i.e. a cons
108 * cell whose head is a GNODE object)
109 * tmpnodelist_alloc allocates a temporary node list element (i.e. a cons
110 * cell whose head is a GNODE object)
111 * free_regionnodelist deallocate a list of node list elements.
112 * These were used as storage of regions.
113 *
114 * edgealloc allocates a GEDGE object (edge), adds it to edgelist
115 * tmpedgealloc allocates a temporary GEDGE object
116 *
117 * near_edge_insert insert a near edge into near_edge_list. A near edge
118 * is a special edge that must always be placed near an
119 * other edge. See the nearedge-specification-feature.
120 * We use a special adjacency list to notify all
121 * near edges.
122 * bentnear_edge_insert insert a bent near edge into bent_near_edge_list.
123 * A bent near edge is a special edge consisting of a
124 * near edge, a dummy node and a normal edge.
125 * See the nearedge-specification-feature.
126 * We use a special adjacency list to notify all
127 * bent near edges.
128 * back_edge_insert insert a back edge into back_edge_list. A back edge
129 * is an edge that preferably is reverted.
130 * We use a special adjacency list to notify all
131 * back edges.
132 * prededgealloc allocates an edge list element (i.e. a cons cell whose
133 * head is a GEDGE object), used as adjacency list of
134 * predecessors of a node.
135 * succedgealloc allocates an edge list element (i.e. a cons cell whose
136 * head is a GEDGE object), used as adjacency list of
137 * succecessors of a node.
138 *
139 * connectalloc allocates a CONNECT element of a node
140 *
141 * dllist_alloc allocates a DLLIST-cons cell. These are double linked
142 * lists of nodes.
143 * dllist_free gives one DLLIST-cons cell free.
144 *
145 * free_all_lists gives all temporary memory free.
146 * reinit_all_lists reinitialize all memory lists. This is done if the
147 * memory is given free: all lists are set to NULL.
148 ***************************************************************************/
149
150
151 #include <stdio.h>
152 #include <stdlib.h>
153 #include "globals.h"
154 #include "grammar.h"
155 #include "main.h"
156 #include "options.h"
157 #include "alloc.h"
158 #include "folding.h"
159
160 #undef DEBUG
161 #undef debugmessage
162 #ifdef DEBUG
163 #define debugmessage(a,b) {FPRINTF(stderr,"Debug: %s %s\n",a,b);}
164 #else
165 #define debugmessage(a,b) /**/
166 #endif
167
168
169 /* Prototypes
170 * ----------
171 */
172
173 static GNODE internal_nodealloc _PP((void));
174 static void free_nodelists _PP((void));
175 static GEDGE internal_edgealloc _PP((void));
176 static void free_tmpedges _PP((void));
177 static ADJEDGE edgelist_alloc _PP((void));
178 static void free_edgelists _PP((void));
179 static void free_connect _PP((void));
180
181 /*--------------------------------------------------------------------*/
182 /* Memory allocation */
183 /*--------------------------------------------------------------------*/
184
185 /* Core Memory Management
186 * ======================
187 */
188
189 #ifdef DEBUG
190 static long act_alloc_size = 0;
191 static long act_alloc_edges = 0;
192 static long act_alloc_nodes = 0;
193 #endif
194
195 static long node_refnum = 0L; /* reference counter for REFNUM of nodes */
196
197
198 /* Core Memory allocation
199 * ----------------------
200 * allocate x bytes. We use the memory mechanism from the generated
201 * parser.
202 */
203
204 #ifdef ANSI_C
myalloc(int x)205 char *myalloc(int x)
206 #else
207 char *myalloc(x)
208 int x;
209 #endif
210 {
211 debugmessage("myalloc. Nr. of Bytes:",my_itoa(x));
212 #ifdef DEBUG
213 act_alloc_size += x;
214 PRINTF("Alloc Summary: %ld Bytes allocated\n",act_alloc_size);
215 #endif
216 return(ParseMalloc(x));
217 }
218
219
220 /* Core Memory deallocation
221 * ------------------------
222 * deallocate the complete memory.
223 */
224
225 #ifdef ANSI_C
free_memory(void)226 void free_memory(void)
227 #else
228 void free_memory()
229 #endif
230 {
231 debugmessage("free_memory","");
232 #ifdef DEBUG
233 act_alloc_size = 0;
234 act_alloc_nodes = 0;
235 act_alloc_edges = 0;
236 #endif
237 FreeHash();
238 ParseFree();
239 node_refnum = 0L;
240 reinit_all_lists();
241 }
242
243 /*--------------------------------------------------------------------*/
244
245 /* Memory Management for Nodes
246 * ===========================
247 */
248
249 /* We distinguish between
250 * 1) GNODE objects as nodes from the specification
251 * 2) GNODE objects as representation of subgraphs
252 * 3) temporary GNODE objects, used to calculate a layout.
253 * They can be deleted on each change of layout.
254 */
255
256 /* Nodes from the specification come into the nodelist.
257 * Subgraphs come into the subgraphlist.
258 * Temporary nodes come into the tmpnodelist.
259 * Free GNODE objects are collected into the node_freelist.
260 */
261
262 int nodeanz = 0; /* Number of nodes in nodelist */
263 int dummyanz = 0; /* Number of dummy nodes (not labels) */
264
265
266 GNODE nodelist = NULL; /* List of all real nodes as specified */
267 GNODE nodelistend = NULL; /* End of this list */
268 GNODE graphlist = NULL; /* List of all subgraphs as specified */
269 GNODE graphlistend = NULL; /* End of this list */
270
271 GNODE invis_nodes = NULL; /* List of all invisible nodes */
272 GNODE labellist = NULL; /* List of dummy nodes that contain */
273 /* the text of an edge label */
274 GNODE labellistend = NULL; /* End of this list */
275 GNODE dummylist = NULL; /* List of other dummy nodes */
276
277 GNODE tmpnodelist = NULL; /* list of allocated temoprary nodes */
278 static GNODE node_freelist = NULL; /* list of free GNODE objects */
279
280
281
282 /* Allocate a GNODE object
283 * -----------------------
284 * First, we look in the free list, if we have a free node. Otherwise,
285 * we allocate a node from the core memory.
286 * We also set some default values.
287 */
288
289 #ifdef ANSI_C
internal_nodealloc(void)290 static GNODE internal_nodealloc(void)
291 #else
292 static GNODE internal_nodealloc()
293 #endif
294 {
295 GNODE h;
296
297 debugmessage("internal_nodealloc","");
298 if (node_freelist) {
299 h = node_freelist;
300 node_freelist = NINTERN(node_freelist);
301 }
302 else {
303 h = (GNODE) myalloc(sizeof(struct gnode));
304 #ifdef DEBUG
305 act_alloc_nodes++;
306 PRINTF("Alloc Summary: %ld GNODEs allocated\n",act_alloc_nodes);
307 #endif
308 }
309
310 NREFNUM(h) = node_refnum++;
311 NTITLE(h) = NULL;
312 NLABEL(h) = NULL;
313 NINFO1(h) = NULL;
314 NINFO2(h) = NULL;
315 NINFO3(h) = NULL;
316 NLEVEL(h) = -1;
317 NSHAPE(h) = 0;
318 NHORDER(h) = -1;
319 NSX(h) = 0L;
320 NSY(h) = 0L;
321 NX(h) = 0L;
322 NY(h) = 0L;
323 NSGRAPH(h) = NULL;
324 NROOT(h) = NULL;
325 NREGREPL(h) = NULL;
326 NREGION(h) = NULL;
327 NREGROOT(h) = NULL;
328 NINLIST(h) = 1;
329 NINVISIBLE(h) = 0;
330 NTIEFE(h) = -1;
331 NPOS(h) = -1;
332 NWEIGHTS(h) = 0L;
333 NWEIGHTP(h) = 0L;
334 NMARK(h) = 0;
335 NREVERT(h) = 0;
336 NANCHORNODE(h) = 0;
337 h->bary = -1;
338 NDFS(h) = -1L;
339 NINDEG(h) = 0;
340 NOUTDEG(h) = 0;
341 NVPTR(h) = NULL;
342 NPRED(h) = NULL;
343 NSUCC(h) = NULL;
344 NSVPRED(h) = NULL;
345 NSVSUCC(h) = NULL;
346 NPREDL(h) = NULL;
347 NPREDR(h) = NULL;
348 NSUCCL(h) = NULL;
349 NSUCCR(h) = NULL;
350 NCONNECT(h) = NULL;
351 NNEXT(h) = NULL;
352 NINTERN(h) = NULL;
353 return(h);
354 }
355
356
357
358 /* Allocate a real node
359 * --------------------
360 * and update the nodelist. Real nodes are such nodes that are specified
361 * as node: { .... }.
362 * We inheret the attributes from the refnode.
363 */
364
365 #ifdef ANSI_C
nodealloc(GNODE refnode)366 GNODE nodealloc(GNODE refnode)
367 #else
368 GNODE nodealloc(refnode)
369 GNODE refnode;
370 #endif
371 {
372 GNODE h;
373
374 debugmessage("nodealloc","");
375 h = internal_nodealloc();
376 copy_nodeattributes(refnode, h);
377 NBEFORE(h) = nodelistend;
378 if (nodelistend) NNEXT(nodelistend) = h;
379 nodelistend = h;
380 nodeanz++;
381 if (nodelist == NULL) nodelist = h;
382 return(h);
383
384 }
385
386 /* Initialize a node with the node defaults
387 * ----------------------------------------
388 */
389
390 #ifdef ANSI_C
nodedefaults(GNODE node)391 void nodedefaults(GNODE node)
392 #else
393 void nodedefaults(node)
394 GNODE node;
395 #endif
396 {
397 debugmessage("nodedefaults","");
398
399 NTITLE(node) = G_title;
400 NLABEL(node) = NULL;
401 NLEVEL(node) = -1;
402 NSHAPE(node) = BOX;
403 NHORDER(node) = -1;
404 NINFO1(node) = "";
405 NINFO2(node) = "";
406 NINFO3(node) = "";
407 NSX(node) = 0L;
408 NSY(node) = 0L;
409 NTEXTMODE(node) = CENTER;
410 NSTATE(node) = 0;
411 NWIDTH(node) = -1;
412 NHEIGHT(node) = -1;
413 NBORDERW(node) = 2;
414 NFOLDING(node) = -1;
415 NCOLOR(node) = G_color;
416 NTCOLOR(node) = BLACK;
417 NBCOLOR(node) = BLACK;
418 NSHRINK(node) = 1;
419 NSTRETCH(node) = 1;
420 }
421
422
423 /* Initialize a node with the foldnode defaults
424 * --------------------------------------------
425 */
426
427 #ifdef ANSI_C
foldnodedefaults(GNODE node)428 void foldnodedefaults(GNODE node)
429 #else
430 void foldnodedefaults(node)
431 GNODE node;
432 #endif
433 {
434 debugmessage("foldnodedefaults","");
435
436 NTITLE(node) = NULL;
437 NLABEL(node) = NULL;
438 NLEVEL(node) = -1;
439 NSHAPE(node) = -1;
440 NHORDER(node) = -1;
441 NINFO1(node) = NULL;
442 NINFO2(node) = NULL;
443 NINFO3(node) = NULL;
444 NSX(node) = 0L;
445 NSY(node) = 0L;
446 NTEXTMODE(node) = -1;
447 NSTATE(node) = -1;
448 NWIDTH(node) = -1;
449 NHEIGHT(node) = -1;
450 NBORDERW(node) = 4;
451 NFOLDING(node) = -1;
452 NCOLOR(node) = -1;
453 NTCOLOR(node) = -1;
454 NBCOLOR(node) = -1;
455 NSHRINK(node) = -1;
456 NSTRETCH(node) = -1;
457 }
458
459
460 /* Copy the foldnode attributes from fn to y
461 * -----------------------------------------
462 */
463
464 #ifdef ANSI_C
inherit_foldnode_attributes(GNODE fn,GNODE y)465 void inherit_foldnode_attributes(GNODE fn, GNODE y)
466 #else
467 void inherit_foldnode_attributes(fn, y)
468 GNODE fn, y;
469 #endif
470 {
471 debugmessage("inherit_foldnode_attributes","");
472
473 /* NTITLE not needed */
474 /* NFOLDING not needed */
475 if (NLABEL(fn)) NLABEL(y) = NLABEL(fn);
476 if (NLEVEL(fn)!= -1) NLEVEL(y) = NLEVEL(fn);
477 if (NSHAPE(fn)!= -1) NSHAPE(y) = NSHAPE(fn);
478 if (NHORDER(fn)!= -1) NHORDER(y) = NHORDER(fn);
479 if (NINFO1(fn)) NINFO1(y) = NINFO1(fn);
480 if (NINFO2(fn)) NINFO2(y) = NINFO2(fn);
481 if (NINFO3(fn)) NINFO3(y) = NINFO3(fn);
482 if (NSX(fn)!= -1L) NSX(y) = NSX(fn);
483 if (NSY(fn)!= -1L) NSY(y) = NSY(fn);
484 if (NTEXTMODE(fn)!= -1) NTEXTMODE(y) = NTEXTMODE(fn);
485 if (NSTATE(fn)!= -1) NSTATE(y) = NSTATE(fn);
486 if (NWIDTH(fn)!= -1) NWIDTH(y) = NWIDTH(fn);
487 if (NHEIGHT(fn)!= -1) NHEIGHT(y) = NHEIGHT(fn);
488 if (NBORDERW(fn)!= -1) NBORDERW(y) = NBORDERW(fn);
489 if (NCOLOR(fn)!= -1) NCOLOR(y) = NCOLOR(fn);
490 if (NTCOLOR(fn)!= -1) NTCOLOR(y) = NTCOLOR(fn);
491 if (NBCOLOR(fn)!= -1) NBCOLOR(y) = NBCOLOR(fn);
492 if (NSHRINK(fn)!= -1) NSHRINK(y) = NSHRINK(fn);
493 if (NSTRETCH(fn)!= -1) NSTRETCH(y) = NSTRETCH(fn);
494 }
495
496
497 /* Copy a GNODE object x into a second GNODE object y
498 * --------------------------------------------------
499 */
500
501 #ifdef ANSI_C
copy_nodeattributes(GNODE x,GNODE y)502 void copy_nodeattributes(GNODE x, GNODE y)
503 #else
504 void copy_nodeattributes(x, y)
505 GNODE x, y;
506 #endif
507 {
508 NTITLE(y) = NTITLE(x);
509 NLABEL(y) = NLABEL(x);
510 NLEVEL(y) = NLEVEL(x);
511 NSHAPE(y) = NSHAPE(x);
512 NHORDER(y) = NHORDER(x);
513 NINFO1(y) = NINFO1(x);
514 NINFO2(y) = NINFO2(x);
515 NINFO3(y) = NINFO3(x);
516 NSX(y) = NSX(x);
517 NSY(y) = NSY(x);
518 NTEXTMODE(y) = NTEXTMODE(x);
519 NSTATE(y) = NSTATE(x);
520 NWIDTH(y) = NWIDTH(x);
521 NHEIGHT(y) = NHEIGHT(x);
522 NBORDERW(y) = NBORDERW(x);
523 NFOLDING(y) = NFOLDING(x);
524 NCOLOR(y) = NCOLOR(x);
525 NTCOLOR(y) = NTCOLOR(x);
526 NBCOLOR(y) = NBCOLOR(x);
527 NSHRINK(y) = NSHRINK(x);
528 NSTRETCH(y) = NSTRETCH(x);
529 }
530
531
532
533 /* Allocate a graph object
534 * -----------------------
535 * and update the graphlist. Such objects are summary nodes whose graph
536 * is specified as graph: { .... }.
537 * We inheret the attributes from the refnode.
538 */
539
540 #ifdef ANSI_C
graphalloc(GNODE refnode)541 GNODE graphalloc(GNODE refnode)
542 #else
543 GNODE graphalloc(refnode)
544 GNODE refnode;
545 #endif
546 {
547 GNODE h;
548
549 debugmessage("graphalloc","");
550 h = internal_nodealloc();
551 copy_nodeattributes(refnode, h);
552 NFOLDING(h) = -1;
553 NINLIST(h) = 0;
554 NINVISIBLE(h) = 1;
555 NDFS(h) = 0L;
556 NBEFORE(h) = graphlistend;
557
558 if (graphlistend) NNEXT(graphlistend) = h;
559 graphlistend = h;
560 if (graphlist == NULL) graphlist = h;
561 return(h);
562 }
563
564
565 /* Allocate a temporary GNODE object
566 * ---------------------------------
567 * and update the tmpnodelist. These are node for dummy's, label's etc.
568 * These nodes are only needed for the layouting.
569 */
570
571 #ifdef ANSI_C
tmpnodealloc(int textm,int width,int height,int borderw,int fold,int color,int textc,int borderc,int shrink,int stretch,int horder)572 GNODE tmpnodealloc(
573 int textm,
574 int width,
575 int height,
576 int borderw,
577 int fold,
578 int color,
579 int textc,
580 int borderc,
581 int shrink,
582 int stretch,
583 int horder)
584 #else
585 GNODE tmpnodealloc(textm,width,height,borderw,fold,color,textc,borderc,
586 shrink,stretch,horder)
587 int textm,width,height,borderw,fold,color,textc,borderc;
588 int shrink,stretch,horder;
589 #endif
590 {
591 GNODE h;
592
593 debugmessage("tmpnodealloc","");
594 h = internal_nodealloc();
595
596 NHORDER(h) = horder;
597 NTEXTMODE(h) = textm;
598 NSTATE(h) = 0;
599 NWIDTH(h) = width;
600 NHEIGHT(h) = height;
601 NBORDERW(h) = borderw;
602 NFOLDING(h) = fold;
603 NCOLOR(h) = color;
604 NTCOLOR(h) = textc;
605 NBCOLOR(h) = borderc;
606 NSHRINK(h) = shrink;
607 NSTRETCH(h) = stretch;
608 NINLIST(h) = 0;
609 NINVISIBLE(h) = 1;
610 NDFS(h) = 0L;
611 NBEFORE(h) = NULL;
612
613 NINTERN(h) = tmpnodelist;
614 tmpnodelist = h;
615 return(h);
616 }
617
618
619 /* Deallocate all temporary GNODE objects
620 * --------------------------------------
621 */
622
623 #ifdef ANSI_C
free_tmpnodes(void)624 void free_tmpnodes(void)
625 #else
626 void free_tmpnodes()
627 #endif
628 {
629 GNODE h;
630
631 debugmessage("free_tmpnodes","");
632 h = tmpnodelist;
633 if (h) {
634 while (NINTERN(h)) h = NINTERN(h);
635 NINTERN(h) = node_freelist;
636 node_freelist = tmpnodelist;
637 tmpnodelist = NULL;
638 }
639 labellist = NULL;
640 labellistend = NULL;
641 dummylist = NULL;
642 /* Labels and dummys are temporary nodes thus they
643 * are given free, too
644 */
645 }
646
647
648 /* Deallocate one GNODE objects
649 * ----------------------------
650 * This object should not be temporary !!!
651 * In fact, it is a region summary substitution node. See folding.c
652 * If the object would be allocated by tmpnodealloc,
653 * it could be given free twice, which is wrong.
654 */
655
656 #ifdef ANSI_C
free_node(GNODE h)657 void free_node(GNODE h)
658 #else
659 void free_node(h)
660 GNODE h;
661 #endif
662 {
663 debugmessage("free_node","");
664 NINTERN(h) = node_freelist;
665 node_freelist = h;
666 }
667
668
669 /* Give a position, search a node in the node list
670 * -----------------------------------------------
671 * This is used in the menues after selecting a node.
672 * At this time point, all visible nodes are in the node list.
673 */
674
675 #ifdef ANSI_C
search_xy_node(long x,long y)676 GNODE search_xy_node(long x,long y)
677 #else
678 GNODE search_xy_node(x,y)
679 long x,y;
680 #endif
681 {
682 GNODE v;
683 int width, height;
684 long xpos, ypos;
685
686 v = nodelist;
687 while (v) {
688 xpos = (NX(v)*G_stretch)/G_shrink - V_xmin;
689 ypos = (NY(v)*G_stretch)/G_shrink - V_ymin;
690 width = (NWIDTH(v)*G_stretch)/G_shrink;
691 height = (NHEIGHT(v)*G_stretch)/G_shrink;
692 if ( (xpos <= x) && (x <= xpos+width) &&
693 (ypos <= y) && (y <= ypos+height) )
694 return(v); /* node found */
695 v = NNEXT(v);
696 }
697 return(NULL); /* no node found */
698 }
699
700
701 /* Check the graph consistency
702 * ---------------------------
703 * A serious problem is that subgraphs may not have any nodes.
704 * This leads to confusion if such a subgraph is folded.
705 * Thus, for such subgraphs, we add auxiliary nodes.
706 */
707
708 #ifdef ANSI_C
check_graph_consistency(void)709 void check_graph_consistency(void)
710 #else
711 void check_graph_consistency()
712 #endif
713 {
714 GNODE v,w;
715
716 v = graphlist;
717
718 while (v) {
719 if (NSGRAPH(v)==NULL) {
720 if (!silent) {
721 FPRINTF(stderr,"\nWarning: Graph %s",
722 (NTITLE(v)?NTITLE(v):""));
723 FPRINTF(stderr," has no nodes.");
724 FPRINTF(stderr," I add a node ! \n");
725 }
726
727 w = nodealloc( v );
728 NTITLE(w) = "artificial node";
729 NROOT(w) = v;
730 NSGRAPH(v) = nodelist_alloc(w);
731 }
732 v = NNEXT(v);
733 }
734 }
735
736 /*--------------------------------------------------------------------*/
737
738
739 /* Memory Management lists of GNODE objects
740 * ========================================
741 */
742
743 /* Lists of GNODE objects, if they are not connected via internal
744 * GNODE pointers, use special cons-cells, i.e. GNLIST objects, whose
745 * heads are GNODE objects. Because some cons-cells are temporary,
746 * we use a similar memory management as for temporary GNODE objects.
747 */
748
749
750 static GNLIST tmpnconslist = NULL; /* list of allocated cons cells */
751 static GNLIST foldnconslist = NULL; /* list of all. fold cons cells */
752 static GNLIST ncons_freelist = NULL; /* list of free cons cells */
753
754
755 /* Allocate a GNLIST object
756 * ------------------------
757 * First, we look in the free list, if we have a free node. Otherwise,
758 * we allocate a node from the core memory.
759 * We also set some default values.
760 * These node lists are part of the stable graph representation, i.e.
761 * need not to be freed unless a reload of the graph. Thus we don't
762 * store them in the tmpnconslist.
763 */
764
765 #ifdef ANSI_C
nodelist_alloc(GNODE v)766 GNLIST nodelist_alloc(GNODE v)
767 #else
768 GNLIST nodelist_alloc(v)
769 GNODE v;
770 #endif
771 {
772 GNLIST h;
773
774 debugmessage("nodelist_alloc","");
775 h = (GNLIST)myalloc(sizeof(struct gnlist));
776 GNINTERN(h) = NULL;
777 GNNODE(h) = v;
778 GNNEXT(h) = NULL;
779 return(h);
780 }
781
782 /* Allocate a temporary GNLIST object
783 * ----------------------------------
784 * First, we look in the free list, if we have a free node. Otherwise,
785 * we allocate a node from the core memory.
786 * We also set some default values.
787 * These node lists are temporary, thus we store them in the
788 * tmpnconslist, to give them free later.
789 */
790
791 #ifdef ANSI_C
tmpnodelist_alloc(void)792 GNLIST tmpnodelist_alloc(void)
793 #else
794 GNLIST tmpnodelist_alloc()
795 #endif
796 {
797 GNLIST h;
798
799 debugmessage("tmpnodelist_alloc","");
800 if (ncons_freelist) {
801 h = ncons_freelist;
802 ncons_freelist = GNINTERN(ncons_freelist);
803 }
804 else h = (GNLIST)myalloc(sizeof(struct gnlist));
805 GNINTERN(h) = tmpnconslist;
806 GNNODE(h) = NULL;
807 GNNEXT(h) = NULL;
808 tmpnconslist = h;
809 return(h);
810 }
811
812
813 /* Allocate a foldlist GNLIST object
814 * ---------------------------------
815 * First, we look in the free list, if we have a free node. Otherwise,
816 * we allocate a node from the core memory.
817 * We also set some default values.
818 * These node lists are used for the folding action keepers in
819 * folding.c. They live longer than temporary nodes, but are
820 * also temporary, because they are deallocated after folding.
821 */
822
823 #ifdef ANSI_C
foldnodelist_alloc(void)824 GNLIST foldnodelist_alloc(void)
825 #else
826 GNLIST foldnodelist_alloc()
827 #endif
828 {
829 GNLIST h;
830
831 debugmessage("foldnodelist_alloc","");
832 if (ncons_freelist) {
833 h = ncons_freelist;
834 ncons_freelist = GNINTERN(ncons_freelist);
835 }
836 else h = (GNLIST)myalloc(sizeof(struct gnlist));
837 GNINTERN(h) = foldnconslist;
838 GNNODE(h) = NULL;
839 GNNEXT(h) = NULL;
840 foldnconslist = h;
841 return(h);
842 }
843
844
845
846 /* Deallocate all temporary GNLIST objects
847 * --------------------------------------
848 */
849
850 #ifdef ANSI_C
free_nodelists(void)851 static void free_nodelists(void)
852 #else
853 static void free_nodelists()
854 #endif
855 {
856 GNLIST h;
857
858 debugmessage("free_nodelists","");
859 h = tmpnconslist;
860 if (h) {
861 while(GNINTERN(h)) h = GNINTERN(h);
862 GNINTERN(h) = ncons_freelist;
863 ncons_freelist = tmpnconslist;
864 tmpnconslist = NULL;
865 }
866 }
867
868
869 /* Deallocate all fold GNLIST objects
870 * ----------------------------------
871 */
872
873 #ifdef ANSI_C
free_foldnodelists(void)874 void free_foldnodelists(void)
875 #else
876 void free_foldnodelists()
877 #endif
878 {
879 GNLIST h;
880
881 debugmessage("free_foldnodelists","");
882 h = foldnconslist;
883 if (h) {
884 while(GNINTERN(h)) h = GNINTERN(h);
885 GNINTERN(h) = ncons_freelist;
886 ncons_freelist = foldnconslist;
887 foldnconslist = NULL;
888 }
889 }
890
891
892 /* Deallocate GNLIST objects of regions
893 * ------------------------------------
894 * These GNLIST objects should be allocated by nodelist_alloc,
895 * i.e. should not be temporary.
896 */
897
898 #ifdef ANSI_C
free_regionnodelist(GNLIST r)899 void free_regionnodelist(GNLIST r)
900 #else
901 void free_regionnodelist(r)
902 GNLIST r;
903 #endif
904 {
905 GNLIST h;
906
907 debugmessage("free_regionnodelists","");
908 h = r;
909 if (h) {
910 while(GNINTERN(h)) h = GNINTERN(h);
911 GNINTERN(h) = ncons_freelist;
912 ncons_freelist = r;
913 }
914 }
915
916
917 /*--------------------------------------------------------------------*/
918
919
920 /* Memory Management for Edges
921 * ===========================
922 */
923
924 /* We distinguish between
925 * 1) GEDGE objects as edges from the specification
926 * 2) GEDGE objects from the specification that are not visualized
927 * directly. Neverthelesss, we need the attributes of these
928 * edges, thus we create a auxiliary GEDGE object for them.
929 * 3) temporary GEDGE objects, used to calculate a layout.
930 * They can be deleted on each change of layout.
931 */
932
933 /* Edge from the specification come into the edgelist.
934 * Temporary edges come into the tmpedgelist.
935 * Free GEDGE objects are collected into the node_freelist.
936 */
937
938 int edgeanz = 0; /* Number of edges in edgelist */
939
940 GEDGE edgelist = NULL; /* List of all real edges as specified */
941 GEDGE edgelistend = NULL; /* End of this list */
942
943 GEDGE tmpedgelist = NULL; /* list of allocated temporary edges */
944 static GEDGE edge_freelist = NULL; /* list of free GEDGE objects */
945
946
947 /* Allocate a GEDGE object
948 * -----------------------
949 * First, we look in the free list, if we have a free edge. Otherwise,
950 * we allocate an edge from the core memory.
951 * We also set some default values.
952 */
953
954 #ifdef ANSI_C
internal_edgealloc(void)955 static GEDGE internal_edgealloc(void)
956 #else
957 static GEDGE internal_edgealloc()
958 #endif
959 {
960 GEDGE h;
961
962 debugmessage("internal_edgealloc","");
963 if (edge_freelist) {
964 h = edge_freelist;
965 edge_freelist = EINTERN(edge_freelist);
966 }
967 else {
968 h = (GEDGE) myalloc(sizeof(struct gedge));
969 #ifdef DEBUG
970 act_alloc_edges++;
971 PRINTF("Alloc Summary: %ld GEDGEs allocated\n",act_alloc_edges);
972 #endif
973 }
974
975 ESTART(h) = NULL;
976 EEND(h) = NULL;
977 ESTARTX(h) = 0;
978 ESTARTY(h) = 0;
979 ETBENDX(h) = 0;
980 ETBENDY(h) = 0;
981 EBBENDX(h) = 0;
982 EBBENDY(h) = 0;
983 EENDX(h) = 0;
984 EENDY(h) = 0;
985 EORI(h) = NO_ORI;
986 EORI2(h) = NO_ORI;
987 ELABEL(h) = NULL;
988 EART(h) = 'U';
989 ELNODE(h) = NULL;
990 EANCHOR(h) = 0;
991 EINVISIBLE(h) = 0;
992 EWEIGHTS(h) = 0;
993 EWEIGHTP(h) = 0;
994 ENEXT(h) = NULL;
995 EINTERN(h) = NULL;
996 ELABELCOL(h) = BLACK;
997 return(h);
998 }
999
1000
1001 /* Allocate a real edge
1002 * --------------------
1003 * and update the edgelist. These edges are specified, e.g.
1004 * as edge: { ... }
1005 * We inheret the attributes from the refedge.
1006 */
1007
1008 #ifdef ANSI_C
edgealloc(GEDGE refedge)1009 GEDGE edgealloc(GEDGE refedge)
1010 #else
1011 GEDGE edgealloc(refedge)
1012 GEDGE refedge;
1013 #endif
1014 {
1015 GEDGE h;
1016
1017 debugmessage("edgealloc","");
1018 h = internal_edgealloc();
1019 copy_edgeattributes(refedge, h);
1020 EBEFORE(h) = edgelistend;
1021 if (edgelistend) ENEXT(edgelistend) = h;
1022 edgelistend = h;
1023 edgeanz++;
1024 if (edgelist == NULL) edgelist = h;
1025 return(h);
1026 }
1027
1028
1029 /* Initialize an edge with the edge defaults
1030 * -----------------------------------------
1031 */
1032
1033 #ifdef ANSI_C
edgedefaults(GEDGE edge)1034 void edgedefaults(GEDGE edge)
1035 #else
1036 void edgedefaults(edge)
1037 GEDGE edge;
1038 #endif
1039 {
1040 debugmessage("edgedefaults","");
1041
1042 ELABEL(edge) = NULL;
1043 ELSTYLE(edge) = SOLID;
1044 ETHICKNESS(edge) = 2;
1045 ECLASS(edge) = 1;
1046 EPRIO(edge) = 1;
1047 EHORDER(edge) = -1;
1048 ECOLOR(edge) = BLACK;
1049 ELABELCOL(edge) = BLACK;
1050 EARROWSIZE(edge) = 10;
1051 EARROWSTYLE(edge) = ASSOLID;
1052 EARROWCOL(edge) = BLACK;
1053 EARROWBSIZE(edge) = 0;
1054 EARROWBSTYLE(edge) = ASNONESPEC;
1055 EARROWBCOL(edge) = BLACK;
1056 }
1057
1058
1059 /* Initialize an edge with the foldedge defaults
1060 * ---------------------------------------------
1061 */
1062
1063 #ifdef ANSI_C
foldedgedefaults(GEDGE edge)1064 void foldedgedefaults(GEDGE edge)
1065 #else
1066 void foldedgedefaults(edge)
1067 GEDGE edge;
1068 #endif
1069 {
1070 debugmessage("foldedgedefaults","");
1071
1072 ELABEL(edge) = "...";
1073 ELSTYLE(edge) = -1;
1074 ETHICKNESS(edge) = 4;
1075 ECLASS(edge) = -1;
1076 EPRIO(edge) = -1;
1077 EHORDER(edge) = -1;
1078 ECOLOR(edge) = -1;
1079 ELABELCOL(edge) = -1;
1080 EARROWSIZE(edge) = -1;
1081 EARROWSTYLE(edge) = -1;
1082 EARROWCOL(edge) = -1;
1083 EARROWBSIZE(edge) = -1;
1084 EARROWBSTYLE(edge) = -1;
1085 EARROWBCOL(edge) = -1;
1086 }
1087
1088
1089 /* Copy the foldedge attributes from fn to y
1090 * -----------------------------------------
1091 */
1092
1093 #ifdef ANSI_C
inherit_foldedge_attributes(GEDGE fn,GEDGE y)1094 void inherit_foldedge_attributes(GEDGE fn, GEDGE y)
1095 #else
1096 void inherit_foldedge_attributes(fn, y)
1097 GEDGE fn, y;
1098 #endif
1099 {
1100 debugmessage("inherit_foldedge_attributes","");
1101
1102 if (ELABEL(fn)) ELABEL(y) = ELABEL(fn);
1103 if (ELSTYLE(fn) != -1) ELSTYLE(y) = ELSTYLE(fn);
1104 if (ETHICKNESS(fn) != -1) ETHICKNESS(y) = ETHICKNESS(fn);
1105 if (ECLASS(fn) != -1) ECLASS(y) = ECLASS(fn);
1106 if (EPRIO(fn) != -1) EPRIO(y) = EPRIO(fn);
1107 if (EHORDER(fn) != -1) EHORDER(y) = EHORDER(fn);
1108 if (ECOLOR(fn) != -1) ECOLOR(y) = ECOLOR(fn);
1109 if (ELABELCOL(fn) != -1) ELABELCOL(y) = ELABELCOL(fn);
1110 if (EARROWSIZE(fn) != -1) EARROWSIZE(y) = EARROWSIZE(fn);
1111 if (EARROWSTYLE(fn) != -1) EARROWSTYLE(y) = EARROWSTYLE(fn);
1112 if (EARROWCOL(fn) != -1) EARROWCOL(y) = EARROWCOL(fn);
1113 if (EARROWBSIZE(fn) != -1) EARROWBSIZE(y) = EARROWBSIZE(fn);
1114 if (EARROWBSTYLE(fn)!= -1) EARROWBSTYLE(y) = EARROWBSTYLE(fn);
1115 if (EARROWBCOL(fn) != -1) EARROWBCOL(y) = EARROWBCOL(fn);
1116 }
1117
1118
1119 /* Copy a GEDGE object x into a second GEDGE object y
1120 * --------------------------------------------------
1121 */
1122
1123 #ifdef ANSI_C
copy_edgeattributes(GEDGE x,GEDGE y)1124 void copy_edgeattributes(GEDGE x, GEDGE y)
1125 #else
1126 void copy_edgeattributes(x, y)
1127 GEDGE x, y;
1128 #endif
1129 {
1130 ELABEL(y) = ELABEL(x);
1131 ELSTYLE(y) = ELSTYLE(x);
1132 ETHICKNESS(y) = ETHICKNESS(x);
1133 ECLASS(y) = ECLASS(x);
1134 EPRIO(y) = EPRIO(x);
1135 EHORDER(y) = EHORDER(x);
1136 ECOLOR(y) = ECOLOR(x);
1137 ELABELCOL(y) = ELABELCOL(x);
1138 EARROWSIZE(y) = EARROWSIZE(x);
1139 EARROWSTYLE(y) = EARROWSTYLE(x);
1140 EARROWCOL(y) = EARROWCOL(x);
1141 EARROWBSIZE(y) = EARROWBSIZE(x);
1142 EARROWBSTYLE(y) = EARROWBSTYLE(x);
1143 EARROWBCOL(y) = EARROWBCOL(x);
1144 }
1145
1146
1147
1148 /* Allocate a temporary GEDGE object
1149 * ---------------------------------
1150 * and update the tmpedgelist. These are edges to dummy nodes or
1151 * to labels.
1152 */
1153
1154 #ifdef ANSI_C
tmpedgealloc(int lstyle,int thick,int xclass,int prio,int ecolor,int elcol,int arrows,int barrows,int arrowsty,int barrowsty,int arrowc,int barrowc,int horder)1155 GEDGE tmpedgealloc(
1156 int lstyle,
1157 int thick,
1158 int xclass,
1159 int prio,
1160 int ecolor,
1161 int elcol,
1162 int arrows,
1163 int barrows,
1164 int arrowsty,
1165 int barrowsty,
1166 int arrowc,
1167 int barrowc,
1168 int horder)
1169 #else
1170 GEDGE tmpedgealloc(lstyle,thick,xclass,prio,ecolor,elcol,arrows,
1171 barrows,arrowsty,barrowsty,arrowc,barrowc,horder)
1172 int lstyle,thick,xclass,prio,ecolor,elcol,arrows,
1173 barrows,arrowsty,barrowsty,arrowc,barrowc,horder;
1174 #endif
1175 {
1176 GEDGE h;
1177
1178 debugmessage("tmpedgealloc","");
1179 h = internal_edgealloc();
1180
1181 ELSTYLE(h) = lstyle;
1182 ETHICKNESS(h) = thick;
1183 ECLASS(h) = xclass;
1184 EPRIO(h) = prio;
1185 EHORDER(h) = horder;
1186 ECOLOR(h) = ecolor;
1187 ELABELCOL(h) = elcol;
1188 EBEFORE(h) = NULL;
1189 EARROWSTYLE(h) = ASSOLID;
1190 EARROWCOL(h) = ecolor;
1191 EARROWSIZE(h) = arrows;
1192 EARROWSTYLE(h) = arrowsty;
1193 EARROWCOL(h) = arrowc;
1194 EARROWBSIZE(h) = barrows;
1195 EARROWBSTYLE(h) = barrowsty;
1196 EARROWBCOL(h) = barrowc;
1197
1198 EINTERN(h) = tmpedgelist;
1199 tmpedgelist = h;
1200 return(h);
1201 }
1202
1203
1204 /* Deallocate all temporary GEDGE objects
1205 * --------------------------------------
1206 */
1207
1208 #ifdef ANSI_C
free_tmpedges(void)1209 static void free_tmpedges(void)
1210 #else
1211 static void free_tmpedges()
1212 #endif
1213 {
1214 GEDGE h;
1215
1216 debugmessage("free_tmpedges","");
1217 h = tmpedgelist;
1218 if (h) {
1219 while (EINTERN(h)) h = EINTERN(h);
1220 EINTERN(h) = edge_freelist;
1221 edge_freelist = tmpedgelist;
1222 tmpedgelist = NULL;
1223 }
1224 }
1225
1226
1227 /*--------------------------------------------------------------------*/
1228
1229 /* Memory Management lists of GEDGE objects
1230 * ========================================
1231 */
1232
1233 /* Lists of GEDGE objects are used in adjacency lists.
1234 * We use special cons-cells, i.e. ADJEDGE objects, whose
1235 * heads are GEDGE objects. Because these cons-cells are temporary,
1236 * we use a similar memory management as for temporary GNODE objects.
1237 *
1238 * Further, we have one nontemporary list of edges that contains the
1239 * default connections as specified by `near_edge'. This is the
1240 * near_edge_list.
1241 * Dito, we have one nontemporary list of edges that contains the
1242 * edges specified by `back_edge'. This is the back_edge_list.
1243 */
1244
1245
1246 /* for stable default connections: */
1247
1248 ADJEDGE near_edge_list = NULL; /* list of default connections */
1249 ADJEDGE bent_near_edge_list = NULL; /* list of bent near edges */
1250 ADJEDGE back_edge_list = NULL; /* list of back edges */
1251
1252 /* for temporaries: */
1253
1254 static ADJEDGE tmpeconslist = NULL; /* list of allocated cons cells */
1255 static ADJEDGE econs_freelist = NULL; /* list of free cons cells */
1256
1257
1258 /* Insert a near edge into near_edge_list
1259 * --------------------------------------
1260 * First, we look in the free list, if we have a free cell. Otherwise,
1261 * we allocate a cell from the core memory.
1262 */
1263
1264 #ifdef ANSI_C
near_edge_insert(GEDGE e)1265 void near_edge_insert(GEDGE e)
1266 #else
1267 void near_edge_insert(e)
1268 GEDGE e;
1269 #endif
1270 {
1271 ADJEDGE h;
1272
1273 debugmessage("near_edge_insert","");
1274 if (econs_freelist) {
1275 h = econs_freelist;
1276 econs_freelist = AINTERN(econs_freelist);
1277 }
1278 else h = (ADJEDGE)myalloc(sizeof(struct adjedge));
1279 AKANTE(h) = e;
1280 ANEXT(h) = AINTERN(h) = near_edge_list;
1281 near_edge_list = h;
1282 }
1283
1284
1285 /* Insert a bent near edge into bent_near_edge_list
1286 * ------------------------------------------------
1287 * First, we look in the free list, if we have a free cell. Otherwise,
1288 * we allocate a cell from the core memory.
1289 */
1290
1291 #ifdef ANSI_C
bentnear_edge_insert(GEDGE e)1292 void bentnear_edge_insert(GEDGE e)
1293 #else
1294 void bentnear_edge_insert(e)
1295 GEDGE e;
1296 #endif
1297 {
1298 ADJEDGE h;
1299
1300 debugmessage("bentnear_edge_insert","");
1301 if (econs_freelist) {
1302 h = econs_freelist;
1303 econs_freelist = AINTERN(econs_freelist);
1304 }
1305 else h = (ADJEDGE)myalloc(sizeof(struct adjedge));
1306 AKANTE(h) = e;
1307 ANEXT(h) = AINTERN(h) = bent_near_edge_list;
1308 bent_near_edge_list = h;
1309 }
1310
1311
1312
1313 /* Insert a back edge into back_edge_list
1314 * --------------------------------------
1315 * First, we look in the free list, if we have a free cell. Otherwise,
1316 * we allocate a cell from the core memory.
1317 */
1318
1319 #ifdef ANSI_C
back_edge_insert(GEDGE e)1320 void back_edge_insert(GEDGE e)
1321 #else
1322 void back_edge_insert(e)
1323 GEDGE e;
1324 #endif
1325 {
1326 ADJEDGE h;
1327
1328 debugmessage("back_edge_insert","");
1329 if (econs_freelist) {
1330 h = econs_freelist;
1331 econs_freelist = AINTERN(econs_freelist);
1332 }
1333 else h = (ADJEDGE)myalloc(sizeof(struct adjedge));
1334 AKANTE(h) = e;
1335 ANEXT(h) = AINTERN(h) = back_edge_list;
1336 back_edge_list = h;
1337 }
1338
1339
1340
1341 /* Allocate a ADJEDGE object
1342 * -------------------------
1343 * First, we look in the free list, if we have a free cell. Otherwise,
1344 * we allocate a cell from the core memory.
1345 */
1346
1347 #ifdef ANSI_C
edgelist_alloc(void)1348 static ADJEDGE edgelist_alloc(void)
1349 #else
1350 static ADJEDGE edgelist_alloc()
1351 #endif
1352 {
1353 ADJEDGE h;
1354
1355 debugmessage("edgelist_alloc","");
1356 if (econs_freelist) {
1357 h = econs_freelist;
1358 econs_freelist = AINTERN(econs_freelist);
1359 }
1360 else h = (ADJEDGE)myalloc(sizeof(struct adjedge));
1361 AINTERN(h) = tmpeconslist;
1362 tmpeconslist = h;
1363 return(h);
1364 }
1365
1366
1367 /* Add a new edge to the predecessors of a node
1368 * --------------------------------------------
1369 */
1370
1371 #ifdef ANSI_C
prededgealloc(GNODE node,GEDGE edge)1372 ADJEDGE prededgealloc(GNODE node, GEDGE edge)
1373 #else
1374 ADJEDGE prededgealloc(node,edge)
1375 GNODE node;
1376 GEDGE edge;
1377 #endif
1378 {
1379 ADJEDGE e;
1380
1381 /* assert((EEND(edge)==node)); */
1382 e = edgelist_alloc();
1383 AKANTE(e) = edge;
1384 ANEXT(e) = NPRED(node);
1385 NPRED(node) = e;
1386 return(e);
1387 }
1388
1389
1390 /* Add a new cons cell to the successors of a node
1391 * -----------------------------------------------
1392 */
1393
1394 #ifdef ANSI_C
succedgealloc(GNODE node,GEDGE edge)1395 ADJEDGE succedgealloc(GNODE node, GEDGE edge)
1396 #else
1397 ADJEDGE succedgealloc(node,edge)
1398 GNODE node;
1399 GEDGE edge;
1400 #endif
1401 {
1402 ADJEDGE e;
1403
1404 /* assert((ESTART(edge)==node)); */
1405 e = edgelist_alloc();
1406 AKANTE(e) = edge;
1407 ANEXT(e) = NSUCC(node);
1408 NSUCC(node) = e;
1409 return(e);
1410 }
1411
1412
1413 /* Deallocate all temporary ADJEDGE objects
1414 * ----------------------------------------
1415 */
1416
1417 #ifdef ANSI_C
free_edgelists(void)1418 static void free_edgelists(void)
1419 #else
1420 static void free_edgelists()
1421 #endif
1422 {
1423 ADJEDGE h;
1424
1425 debugmessage("free_edgelists","");
1426 h = tmpeconslist;
1427 if (h) {
1428 while(AINTERN(h)) h = AINTERN(h);
1429 AINTERN(h) = econs_freelist;
1430 econs_freelist = tmpeconslist;
1431 tmpeconslist = NULL;
1432 }
1433 }
1434
1435
1436
1437 /*--------------------------------------------------------------------*/
1438
1439 /* Memory Management for CONNECT objects
1440 * =====================================
1441 */
1442
1443 /* CONNECT objects are annotations of GNODE objects.
1444 * They indicate that two nodes must be directly neigboured during
1445 * the layout. This occurs if nodes are at the same level connected.
1446 * E.g.
1447 * / | \ this situation is layouted as if we had only
1448 * A<----B---->C one node B. The connections of B are A and C.
1449 */
1450
1451 static CONNECT connectlist = NULL; /* list of alloc. connect cells */
1452 static CONNECT connect_freelist = NULL; /* list of free connect cells */
1453
1454
1455 /* Allocate a CONNECT object
1456 * -------------------------
1457 * First, we look in the free list, if we have a free cell. Otherwise,
1458 * we allocate a cell from the core memory.
1459 * The new connect node is inserted into the connection field of the
1460 * GNODE node.
1461 */
1462
1463 #ifdef ANSI_C
connectalloc(GNODE node)1464 CONNECT connectalloc(GNODE node)
1465 #else
1466 CONNECT connectalloc(node)
1467 GNODE node;
1468 #endif
1469 {
1470 CONNECT h;
1471
1472 debugmessage("connectalloc","");
1473 if (connect_freelist) {
1474 h = connect_freelist;
1475 connect_freelist = CINTERN(connect_freelist);
1476 }
1477 else h = (CONNECT)myalloc(sizeof(struct connect));
1478 CTARGET(h) = NULL;
1479 CEDGE(h) = NULL;
1480 CTARGET2(h) = NULL;
1481 CEDGE2(h) = NULL;
1482 CINTERN(h) = connectlist;
1483 connectlist = h;
1484 NCONNECT(node) = h;
1485 return(h);
1486 }
1487
1488
1489 /* Deallocate all temporary CONNECT objects
1490 * ----------------------------------------
1491 */
1492
1493 #ifdef ANSI_C
free_connect(void)1494 static void free_connect(void)
1495 #else
1496 static void free_connect()
1497 #endif
1498 {
1499 CONNECT h;
1500
1501 debugmessage("free_connect","");
1502 h = connectlist;
1503 if (h) {
1504 while(CINTERN(h)) h = CINTERN(h);
1505 CINTERN(h) = connect_freelist;
1506 connect_freelist = connectlist;
1507 connectlist = NULL;
1508 }
1509 }
1510
1511
1512 /*--------------------------------------------------------------------*/
1513
1514 /* Memory Management for DLLIST objects
1515 * ====================================
1516 */
1517
1518 /* To have a good layout, we calculate the number of crossings of edges
1519 * and try to minimize them. For the calculation of crossings, we need
1520 * double linked lists of nodes (see step2.c) representing the upper
1521 * list of touched nodes and the lower list of touched nodes. Because
1522 * nodes may have multible occurences in these lists, we use the special
1523 * data structure DLLIST.
1524 * We reuse the DSUCC field to keep the list of free dllist nodes.
1525 * But THIS dllist_freelist is NOT double linked.
1526 */
1527
1528 static DLLIST dllist_freelist = NULL; /* list of free dllist nodes */
1529
1530
1531 /* Allocate a DLLIST object
1532 * ------------------------
1533 * First, we look in the free list, if we have a free cell. Otherwise,
1534 * we allocate a cell from the core memory.
1535 * The successor is always NULL, because we append at the end of the
1536 * list. pred is the predecessor.
1537 */
1538
1539
1540 #ifdef ANSI_C
dllist_alloc(GNODE node,DLLIST pred)1541 DLLIST dllist_alloc(GNODE node, DLLIST pred)
1542 #else
1543 DLLIST dllist_alloc(node,pred)
1544 GNODE node;
1545 DLLIST pred;
1546 #endif
1547 {
1548 DLLIST h;
1549
1550 debugmessage("dllist_alloc","");
1551 if (dllist_freelist) {
1552 h = dllist_freelist;
1553 dllist_freelist = DSUCC(dllist_freelist);
1554 }
1555 else h = (DLLIST)myalloc(sizeof(struct dllist));
1556 DNODE(h) = node;
1557 DPRED(h) = pred;
1558 DSUCC(h) = NULL;
1559 return(h);
1560 }
1561
1562
1563 /* Deallocate one DLLIST objects
1564 * -----------------------------
1565 * The crossing algorithm is stable enough such that after calculation
1566 * of crossings all DLLIST elements are given free by this function.
1567 * Thus we don't need any additional memory management.
1568 */
1569
1570 #ifdef ANSI_C
dllist_free(DLLIST x)1571 void dllist_free(DLLIST x)
1572 #else
1573 void dllist_free(x)
1574 DLLIST x;
1575 #endif
1576 {
1577 debugmessage("dllist_free","");
1578 DSUCC(x) = dllist_freelist;
1579 dllist_freelist = x;
1580 }
1581
1582
1583 /* Deallocate a list of DLLIST objects
1584 * -----------------------------------
1585 */
1586
1587 #ifdef ANSI_C
dllist_free_all(DLLIST x)1588 void dllist_free_all(DLLIST x)
1589 #else
1590 void dllist_free_all(x)
1591 DLLIST x;
1592 #endif
1593 {
1594 DLLIST h;
1595
1596 debugmessage("dllist_free","");
1597 if (x) {
1598 h = x;
1599 while (DSUCC(h)) h = DSUCC(h);
1600 DSUCC(h) = dllist_freelist;
1601 dllist_freelist = x;
1602 }
1603 }
1604
1605
1606
1607 /*--------------------------------------------------------------------*/
1608
1609
1610 /* Deallocation of all temporary lists
1611 * ===================================
1612 */
1613
1614
1615 #ifdef ANSI_C
free_all_lists(void)1616 void free_all_lists(void)
1617 #else
1618 void free_all_lists()
1619 #endif
1620 {
1621 free_tmpnodes();
1622 free_tmpedges();
1623 free_nodelists();
1624 free_edgelists();
1625 free_connect();
1626 }
1627
1628
1629 /* Reinitialization of all struct keeping lists
1630 * --------------------------------------------
1631 */
1632
1633 #ifdef ANSI_C
reinit_all_lists(void)1634 void reinit_all_lists(void)
1635 #else
1636 void reinit_all_lists()
1637 #endif
1638 {
1639 ufoldstart = NULL;
1640 foldstart = NULL;
1641 foldstops = NULL;
1642 f_subgraphs = NULL;
1643 uf_subgraphs= NULL;
1644 invis_nodes = NULL;
1645 labellist = NULL;
1646 labellistend = NULL;
1647 dummylist = NULL;
1648
1649 nodeanz = 0;
1650 dummyanz = 0;
1651 nodelist = NULL;
1652 nodelistend = NULL;
1653 graphlist = NULL;
1654 graphlistend = NULL;
1655 tmpnodelist = NULL;
1656 node_freelist = NULL;
1657
1658 tmpnconslist = NULL;
1659 ncons_freelist = NULL;
1660
1661 edgeanz = 0;
1662 edgelist = NULL;
1663 edgelistend = NULL;
1664 tmpedgelist = NULL;
1665 edge_freelist = NULL;
1666
1667 near_edge_list = NULL;
1668 back_edge_list = NULL;
1669 bent_near_edge_list = NULL;
1670 tmpeconslist = NULL;
1671 econs_freelist = NULL;
1672
1673 connectlist = NULL;
1674 connect_freelist = NULL;
1675
1676 dllist_freelist = NULL;
1677 }
1678
1679
1680