← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to dag/check.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
dag/check.c
 
1
/* Various runtime sanity checks.  These should be disabled in
 
2
 * a production version of the code.
 
3
 */
 
4
 
 
5
#include <dag.h>
 
6
 
 
7
#ifdef DMALLOC
 
8
#include "dmalloc.h"
 
9
#endif
 
10
 
 
11
/* Test global consistency of the view. */
 
12
void dd_check_all(ddview_t *view)
 
13
{
 
14
        int             r;
 
15
 
 
16
        for (r = view->config->low; r <= view->config->high; r++)
 
17
                dd_check_rank(view,r);
 
18
        dd_check_edges(view->layout);
 
19
}
 
20
 
 
21
/* Check consistency of the nodes within one rank. */
 
22
void dd_check_rank(ddview_t *view, int r)
 
23
{
 
24
        Agnode_t        *ln,*rn,**list;
 
25
        int                     i;
 
26
        rank_t          *rd;
 
27
 
 
28
        rd = dd_rankd(view,r);
 
29
        list = rd->v;
 
30
        i = 0;
 
31
        ln = NILnode;
 
32
        for (rn = dd_leftmost(view,r); rn; rn = dd_right(view,rn)) {
 
33
                assert(list[i] == rn); i++;
 
34
                assert(dd_node_in_config(rn));
 
35
                assert(dd_rank(rn) == r);
 
36
                dd_check_elts(view,rn);
 
37
                if (ln) {
 
38
                        assert(dd_order(ln) + 1 == dd_order(rn));
 
39
                        assert(dd_pos(ln).x + BASE(view)->client->separation.x <= dd_pos(rn).x);
 
40
                }
 
41
                ln = rn;
 
42
        }
 
43
        assert (i == rd->n);
 
44
}
 
45
 
 
46
/* Check membership of a node w.r.t. graph configuration. */
 
47
void dd_check_containment(ddview_t *view, int r, Agnode_t *n, int must_be_in)
 
48
{
 
49
        Agnode_t        *rn;
 
50
 
 
51
        for (rn = dd_leftmost(view,r); rn; rn = dd_right(view,rn)) {
 
52
                if (must_be_in) { if (n == rn) break; }
 
53
                else assert (n != rn);
 
54
        }
 
55
        if (must_be_in) assert (n == rn);
 
56
}
 
57
 
 
58
/* all edges should be unit-length */
 
59
void dd_check_edges(Agraph_t *g)
 
60
{
 
61
        Agnode_t        *u,*v;
 
62
        Agedge_t        *e;
 
63
        ddpath_t        *p;
 
64
 
 
65
        for (u = agfstnode(g); u; u = agnxtnode(u)) {
 
66
                if (NOT(dd_node_in_config(u))) continue;
 
67
                for (e = agfstout(u); e; e = agnxtout(e)) {
 
68
                        p = dd_path(e);
 
69
                        assert(aghead(p->last));
 
70
                        v = aghead(e);
 
71
                        if (NOT(dd_node_in_config(v))) continue;
 
72
                        if (dd_first_elt(e) == NILedge) continue;
 
73
                        assert(dd_rank(u) + 1 == dd_rank(v));
 
74
                }
 
75
        }
 
76
}
 
77
 
 
78
ilbool dd_check_pathnode(ddview_t *view, Agnode_t *n)
 
79
{
 
80
        rank_t          *rd;
 
81
        int                     i,r;
 
82
 
 
83
        i = dd_order(n);
 
84
        r = dd_rank(n);
 
85
        rd = dd_rankd(view,r);
 
86
        assert(rd->v[i] == n);
 
87
        return FALSE;
 
88
}
 
89
 
 
90
void dd_check_vnode_path(ddview_t *view, Agedge_t **vpath)
 
91
{
 
92
        int                     i;
 
93
        Agedge_t        *e,*f;
 
94
 
 
95
        f = NILedge;
 
96
        for (i = 0; (e = vpath[i]); i++) {
 
97
                dd_check_pathnode(view,agtail(e));
 
98
                if (i > 0) assert(dd_is_a_vnode(agtail(e)));
 
99
                f = e;
 
100
        }
 
101
        dd_check_pathnode(view,aghead(f));
 
102
}
 
103
 
 
104
void dd_check_elts(ddview_t *view, Agnode_t *n)
 
105
{
 
106
        Agedge_t        *e,*f,*fst,*lst;
 
107
 
 
108
        if (dd_is_a_vnode(n)) return;
 
109
        for (e = agfstout(n); e; e = agnxtout(e)) {
 
110
                fst = dd_first_elt(e);
 
111
                lst = dd_last_elt(e);
 
112
 
 
113
                for (f = fst; f; f = agfstout(aghead(f))) {
 
114
                        dd_check_pathnode(view,aghead(f));
 
115
                        if (f == lst) break;
 
116
                }
 
117
        }
 
118
}
 
119
 
 
120
void dd_check_newranks(Agraph_t *g)
 
