Graphviz  2.41.20170921.2350
node.c
Go to the documentation of this file.
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 
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 
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 
39 {
40  Agsubnode_t *sn;
41  sn = (Agsubnode_t *) dtfirst(g->n_seq);
42  return sn ? sn->node : NILnode;
43 }
44 
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 
54 {
55  Agsubnode_t *sn;
56  sn = (Agsubnode_t *) dtlast(g->n_seq);
57  return sn ? sn->node : NILnode;
58 }
59 
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 */
70 static 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 
87 static 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 
103 static 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 
111 static 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 */
119 Agnode_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 
142 Agnode_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. */
174 void 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 
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)
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 
217 static 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 
231 int 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> */
254 Agnode_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 
274 int 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 
286 int 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  */
306 static void
307 free_subnode (Dt_t* d, Agsubnode_t* sn, Dtdisc_t * disc)
308 {
309 
310  if (!AGSNMAIN(sn))
311  agfree (sn->node->root, sn);
312 }
313 
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),
321  NIL(Dthash_f),
322  agdictobjmem,
323  NIL(Dtevent_f)
324 };
325 
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,
333  NIL(Dthash_f),
334  agdictobjmem,
335  NIL(Dtevent_f)
336 };
337 
338 void 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 
346 void 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 
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 }
CGRAPH_API int agdeledge(Agraph_t *g, Agedge_t *arg_e)
Definition: edge.c:357
void agnodeattr_init(Agraph_t *g, Agnode_t *n)
Definition: attr.c:390
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
#define AGSEQ(obj)
Definition: cgraph.h:115
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
#define dtprev(d, o)
Definition: cdt.h:258
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
#define SUCCESS
Definition: cghdr.h:62
CGRAPH_API int agdelnode(Agraph_t *g, Agnode_t *arg_n)
Definition: node.c:192
void agrecclose(Agobj_t *obj)
Definition: rec.c:263
Agdesc_t desc
Definition: cgraph.h:241
int agmapnametoid(Agraph_t *g, int objtype, char *str, IDTYPE *result, int allocflag)
Definition: id.c:96
void agregister(Agraph_t *g, int objtype, void *obj)
Definition: id.c:169
#define AGID(obj)
Definition: cgraph.h:114
Dict_t * n_seq
Definition: cgraph.h:243
#define dtdelete(d, o)
Definition: cdt.h:264
#define assert(x)
Definition: cghdr.h:47
CGRAPH_API Agnode_t * agprvnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:60
void agnoderenew(Agraph_t *g, Agnode_t *n, void *ignored)
Definition: node.c:346
#define NOTUSED(var)
Definition: cghdr.h:54
Definition: cdt.h:80
Dtdisc_t Ag_subnode_seq_disc
Definition: node.c:326
#define dtfirst(d)
Definition: cdt.h:254
Agtag_t tag
Definition: cgraph.h:108
#define dtlast(d)
Definition: cdt.h:257
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
Agobj_t base
Definition: cgraph.h:134
Dtdisc_t Ag_subnode_id_disc
Definition: node.c:314
CDT_API void * dtrenew(Dt_t *, void *)
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
IDTYPE id
Definition: cgraph.h:96
uint64_t agnextseq(Agraph_t *g, int objtype)
Definition: graph.c:157
CGRAPH_API void agfree(Agraph_t *g, void *ptr)
Definition: mem.c:89
#define AGTYPE(obj)
Definition: cgraph.h:113
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
#define dtfinger(d)
Definition: cdt.h:252
uint64_t IDTYPE
Definition: cgraph.h:51
#define NILnode
Definition: cghdr.h:57
Dict_t * n_id
Definition: cgraph.h:244
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
unsigned has_attrs
Definition: cgraph.h:157
#define NIL(t)
Definition: dthdr.h:13
#define dtsearch(d, o)
Definition: cdt.h:260
#define FAILURE
Definition: cghdr.h:63
uint64_t seq[3]
Definition: cgraph.h:232
void agdelnodeimage(Agraph_t *g, Agnode_t *node, void *ignored)
Definition: node.c:174
Agnode_t * agfindnode_by_name(Agraph_t *g, char *name)
Definition: node.c:28
CGRAPH_API Agraph_t * agparent(Agraph_t *g)
Definition: subg.c:85
#define dtnext(d, o)
Definition: cdt.h:255
CGRAPH_API int agrelabel_node(Agnode_t *n, char *newname)
Definition: node.c:231
void agdeledgeimage(Agraph_t *g, Agedge_t *edge, void *ignored)
Definition: edge.c:327
void agnodesetfinger(Agraph_t *g, Agnode_t *n, void *ignored)
Definition: node.c:338
int agsubnodeidcmpf(Dict_t *d, void *arg0, void *arg1, Dtdisc_t *disc)
Definition: node.c:274
void agmethod_delete(Agraph_t *g, void *obj)
Definition: obj.c:138
CGRAPH_API Agnode_t * aglstnode(Agraph_t *g)
Definition: node.c:53
void agfreeid(Agraph_t *g, int objtype, IDTYPE id)
Definition: id.c:131
CDT_API int dtsize(Dt_t *)
Definition: dtsize.c:12
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define AGNODE
Definition: cgraph.h:101
void agmethod_init(Agraph_t *g, void *obj)
Definition: obj.c:76
CGRAPH_API Agsubnode_t * agsubrep(Agraph_t *g, Agnode_t *n)
Definition: edge.c:157
#define dtinsert(d, o)
Definition: cdt.h:262
char * AgDataRecName
Definition: attr.c:169
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
int agallocid(Agraph_t *g, int objtype, IDTYPE request)
Definition: id.c:126
Agnode_t * node
Definition: cgraph.h:128
CGRAPH_API int agnodebefore(Agnode_t *u, Agnode_t *v)
Definition: node.c:353
CGRAPH_API void * agalloc(Agraph_t *g, size_t size)
Definition: mem.c:62
#define AGSNMAIN(sn)
Definition: cgraph.h:448
void * agdictobjmem(Dict_t *dict, void *p, size_t size, Dtdisc_t *disc)
Definition: utils.c:19
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
Definition: cdt.h:99
Agraph_t * root
Definition: cgraph.h:135
void agnodeattr_delete(Agnode_t *n)
Definition: attr.c:399
Agclos_t * clos
Definition: cgraph.h:248
CGRAPH_API Agnode_t * agidnode(Agraph_t *g, IDTYPE id, int createflag)
Definition: node.c:119
Agnode_t * agfindnode_by_id(Agraph_t *g, IDTYPE id)
Definition: node.c:16
Agsubnode_t mainsub
Definition: cgraph.h:136
int agapply(Agraph_t *g, Agobj_t *obj, agobjfn_t fn, void *arg, int preorder)
Definition: apply.c:61
#define FALSE
Definition: cgraph.h:35
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
void(* agobjfn_t)(Agraph_t *g, Agobj_t *obj, void *arg)
Definition: cgraph.h:210
int agsubnodeseqcmpf(Dict_t *d, void *arg0, void *arg1, Dtdisc_t *disc)
Definition: node.c:286
#define TRUE
Definition: cgraph.h:38