← Back to branch summary

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

« back to all changes in this revision

Viewing changes to agraph/edge.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:
agraph/edge.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
#pragma prototyped
 
11
 
 
12
#include <aghdr.h>
 
13
 
 
14
#ifdef DMALLOC
 
15
#include "dmalloc.h"
 
16
#endif
 
17
 
 
18
#define IN_SET FALSE
 
19
#define OUT_SET TRUE
 
20
#define ID_ORDER TRUE
 
21
#define SEQ_ORDER FALSE
 
22
 
 
23
static Agtag_t  Tag;    /* to silence warnings about initialization */
 
24
 
 
25
Agedge_t *agfstout(Agnode_t *n)
 
26
{
 
27
        Agraph_t        *g;
 
28
        Agedge_t        *e = NILedge;
 
29
 
 
30
        g = agraphof(n);
 
31
        if (agisflattened(g)) e = AGFSTOUT(n);
 
32
        else {
 
33
                dtrestore(g->e_seq,&(n->out->base.seq_link));
 
34
                e = (Agedge_t*) dtfirst(g->e_seq);
 
35
                n->out = (Agedge_t*)dtextract(g->e_seq);
 
36
        }
 
37
        return e;
 
38
}
 
39
 
 
40
Agedge_t *agnxtout(Agedge_t *e)
 
41
{
 
42
        Agraph_t        *g;
 
43
        Agnode_t        *n;
 
44
        Agedge_t        *f;
 
45
 
 
46
        g = agraphof(e);
 
47
        if (agisflattened(g)) f = AGNXTE(e);
 
48
        else {
 
49
                n = AGTAIL(e);
 
50
                dtrestore(g->e_seq,&(n->out->base.seq_link));
 
51
                f = (Agedge_t*) dtnext(g->e_seq,e);
 
52
                n->out = (Agedge_t*)dtextract(g->e_seq);
 
53
        }
 
54
        return f;
 
55
}
 
56
 
 
57
Agedge_t *agfstin(Agnode_t *n)
 
58
{
 
59
        Agraph_t        *g;
 
60
        Agedge_t        *e = NILedge;
 
61
 
 
62
        g = agraphof(n);
 
63
        if (agisflattened(g)) e = AGFSTIN(n);
 
64
        else {
 
65
                dtrestore(g->e_seq,&(n->in->base.seq_link));
 
66
                e = (Agedge_t*) dtfirst(g->e_seq);
 
67
                n->in = (Agedge_t*)dtextract(g->e_seq);
 
68
        }
 
69
        return e;
 
70
}
 
71
 
 
72
Agedge_t *agnxtin(Agedge_t *e)
 
73
{
 
74
        Agraph_t        *g;
 
75
        Agnode_t        *n;
 
76
        Agedge_t        *f;
 
77
 
 
78
        g = agraphof(e);
 
79
        if (agisflattened(g)) f = AGNXTE(e);
 
80
        else {
 
81
                n = AGHEAD(e);
 
82
                dtrestore(g->e_seq,&(n->in->base.seq_link));
 
83
                f = (Agedge_t*) dtnext(g->e_seq,e);
 
84
                n->in = (Agedge_t*)dtextract(g->e_seq);
 
85
        }
 
86
        return f;
 
87
}
 
88
 
 
89
Agedge_t *agfstedge(Agnode_t *n) 
 
90
{
 
91
        Agedge_t  *rv;
 
92
        rv = agfstout(n);
 
93
        if (rv == NILedge) rv = agfstin(n);
 
94
        return rv;
 
95
}
 
96
 
 
97
Agedge_t *agnxtedge(Agedge_t *e, Agnode_t *n)
 
98
{
 
99
        Agedge_t  *rv;
 
100
        if (AGID(n) == AGID(agtail(e))) {
 
101
                rv = agnxtout(e);
 
102
                if (rv == NILedge) rv = agfstin(n);
 
103
        }
 
104
        else rv = agnxtin(e);
 
105
        return rv;
 
106
}
 
107
 
 
108
static Agedge_t *agfindedge(Agnode_t *t, Agnode_t *h, Agtag_t key)
 
