1 /*
2 * mpatrol
3 * A library for controlling and tracing dynamic memory allocations.
4 * Copyright (C) 1997-2002 Graeme S. Roy <graeme.roy@analog.com>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public
17 * License along with this library; if not, write to the Free
18 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
19 * MA 02111-1307, USA.
20 */
21
22
23 /*
24 * Directed graphs. Not only are the edges directed, but the overall
25 * graph has a beginning and end for the purposes of representing a call
26 * graph.
27 */
28
29
30 #include "graph.h"
31
32
33 #if MP_IDENT_SUPPORT
34 #ident "$Id: graph.c,v 1.6 2002/01/08 20:13:59 graeme Exp $"
35 #else /* MP_IDENT_SUPPORT */
36 static MP_CONST MP_VOLATILE char *graph_id = "$Id: graph.c,v 1.6 2002/01/08 20:13:59 graeme Exp $";
37 #endif /* MP_IDENT_SUPPORT */
38
39
40 #ifdef __cplusplus
41 extern "C"
42 {
43 #endif /* __cplusplus */
44
45
46 /* Initialise the fields of a graph head so that the graph becomes empty.
47 * Note the two sentinel graph nodes representing the start and end nodes
48 * of the graph, which make manipulation and traversal a lot easier.
49 */
50
51 MP_GLOBAL
52 void
__mp_newgraph(graphhead * g)53 __mp_newgraph(graphhead *g)
54 {
55 __mp_newlist(&g->start.parents);
56 __mp_newlist(&g->start.children);
57 __mp_newlist(&g->end.parents);
58 __mp_newlist(&g->end.children);
59 g->nodes = g->edges = 0;
60 }
61
62
63 /* Initialise the fields of a graph node and associate it with a given graph.
64 */
65
66 MP_GLOBAL
67 void
__mp_addnode(graphhead * g,graphnode * n)68 __mp_addnode(graphhead *g, graphnode *n)
69 {
70 __mp_newlist(&n->parents);
71 __mp_newlist(&n->children);
72 g->nodes++;
73 }
74
75
76 /* Remove a graph node from a given graph.
77 */
78
79 MP_GLOBAL
80 void
__mp_removenode(graphhead * g,graphnode * n)81 __mp_removenode(graphhead *g, graphnode *n)
82 {
83 graphedge *e;
84 listnode *l, *p;
85
86 for (l = n->parents.head; p = l->next; l = p)
87 {
88 e = (graphedge *) ((char *) l - offsetof(graphedge, pnode));
89 __mp_removeedge(g, e);
90 }
91 for (l = n->children.head; p = l->next; l = p)
92 {
93 e = (graphedge *) ((char *) l - offsetof(graphedge, cnode));
94 __mp_removeedge(g, e);
95 }
96 g->nodes--;
97 }
98
99
100 /* Initialise the fields of a graph edge and associate it with parent and
101 * child nodes in a given graph.
102 */
103
104 MP_GLOBAL
105 void
__mp_addedge(graphhead * g,graphedge * e,graphnode * p,graphnode * c)106 __mp_addedge(graphhead *g, graphedge *e, graphnode *p, graphnode *c)
107 {
108 __mp_addtail(&c->parents, &e->pnode);
109 __mp_addtail(&p->children, &e->cnode);
110 e->parent = p;
111 e->child = c;
112 g->edges++;
113 }
114
115
116 /* Remove a graph edge from a given graph.
117 */
118
119 MP_GLOBAL
120 void
__mp_removeedge(graphhead * g,graphedge * e)121 __mp_removeedge(graphhead *g, graphedge *e)
122 {
123 __mp_remove(&e->child->parents, &e->pnode);
124 __mp_remove(&e->parent->children, &e->cnode);
125 e->parent = e->child = NULL;
126 g->edges--;
127 }
128
129
130 /* Search for a graph edge which joins one graph node to another.
131 */
132
133 MP_GLOBAL
134 graphedge *
__mp_findedge(graphhead * g,graphnode * p,graphnode * c)135 __mp_findedge(graphhead *g, graphnode *p, graphnode *c)
136 {
137 graphedge *e;
138 listnode *n;
139
140 for (n = c->parents.head; n->next != NULL; n = n->next)
141 {
142 e = (graphedge *) ((char *) n - offsetof(graphedge, pnode));
143 if (e->parent == p)
144 return e;
145 }
146 return NULL;
147 }
148
149
150 #ifdef __cplusplus
151 }
152 #endif /* __cplusplus */
153