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 21 extern "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 51 typedef uint64_t IDTYPE; 52 53 /* forward struct type declarations */ 54 typedef struct Agtag_s Agtag_t; 55 typedef struct Agobj_s Agobj_t; /* generic object header */ 56 typedef struct Agraph_s Agraph_t; /* graph, subgraph (or hyperedge) */ 57 typedef struct Agnode_s Agnode_t; /* node (atom) */ 58 typedef struct Agedge_s Agedge_t; /* node pair */ 59 typedef struct Agdesc_s Agdesc_t; /* graph descriptor */ 60 typedef struct Agmemdisc_s Agmemdisc_t; /* memory allocator */ 61 typedef struct Agiddisc_s Agiddisc_t; /* object ID allocator */ 62 typedef struct Agiodisc_s Agiodisc_t; /* IO services */ 63 typedef struct Agdisc_s Agdisc_t; /* union of client discipline methods */ 64 typedef struct Agdstate_s Agdstate_t; /* client state (closures) */ 65 typedef struct Agsym_s Agsym_t; /* string attribute descriptors */ 66 typedef struct Agattr_s Agattr_t; /* string attribute container */ 67 typedef struct Agcbdisc_s Agcbdisc_t; /* client event callbacks */ 68 typedef struct Agcbstack_s Agcbstack_t; /* enclosing state for cbdisc */ 69 typedef struct Agclos_s Agclos_t; /* common fields for graph/subgs */ 70 typedef struct Agrec_s Agrec_t; /* generic runtime record */ 71 typedef struct Agdatadict_s Agdatadict_t; /* set of dictionaries per graph */ 72 typedef struct Agedgepair_s Agedgepair_t; /* the edge object */ 73 typedef struct Agsubnode_s Agsubnode_t; 74 75 /* Header of a user record. These records are attached by client programs 76 dynamically at runtime. A unique string ID must be given to each record 77 attached to the same object. Cgraph has functions to create, search for, 78 and delete these records. The records are maintained in a circular list, 79 with obj->data pointing somewhere in the list. The search function has 80 an option to lock this pointer on a given record. The application must 81 be written so only one such lock is outstanding at a time. */ 82 83 struct 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 90 for a given node or edges, there is only one unique ID (per main graph). */ 91 struct 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 */ 107 struct 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 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*) 123 for the name. */ 124 125 struct 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 133 struct Agnode_s { 134 Agobj_t base; 135 Agraph_t *root; 136 Agsubnode_t mainsub; /* embedded for main graph */ 137 }; 138 139 struct 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 146 struct Agedgepair_s { 147 Agedge_t out, in; 148 }; 149 150 struct 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 163 struct 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 171 struct 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 182 struct 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 189 struct Agdisc_s { /* user's discipline */ 190 Agmemdisc_t *mem; 191 Agiddisc_t *id; 192 Agiodisc_t *io; 193 }; 194 195 /* default resource disciplines */ 196 197 CGRAPH_API Agmemdisc_t AgMemDisc; 198 CGRAPH_API Agiddisc_t AgIdDisc; 199 CGRAPH_API Agiodisc_t AgIoDisc; 200 201 CGRAPH_API Agdisc_t AgDefaultDisc; 202 203 struct 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 210 typedef void (*agobjfn_t) (Agraph_t * g, Agobj_t * obj, void *arg); 211 typedef void (*agobjupdfn_t) (Agraph_t * g, Agobj_t * obj, void *arg, 212 Agsym_t * sym); 213 214 struct Agcbdisc_s { 215 struct { 216 agobjfn_t ins; 217 agobjupdfn_t mod; 218 agobjfn_t del; 219 } graph, node, edge; 220 }; 221 222 struct 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 228 struct 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 239 struct 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 251 CGRAPH_API void agpushdisc(Agraph_t * g, Agcbdisc_t * disc, void *state); 252 CGRAPH_API int agpopdisc(Agraph_t * g, Agcbdisc_t * disc); 253 CGRAPH_API int agcallbacks(Agraph_t * g, int flag); /* return prev value */ 254 255 /* graphs */ 256 CGRAPH_API Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t * disc); 257 CGRAPH_API int agclose(Agraph_t * g); 258 CGRAPH_API Agraph_t *agread(void *chan, Agdisc_t * disc); 259 CGRAPH_API Agraph_t *agmemread(const char *cp); 260 CGRAPH_API Agraph_t *agmemconcat(Agraph_t *g, const char *cp); 261 CGRAPH_API void agreadline(int); 262 CGRAPH_API void agsetfile(char *); 263 CGRAPH_API Agraph_t *agconcat(Agraph_t * g, void *chan, Agdisc_t * disc); 264 CGRAPH_API int agwrite(Agraph_t * g, void *chan); 265 CGRAPH_API int agisdirected(Agraph_t * g); 266 CGRAPH_API int agisundirected(Agraph_t * g); 267 CGRAPH_API int agisstrict(Agraph_t * g); 268 CGRAPH_API int agissimple(Agraph_t * g); 269 270 /* nodes */ 271 CGRAPH_API Agnode_t *agnode(Agraph_t * g, char *name, int createflag); 272 CGRAPH_API Agnode_t *agidnode(Agraph_t * g, IDTYPE id, int createflag); 273 CGRAPH_API Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n, int createflag); 274 CGRAPH_API Agnode_t *agfstnode(Agraph_t * g); 275 CGRAPH_API Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n); 276 CGRAPH_API Agnode_t *aglstnode(Agraph_t * g); 277 CGRAPH_API Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n); 278 279 CGRAPH_API Agsubnode_t *agsubrep(Agraph_t * g, Agnode_t * n); 280 CGRAPH_API int agnodebefore(Agnode_t *u, Agnode_t *v); /* we have no shame */ 281 282 /* edges */ 283 CGRAPH_API Agedge_t *agedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, 284 char *name, int createflag); 285 CGRAPH_API Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, 286 IDTYPE id, int createflag); 287 CGRAPH_API Agedge_t *agsubedge(Agraph_t * g, Agedge_t * e, int createflag); 288 CGRAPH_API Agedge_t *agfstin(Agraph_t * g, Agnode_t * n); 289 CGRAPH_API Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e); 290 CGRAPH_API Agedge_t *agfstout(Agraph_t * g, Agnode_t * n); 291 CGRAPH_API Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e); 292 CGRAPH_API Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n); 293 CGRAPH_API Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n); 294 295 /* generic */ 296 CGRAPH_API Agraph_t *agraphof(void* obj); 297 CGRAPH_API Agraph_t *agroot(void* obj); 298 CGRAPH_API int agcontains(Agraph_t *, void *); 299 CGRAPH_API char *agnameof(void *); 300 CGRAPH_API int agrelabel(void *obj, char *name); /* scary */ 301 CGRAPH_API int agrelabel_node(Agnode_t * n, char *newname); 302 CGRAPH_API int agdelete(Agraph_t * g, void *obj); 303 CGRAPH_API long agdelsubg(Agraph_t * g, Agraph_t * sub); /* could be agclose */ 304 CGRAPH_API int agdelnode(Agraph_t * g, Agnode_t * arg_n); 305 CGRAPH_API int agdeledge(Agraph_t * g, Agedge_t * arg_e); 306 CGRAPH_API int agobjkind(void *); 307 308 /* strings */ 309 CGRAPH_API char *agstrdup(Agraph_t *, char *); 310 CGRAPH_API char *agstrdup_html(Agraph_t *, char *); 311 CGRAPH_API int aghtmlstr(char *); 312 CGRAPH_API char *agstrbind(Agraph_t * g, char *); 313 CGRAPH_API int agstrfree(Agraph_t *, char *); 314 CGRAPH_API char *agcanon(char *, int); 315 CGRAPH_API char *agstrcanon(char *, char *); 316 CGRAPH_API char *agcanonStr(char *str); /* manages its own buf */ 317 318 /* definitions for dynamic string attributes */ 319 struct Agattr_s { /* dynamic string attributes */ 320 Agrec_t h; /* common data header */ 321 Dict_t *dict; /* shared dict to interpret attr field */ 322 char **str; /* the attribute string values */ 323 }; 324 325 struct Agsym_s { /* symbol in one of the above dictionaries */ 326 Dtlink_t link; 327 char *name; /* attribute's name */ 328 char *defval; /* its default value for initialization */ 329 int id; /* its index in attr[] */ 330 unsigned char kind; /* referent object type */ 331 unsigned char fixed; /* immutable value */ 332 unsigned char print; /* always print */ 333 }; 334 335 struct Agdatadict_s { /* set of dictionaries per graph */ 336 Agrec_t h; /* installed in list of graph recs */ 337 struct { 338 Dict_t *n, *e, *g; 339 } dict; 340 }; 341 342 CGRAPH_API Agsym_t *agattr(Agraph_t * g, int kind, char *name, char *value); 343 CGRAPH_API Agsym_t *agattrsym(void *obj, char *name); 344 CGRAPH_API Agsym_t *agnxtattr(Agraph_t * g, int kind, Agsym_t * attr); 345 CGRAPH_API int agcopyattr(void *oldobj, void *newobj); 346 347 CGRAPH_API void *agbindrec(void *obj, char *name, unsigned int size, 348 int move_to_front); 349 CGRAPH_API Agrec_t *aggetrec(void *obj, char *name, int move_to_front); 350 CGRAPH_API int agdelrec(void *obj, char *name); 351 CGRAPH_API void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size, 352 int move_to_front); 353 CGRAPH_API void agclean(Agraph_t * g, int kind, char *rec_name); 354 355 CGRAPH_API char *agget(void *obj, char *name); 356 CGRAPH_API char *agxget(void *obj, Agsym_t * sym); 357 CGRAPH_API int agset(void *obj, char *name, char *value); 358 CGRAPH_API int agxset(void *obj, Agsym_t * sym, char *value); 359 CGRAPH_API int agsafeset(void* obj, char* name, char* value, char* def); 360 361 /* defintions for subgraphs */ 362 CGRAPH_API Agraph_t *agsubg(Agraph_t * g, char *name, int cflag); /* constructor */ 363 CGRAPH_API Agraph_t *agidsubg(Agraph_t * g, IDTYPE id, int cflag); /* constructor */ 364 CGRAPH_API Agraph_t *agfstsubg(Agraph_t * g); 365 CGRAPH_API Agraph_t *agnxtsubg(Agraph_t * subg); 366 CGRAPH_API Agraph_t *agparent(Agraph_t * g); 367 368 /* set cardinality */ 369 CGRAPH_API int agnnodes(Agraph_t * g); 370 CGRAPH_API int agnedges(Agraph_t * g); 371 CGRAPH_API int agnsubg(Agraph_t * g); 372 CGRAPH_API int agdegree(Agraph_t * g, Agnode_t * n, int in, int out); 373 CGRAPH_API int agcountuniqedges(Agraph_t * g, Agnode_t * n, int in, int out); 374 375 /* memory */ 376 CGRAPH_API void *agalloc(Agraph_t * g, size_t size); 377 CGRAPH_API void *agrealloc(Agraph_t * g, void *ptr, size_t oldsize, 378 size_t size); 379 CGRAPH_API void agfree(Agraph_t * g, void *ptr); 380 CGRAPH_API struct _vmalloc_s *agheap(Agraph_t * g); 381 382 /* an engineering compromise is a joy forever */ 383 CGRAPH_API void aginternalmapclearlocalnames(Agraph_t * g); 384 385 #define agnew(g,t) ((t*)agalloc(g,sizeof(t))) 386 #define agnnew(g,n,t) ((t*)agalloc(g,(n)*sizeof(t))) 387 388 /* error handling */ 389 typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t; 390 typedef int (*agusererrf) (char*); 391 CGRAPH_API agerrlevel_t agseterr(agerrlevel_t); 392 CGRAPH_API char *aglasterr(void); 393 CGRAPH_API int agerr(agerrlevel_t level, const char *fmt, ...); 394 CGRAPH_API void agerrorf(const char *fmt, ...); 395 CGRAPH_API void agwarningf(const char *fmt, ...); 396 CGRAPH_API int agerrors(void); 397 CGRAPH_API int agreseterrors(void); 398 CGRAPH_API agusererrf agseterrf(agusererrf); 399 400 /* data access macros */ 401 /* this assumes that e[0] is out and e[1] is inedge, see edgepair in edge.c */ 402 #define AGIN2OUT(e) ((e)-1) 403 #define AGOUT2IN(e) ((e)+1) 404 #define AGOPP(e) ((AGTYPE(e)==AGINEDGE)?AGIN2OUT(e):AGOUT2IN(e)) 405 #define AGMKOUT(e) (AGTYPE(e) == AGOUTEDGE? (e): AGIN2OUT(e)) 406 #define AGMKIN(e) (AGTYPE(e) == AGINEDGE? (e): AGOUT2IN(e)) 407 #define AGTAIL(e) (AGMKIN(e)->node) 408 #define AGHEAD(e) (AGMKOUT(e)->node) 409 #define AGEQEDGE(e,f) (AGMKOUT(e) == AGMKOUT(f)) 410 /* These macros are also exposed as functions, so they can be linked against. */ 411 #define agtail(e) AGTAIL(e) 412 #define aghead(e) AGHEAD(e) 413 #define agopp(e) AGOPP(e) 414 #define ageqedge(e,f) AGEQEDGE(e,f) 415 416 #define TAILPORT_ID "tailport" 417 #define HEADPORT_ID "headport" 418 419 CGRAPH_API Agdesc_t Agdirected; 420 CGRAPH_API Agdesc_t Agstrictdirected; 421 CGRAPH_API Agdesc_t Agundirected; 422 CGRAPH_API Agdesc_t Agstrictundirected; 423 424 /* fast graphs */ 425 void agflatten(Agraph_t * g, int flag); 426 typedef Agsubnode_t Agnoderef_t; 427 typedef Dtlink_t Agedgeref_t; 428 429 #define AGHEADPOINTER(g) ((Agnoderef_t*)(g->n_seq->data->hh._head)) 430 #define AGRIGHTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.right?((void*)((rep)->seq_link.right) - offsetof(Agsubnode_t,seq_link)):0)) 431 #define AGLEFTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.hl._left?((void*)((rep)->seq_link.hl._left) - offsetof(Agsubnode_t,seq_link)):0)) 432 433 #define FIRSTNREF(g) (agflatten(g,1), AGHEADPOINTER(g)) 434 435 #define NEXTNREF(g,rep) (AGRIGHTPOINTER(rep) == AGHEADPOINTER(g)?0:AGRIGHTPOINTER(rep)) 436 437 #define PREVNREF(g,rep) (((rep)==AGHEADPOINTER(g))?0:(AGLEFTPOINTER(rep))) 438 439 #define LASTNREF(g) (agflatten(g,1), AGHEADPOINTER(g)?AGLEFTPOINTER(AGHEADPOINTER(g)):0) 440 #define NODEOF(rep) ((rep)->node) 441 442 #define FIRSTOUTREF(g,sn) (agflatten(g,1), (sn)->out_seq) 443 #define LASTOUTREF(g,sn) (agflatten(g,1), (Agedgeref_t*)dtlast(sn->out_seq)) 444 #define FIRSTINREF(g,sn) (agflatten(g,1), (sn)->in_seq) 445 #define NEXTEREF(g,rep) ((rep)->right) 446 #define PREVEREF(g,rep) ((rep)->hl._left) 447 /* this is expedient but a bit slimey because it "knows" that dict entries of both nodes 448 and edges are embedded in main graph objects but allocated separately in subgraphs */ 449 #define AGSNMAIN(sn) ((sn)==(&((sn)->node->mainsub))) 450 #define EDGEOF(sn,rep) (AGSNMAIN(sn)?((Agedge_t*)((unsigned char*)(rep) - offsetof(Agedge_t,seq_link))) : ((Dthold_t*)(rep))->obj) 451 452 #ifdef __cplusplus 453 } 454 #endif 455 #endif 456