109
{
 
110
        Agraph_t        *g;
 
111
        Agedge_t        *e, template;
 
112
 
 
113
        assert(agraphof(t) == agraphof(h));
 
114
 
 
115
        g = agraphof(t);
 
116
        template.base.tag = key;                /* guess that fan-in < fan-out */
 
117
        template.node = t;
 
118
        if (t != h) { /* guess that fan-in < fan-out */
 
119
                dtrestore(g->e_id,h->inid);
 
120
                e = (Agedge_t*) dtsearch(g->e_id,&template);
 
121
                h->inid = dtextract(g->e_id);
 
122
        }
 
123
        else {
 
124
                dtrestore(g->e_id,t->outid);
 
125
                e = (Agedge_t*) dtsearch(g->e_id,&template);
 
126
                t->outid = dtextract(g->e_id);
 
127
        }
 
128
        return e;
 
129
}
 
130
 
 
131
static Agedge_t *agfindedge_by_id(Agnode_t *t, Agnode_t *h, unsigned long id)
 
132
{
 
133
        Agtag_t         tag;
 
134
 
 
135
        assert(agraphof(t) == agraphof(h));
 
136
        tag = Tag;
 
137
        tag.objtype = AGEDGE;
 
138
        tag.id = id;
 
139
        return agfindedge(t,h,tag);
 
140
}
 
141
 
 
142
void agedgesetop(Agraph_t *g, Agedge_t *e, int ins)
 
143
{
 
144
        Dtlink_t **seq_set, **id_set;
 
145
        Agnode_t        *n;                      /* node where <e> is referenced */
 
146
 
 
147
        if (AGTYPE(e) == AGOUTEDGE) {
 
148
                n = AGOUT2IN(e)->node;
 
149
                seq_set = (Dtlink_t**)&(n->out);
 
150
                id_set = &(n->outid);
 
151
        }
 
152
        else {
 
153
                n = AGIN2OUT(e)->node;
 
154
                seq_set = (Dtlink_t**)&(n->in);
 
155
                id_set = &(n->inid);
 
156
        }
 
157
 
 
158
        dtrestore(g->e_seq,*seq_set);
 
159
        if (ins) dtinsert(g->e_seq,e);
 
160
        else dtdelete(g->e_seq,e);
 
161
        *seq_set = dtextract(g->e_seq);
 
162
 
 
163
        dtrestore(g->e_id,*id_set);
 
164
        if (ins) dtinsert(g->e_id,e);
 
165
        else dtdelete(g->e_id,e);
 
166
        *id_set = dtextract(g->e_id);
 
167
}
 
168
 
 
169
/* creates new edge pair and returns outedge */
 
170
static Agedgepair_t *newedgepair(Agraph_t *g, Agnode_t *t, Agnode_t *h, unsigned long id,
 
171
        unsigned long seq)
 
172
{
 
173
        Agedgepair_t    *e2;
 
174
        Agedge_t        *in,*out;
 
175
 
 
176
        e2 = (Agedgepair_t*)agalloc(g,sizeof(Agedgepair_t));
 
177
        in = &(e2->in); out = &(e2->out);
 
178
        AGTYPE(in) = AGINEDGE;
 
179
        AGTYPE(out) = AGOUTEDGE;
 
180
        AGID(in) = AGID(out) = id;
 
181
        AGSEQ(in) = AGSEQ(out) = seq;
 
182
        in->node = t;
 
183
        out->node = h;
 
184
        agedgesetop(g,out,TRUE);
 
185
        if (t != h) agedgesetop(g,in,TRUE);
 
186
        return e2;
 
187
}
 
188
 
 
189
static Agedge_t *localedge(Agraph_t *g, Agnode_t *arg_t, Agnode_t *arg_h, unsigned long id)
 
190
{
 
191
        Agedge_t        *e,*epar;
 
192
        Agraph_t        *par;
 
193
        Agnode_t        *t,*h;
 
194
        Agtag_t         key;
 
195
        Agedgepair_t    *e2;
 
196
 
 
197
        agnotflat(g);
 
198
 
 
199
        t = agsubnode(g,arg_t,TRUE);
 
200
        h = agsubnode(g,arg_h,TRUE);
 
201
                /* protect against multi-edges */
 
202
        key = Tag;
 
203
        if (agisstrict(g)) key.objtype = 0;
 
204
        else key.objtype = AGEDGE;
 
205
        key.id = id;
 
206
        if ((e = agfindedge(t,h,key))) return e;
 
207
 
 
208
        if ((par = agparent(g))) {
 
209
                epar = localedge(par, t, h, id);
 
210
        }
 
211
        else {
 
212
                epar = NILedge;
 
213
        }
 
214
 
 
215
        e2 = newedgepair(g,t,h,id,epar?AGSEQ(epar):agnextseq(g,AGEDGE));
 
216
        e =  &(e2->out);
 
217
        if (epar) AGDATA(&(e2->in)) = AGDATA(&(e2->out)) = AGDATA(epar);
 
218
        else {
 
219
                if (g->desc.has_attrs) agedgeattr_init(e, TRUE);
 
220
                agmethod_init(g, e);
 
221
        }
 
222
        return e;
 
223
}
 