121
{
 
122
        Agnode_t        *n;
 
123
        Agedge_t        *e;
 
124
 
 
125
        for (n = agfstnode(g); n; n = agnxtnode(n)) {
 
126
                if (dd_is_a_vnode(n)) continue;
 
127
                for (e = agfstout(n); e; e = agnxtout(e)) {
 
128
                        if (NOT(dd_constraint(e))) continue;
 
129
                        assert (dd_newrank(dd_pathhead(e)) - dd_newrank(dd_pathtail(e)) >= 1);
 
130
                }
 
131
        }
 
132
}
 
133
 
 
134
static void check_mg(Agraph_t *g, Agraph_t *root)
 
135
{
 
136
        Agnode_t        *mn;
 
137
        Agedge_t        *me;
 
138
 
 
139
        for (mn = agfstnode(g); mn; mn = agnxtnode(mn)) {
 
140
                assert(mn->base.data);
 
141
                assert(agsubnode(root,mn,FALSE));
 
142
                for (me = agfstout(mn); me; me = agnxtout(me)) {
 
143
                        assert(me->base.data);
 
144
                        assert(agsubedge(root,me,FALSE));
 
145
                }
 
146
        }
 
147
}
 
148
 
 
149
void dd_check_model(ddview_t *view)
 
150
{
 
151
        Agraph_t        *root;
 
152
 
 
153
        root = BASE(view)->model.main;
 
154
        check_mg(root,root);
 
155
        check_mg(BASE(view)->model.v[IL_INS],root);
 
156
        check_mg(BASE(view)->model.e[IL_INS],root);
 
157
        check_mg(BASE(view)->model.v[IL_MOD],root);
 
158
        check_mg(BASE(view)->model.e[IL_MOD],root);
 
159
        check_mg(BASE(view)->model.v[IL_DEL],root);
 
160
        check_mg(BASE(view)->model.e[IL_DEL],root);
 
161
}
 
162
 
 
163
void dd_check_really_gone(Agraph_t *g, Agnode_t *n, unsigned long id)
 
164
{
 
165
        Agnode_t        *u;
 
166
        Agedge_t        *e;
 
167
 
 
168
        assert (agidnode(g,id,FALSE) == NILnode);
 
169
 
 
170
        for (u = agfstnode(g); u; u = agnxtnode(u)) {
 
171
                assert(u != n);
 
172
                for (e = agfstedge(u); e; e = agnxtedge(e,u))
 
173
                        assert(e->node != n);
 
174
        }
 
175
}
 
176
 
 
177
void dd_check_vnodes(ddview_t *view)
 
178
{
 
179
        Agnode_t        *n;
 
180
        Agedge_t        *e;
 
181
 
 
182
        for (n = agfstnode(view->layout); n; n = agnxtnode(n)) {
 
183
                if (NOT(dd_is_a_vnode(n))) continue;
 
184
                e = agfstin(n);
 
185
                if (e == NILedge) abort();
 
186
                e = agfstout(n);
 
187
                if (e == NILedge) abort();
 
188
        }
 
189
}
 
190
 
 
191
static int CLcnt = 0;
 
192
void dd_check_links(ddview_t *view)
 
193
{
 
194
        Agraph_t        *model, *layout;
 
195
        Agnode_t        *mn, *ln;
 
196
        Agedge_t        *me, *le, *mme;
 
197
        ddpath_t        *path;
 
198
 
 
199
dd_check_model(view);
 
200
        model = BASE(view)->model.main;
 
201
        layout = view->layout;
 
202
 
 
203
        /* check model graph links to layout graph */
 
204
        for (mn = agfstnode(model); mn; mn = agnxtnode(mn)) {
 
205
                ln = dd_rep(mn);
 
206
                if (ln == NILnode) continue;
 
207
                assert(dd_node(ln)->model == mn);
 
208
 
 
209
                for (me = agfstedge(mn); me; me = agnxtedge(me,mn)) {
 
210
                        path = dd_pathrep(me);
 
211
                        mme = path->model;
 
212
                        if (mme == NILedge) continue;
 
213
                        assert((mme == me) || (mme == AGOPP(me)));
 
214
                }
 
215
        }
 
216
 
 
217
        /* check layout object links to model objects */
 
218
        for (ln = agfstnode(layout); ln; ln = agnxtnode(ln)) {
 
219
                if (dd_is_a_vnode(ln) == FALSE) {
 
220
                        mn = dd_node(ln)->model;
 
221
                        assert(mn);
 
222
                        assert(agsubnode(model,mn,FALSE) == mn);
 
223
                        assert(ln == dd_rep(mn));
 
224
                        for (le = agfstedge(ln); le; le = agnxtedge(le,ln)) {
 
225
                                path = dd_edge(le)->path;
 
226
                                me = path->model;
 
227
                                assert(agsubedge(model,me,FALSE) == me);
 
228
                        }
 
229
                }
 
230
                else {
 
231
                        assert(agfstin(ln) != NILedge);
 
232
                        assert(agfstout(ln) != NILedge);
 
233
                }
 
234
        }
 
235
CLcnt++;
 
236
}