1 /* SCCS-info %W% %E% */ 2 3 /*--------------------------------------------------------------------*/ 4 /* */ 5 /* VCG : Visualization of Compiler Graphs */ 6 /* -------------------------------------- */ 7 /* */ 8 /* file: alloc.h */ 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 21 /* $Id: alloc.h,v 3.12 1995/02/08 11:11:14 sander Exp $ */ 22 23 /* 24 * Copyright (C) 1993-2005 Saarland University 25 * 26 * This program and documentation is free software; you can redistribute 27 * it under the terms of the GNU General Public License as published by 28 * the Free Software Foundation; either version 2 of the License, or 29 * (at your option) any later version. 30 * 31 * This program is distributed in the hope that it will be useful, 32 * but WITHOUT ANY WARRANTY; without even the implied warranty of 33 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 34 * GNU General Public License for more details. 35 * 36 * You should have received a copy of the GNU General Public License 37 * along with this program; if not, write to the Free Software 38 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 39 * 40 * The software is available per anonymous ftp at ftp.cs.uni-sb.de. 41 * Contact sander@cs.uni-sb.de for additional information. 42 */ 43 44 45 /* 46 * $Log: alloc.h,v $ 47 * Revision 3.12 1995/02/08 11:11:14 sander 48 * Distribution version 1.3. 49 * 50 * Revision 3.11 1994/12/23 18:12:45 sander 51 * Manhatten layout added. 52 * Option interface cleared. 53 * infobox behaviour improved. 54 * First version of fisheye (carthesian). 55 * Options Noedge and nonode. 56 * Titles in the node title box are now sorted. 57 * Timelimit functionality improved. 58 * 59 * Revision 3.10 1994/08/05 12:13:25 sander 60 * Treelayout added. Attributes "treefactor" and "spreadlevel" added. 61 * Scaling as abbreviation of "stretch/shrink" added. 62 * 63 * Revision 3.9 1994/08/03 13:58:44 sander 64 * Horizontal order mechanism changed. 65 * Attribute horizontal_order for edges added. 66 * 67 * Revision 3.8 1994/08/02 15:36:12 sander 68 * CHECKNODE option added to allow tracing of properties 69 * of one single node. 70 * 71 * Revision 3.7 1994/06/07 14:09:59 sander 72 * Splines implemented. 73 * HP-UX, Linux, AIX, Sun-Os, IRIX compatibility tested. 74 * The tool is now ready to be distributed. 75 * 76 * Revision 3.6 1994/05/16 08:56:03 sander 77 * shape attribute (boxes, rhombs, ellipses, triangles) added. 78 * 79 * Revision 3.5 1994/05/05 08:20:30 sander 80 * dllist_free_all added for the local optimization of crossings. 81 * 82 * Revision 3.4 1994/04/27 16:05:19 sander 83 * Some general changes for the PostScript driver. 84 * Horizontal order added. Bug fixes of the folding phases: 85 * Folding of nested graphs works now. 86 * 87 * Revision 3.3 1994/03/04 19:11:24 sander 88 * Specification of levels per node added. 89 * X11 geometry behaviour (option -geometry) changed such 90 * that the window is now opened automatically. 91 * 92 * Revision 3.2 1994/03/03 15:35:39 sander 93 * Edge line style `invisible' added. 94 * 95 * Revision 3.1 1994/03/01 10:59:55 sander 96 * Copyright and Gnu Licence message added. 97 * Problem with "nearedges: no" and "selfloops" solved. 98 * 99 * Revision 2.4 1994/01/21 19:33:46 sander 100 * VCG Version tested on Silicon Graphics IRIX, IBM R6000 AIX and Sun 3/60. 101 * Option handling improved. Option -grabinputfocus installed. 102 * X11 Font selection scheme implemented. The user can now select a font 103 * during installation. 104 * Sun K&R C (a nonansi compiler) tested. Some portabitility problems solved. 105 * 106 * Revision 2.3 1994/01/03 15:29:06 sander 107 * First complete X11 version. 108 */ 109 110 #ifndef ALLOC_H 111 #define ALLOC_H 112 113 /*--------------------------------------------------------------------*/ 114 115 /* Attribute values 116 *----------------- 117 */ 118 119 /* Color definitions 120 * - - - - - - - - - 121 */ 122 123 /* COFFSET is the vertical offset: we need to make the drawing area 124 * 60 bits larger than specified, because of a bug in Sunview on 125 * color screens. 126 * Maybe it is not needed for X11 (?) 127 */ 128 129 #define COFFSET 60 130 131 /* number of colors */ 132 133 #define CMAPSIZE 256 134 #define BASECMAPSIZE 32 135 136 /* color access */ 137 138 #define COLOR(c) (c) 139 140 #define BLACK 31 141 #define BLUE 1 142 #define RED 2 143 #define GREEN 3 144 #define YELLOW 4 145 #define MAGENTA 5 146 #define CYAN 6 147 #define WHITE 0 148 #define DARKGREY 7 149 #define DARKBLUE 8 150 #define DARKRED 9 151 #define DARKGREEN 10 152 #define DARKYELLOW 11 153 #define DARKMAGENTA 12 154 #define DARKCYAN 13 155 #define GOLD 14 156 #define LIGHTGREY 15 157 #define LIGHTBLUE 16 158 #define LIGHTRED 17 159 #define LIGHTGREEN 18 160 #define LIGHTYELLOW 19 161 #define LIGHTMAGENTA 20 162 #define LIGHTCYAN 21 163 #define LILAC 22 164 #define TURQUOISE 23 165 #define AQUAMARINE 24 166 #define KHAKI 25 167 #define PURPLE 26 168 #define YELLOWGREEN 27 169 #define PINK 28 170 #define ORANGE 29 171 #define ORCHID 30 172 173 /* Graph orientation */ 174 175 #define TOP_TO_BOTTOM 0 176 #define LEFT_TO_RIGHT 1 177 #define RIGHT_TO_LEFT 2 178 #define BOTTOM_TO_TOP 3 179 180 /* Node y-alignment */ 181 182 #define AL_TOP 0 183 #define AL_CENTER 1 184 #define AL_BOTTOM 2 185 186 /* Display edge labels */ 187 188 #define NO 0 189 #define YES 1 190 191 /* Textmodes */ 192 193 #define CENTER 0 194 #define LEFT 1 195 #define RIGHT 2 196 197 /* Linestyles */ 198 199 #define SOLID 0 200 #define DOTTED 1 201 #define DASHED 2 202 #define UNVISIBLE 3 203 204 /* Arrowstyles */ 205 206 #define ASNONE 0 207 #define ASSOLID 1 208 #define ASLINE 2 209 #define ASNONESPEC 3 210 211 /* Arrow modi */ 212 213 #define AMFIXED 0 214 #define AMFREE 1 215 216 /* Shapes */ 217 218 #define BOX 0 219 #define RHOMB 1 220 #define ELLIPSE 2 221 #define TRIANGLE 3 222 223 /* Edge orientation (no orientation, north, north east, ...) */ 224 225 #define NO_ORI 0 226 #define ORI_NORTH 1 227 #define ORI_NORTHEAST 2 228 #define ORI_NORTHWEST 3 229 #define ORI_SOUTH 4 230 #define ORI_SOUTHEAST 5 231 #define ORI_SOUTHWEST 6 232 #define ORI_EAST 7 233 #define ORI_WEST 8 234 235 /*--------------------------------------------------------------------*/ 236 237 /* Auxiliary Structs 238 * ================= 239 */ 240 241 /* Connections 242 * ------------ 243 */ 244 245 /* Connections are necessary for the layout of directly neighboured 246 * connected nodes at the same level. This situation may occur accidently, 247 * but automatical occurs if there is a self loop. 248 * 249 * On self loops: 250 * - - - - - - - N A self loop of N is an edge (N,N). 251 * / ^ To layout this, we create a dummy node 252 * / \ D and a pseudo node P. D and P are 253 * D-----P always neighboured at the same level. 254 * 255 * Only N and D is layouted. The connection of the dummy node D contains the 256 * information needed to draw P (that is not layouted), i.e.: 257 * CTARGET(D) -> P 258 * CEDGE(D) -> edge (D,P) 259 * CTARGET(P) -> D 260 * CEDGE(P) -> edge (D,P) 261 * 262 * On connected neigboured nodes: 263 * - - - - - - - - - - - - - - - 264 * / | \ or | \ or / | 265 * A<----B---->C B----->C C<-----B 266 * 267 * Only B is layouted. The connection of B contains the information 268 * to draw A and/or C, i.e. 269 * CTARGET(B) -> C 270 * CEDGE(B) -> edge (B,C) 271 * CTARGET2(B) -> A or NULL, if not necessary 272 * CEDGE2(B) -> edge (B,A) or NULL, if not necessary 273 * 274 * CTARGET(C) -> B 275 * CEDGE(C) -> edge (B,C) 276 * etc. 277 * 278 * We call the connection field of B a `forward connection' and the 279 * connection field of B or A a `backward connection', because its 280 * in converse of the edge direction. 281 * Note that A or C can also contain connections, e.g. on 282 * | \ \ 283 * B---->C---->D CTARGET(B) = C, CTARGET(C) = D, ... 284 * 285 * 286 */ 287 288 289 typedef struct connect { 290 struct gnode *target; /* First found target */ 291 struct gedge *edge; /* and its edge */ 292 struct gnode *target2; /* Second found target */ 293 struct gedge *edge2; /* and its edge */ 294 struct connect *internal_next; /* for memory allocation only */ 295 } *CONNECT; 296 297 #define CTARGET(x) ((x)->target) 298 #define CEDGE(x) ((x)->edge) 299 #define CTARGET2(x) ((x)->target2) 300 #define CEDGE2(x) ((x)->edge2) 301 #define CINTERN(x) ((x)->internal_next) 302 303 304 305 /*--------------------------------------------------------------------*/ 306 307 /* Graphs 308 * ====== 309 * The complete data structure of a graph is an adjacency list 310 * representation, i.e. all nodes contain adjacency lists of 311 * incoming and outgoing edges. 312 * Furthermore, all nodes contain in NROOT a pointer to the subgraph 313 * summary node they belong to. NROOT of top level nodes is NULL. 314 * Summary nodes of subgraphs contain in NSGRAPH a list of all nodes 315 * that belong to this subgraph. 316 * Furthermore all real nodes are in the node list, while all graph 317 * summary nodes are in the graphlist. 318 * E.g. the top graph contains a node A and a graph S1 319 * which contains nodes B and C and a graph S2 320 * which contains nodes D and E 321 * NROOT connection: 322 * 323 * nodelist --> A --> B ---> C --> D ---> E 324 * | \ / \ / 325 * NULL \ / \ /NROOT 326 * \/ \/ 327 * graphlist ----------> S1 --------> S2 328 * | | 329 * V V 330 * NULL NULL 331 * 332 * ,-----------------------------, 333 * NSGRAPH connection: | ,-------------, | 334 * V V | | 335 * *->* *----->*->* *----->* | | 336 * | | | | | | | | | 337 * V | V V | V V | | 338 * nodelist --> A -+> B ---> C -+> D ---> E | | 339 * | | | | 340 * `-----, `-----, | | 341 * | | NSGRAPH| |NSGRAPH 342 * V V | | 343 * graphlist ----------> S1 --------> S2 | | 344 * | | | | 345 * | `----------' | 346 * `--------------------------' 347 */ 348 349 350 /* Nodes of a graph 351 * ---------------- 352 * Graphs are also represented as nodes, i.e. as summary node. 353 * Graphs s are initially not in the nodelist, but in the graphlist. 354 * In consequence, NINLIST(s) is 0 for them. 355 */ 356 357 typedef struct gnode { 358 359 /* Each node has an unique reference number. 360 * These are used to debug, and to have a stable layout, 361 * because we use the numbers as sorting criteria. 362 */ 363 364 long refnum; 365 366 /* These attributes come directly from the specification */ 367 368 char *title; 369 char *label; 370 char *info1; 371 char *info2; 372 char *info3; 373 int width; 374 int height; 375 long sxloc; 376 long syloc; 377 char textmode; 378 char borderwidth; 379 char folding; 380 char color; 381 char textcolor; 382 char bordercolor; 383 char status; 384 char shape; 385 int shrink; 386 int stretch; 387 int level; 388 int nhorder; 389 390 /* These attributes are on summary nodes (graphs,regions) */ 391 392 struct gnlist *subgraph; /* List of subgraphs */ 393 struct gnode *root; /* Root of graph */ 394 struct gnode *regionrepl; /* Replacement node for */ 395 /* roots of regions */ 396 struct gnlist *region; /* List of nodes in region */ 397 struct gnode *regroot; /* Root of region */ 398 399 /* These are the locations used for the layout */ 400 401 long xloc; 402 long yloc; 403 404 /* nodelist, graphlist links: these are double linked lists */ 405 406 struct gnode *next; /* successor in the node/graphlist */ 407 struct gnode *before; /* predecessor in the node/graphlist */ 408 409 char in_nodelist; /* flag, 1 if node is in nodelist */ 410 char invisible; /* flag, 1 if node is invisible */ 411 412 /* layout attributes: nodes are distributed into layers according 413 * to their deeths relatively to the root of the graph, and have 414 * positions in these layers. 415 */ 416 417 char markiert; /* marker for depth first search */ 418 char revert; /* marker for reverted drawing */ 419 char anchordummy; /* marker for anchor dummy nodes */ 420 int tiefe; /* the number (deepth) of the layer */ 421 int position; /* the position in the layer */ 422 float bary; /* the weight of the bary centering */ 423 424 /* The following two fields have sev. purposes: they are the layout 425 * weights nws and nwp of the layout algorithm, and on drawing 426 * they are used as number of anchor points. 427 * The field weights is also used during the partitioning of 428 * edges as LOWPT of the strongly connected component. 429 * The field weightp is aslo used during the partitioning of 430 * edges as OPENSCC flag of the strongly connected component. 431 */ 432 433 long weights; /* node weight succ. (nws) */ 434 long weightp; /* node weight pred. (nwp) */ 435 436 /* For partitioning the edges, we need to know cross edges, tree 437 * edges, forward edges and backward edges. Thus, we calculate a 438 * depth first search (dfs) and protocol by numbers when we entry 439 * the dfs for a node and when we leave the dfs of this node. 440 */ 441 442 long dfsnum; /* the dfs entry number */ 443 444 int indegree; /* number of incoming edges */ 445 int outdegree; /* number of outgoing edges */ 446 447 /* To calculate crossings, we need a pointer to the last instance 448 * of the upper or lower completion lists. See step2.c 449 */ 450 451 struct dllist *Vpointer; /* this crossing pointer */ 452 453 /* The graph is represented with adjacency lists. We have some 454 * fast accesses to the leftest or rightedst prede/successor. 455 * Further, at connections we temporary change the adjacency 456 * lists. Thus we store the original list in save fields. 457 * For crossing calculation, we need to reorder the adjacency 458 * lists. Thus we use a pointer tmpadj to the actual position 459 * in the adjacency list. 460 */ 461 462 struct adjedge *tmpadj; /* temporary adjacency list */ 463 struct adjedge *pred; /* adjacency list: predecessors */ 464 struct adjedge *succ; /* adjacency list: successors */ 465 struct adjedge *savepred; /* adjacency list: predecessors */ 466 struct adjedge *savesucc; /* adjacency list: successors */ 467 struct gedge *predleft; /* leftest predecessor */ 468 struct gedge *predright; /* rightest predecessor */ 469 struct gedge *succleft; /* leftest successor */ 470 struct gedge *succright; /* rightest successor */ 471 472 struct connect *connection; /* horizontal connection to a */ 473 /* neighboured node, see above */ 474 475 /* The next field has two purposes: During parsing, we use it to 476 * create a hash table of all nontemporary node, to have fast 477 * access to the title. 478 * Otherwise, it is used for the memory management of temporary 479 * nodes. 480 */ 481 482 struct gnode *internal_next; 483 } *GNODE; 484 485 #define NREFNUM(x) ((x)->refnum) 486 #define NTITLE(x) ((x)->title) 487 #define NLABEL(x) ((x)->label) 488 #define NINFO1(x) ((x)->info1) 489 #define NINFO2(x) ((x)->info2) 490 #define NINFO3(x) ((x)->info3) 491 #define NTEXTMODE(x) ((x)->textmode) 492 #define NWIDTH(x) ((x)->width) 493 #define NHEIGHT(x) ((x)->height) 494 #define NSTATE(x) ((x)->status) 495 #define NSHAPE(x) ((x)->shape) 496 #define NBORDERW(x) ((x)->borderwidth) 497 #define NSX(x) ((x)->sxloc) 498 #define NSY(x) ((x)->syloc) 499 #define NX(x) ((x)->xloc) 500 #define NY(x) ((x)->yloc) 501 #define NFOLDING(x) ((x)->folding) 502 #define NCOLOR(x) ((x)->color) 503 #define NTCOLOR(x) ((x)->textcolor) 504 #define NBCOLOR(x) ((x)->bordercolor) 505 #define NSHRINK(x) ((x)->shrink) 506 #define NSTRETCH(x) ((x)->stretch) 507 #define NLEVEL(x) ((x)->level) 508 #define NHORDER(x) ((x)->nhorder) 509 #define NSGRAPH(x) ((x)->subgraph) 510 #define NROOT(x) ((x)->root) 511 #define NREGREPL(x) ((x)->regionrepl) 512 #define NREGION(x) ((x)->region) 513 #define NREGROOT(x) ((x)->regroot) 514 #define NNEXT(x) ((x)->next) 515 #define NBEFORE(x) ((x)->before) 516 #define NINLIST(x) ((x)->in_nodelist) 517 #define NINVISIBLE(x) ((x)->invisible) 518 #define NTIEFE(x) ((x)->tiefe) 519 #define NPOS(x) ((x)->position) 520 #define NMARK(x) ((x)->markiert) 521 #define NREVERT(x) ((x)->revert) 522 #define NANCHORNODE(x) ((x)->anchordummy) 523 #define NBARY(x) ((x)->bary) 524 #define NLOWPT(x) ((x)->weights) 525 #define NOPENSCC(x) ((x)->weightp) 526 #define NWEIGHTS(x) ((x)->weights) 527 #define NWEIGHTP(x) ((x)->weightp) 528 #define NDFS(x) ((x)->dfsnum) 529 #define NHIGHPRIO(x) ((x)->dfsnum) 530 #define NINDEG(x) ((x)->indegree) 531 #define NOUTDEG(x) ((x)->outdegree) 532 #define NVPTR(x) ((x)->Vpointer) 533 #define NTMPADJ(x) ((x)->tmpadj) 534 #define NPRED(x) ((x)->pred) 535 #define NSUCC(x) ((x)->succ) 536 #define NSVPRED(x) ((x)->savepred) 537 #define NSVSUCC(x) ((x)->savesucc) 538 #define NPREDL(x) ((x)->predleft) 539 #define NPREDR(x) ((x)->predright) 540 #define NSUCCL(x) ((x)->succleft) 541 #define NSUCCR(x) ((x)->succright) 542 #define NCONNECT(x) ((x)->connection) 543 #define NINTERN(x) ((x)->internal_next) 544 545 #define NCONTAR(x) (CTARGET(NCONNECT(x))) 546 #define NCONEDG(x) (CEDGE(NCONNECT(x))) 547 #define NCONTAR2(x) (CTARGET2(NCONNECT(x))) 548 #define NCONEDG2(x) (CEDGE2(NCONNECT(x))) 549 550 /* For NREVERT, we allow the values: 551 * --------------------------------- 552 */ 553 554 #define NOREVERT 0 555 #define AREVERT 1 556 #define BREVERT 2 557 558 559 /*--------------------------------------------------------------------*/ 560 561 /* List of GNODE-objects 562 * --------------------- 563 * These are used for various reasons: as list of nodes of a (sub)graph, 564 * as lists of nodes of a region, etc. 565 */ 566 567 typedef struct gnlist { 568 struct gnode *node; /* The node */ 569 struct gnlist *next; /* The remaining list */ 570 struct gnlist *internal_next; /* For memory management */ 571 } *GNLIST; 572 573 #define GNNODE(x) ((x)->node) 574 #define GNNEXT(x) ((x)->next) 575 #define GNINTERN(x) ((x)->internal_next) 576 577 /*--------------------------------------------------------------------*/ 578 579 580 /* Edges of a graph 581 * ---------------- 582 * During the layout, edges are partitioned into reverted edges, 583 * etc. Thus, we have for `kantenart', or EART, or EKIND, respectively, 584 * the following possibilities: 585 * 'U' -> the kind of this edge is undefined, (it is a normal edge) 586 * 'S' -> this is a self loop 587 * 'D' -> this is a biconnection, i.e. arrows at both sides 588 * 'R' -> this is a reverted edge. 589 * If we do not self-layout, we have further: 590 * 'l' -> this edge goes to the left 591 * 'r' -> this edge goes to the right 592 * 593 * The following tags indicate the initial partitionig, but they are not 594 * anymore used. 595 * 'T' -> this is a tree edge 596 * 'F' -> this is a forward edge 597 * 'B' -> this is a backward edge (not yet reverted) 598 * 'C' -> this is a cross edge 599 * 600 * For the x,y co-ordinates, there is a problem if neighoured nodes 601 * are to large. To avoid (1), we allow that edges are bend, see (2) 602 * 603 * - -------- - -------- 604 * |A| | | |A| | | 605 * - | | - | | 606 * \ | M | | | M | 607 * (1) \| | (2) | | | 608 * \ | | | | 609 * |\ | | | | 610 * -\------ \ -------- 611 * \ \ 612 * 613 * i.e. each edge have start point and end point, and further a 614 * bend point that has the same x-co-ordinate as the start point 615 * (hold for top_down_layout). 616 */ 617 618 typedef struct gedge { 619 struct gnode *start; /* Source node */ 620 long sxloc; /* and its co-ordinates */ 621 long syloc; 622 long btxloc; /* Bend location on top of */ 623 long btyloc; /* a node */ 624 long bbxloc; /* Bend location on bottom */ 625 long bbyloc; 626 struct gnode *end; /* Target node */ 627 long exloc; /* and its co-ordinates */ 628 long eyloc; 629 char orientation; /* updown, northwest, etc. */ 630 char orientation2; /* dito, for double edges */ 631 632 /* These attributes come directly from the specification */ 633 634 char linestyle; 635 char thickness; 636 char *label; 637 int priority; 638 int horder; 639 char eclass; 640 char color; 641 char arrowstyle1; 642 char arrowstyle2; 643 char arrowsize1; 644 char arrowcolor1; 645 char arrowsize2; 646 char arrowcolor2; 647 char labelcolor; 648 649 #ifdef ANSI_C 650 #ifdef VMS 651 int anchor; 652 #else 653 signed char anchor; 654 #endif 655 #else 656 int anchor; 657 #endif 658 659 /* The layout decides wether an edge is visible or reverted, etc. */ 660 661 char kantenart; /* flag 'U', 'S' etc. see above */ 662 char invisible; /* 1, if the edge is not visible */ 663 664 /* The following two fields are the layout weights ews and ewp of 665 * the layout algorithm. See the documentation of the layout alg. 666 * On drawing, they are further used as number of anchor point. 667 */ 668 669 long weights; /* edge weight succ. (ews) */ 670 long weightp; /* edge weight pred. (ewp) */ 671 672 struct gnode *labelnode; /* Label node if the edge is replaced */ 673 674 /* edgelist links: these are double linked lists */ 675 676 struct gedge *next; /* successor in the edgelist */ 677 struct gedge *before; /* predecessor in the edgelist */ 678 struct gedge *internal_next; /* for memory allocation */ 679 } *GEDGE; 680 681 #define ESTART(x) ((x)->start) 682 #define EEND(x) ((x)->end) 683 #define ESTARTX(x) ((x)->sxloc) 684 #define ESTARTY(x) ((x)->syloc) 685 #define ETBENDX(x) ((x)->btxloc) 686 #define ETBENDY(x) ((x)->btyloc) 687 #define EBBENDX(x) ((x)->bbxloc) 688 #define EBBENDY(x) ((x)->bbyloc) 689 #define EENDX(x) ((x)->exloc) 690 #define EENDY(x) ((x)->eyloc) 691 #define EORI(x) ((x)->orientation) 692 #define EORI2(x) ((x)->orientation2) 693 #define ELABEL(x) ((x)->label) 694 #define ELABELCOL(x) ((x)->labelcolor) 695 #define ELSTYLE(x) ((x)->linestyle) 696 #define ETHICKNESS(x) ((x)->thickness) 697 #define ECLASS(x) ((x)->eclass) 698 #define EPRIO(x) ((x)->priority) 699 #define EHORDER(x) ((x)->horder) 700 #define ECOLOR(x) ((x)->color) 701 #define EARROWSTYLE(x) ((x)->arrowstyle1) 702 #define EARROWBSTYLE(x) ((x)->arrowstyle2) 703 #define EARROWSIZE(x) ((x)->arrowsize1) 704 #define EARROWBSIZE(x) ((x)->arrowsize2) 705 #define EARROWCOL(x) ((x)->arrowcolor1) 706 #define EARROWBCOL(x) ((x)->arrowcolor2) 707 #define EANCHOR(x) ((x)->anchor) 708 #define ELNODE(x) ((x)->labelnode) 709 #define ENEXT(x) ((x)->next) 710 #define EBEFORE(x) ((x)->before) 711 #define EART(x) ((x)->kantenart) 712 #define EINVISIBLE(x) ((x)->invisible) 713 #define EWEIGHTS(x) ((x)->weights) 714 #define EWEIGHTP(x) ((x)->weightp) 715 #define EINTERN(x) ((x)->internal_next) 716 717 718 719 /*--------------------------------------------------------------------*/ 720 721 /* Adjacency lists 722 * --------------- 723 * Graphs are represented as adjacency list, see above. 724 * The cons cell of the list of edges used in adjacency list 725 * is the struct adjedge. 726 */ 727 728 typedef struct adjedge { 729 struct gedge *kante; /* Edge */ 730 struct adjedge *next; 731 struct adjedge *internal_next; 732 } *ADJEDGE; 733 734 /* direct accesses */ 735 736 #define AKANTE(x) ((x)->kante) 737 #define ANEXT(x) ((x)->next) 738 #define AINTERN(x) ((x)->internal_next) 739 740 /* accesses to attributes of source and target of an edge */ 741 742 #define SOURCE(x) (ESTART(AKANTE(x))) 743 #define TARGET(x) (EEND(AKANTE(x))) 744 #define ESOURCEX(x) (ESTARTX(AKANTE(x))) 745 #define ESOURCEY(x) (ESTARTY(AKANTE(x))) 746 #define ETARGETX(x) (EENDX(AKANTE(x))) 747 #define ETARGETY(x) (EENDY(AKANTE(x))) 748 #define EKIND(x) (EART(AKANTE(x))) 749 #define NSOURTIEFE(x) (NTIEFE(ESTART(AKANTE(x)))) 750 #define NTARTIEFE(x) (NTIEFE(EEND(AKANTE(x)))) 751 752 /*--------------------------------------------------------------------*/ 753 754 /* Layout structs 755 * ============== 756 * To calculate the layout, the nodes are scheduled into layers. 757 * All nodes of one layer have the same vertical position, i.e. 758 * have the same deepth (level number) in the spanning tree of the graph. 759 * Inside the layers, the nodes are scheduled to minimize the crossings 760 * of the edges. 761 */ 762 763 764 /* Depth entries 765 * ------------- 766 * This is an entry in the table of existing layers. Each layer 767 * node contains the list of nodes of this layer, and the layout 768 * values. For the list of nodes, we use two lists to traverse 769 * the nodes forward and backward (similar to a double linked list). 770 */ 771 772 typedef struct depth_entry { 773 int anz; /* Number of nodes of this layer */ 774 int actx; /* actual x coord.in this layer */ 775 int cross; /* number of crossings of layer */ 776 GNODE refnode; /* Reference node for part 3 */ 777 struct gnlist *predlist; /* nodes of this layer (forward) */ 778 struct gnlist *succlist; /* nodes of this layer (backward)*/ 779 char resort_necessary; /* indicates if resorting by */ 780 /* barycentering etc. is needed */ 781 } DEPTH; 782 783 #define TANZ(x) ((x).anz) 784 #define TPRED(x) ((x).predlist) 785 #define TSUCC(x) ((x).succlist) 786 #define TCROSS(x) ((x).cross) 787 #define TACTX(x) ((x).actx) 788 #define TREFN(x) ((x).refnode) 789 #define TRESNEEDED(x) ((x).resort_necessary) 790 791 792 /*--------------------------------------------------------------------*/ 793 794 /* Dllists 795 * ------- 796 * To calculate the number of crossings, we use a plain sweep algorithm 797 * that uses two lists. These sets are implemented as double 798 * linked lists containing nodes. 799 */ 800 801 typedef struct dllist { 802 struct gnode *node; /* the node */ 803 int dlinfo; /* the node info */ 804 int dlx; /* the info coordinate */ 805 struct dllist *pred; /* predecessor cons cell */ 806 struct dllist *succ; /* successor cons cell */ 807 } *DLLIST; 808 809 #define DPRED(x) ((x)->pred) 810 #define DSUCC(x) ((x)->succ) 811 #define DNODE(x) ((x)->node) 812 #define DNX(x) ((x)->dlx) 813 #define DINFO(x) ((x)->dlinfo) 814 815 /*--------------------------------------------------------------------*/ 816 817 818 /* see alloc.c for more information */ 819 820 /* Global Variables 821 * ---------------- 822 */ 823 824 extern int nodeanz; 825 extern int dummyanz; 826 extern GNODE nodelist; 827 extern GNODE nodelistend; 828 extern GNODE tmpnodelist; 829 extern GNODE graphlist; 830 extern GNODE graphlistend; 831 extern GNODE invis_nodes; 832 extern GNODE labellist; 833 extern GNODE labellistend; 834 extern GNODE dummylist; 835 extern int edgeanz; 836 extern GEDGE edgelist; 837 extern GEDGE edgelistend; 838 extern GEDGE tmpedgelist; 839 extern GEDGE hedgelist; 840 extern GEDGE hedgelistend; 841 extern GEDGE invis_edges; 842 extern ADJEDGE near_edge_list; 843 extern ADJEDGE bent_near_edge_list; 844 extern ADJEDGE back_edge_list; 845 846 #ifdef CHECKNODE 847 extern GNODE debug_checknode; 848 #endif 849 850 851 /* Prototypes 852 * ---------- 853 * See alloc.c for more information. 854 */ 855 856 char *myalloc _PP((int x)); 857 void free_memory _PP((void)); 858 859 GNODE nodealloc _PP((GNODE refnode)); 860 GNODE graphalloc _PP((GNODE refnode)); 861 void nodedefaults _PP((GNODE node)); 862 void foldnodedefaults _PP((GNODE node)); 863 void inherit_foldnode_attributes _PP((GNODE fn, GNODE y)); 864 void copy_nodeattributes _PP((GNODE fn, GNODE y)); 865 866 GNODE tmpnodealloc _PP((int textm,int width,int height,int borderw,int fold,int color,int textc,int borderc, int shrink,int stretch,int horder)); 867 void free_node _PP((GNODE v)); 868 void free_tmpnodes _PP((void)); 869 GNODE search_xy_node _PP((long x,long y)); 870 void check_graph_consistency _PP((void)); 871 872 873 GNLIST nodelist_alloc _PP((GNODE v)); 874 GNLIST tmpnodelist_alloc _PP((void)); 875 GNLIST foldnodelist_alloc _PP((void)); 876 void free_regionnodelist _PP(( GNLIST r)); 877 void free_foldnodelists _PP((void)); 878 879 GEDGE edgealloc _PP((GEDGE refedge)); 880 void edgedefaults _PP((GEDGE edge)); 881 void foldedgedefaults _PP((GEDGE edge)); 882 void inherit_foldedge_attributes _PP((GEDGE fn, GEDGE y)); 883 void copy_edgeattributes _PP((GEDGE fn, GEDGE y)); 884 885 GEDGE tmpedgealloc _PP((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)); 886 void near_edge_insert _PP((GEDGE e)); 887 void bentnear_edge_insert _PP((GEDGE e)); 888 void back_edge_insert _PP((GEDGE e)); 889 ADJEDGE prededgealloc _PP((GNODE node,GEDGE edge)); 890 ADJEDGE succedgealloc _PP((GNODE node,GEDGE edge)); 891 892 CONNECT connectalloc _PP((GNODE node)); 893 894 DLLIST dllist_alloc _PP((GNODE node, DLLIST pred)); 895 void dllist_free _PP((DLLIST x)); 896 void dllist_free_all _PP((DLLIST x)); 897 898 void free_all_lists _PP((void)); 899 void reinit_all_lists _PP((void)); 900 901 /*--------------------------------------------------------------------*/ 902 903 #endif /* ALLOC_H */ 904 905