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.
29
#include <sys/types.h>
45
#define NIL(type) ((type)0)
47
#define NILgraph NIL(Agraph_t*)
48
#define NILnode NIL(Agnode_t*)
49
#define NILedge NIL(Agedge_t*)
50
#define NILsym NIL(Agsym_t*)
52
/* forward struct type declarations */
53
typedef struct Agtag_s Agtag_t;
54
typedef struct Agobj_s Agobj_t; /* generic object header */
55
typedef struct Agraph_s Agraph_t; /* graph, subgraph (or hyperedge) */
56
typedef struct Agnode_s Agnode_t; /* node (atom) */
57
typedef struct Agedge_s Agedge_t; /* node pair */
58
typedef struct Agdesc_s Agdesc_t; /* graph descriptor */
59
typedef struct Agmemdisc_s Agmemdisc_t; /* memory allocator */
60
typedef struct Agiddisc_s Agiddisc_t; /* object ID allocator */
61
typedef struct Agiodisc_s Agiodisc_t; /* IO services */
62
typedef struct Agdisc_s Agdisc_t; /* union of client discipline methods */
63
typedef struct Agdstate_s Agdstate_t; /* client state (closures) */
64
typedef struct Agsym_s Agsym_t; /* string attribute descriptors */
65
typedef struct Agattr_s Agattr_t; /* string attribute container */
66
typedef struct Agcbdisc_s Agcbdisc_t; /* client event callbacks */
67
typedef struct Agcbstack_s Agcbstack_t; /* enclosing state for cbdisc */
68
typedef struct Agclos_s Agclos_t; /* common fields for graph/subgs */
69
typedef struct Agrec_s Agrec_t; /* generic runtime record */
70
typedef struct Agdatadict_s Agdatadict_t; /* set of dictionaries per graph */
71
typedef struct Agedgepair_s Agedgepair_t;
73
/* Header of a user record. These records are attached by client programs
74
dynamically at runtime. A unique string ID must be given to each record
75
attached to the same object. Libgraph has functions to create, search for,
76
and delete these records. The records are maintained in a circular list,
77
with obj->data pointing somewhere in the list. The search function has
78
an option to lock this pointer on a given record. The application must
79
be written so only one such lock is outstanding at a time. */
84
/* following this would be any programmer-defined data */
87
/* Object tag for graphs, nodes, and edges. While there may be several structs
88
for a given node or edges, there is only one unique ID (per main graph). */
90
unsigned objtype : 2; /* see literal tags below */
91
unsigned mtflock : 1; /* move-to-front lock, see above */
92
unsigned attrwf : 1; /* attrs written (parity, write.c) */
93
unsigned seq : (sizeof(unsigned)*8 - 6); /* sequence no. */
94
unsigned long id; /* client ID*/
98
#define AGRAPH 0 /* can't exceed 2 bits. see Agtag_t. */
101
#define AGINEDGE 3 /* (1 << 1) indicates an edge tag. */
102
#define AGEDGE AGOUTEDGE /* synonym in object kind args */
104
/* a generic graph/node/edge header */
105
struct Agobj_s { /* 7 words */ /* seq_link must be first! */
106
Dtlink_t seq_link; /* link for ordering by local sequence */
107
Dtlink_t id_link; /* link for ordering by global id */
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)
119
/* This is the node struct allocated per graph (or subgraph). It resides
120
in the n_dict of the graph. The node set is maintained by libdict, but
121
transparently to libgraph callers. Every node may be given an optional
122
string name at its time of creation, or it is permissible to pass NIL(char*)
125
struct Agnode_s { /* 12 words */
128
Dtlink_t *outid,*inid; /* in- and out-edge trees by index */
129
Agedge_t *out,*in; /* in- and out-edge trees by seq */
132
struct Agedge_s { /* 8 words, but allocated in pairs -> 16 words */
134
Agnode_t *node; /* the endpoint node */
137
struct Agedgepair_s {
141
struct Agdesc_s { /* graph descriptor */
142
unsigned directed : 1; /* if edges are assymetric */
143
unsigned strict : 1; /* if and self, multi-edges forbidden*/
144
unsigned flatlock : 1; /* if sets are flattened into lists */
145
unsigned maingraph: 1; /* if this is the top level graph */
146
unsigned has_cmpnd : 1; /* if may contain collapsed nodes */
147
unsigned no_write : 1; /* if a temporary subgraph */
148
unsigned has_attrs : 1; /* if string attr tables should be initialized */
151
/* disciplines for external resources needed by libgraph */
153
struct Agmemdisc_s { /* memory allocator */
154
void *(*open)(void); /* independent of other resources */
155
void *(*alloc)(void *state, size_t req);
156
void *(*resize)(void *state, void *ptr, size_t old, size_t req);
157
void (*free)(void *state, void *ptr);
158
void (*close)(void *state);
161
struct Agiddisc_s { /* object ID allocator */
162
void *(*open)(Agraph_t *g); /* associated with a graph */
163
long (*map)(void *state, int objtype, char *str, unsigned long *id, int createflag);
164
long (*alloc)(void *state, int objtype, unsigned long id);
165
void (*free)(void *state, int objtype, unsigned long id);
166
char *(*print)(void *state, int objtype, unsigned long id);
167
void (*close)(void *state);
171
int (*afread)(void *chan, char *buf, int bufsize);
172
int (*putstr)(void *chan, char *str);
173
int (*flush)(void *chan); /* sync */
174
/* error messages? */
177
struct Agdisc_s { /* user's discipline */
183
extern Agdisc_t AgDefaultDisc;
188
/* IO must be initialized and finalized outside Libgraph,
189
* and channels (FILES) are passed as void* arguments. */
192
typedef void (*agobjfn_t)(Agobj_t *obj, void *arg);
193
typedef void (*agobjupdfn_t)(Agobj_t *obj, void *arg, Agsym_t *sym);
203
struct Agcbstack_s { /* object event callbacks */
204
Agcbdisc_t *f; /* methods */
205
void *state; /* closure */
206
Agcbstack_t *prev; /* kept in a stack, unlike other disciplines */
210
Agdisc_t disc; /* resource discipline functions */
211
Agdstate_t state; /* resource closures */
212
Dict_t *strdict; /* shared string dict */
213
unsigned long seq[3]; /* local object sequence number counter */
214
Agcbstack_t *cb; /* user and system callback function stacks */
215
unsigned char callbacks_enabled; /* issue user callbacks or hold them? */
216
Dict_t *lookup_by_name[3];
217
Dict_t *lookup_by_id[3];
220
struct Agraph_s { /* 14 words */
223
Dict_t *n_seq; /* the node set in sequence */
224
Dict_t *n_id; /* the node set indexed by ID */
225
Dict_t *e_seq; /* template for edge set operations */
226
Dict_t *e_id; /* template for edge set operations */
227
Dict_t *g_dict; /* subgraphs - descendants */
228
Agraph_t *parent, *root; /* subgraphs - ancestors */
229
Agclos_t *clos; /* shared resources */
234
/* fine control of object callbacks */
235
# if defined(_BLD_agraph) && defined(__EXPORT__)
236
# define extern __EXPORT__
238
# if !defined(_BLD_agraph) && defined(__IMPORT__)
239
# define extern __IMPORT__
243
extern void agpushdisc(Agraph_t *g, Agcbdisc_t *disc, void *state);
244
extern int agpopdisc(Agraph_t *g, Agcbdisc_t *disc);
245
extern int agcallbacks(Agraph_t *g, int flag); /* return prev value */
248
extern Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t *disc);
249
extern int agclose(Agraph_t *g);
250
extern Agraph_t *agread(void *chan, Agdisc_t *disc);
251
extern Agraph_t *agconcat(Agraph_t *g, void *chan, Agdisc_t *disc);
252
extern int agwrite(Agraph_t *g, void *chan);
253
extern void agflatten(Agraph_t *g, int flag);
254
extern int agisflattened(Agraph_t *g);
255
extern int agisdirected(Agraph_t*g);
256
extern int agisundirected(Agraph_t*g);
257
extern int agisstrict(Agraph_t*g);
260
extern Agnode_t *agnode(Agraph_t *g, char *name, int createflag);
261
extern Agnode_t *agidnode(Agraph_t *g, unsigned long id, int createflag);
262
extern Agnode_t *agsubnode(Agraph_t *g, Agnode_t *n, int createflag);
263
extern Agnode_t *agfstnode(Agraph_t *g);
264
extern Agnode_t *agnxtnode(Agnode_t *n);
267
extern Agedge_t *agedge(Agnode_t *t, Agnode_t *h, char *name, int createflag);
268
extern Agedge_t *agidedge(Agnode_t *t, Agnode_t *h, unsigned long id, int createflag);
269
extern Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int createflag);
270
extern Agedge_t *agfstin(Agnode_t *n);
271
extern Agedge_t *agnxtin(Agedge_t *e);
272
extern Agedge_t *agfstout(Agnode_t *n);
273
extern Agedge_t *agnxtout(Agedge_t *e);
274
extern Agedge_t *agfstedge(Agnode_t *n);
275
extern Agedge_t *agnxtedge(Agedge_t *e, Agnode_t *n);
278
extern Agraph_t *agraphof(void*);
279
extern char *agnameof(void*);
280
extern int agrelabel(void *obj, char *name); /* scary */
281
extern int agdelete(Agraph_t *g, void *obj);
282
extern long agdelsubg(Agraph_t *g, Agraph_t *sub); /* could be agclose */
283
extern int agdelnode(Agnode_t *arg_n);
284
extern int agdeledge(Agedge_t *arg_e);
285
extern int agisarootobj(void*);
288
extern char *agstrdup(Agraph_t *, char *);
289
extern char *agstrbind(Agraph_t *g, char*);
290
extern int agstrfree(Agraph_t *, char *);
292
/* definitions for dynamic string attributes */
293
struct Agattr_s { /* dynamic string attributes */
294
Agrec_t h; /* common data header */
295
Dict_t *dict; /* shared dict to interpret attr field */
296
char **str; /* the attribute string values */
299
struct Agsym_s { /* symbol in one of the above dictionaries */
301
char *name; /* attribute's name */
302
char *defval; /* its default value for initialization */
303
int id; /* its index in attr[] */
304
int kind; /* referent object type */
307
struct Agdatadict_s { /* set of dictionaries per graph */
308
Agrec_t h; /* installed in list of graph recs */
309
struct {Dict_t *n,*e,*g;} dict;
312
extern Agsym_t *agattr(Agraph_t *g, int kind, char *name, char *value);
313
extern Agsym_t *agattrsym(void *obj, char *name);
314
extern Agsym_t *agnxtattr(Agraph_t *g, int kind, Agsym_t *attr);
315
extern void *agbindrec(void *obj, char *name, unsigned int size,int move_to_front);
316
extern Agrec_t *aggetrec(void *obj, char *name, int move_to_front);
317
extern int agdelrec(void *obj, char *name);
318
extern void aginit(Agraph_t *g, int kind, char *rec_name, int rec_size, int move_to_front);
319
extern void agclean(Agraph_t *g, int kind, char *rec_name);
321
extern char *agget(void *obj, char *name);
322
extern char *agxget(void *obj, Agsym_t *sym);
323
extern int agset(void *obj, char *name, char *value);
324
extern int agxset(void *obj, Agsym_t *sym, char *value);
326
/* defintions for subgraphs */
327
extern Agraph_t *agsubg(Agraph_t *g, char *name, int cflag); /* constructor */
328
extern Agraph_t *agidsubg(Agraph_t *g, unsigned long id, int cflag); /* constructor */
329
extern Agraph_t *agfstsubg(Agraph_t *g), *agnxtsubg(Agraph_t *subg);
330
extern Agraph_t *agparent(Agraph_t *g),*agroot(Agraph_t *g);
332
/* set cardinality */
333
extern int agnnodes(Agraph_t *g),agnedges(Agraph_t *g);
334
extern int agdegree(Agnode_t *n, int in, int out);
337
extern void *agalloc(Agraph_t *g, size_t size);
338
extern void *agrealloc(Agraph_t *g, void *ptr, size_t oldsize, size_t size);
339
extern void agfree(Agraph_t *g, void *ptr);
340
extern struct _vmalloc_s *agheap(Agraph_t *g);
342
/* an engineering compromise is a joy forever */
343
extern void aginternalmapclearlocalnames(Agraph_t *g);
345
#define agnew(g,t) ((t*)agalloc(g,sizeof(t)))
346
#define agnnew(g,n,t) ((t*)agalloc(g,(n)*sizeof(t)))
349
extern void agerror(int code, char *str);
350
#define AGERROR_SYNTAX 1 /* error encountered in lexing or parsing */
351
#define AGERROR_MEMORY 2 /* out of memory */
352
#define AGERROR_UNIMPL 3 /* unimplemented feature */
353
#define AGERROR_MTFLOCK 4 /* move to front lock has been set */
354
#define AGERROR_CMPND 5 /* conflict in restore_endpoint() */
355
#define AGERROR_BADOBJ 6 /* passed an illegal pointer */
356
#define AGERROR_IDOVFL 7 /* object ID overflow */
357
#define AGERROR_FLAT 8 /* attempt to break a flat lock */
358
#define AGERROR_WRONGGRAPH 9 /* mismatched graph and object */
360
/* abbreviations, convenience */
362
#define AGFIRSTNODE(g) ((Agnode_t*)dtfirst((g)->n_seq))
363
#define AGPREVNODE(n) ((Agnode_t*)((n)->base.seq_link.hl._left))
364
#define AGNEXTNODE(n) ((Agnode_t*)((n)->base.seq_link.right))
365
#define AGFSTOUT(n) ((Agedge_t*)((n)->out))
366
#define AGFSTIN(n) ((Agedge_t*)((n)->in))
367
#define AGPREV(e) ((Agedge_t*)((e)->base.seq_link.hl._left))
368
#define AGNXTE(e) ((Agedge_t*)((e)->base.seq_link.right))
369
/* this assumes that e[0] is out and e[1] is inedge, see edgepair in edge.c */
370
#define AGIN2OUT(e) ((e)-1)
371
#define AGOUT2IN(e) ((e)+1)
372
#define AGOPP(e) ((AGTYPE(e)==AGINEDGE)?AGIN2OUT(e):AGOUT2IN(e))
373
#define AGMKOUT(e) (AGTYPE(e) == AGOUTEDGE? (e): AGIN2OUT(e))
374
#define AGMKIN(e) (AGTYPE(e) == AGINEDGE? (e): AGOUT2IN(e))
375
#define AGTAIL(e) (AGMKIN(e)->node)
376
#define AGHEAD(e) (AGMKOUT(e)->node)
377
#define agtail(e) AGTAIL(e)
378
#define aghead(e) AGHEAD(e)
379
#define agopp(e) AGOPP(e)
382
# if !defined(_BLD_agraph) && defined(__IMPORT__)
383
# define extern __IMPORT__
387
extern Agdesc_t Agdirected, Agstrictdirected, Agundirected, Agstrictundirected;