1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include <cghdr.h>
15
16Agnode_t *agfindnode_by_id(Agraph_t * g, IDTYPE id)
17{
18 Agsubnode_t *sn;
19 static Agsubnode_t template;
20 static Agnode_t dummy;
21
22 dummy.base.tag.id = id;
23 template.node = &dummy;
24 sn = (Agsubnode_t *) dtsearch(g->n_id, &template);
25 return sn ? sn->node : NILnode;
26}
27
28Agnode_t *agfindnode_by_name(Agraph_t * g, char *name)
29{
30 IDTYPE id;
31
32 if (agmapnametoid(g, AGNODE, name, &id, FALSE))
33 return agfindnode_by_id(g, id);
34 else
35 return NILnode;
36}
37
38Agnode_t *agfstnode(Agraph_t * g)
39{
40 Agsubnode_t *sn;
41 sn = (Agsubnode_t *) dtfirst(g->n_seq);
42 return sn ? sn->node : NILnode;
43}
44
45Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n)
46{
47 Agsubnode_t *sn;
48 sn = agsubrep(g, n);
49 if (sn) sn = ((Agsubnode_t *) dtnext(g->n_seq, sn));
50 return sn ? sn->node : NILnode;
51}
52
53Agnode_t *aglstnode(Agraph_t * g)
54{
55 Agsubnode_t *sn;
56 sn = (Agsubnode_t *) dtlast(g->n_seq);
57 return sn ? sn->node : NILnode;
58}
59
60Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n)
61{
62 Agsubnode_t *sn;
63 sn = agsubrep(g, n);
64 if (sn) sn = ((Agsubnode_t *) dtprev(g->n_seq, sn));
65 return sn ? sn->node : NILnode;
66}
67
68
69/* internal node constructor */
70static Agnode_t *newnode(Agraph_t * g, IDTYPE id, uint64_t seq)
71{
72 Agnode_t *n;
73
74 n = agalloc(g, sizeof(Agnode_t));
75 AGTYPE(n) = AGNODE;
76 AGID(n) = id;
77 AGSEQ(n) = seq;
78 n->root = agroot(g);
79 if (agroot(g)->desc.has_attrs)
80 (void) agbindrec(n, AgDataRecName, sizeof(Agattr_t), FALSE);
81 /* nodeattr_init and method_init will be called later, from the
82 * subgraph where the node was actually created, but first it has
83 * to be installed in all the (sub)graphs up to root. */
84 return n;
85}
86
87static void installnode(Agraph_t * g, Agnode_t * n)
88{
89 Agsubnode_t *sn;
90 int osize;
91
92 assert(dtsize(g->n_id) == dtsize(g->n_seq));
93 osize = dtsize(g->n_id);
94 if (g == agroot(g)) sn = &(n->mainsub);
95 else sn = agalloc(g, sizeof(Agsubnode_t));
96 sn->node = n;
97 dtinsert(g->n_id, sn);
98 dtinsert(g->n_seq, sn);
99 assert(dtsize(g->n_id) == dtsize(g->n_seq));
100 assert(dtsize(g->n_id) == osize + 1);
101}
102
103static void installnodetoroot(Agraph_t * g, Agnode_t * n)
104{
105 Agraph_t *par;
106 installnode(g, n);
107 if ((par = agparent(g)))
108 installnodetoroot(par, n);
109}
110
111static void initnode(Agraph_t * g, Agnode_t * n)
112{
113 if (agroot(g)->desc.has_attrs)
114 agnodeattr_init(g,n);
115 agmethod_init(g, n);
116}
117
118/* external node constructor - create by id */
119Agnode_t *agidnode(Agraph_t * g, IDTYPE id, int cflag)
120{
121 Agraph_t *root;
122 Agnode_t *n;
123
124 n = agfindnode_by_id(g, id);
125 if ((n == NILnode) && cflag) {
126 root = agroot(g);
127 if ((g != root) && ((n = agfindnode_by_id(root, id)))) /*old */
128 agsubnode(g, n, TRUE); /* insert locally */
129 else {
130 if (agallocid(g, AGNODE, id)) { /* new */
131 n = newnode(g, id, agnextseq(g, AGNODE));
132 installnodetoroot(g, n);
133 initnode(g, n);
134 } else
135 n = NILnode; /* allocid for new node failed */
136 }
137 }
138 /* else return probe result */
139 return n;
140}
141
142Agnode_t *agnode(Agraph_t * g, char *name, int cflag)
143{
144 Agraph_t *root;
145 Agnode_t *n;
146 IDTYPE id;
147
148 root = agroot(g);
149 /* probe for existing node */
150 if (agmapnametoid(g, AGNODE, name, &id, FALSE)) {
151 if ((n = agfindnode_by_id(g, id)))
152 return n;
153
154 /* might already exist globally, but need to insert locally */
155 if (cflag && (g != root) && ((n = agfindnode_by_id(root, id)))) {
156 return agsubnode(g, n, TRUE);
157 }
158 }
159
160 if (cflag && agmapnametoid(g, AGNODE, name, &id, TRUE)) { /* reserve id */
161 n = newnode(g, id, agnextseq(g, AGNODE));
162 installnodetoroot(g, n);
163 initnode(g, n);
164 assert(agsubrep(g,n));
165 agregister(g, AGNODE, n); /* register in external namespace */
166 return n;
167 }
168
169 return NILnode;
170}
171
172/* removes image of node and its edges from graph.
173 caller must ensure n belongs to g. */
174void agdelnodeimage(Agraph_t * g, Agnode_t * n, void *ignored)
175{
176 Agedge_t *e, *f;
177 static Agsubnode_t template;
178 template.node = n;
179
180 NOTUSED(ignored);
181 for (e = agfstedge(g, n); e; e = f) {
182 f = agnxtedge(g, e, n);
183 agdeledgeimage(g, e, 0);
184 }
185 /* If the following lines are switched, switch the discpline using
186 * free_subnode below.
187 */
188 dtdelete(g->n_id, &template);
189 dtdelete(g->n_seq, &template);
190}
191
192int agdelnode(Agraph_t * g, Agnode_t * n)
193{
194 Agedge_t *e, *f;
195
196 if (!agfindnode_by_id(g, AGID(n)))
197 return FAILURE; /* bad arg */
198 if (g == agroot(g)) {
199 for (e = agfstedge(g, n); e; e = f) {
200 f = agnxtedge(g, e, n);
201 agdeledge(g, e);
202 }
203 if (g->desc.has_attrs)
204 agnodeattr_delete(n);
205 agmethod_delete(g, n);
206 agrecclose((Agobj_t *) n);
207 agfreeid(g, AGNODE, AGID(n));
208 }
209 if (agapply (g, (Agobj_t *) n, (agobjfn_t) agdelnodeimage, NILnode, FALSE) == SUCCESS) {
210 if (g == agroot(g))
211 agfree(g, n);
212 return SUCCESS;
213 } else
214 return FAILURE;
215}
216
217static void dict_relabel(Agnode_t * n, void *arg)
218{
219 Agraph_t *g;
220 uint64_t new_id;
221
222 g = agraphof(n);
223 new_id = *(uint64_t *) arg;
224 dtdelete(g->n_id, n); /* wrong, should be subrep */
225 AGID(n) = new_id;
226 dtinsert(g->n_id, n); /* also wrong */
227 /* because all the subgraphs share the same node now, this
228 now requires a separate deletion and insertion phase */
229}
230
231int agrelabel_node(Agnode_t * n, char *newname)
232{
233 Agraph_t *g;
234 IDTYPE new_id;
235
236 g = agroot(agraphof(n));
237 if (agfindnode_by_name(g, newname))
238 return FAILURE;
239 if (agmapnametoid(g, AGNODE, newname, &new_id, TRUE)) {
240 if (agfindnode_by_id(agroot(g), new_id) == NILnode) {
241 agfreeid(g, AGNODE, AGID(n));
242 agapply(g, (Agobj_t *) n, (agobjfn_t) dict_relabel,
243 (void *) &new_id, FALSE);
244 return SUCCESS;
245 } else {
246 agfreeid(g, AGNODE, new_id); /* couldn't use it after all */
247 }
248 /* obj* is unchanged, so no need to re agregister() */
249 }
250 return FAILURE;
251}
252
253/* lookup or insert <n> in <g> */
254Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n0, int cflag)
255{
256 Agraph_t *par;
257 Agnode_t *n;
258
259 if (agroot(g) != n0->root)
260 return NILnode;
261 n = agfindnode_by_id(g, AGID(n0));
262 if ((n == NILnode) && cflag) {
263 if ((par = agparent(g))) {
264 n = agsubnode(par, n0, cflag);
265 installnode(g, n);
266 /* no callback for existing node insertion in subgraph (?) */
267 }
268 /* else impossible that <n> doesn't belong to <g> */
269 }
270 /* else lookup succeeded */
271 return n;
272}
273
274int agsubnodeidcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc)
275{
276 Agsubnode_t *sn0, *sn1;
277
278 sn0 = (Agsubnode_t *) arg0;
279 sn1 = (Agsubnode_t *) arg1;
280
281 if (AGID(sn0->node) < AGID(sn1->node)) return -1;
282 if (AGID(sn0->node) > AGID(sn1->node)) return 1;
283 return 0;
284}
285
286int agsubnodeseqcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc)
287{
288 Agsubnode_t *sn0, *sn1;
289
290 sn0 = (Agsubnode_t *) arg0;
291 sn1 = (Agsubnode_t *) arg1;
292
293 if (AGSEQ(sn0->node) < AGSEQ(sn1->node)) return -1;
294 if (AGSEQ(sn0->node) > AGSEQ(sn1->node)) return 1;
295 return 0;
296}
297
298/* free_subnode:
299 * Free Agsubnode_t allocated in installnode. This should
300 * only be done for subgraphs, as the root graph uses the
301 * subnode structure built into the node. This explains the
302 * AGSNMAIN test. Also, note that both the id and the seq
303 * dictionaries use the same subnode object, so only one
304 * should do the deletion.
305 */
306static void
307free_subnode (Dt_t* d, Agsubnode_t* sn, Dtdisc_t * disc)
308{
309
310 if (!AGSNMAIN(sn))
311 agfree (sn->node->root, sn);
312}
313
314Dtdisc_t Ag_subnode_id_disc = {
315 0, /* pass object ptr */
316 0, /* size (ignored) */
317 offsetof(Agsubnode_t, id_link), /* link offset */
318 NIL(Dtmake_f),
319 NIL(Dtfree_f),
320 agsubnodeidcmpf,
321 NIL(Dthash_f),
322 agdictobjmem,
323 NIL(Dtevent_f)
324};
325
326Dtdisc_t Ag_subnode_seq_disc = {
327 0, /* pass object ptr */
328 0, /* size (ignored) */
329 offsetof(Agsubnode_t, seq_link), /* link offset */
330 NIL(Dtmake_f),
331 (Dtfree_f)free_subnode,
332 agsubnodeseqcmpf,
333 NIL(Dthash_f),
334 agdictobjmem,
335 NIL(Dtevent_f)
336};
337
338void agnodesetfinger(Agraph_t * g, Agnode_t * n, void *ignored)
339{
340 static Agsubnode_t template;
341 template.node = n;
342 dtsearch(g->n_seq,&template);
343 NOTUSED(ignored);
344}
345
346void agnoderenew(Agraph_t * g, Agnode_t * n, void *ignored)
347{
348 dtrenew(g->n_seq, dtfinger(g->n_seq));
349 NOTUSED(n);
350 NOTUSED(ignored);
351}
352
353int agnodebefore(Agnode_t *fst, Agnode_t *snd)
354{
355 Agraph_t *g;
356 Agnode_t *n, *nxt;
357
358
359 g = agroot(fst);
360 if (AGSEQ(fst) > AGSEQ(snd)) return SUCCESS;
361
362 /* move snd out of the way somewhere */
363 n = snd;
364 if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnodesetfinger, n, FALSE) != SUCCESS) return FAILURE;
365 AGSEQ(snd) = (g->clos->seq[AGNODE] + 2);
366 if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnoderenew, n, FALSE) != SUCCESS) return FAILURE;
367 n = agprvnode(g,snd);
368 do {
369 nxt = agprvnode(g,n);
370 if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnodesetfinger, n, FALSE) != SUCCESS) return FAILURE;
371 AGSEQ(n) = AGSEQ(n) + 1;
372 if (agapply (g, (Agobj_t *) n, (agobjfn_t) agnoderenew, n, FALSE) != SUCCESS) return FAILURE;
373 if (n == fst) break;
374 n = nxt;
375 } while (n);
376 if (agapply (g, (Agobj_t *) snd, (agobjfn_t) agnodesetfinger, n, FALSE) != SUCCESS) return FAILURE;
377 AGSEQ(snd) = AGSEQ(fst) - 1;
378 if (agapply (g, (Agobj_t *) snd, (agobjfn_t) agnoderenew, snd, FALSE) != SUCCESS) return FAILURE;
379 return SUCCESS;
380}
381