224
 
 
225
static int ok_to_make_edge(Agnode_t *t, Agnode_t *h)
 
226
{
 
227
        Agraph_t        *g;
 
228
        Agtag_t         key;
 
229
 
 
230
        g = agraphof(t);
 
231
 
 
232
        /* protect against endpoints in different graphs */
 
233
        g = agraphof(t);
 
234
        if (g != agraphof(h)) return FALSE;
 
235
 
 
236
        /* protect against self, multi-edges in strict graphs */
 
237
        if (agisstrict(g)) {
 
238
                if (AGID(t) == AGID(h)) return FALSE;
 
239
                key = Tag;
 
240
                key.objtype = 0; /* wild card */
 
241
                if (agfindedge(t,h,key)) return FALSE;
 
242
        }
 
243
        return TRUE;
 
244
}
 
245
 
 
246
Agedge_t *agidedge(Agnode_t *t, Agnode_t *h, unsigned long id, int cflag)
 
247
{
 
248
        Agraph_t        *g,*root;
 
249
        Agnode_t        *tr,*hr;
 
250
        Agedge_t        *e;
 
251
 
 
252
        if ((g = agraphof(t)) != agraphof(h)) return NILedge;
 
253
        if (agisundirected(g) && (AGID(t) > AGID(h)))
 
254
                { Agnode_t      *temp; temp = h; h = t; t = temp; }
 
255
 
 
256
        e = agfindedge_by_id(t,h,id);
 
257
        if ((e == NILedge) && cflag && ok_to_make_edge(t,h)) {
 
258
                root = agroot(g);
 
259
                if (((g != root) && ((tr = agsubnode(root,t,FALSE)))    /* old */
 
260
                        && ((hr = agsubnode(root,h,FALSE))) && agfindedge_by_id(tr,hr,id))
 
261
                        || agallocid(g,AGEDGE,id))                                                      /* new */
 
262
                                e = localedge(g, t, h, id);
 
263
        }
 
264
        return e;
 
265
}
 
266
 
 
267
Agedge_t *agedge(Agnode_t *t, Agnode_t *h, char *name, int cflag)
 
268
{
 
269
        Agraph_t        *g;
 
270
        Agedge_t        *e;
 
271
        unsigned long           id;
 
272
        int                     have_id;
 
273
 
 
274
        if ((g = agraphof(t)) != agraphof(h)) return NILedge;
 
275
        if (agisundirected(g) && (AGID(t) > AGID(h)))
 
276
                { Agnode_t      *temp; temp = h; h = t; t = temp; }
 
277
 
 
278
        have_id = agmapnametoid(g, AGEDGE, name, &id, FALSE);
 
279
        if (have_id || ((name == NILstr) && (NOT(cflag) || agisstrict(g)))) {
 
280
                /* probe for pre-existing edge */
 
281
                Agtag_t         key;
 
282
                key = Tag;
 
283
                if (have_id) {key.id = id; key.objtype = AGEDGE;}
 
284
                else {key.id = key.objtype = 0;}
 
285
 
 
286
                /* might already exist locally */
 
287
                if ((e = agfindedge(t,h,key))) return e;
 
288
        }
 
289
 
 
290
        if (cflag && ok_to_make_edge(t,h)
 
291
                && agmapnametoid(g, AGEDGE, name, &id, TRUE))   /* reserve id */
 
292
                        e = localedge(g,t,h,id);
 
293
        else e = NILedge;
 
294
        return e;
 
295
}
 
296
 
 
297
void agdeledgepair(Agedge_t *e, void *ignored)
 
298
{
 
299
        Agraph_t        *g;
 
300
        Agedge_t        *in,*out;
 
301
        Agnode_t        *t,*h;
 
302
 
 
303
        NOTUSED(ignored);
 
304
        g = agraphof(e);
 
305
        agnotflat(g);
 
306
        if (AGTYPE(e) == AGINEDGE) {in = e; out = AGIN2OUT(e);}
 
307
        else {out = e; in = AGOUT2IN(e);}
 
308
        t = in->node; h = out->node;
 
309
        agedgesetop(g,out,FALSE);
 
310
        if (t != h) agedgesetop(g,in,FALSE);
 
311
        agfree(g,out);
 
312
for (e = agfstin(h); e; e = agnxtin(e)) assert(e != in);
 
313
for (e = agfstout(t); e; e = agnxtout(e)) assert(e != out);
 
314
}
 
