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#ifndef ATT_GRAPH_H
15#define ATT_GRAPH_H
16
17#include <inttypes.h>
18#include "cdt.h"
19
20#ifdef __cplusplus
21extern "C" {
22#endif
23
24#ifdef _WIN32
25# ifdef EXPORT_CGRAPH
26# define CGRAPH_API __declspec(dllexport)
27# else
28# define CGRAPH_API __declspec(dllimport)
29# endif
30#else
31# define CGRAPH_API extern
32#endif
33
34#ifndef FALSE
35#define FALSE (0)
36#endif
37#ifndef TRUE
38#define TRUE (!FALSE)
39#endif
40#ifndef NOT
41#define NOT(x) (!(x))
42#endif
43#ifndef NIL
44#define NIL(type) ((type)0)
45#endif
46#define NILgraph NIL(Agraph_t*)
47#define NILnode NIL(Agnode_t*)
48#define NILedge NIL(Agedge_t*)
49#define NILsym NIL(Agsym_t*)
50
51typedef uint64_t IDTYPE;
52
53/* forward struct type declarations */
54typedef struct Agtag_s Agtag_t;
55typedef struct Agobj_s Agobj_t; /* generic object header */
56typedef struct Agraph_s Agraph_t; /* graph, subgraph (or hyperedge) */
57typedef struct Agnode_s Agnode_t; /* node (atom) */
58typedef struct Agedge_s Agedge_t; /* node pair */
59typedef struct Agdesc_s Agdesc_t; /* graph descriptor */
60typedef struct Agmemdisc_s Agmemdisc_t; /* memory allocator */
61typedef struct Agiddisc_s Agiddisc_t; /* object ID allocator */
62typedef struct Agiodisc_s Agiodisc_t; /* IO services */
63typedef struct Agdisc_s Agdisc_t; /* union of client discipline methods */
64typedef struct Agdstate_s Agdstate_t; /* client state (closures) */
65typedef struct Agsym_s Agsym_t; /* string attribute descriptors */
66typedef struct Agattr_s Agattr_t; /* string attribute container */
67typedef struct Agcbdisc_s Agcbdisc_t; /* client event callbacks */
68typedef struct Agcbstack_s Agcbstack_t; /* enclosing state for cbdisc */
69typedef struct Agclos_s Agclos_t; /* common fields for graph/subgs */
70typedef struct Agrec_s Agrec_t; /* generic runtime record */
71typedef struct Agdatadict_s Agdatadict_t; /* set of dictionaries per graph */
72typedef struct Agedgepair_s Agedgepair_t; /* the edge object */
73typedef struct Agsubnode_s Agsubnode_t;
74
75/* Header of a user record. These records are attached by client programs
76dynamically at runtime. A unique string ID must be given to each record
77attached to the same object. Cgraph has functions to create, search for,
78and delete these records. The records are maintained in a circular list,
79with obj->data pointing somewhere in the list. The search function has
80an option to lock this pointer on a given record. The application must
81be written so only one such lock is outstanding at a time. */
82
83struct Agrec_s {
84 char *name;
85 Agrec_t *next;
86 /* following this would be any programmer-defined data */
87};
88
89/* Object tag for graphs, nodes, and edges. While there may be several structs
90for a given node or edges, there is only one unique ID (per main graph). */
91struct Agtag_s {
92 unsigned objtype:2; /* see literal tags below */
93 unsigned mtflock:1; /* move-to-front lock, see above */
94 unsigned attrwf:1; /* attrs written (parity, write.c) */
95 unsigned seq:(sizeof(unsigned) * 8 - 4); /* sequence no. */
96 IDTYPE id; /* client ID */
97};
98
99 /* object tags */
100#define AGRAPH 0 /* can't exceed 2 bits. see Agtag_t. */
101#define AGNODE 1
102#define AGOUTEDGE 2
103#define AGINEDGE 3 /* (1 << 1) indicates an edge tag. */
104#define AGEDGE AGOUTEDGE /* synonym in object kind args */
105
106 /* a generic graph/node/edge header */
107struct Agobj_s {
108 Agtag_t tag;
109 Agrec_t *data;
110};
111
112#define AGTAG(obj) (((Agobj_t*)(obj))->tag)
113#define AGTYPE(obj) (AGTAG(obj).objtype)
114#define AGID(obj) (AGTAG(obj).id)
115#define AGSEQ(obj) (AGTAG(obj).seq)
116#define AGATTRWF(obj) (AGTAG(obj).attrwf)
117#define AGDATA(obj) (((Agobj_t*)(obj))->data)
118
119/* This is the node struct allocated per graph (or subgraph). It resides
120in the n_dict of the graph. The node set is maintained by libdict, but
121transparently to libgraph callers. Every node may be given an optional
122string name at its time of creation, or it is permissible to pass NIL(char*)
123for the name. */
124
125struct Agsubnode_s { /* the node-per-graph-or-subgraph record */
126 Dtlink_t seq_link; /* must be first */
127 Dtlink_t id_link;
128 Agnode_t *node; /* the object */
129 Dtlink_t *in_id, *out_id; /* by node/ID for random access */
130 Dtlink_t *in_seq, *out_seq; /* by node/sequence for serial access */
131};
132
133struct Agnode_s {
134 Agobj_t base;
135 Agraph_t *root;
136 Agsubnode_t mainsub; /* embedded for main graph */
137};
138
139struct Agedge_s {
140 Agobj_t base;
141 Dtlink_t id_link; /* main graph only */
142 Dtlink_t seq_link;
143 Agnode_t *node; /* the endpoint node */
144};
145
146struct Agedgepair_s {
147 Agedge_t out, in;
148};
149
150struct Agdesc_s { /* graph descriptor */
151 unsigned directed:1; /* if edges are asymmetric */
152 unsigned strict:1; /* if multi-edges forbidden */
153 unsigned no_loop:1; /* if no loops */
154 unsigned maingraph:1; /* if this is the top level graph */
155 unsigned flatlock:1; /* if sets are flattened into lists in cdt */
156 unsigned no_write:1; /* if a temporary subgraph */
157 unsigned has_attrs:1; /* if string attr tables should be initialized */
158 unsigned has_cmpnd:1; /* if may contain collapsed nodes */
159};
160
161/* disciplines for external resources needed by libgraph */
162
163struct Agmemdisc_s { /* memory allocator */
164 void *(*open) (Agdisc_t*); /* independent of other resources */
165 void *(*alloc) (void *state, size_t req);
166 void *(*resize) (void *state, void *ptr, size_t old, size_t req);
167 void (*free) (void *state, void *ptr);
168 void (*close) (void *state);
169};
170
171struct Agiddisc_s { /* object ID allocator */
172 void *(*open) (Agraph_t * g, Agdisc_t*); /* associated with a graph */
173 long (*map) (void *state, int objtype, char *str, IDTYPE *id,
174 int createflag);
175 long (*alloc) (void *state, int objtype, IDTYPE id);
176 void (*free) (void *state, int objtype, IDTYPE id);
177 char *(*print) (void *state, int objtype, IDTYPE id);
178 void (*close) (void *state);
179 void (*idregister) (void *state, int objtype, void *obj);
180};
181
182struct Agiodisc_s {
183 int (*afread) (void *chan, char *buf, int bufsize);
184 int (*putstr) (void *chan, const char *str);
185 int (*flush) (void *chan); /* sync */
186 /* error messages? */
187};
188
189struct Agdisc_s { /* user's discipline */
190 Agmemdisc_t *mem;
191 Agiddisc_t *id;
192 Agiodisc_t *io;
193};
194
195 /* default resource disciplines */
196
197CGRAPH_API Agmemdisc_t AgMemDisc;
198CGRAPH_API Agiddisc_t AgIdDisc;
199CGRAPH_API Agiodisc_t AgIoDisc;
200
201CGRAPH_API Agdisc_t AgDefaultDisc;
202
203struct Agdstate_s {
204 void *mem;
205 void *id;
206 /* IO must be initialized and finalized outside Cgraph,
207 * and channels (FILES) are passed as void* arguments. */
208};
209
210typedef void (*agobjfn_t) (Agraph_t * g, Agobj_t * obj, void *arg);
211typedef void (*agobjupdfn_t) (Agraph_t * g, Agobj_t * obj, void *arg,
212 Agsym_t * sym);
213
214struct Agcbdisc_s {
215 struct {
216 agobjfn_t ins;
217 agobjupdfn_t mod;
218 agobjfn_t del;
219 } graph, node, edge;
220};
221
222struct Agcbstack_s { /* object event callbacks */
223 Agcbdisc_t *f; /* methods */
224 void *state; /* closure */
225 Agcbstack_t *prev; /* kept in a stack, unlike other disciplines */
226};
227
228struct Agclos_s {
229 Agdisc_t disc; /* resource discipline functions */
230 Agdstate_t state; /* resource closures */
231 Dict_t *strdict; /* shared string dict */
232 uint64_t seq[3]; /* local object sequence number counter */
233 Agcbstack_t *cb; /* user and system callback function stacks */
234 unsigned char callbacks_enabled; /* issue user callbacks or hold them? */
235 Dict_t *lookup_by_name[3];
236 Dict_t *lookup_by_id[3];
237};
238
239struct Agraph_s {
240 Agobj_t base;
241 Agdesc_t desc;
242 Dtlink_t link;
243 Dict_t *n_seq; /* the node set in sequence */
244 Dict_t *n_id; /* the node set indexed by ID */
245 Dict_t *e_seq, *e_id; /* holders for edge sets */
246 Dict_t *g_dict; /* subgraphs - descendants */
247 Agraph_t *parent, *root; /* subgraphs - ancestors */
248 Agclos_t *clos; /* shared resources */
249};
250
251CGRAPH_API void agpushdisc(Agraph_t * g, Agcbdisc_t * disc, void *state);
252CGRAPH_API int agpopdisc(Agraph_t * g, Agcbdisc_t * disc);
253CGRAPH_API int agcallbacks(Agraph_t * g, int flag); /* return prev value */
254
255/* graphs */
256CGRAPH_API Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t * disc);
257CGRAPH_API int agclose(Agraph_t * g);
258CGRAPH_API Agraph_t *agread(void *chan, Agdisc_t * disc);
259CGRAPH_API Agraph_t *agmemread(const char *cp);
260CGRAPH_API void agreadline(int);
261CGRAPH_API void agsetfile(char *);
262CGRAPH_API Agraph_t *agconcat(Agraph_t * g, void *chan, Agdisc_t * disc);
263CGRAPH_API int agwrite(Agraph_t * g, void *chan);
264CGRAPH_API int agisdirected(Agraph_t * g);
265CGRAPH_API int agisundirected(Agraph_t * g);
266CGRAPH_API int agisstrict(Agraph_t * g);
267CGRAPH_API int agissimple(Agraph_t * g);
268
269/* nodes */
270CGRAPH_API Agnode_t *agnode(Agraph_t * g, char *name, int createflag);
271CGRAPH_API Agnode_t *agidnode(Agraph_t * g, IDTYPE id, int createflag);
272CGRAPH_API Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n, int createflag);
273CGRAPH_API Agnode_t *agfstnode(Agraph_t * g);
274CGRAPH_API Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n);
275CGRAPH_API Agnode_t *aglstnode(Agraph_t * g);
276CGRAPH_API Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n);
277
278CGRAPH_API Agsubnode_t *agsubrep(Agraph_t * g, Agnode_t * n);
279CGRAPH_API int agnodebefore(Agnode_t *u, Agnode_t *v); /* we have no shame */
280
281/* edges */
282CGRAPH_API Agedge_t *agedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
283 char *name, int createflag);
284CGRAPH_API Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
285 IDTYPE id, int createflag);
286CGRAPH_API Agedge_t *agsubedge(Agraph_t * g, Agedge_t * e, int createflag);
287CGRAPH_API Agedge_t *agfstin(Agraph_t * g, Agnode_t * n);
288CGRAPH_API Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e);
289CGRAPH_API Agedge_t *agfstout(Agraph_t * g, Agnode_t * n);
290CGRAPH_API Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e);
291CGRAPH_API Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n);
292CGRAPH_API Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n);
293
294/* generic */
295CGRAPH_API Agraph_t *agraphof(void* obj);
296CGRAPH_API Agraph_t *agroot(void* obj);
297CGRAPH_API int agcontains(Agraph_t *, void *);
298CGRAPH_API char *agnameof(void *);
299CGRAPH_API int agrelabel(void *obj, char *name); /* scary */
300CGRAPH_API int agrelabel_node(Agnode_t * n, char *newname);
301CGRAPH_API int agdelete(Agraph_t * g, void *obj);
302CGRAPH_API long agdelsubg(Agraph_t * g, Agraph_t * sub); /* could be agclose */
303CGRAPH_API int agdelnode(Agraph_t * g, Agnode_t * arg_n);
304CGRAPH_API int agdeledge(Agraph_t * g, Agedge_t * arg_e);
305CGRAPH_API int agobjkind(void *);
306
307/* strings */
308CGRAPH_API char *agstrdup(Agraph_t *, char *);
309CGRAPH_API char *agstrdup_html(Agraph_t *, char *);
310CGRAPH_API int aghtmlstr(char *);
311CGRAPH_API char *agstrbind(Agraph_t * g, char *);
312CGRAPH_API int agstrfree(Agraph_t *, char *);
313CGRAPH_API char *agcanon(char *, int);
314CGRAPH_API char *agstrcanon(char *, char *);
315CGRAPH_API char *agcanonStr(char *str); /* manages its own buf */
316
317/* definitions for dynamic string attributes */
318struct Agattr_s { /* dynamic string attributes */
319 Agrec_t h; /* common data header */
320 Dict_t *dict; /* shared dict to interpret attr field */
321 char **str; /* the attribute string values */
322};
323
324struct Agsym_s { /* symbol in one of the above dictionaries */
325 Dtlink_t link;
326 char *name; /* attribute's name */
327 char *defval; /* its default value for initialization */
328 int id; /* its index in attr[] */
329 unsigned char kind; /* referent object type */
330 unsigned char fixed; /* immutable value */
331 unsigned char print; /* always print */
332};
333
334struct Agdatadict_s { /* set of dictionaries per graph */
335 Agrec_t h; /* installed in list of graph recs */
336 struct {
337 Dict_t *n, *e, *g;
338 } dict;
339};
340
341CGRAPH_API Agsym_t *agattr(Agraph_t * g, int kind, char *name, char *value);
342CGRAPH_API Agsym_t *agattrsym(void *obj, char *name);
343CGRAPH_API Agsym_t *agnxtattr(Agraph_t * g, int kind, Agsym_t * attr);
344CGRAPH_API int agcopyattr(void *oldobj, void *newobj);
345
346CGRAPH_API void *agbindrec(void *obj, char *name, unsigned int size,
347 int move_to_front);
348CGRAPH_API Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
349CGRAPH_API int agdelrec(void *obj, char *name);
350CGRAPH_API void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size,
351 int move_to_front);
352CGRAPH_API void agclean(Agraph_t * g, int kind, char *rec_name);
353
354CGRAPH_API char *agget(void *obj, char *name);
355CGRAPH_API char *agxget(void *obj, Agsym_t * sym);
356CGRAPH_API int agset(void *obj, char *name, char *value);
357CGRAPH_API int agxset(void *obj, Agsym_t * sym, char *value);
358CGRAPH_API int agsafeset(void* obj, char* name, char* value, char* def);
359
360/* defintions for subgraphs */
361CGRAPH_API Agraph_t *agsubg(Agraph_t * g, char *name, int cflag); /* constructor */
362CGRAPH_API Agraph_t *agidsubg(Agraph_t * g, IDTYPE id, int cflag); /* constructor */
363CGRAPH_API Agraph_t *agfstsubg(Agraph_t * g);
364CGRAPH_API Agraph_t *agnxtsubg(Agraph_t * subg);
365CGRAPH_API Agraph_t *agparent(Agraph_t * g);
366
367/* set cardinality */
368CGRAPH_API int agnnodes(Agraph_t * g);
369CGRAPH_API int agnedges(Agraph_t * g);
370CGRAPH_API int agnsubg(Agraph_t * g);
371CGRAPH_API int agdegree(Agraph_t * g, Agnode_t * n, int in, int out);
372CGRAPH_API int agcountuniqedges(Agraph_t * g, Agnode_t * n, int in, int out);
373
374/* memory */
375CGRAPH_API void *agalloc(Agraph_t * g, size_t size);
376CGRAPH_API void *agrealloc(Agraph_t * g, void *ptr, size_t oldsize,
377 size_t size);
378CGRAPH_API void agfree(Agraph_t * g, void *ptr);
379CGRAPH_API struct _vmalloc_s *agheap(Agraph_t * g);
380
381/* an engineering compromise is a joy forever */
382CGRAPH_API void aginternalmapclearlocalnames(Agraph_t * g);
383
384#define agnew(g,t) ((t*)agalloc(g,sizeof(t)))
385#define agnnew(g,n,t) ((t*)agalloc(g,(n)*sizeof(t)))
386
387/* error handling */
388typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t;
389typedef int (*agusererrf) (char*);
390CGRAPH_API agerrlevel_t agseterr(agerrlevel_t);
391CGRAPH_API char *aglasterr(void);
392CGRAPH_API int agerr(agerrlevel_t level, const char *fmt, ...);
393CGRAPH_API void agerrorf(const char *fmt, ...);
394CGRAPH_API void agwarningf(const char *fmt, ...);
395CGRAPH_API int agerrors(void);
396CGRAPH_API int agreseterrors(void);
397CGRAPH_API agusererrf agseterrf(agusererrf);
398
399/* data access macros */
400/* this assumes that e[0] is out and e[1] is inedge, see edgepair in edge.c */
401#define AGIN2OUT(e) ((e)-1)
402#define AGOUT2IN(e) ((e)+1)
403#define AGOPP(e) ((AGTYPE(e)==AGINEDGE)?AGIN2OUT(e):AGOUT2IN(e))
404#define AGMKOUT(e) (AGTYPE(e) == AGOUTEDGE? (e): AGIN2OUT(e))
405#define AGMKIN(e) (AGTYPE(e) == AGINEDGE? (e): AGOUT2IN(e))
406#define AGTAIL(e) (AGMKIN(e)->node)
407#define AGHEAD(e) (AGMKOUT(e)->node)
408#define AGEQEDGE(e,f) (AGMKOUT(e) == AGMKOUT(f))
409/* These macros are also exposed as functions, so they can be linked against. */
410#define agtail(e) AGTAIL(e)
411#define aghead(e) AGHEAD(e)
412#define agopp(e) AGOPP(e)
413#define ageqedge(e,f) AGEQEDGE(e,f)
414
415#define TAILPORT_ID "tailport"
416#define HEADPORT_ID "headport"
417
418CGRAPH_API Agdesc_t Agdirected;
419CGRAPH_API Agdesc_t Agstrictdirected;
420CGRAPH_API Agdesc_t Agundirected;
421CGRAPH_API Agdesc_t Agstrictundirected;
422
423/* fast graphs */
424void agflatten(Agraph_t * g, int flag);
425typedef Agsubnode_t Agnoderef_t;
426typedef Dtlink_t Agedgeref_t;
427
428#define AGHEADPOINTER(g) ((Agnoderef_t*)(g->n_seq->data->hh._head))
429#define AGRIGHTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.right?((void*)((rep)->seq_link.right) - offsetof(Agsubnode_t,seq_link)):0))
430#define AGLEFTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.hl._left?((void*)((rep)->seq_link.hl._left) - offsetof(Agsubnode_t,seq_link)):0))
431
432#define FIRSTNREF(g) (agflatten(g,1), AGHEADPOINTER(g))
433
434#define NEXTNREF(g,rep) (AGRIGHTPOINTER(rep) == AGHEADPOINTER(g)?0:AGRIGHTPOINTER(rep))
435
436#define PREVNREF(g,rep) (((rep)==AGHEADPOINTER(g))?0:(AGLEFTPOINTER(rep)))
437
438#define LASTNREF(g) (agflatten(g,1), AGHEADPOINTER(g)?AGLEFTPOINTER(AGHEADPOINTER(g)):0)
439#define NODEOF(rep) ((rep)->node)
440
441#define FIRSTOUTREF(g,sn) (agflatten(g,1), (sn)->out_seq)
442#define LASTOUTREF(g,sn) (agflatten(g,1), (Agedgeref_t*)dtlast(sn->out_seq))
443#define FIRSTINREF(g,sn) (agflatten(g,1), (sn)->in_seq)
444#define NEXTEREF(g,rep) ((rep)->right)
445#define PREVEREF(g,rep) ((rep)->hl._left)
446/* this is expedient but a bit slimey because it "knows" that dict entries of both nodes
447and edges are embedded in main graph objects but allocated separately in subgraphs */
448#define AGSNMAIN(sn) ((sn)==(&((sn)->node->mainsub)))
449#define EDGEOF(sn,rep) (AGSNMAIN(sn)?((Agedge_t*)((unsigned char*)(rep) - offsetof(Agedge_t,seq_link))) : ((Dthold_t*)(rep))->obj)
450
451#ifdef __cplusplus
452}
453#endif
454#endif
455