315
 
 
316
int agdeledge(Agedge_t *e)
 
317
{
 
318
        Agraph_t        *g;
 
319
 
 
320
        g = agraphof(e);
 
321
        e = AGMKOUT(e);
 
322
 
 
323
        if (agfindedge(agtail(e),aghead(e),AGTAG(e)) == NILedge)
 
324
                return FAILURE;
 
325
 
 
326
        if (agisarootobj(e)) {
 
327
                if (g->desc.has_attrs) agedgeattr_delete(e);
 
328
                agmethod_delete(g,e);
 
329
                agrecclose((Agobj_t*)e);
 
330
                agfreeid(g, AGEDGE, AGID(e));
 
331
        }
 
332
        return agapply(g,(Agobj_t*)e,(agobjfn_t)agdeledgepair,NILedge,FALSE);
 
333
}
 
334
 
 
335
 
 
336
Agedge_t *agsubedge(Agraph_t *g, Agedge_t *arg_e, int cflag)
 
337
{
 
338
        Agnode_t        *t,*h;
 
339
        Agedge_t        *e;
 
340
 
 
341
        if (agraphof(arg_e) == g) return arg_e;
 
342
 
 
343
        agnotflat(g);
 
344
        t = agsubnode(g,AGTAIL(arg_e),cflag);
 
345
        h = agsubnode(g,AGHEAD(arg_e),cflag);
 
346
        if ((t == NILnode) || (h == NILnode)) e = NILedge;
 
347
        else {
 
348
                e = agfindedge(t,h,AGTAG(arg_e));
 
349
                if (cflag && (e == NILedge)) {
 
350
                        e = localedge(g,t,h,AGID(arg_e));
 
351
                }
 
352
        }
 
353
        if (e && (AGTYPE(e) != AGTYPE(arg_e))) e = AGOPP(e);
 
354
        return e;
 
355
}
 
356
 
 
357
 
 
358
/* edge comparison.  OBJTYPE(e) == 0 means ID is a wildcard. */
 
359
int agedgecmpf(Dict_t *d, void *arg_e0, void *arg_e1, Dtdisc_t *disc)
 
360
{
 
361
        int                     rv;
 
362
        Agedge_t        *e0, *e1;
 
363
 
 
364
        NOTUSED(d);
 
365
        e0 = arg_e0; e1 = arg_e1;
 
366
        NOTUSED(disc);
 
367
        rv = AGID(e0->node) - AGID(e1->node);
 
368
        if (rv == 0) {          /* same node */
 
369
                if ((AGTYPE(e0) == 0) || (AGTYPE(e1) == 0))
 
370
                        rv = 0;
 
371
                else
 
372
                        rv = AGID(e0) - AGID(e1);
 
373
        }
 
374
        return rv;
 
375
}
 
376
 
 
377
        /* discipline for edges that compares endpoints + ID */
 
378
Dtdisc_t Ag_edge_disc = {
 
379
        0,              /* obj is passed as key */
 
380
        0,              /* key size (ignored) */
 
381
        offsetof(Agedge_t,base.id_link), /* link offset */
 
382
        NIL(Dtmake_f),
 
383
        NIL(Dtfree_f),
 
384
        agedgecmpf,
 
385
        NIL(Dthash_f)
 
386
};
 
387
 
 
388
/* debug functions */
 
389
#ifdef agtail
 
390
#undef agtail
 
391
#endif
 
392
Agnode_t *agtail(Agedge_t *e) {return AGTAIL(e);}
 
393
 
 
394
#ifdef aghead
 
395
#undef aghead
 
396
#endif
 
397
Agnode_t *aghead(Agedge_t *e) {return AGHEAD(e);}
 
398
 
 
399
#ifdef agopp
 
400
#undef agopp
 
401
#endif
 
402
Agedge_t *agopp(Agedge_t *e) {return AGOPP(e);}
 
403
 
 
404
#ifdef NOTDEF
 
405
        /* could be useful if we write relabel_edge */
 
406
static Agedge_t *agfindedge_by_name(Agnode_t *t, Agnode_t *h, char *name)
 
407
{
 
408
        unsigned long           id;
 
409
 
 
410
        if (agmapnametoid(agraphof(t), AGEDGE, name, &id, FALSE))
 
411
                return agfindedge_by_id(t, h, id);
 
412
        else return NILedge;
 
413
}
 
414
#endif