granicus.if.org Git - graphviz/blob

1 /*************************************************************************

4 * are made available under the terms of the Eclipse Public License v1.0

5 * which accompanies this distribution, and is available at

6 * http://www.eclipse.org/legal/epl-v10.html

7 *

8 * Contributors: Details at https://graphviz.org

9 *************************************************************************/

10

11 #ifndef ATT_GRAPH_H

12 #define ATT_GRAPH_H

13

14 #include <inttypes.h>

15 #include "cdt.h"

16

17 #ifdef __cplusplus

18 extern "C" {

19 #endif

20

21 #ifdef _WIN32

22 # ifdef EXPORT_CGRAPH

23 # define CGRAPH_API __declspec(dllexport)

24 # else

25 # define CGRAPH_API __declspec(dllimport)

26 # endif

27 #else

28 # define CGRAPH_API /* nothing */

29 #endif

30

31 #ifndef FALSE

32 #define FALSE (0)

33 #endif

34 #ifndef TRUE

35 #define TRUE (!FALSE)

36 #endif

37 #ifndef NOT

38 #define NOT(x) (!(x))

39 #endif

40 #ifndef NIL

41 #define NIL(type) ((type)0)

42 #endif

43 #define NILgraph NIL(Agraph_t*)

44 #define NILnode NIL(Agnode_t*)

45 #define NILedge NIL(Agedge_t*)

46 #define NILsym NIL(Agsym_t*)

47

48 typedef uint64_t IDTYPE;

49

50 /* forward struct type declarations */

51 typedef struct Agtag_s Agtag_t;

52 typedef struct Agobj_s Agobj_t; /* generic object header */

53 typedef struct Agraph_s Agraph_t; /* graph, subgraph (or hyperedge) */

54 typedef struct Agnode_s Agnode_t; /* node (atom) */

55 typedef struct Agedge_s Agedge_t; /* node pair */

56 typedef struct Agdesc_s Agdesc_t; /* graph descriptor */

57 typedef struct Agmemdisc_s Agmemdisc_t; /* memory allocator */

58 typedef struct Agiddisc_s Agiddisc_t; /* object ID allocator */

59 typedef struct Agiodisc_s Agiodisc_t; /* IO services */

60 typedef struct Agdisc_s Agdisc_t; /* union of client discipline methods */

61 typedef struct Agdstate_s Agdstate_t; /* client state (closures) */

62 typedef struct Agsym_s Agsym_t; /* string attribute descriptors */

63 typedef struct Agattr_s Agattr_t; /* string attribute container */

64 typedef struct Agcbdisc_s Agcbdisc_t; /* client event callbacks */

65 typedef struct Agcbstack_s Agcbstack_t; /* enclosing state for cbdisc */

66 typedef struct Agclos_s Agclos_t; /* common fields for graph/subgs */

67 typedef struct Agrec_s Agrec_t; /* generic runtime record */

68 typedef struct Agdatadict_s Agdatadict_t; /* set of dictionaries per graph */

69 typedef struct Agedgepair_s Agedgepair_t; /* the edge object */

70 typedef struct Agsubnode_s Agsubnode_t;

71

72 /* Header of a user record. These records are attached by client programs

73 dynamically at runtime. A unique string ID must be given to each record

74 attached to the same object. Cgraph has functions to create, search for,

75 and delete these records. The records are maintained in a circular list,

76 with obj->data pointing somewhere in the list. The search function has

77 an option to lock this pointer on a given record. The application must

78 be written so only one such lock is outstanding at a time. */

79

80 struct Agrec_s {

81 char *name;

82 Agrec_t *next;

83 /* following this would be any programmer-defined data */

84 };

85

86 /* Object tag for graphs, nodes, and edges. While there may be several structs

87 for a given node or edges, there is only one unique ID (per main graph). */

88 struct Agtag_s {

89 unsigned objtype:2; /* see literal tags below */

90 unsigned mtflock:1; /* move-to-front lock, see above */

91 unsigned attrwf:1; /* attrs written (parity, write.c) */

92 unsigned seq:(sizeof(unsigned) * 8 - 4); /* sequence no. */

93 IDTYPE id; /* client ID */

94 };

95

96 /* object tags */

97 #define AGRAPH 0 /* can't exceed 2 bits. see Agtag_t. */

98 #define AGNODE 1

99 #define AGOUTEDGE 2

100 #define AGINEDGE 3 /* (1 << 1) indicates an edge tag. */

101 #define AGEDGE AGOUTEDGE /* synonym in object kind args */

102

103 /* a generic graph/node/edge header */

104 struct Agobj_s {

105 Agtag_t tag;

106 Agrec_t *data;

107 };

108

109 #define AGTAG(obj) (((Agobj_t*)(obj))->tag)

110 #define AGTYPE(obj) (AGTAG(obj).objtype)

111 #define AGID(obj) (AGTAG(obj).id)

112 #define AGSEQ(obj) (AGTAG(obj).seq)

113 #define AGATTRWF(obj) (AGTAG(obj).attrwf)

114 #define AGDATA(obj) (((Agobj_t*)(obj))->data)

115

116 /* This is the node struct allocated per graph (or subgraph). It resides

117 in the n_dict of the graph. The node set is maintained by libdict, but

118 transparently to libgraph callers. Every node may be given an optional

119 string name at its time of creation, or it is permissible to pass NIL(char*)

120 for the name. */

121

122 struct Agsubnode_s { /* the node-per-graph-or-subgraph record */

123 Dtlink_t seq_link; /* must be first */

124 Dtlink_t id_link;

125 Agnode_t *node; /* the object */

126 Dtlink_t *in_id, *out_id; /* by node/ID for random access */

127 Dtlink_t *in_seq, *out_seq; /* by node/sequence for serial access */

128 };

129

130 struct Agnode_s {

131 Agobj_t base;

132 Agraph_t *root;

133 Agsubnode_t mainsub; /* embedded for main graph */

134 };

135

136 struct Agedge_s {

137 Agobj_t base;

138 Dtlink_t id_link; /* main graph only */

139 Dtlink_t seq_link;

140 Agnode_t *node; /* the endpoint node */

141 };

142

143 struct Agedgepair_s {

144 Agedge_t out, in;

145 };

146

147 struct Agdesc_s { /* graph descriptor */

148 unsigned directed:1; /* if edges are asymmetric */

149 unsigned strict:1; /* if multi-edges forbidden */

150 unsigned no_loop:1; /* if no loops */

151 unsigned maingraph:1; /* if this is the top level graph */

152 unsigned flatlock:1; /* if sets are flattened into lists in cdt */

153 unsigned no_write:1; /* if a temporary subgraph */

154 unsigned has_attrs:1; /* if string attr tables should be initialized */

155 unsigned has_cmpnd:1; /* if may contain collapsed nodes */

156 };

157

158 /* disciplines for external resources needed by libgraph */

159

160 struct Agmemdisc_s { /* memory allocator */

161 void *(*open) (Agdisc_t*); /* independent of other resources */

162 void *(*alloc) (void *state, size_t req);

163 void *(*resize) (void *state, void *ptr, size_t old, size_t req);

164 void (*free) (void *state, void *ptr);

165 void (*close) (void *state);

166 };

167

168 struct Agiddisc_s { /* object ID allocator */

169 void *(*open) (Agraph_t * g, Agdisc_t*); /* associated with a graph */

170 long (*map) (void *state, int objtype, char *str, IDTYPE *id,

171 int createflag);

172 long (*alloc) (void *state, int objtype, IDTYPE id);

173 void (*free) (void *state, int objtype, IDTYPE id);

174 char *(*print) (void *state, int objtype, IDTYPE id);

175 void (*close) (void *state);

176 void (*idregister) (void *state, int objtype, void *obj);

177 };

178

179 struct Agiodisc_s {

180 int (*afread) (void *chan, char *buf, int bufsize);

181 int (*putstr) (void *chan, const char *str);

182 int (*flush) (void *chan); /* sync */

183 /* error messages? */

184 };

185

186 struct Agdisc_s { /* user's discipline */

187 Agmemdisc_t *mem;

188 Agiddisc_t *id;

189 Agiodisc_t *io;

190 };

191

192 /* default resource disciplines */

193

194 CGRAPH_API extern Agmemdisc_t AgMemDisc;

195 CGRAPH_API extern Agiddisc_t AgIdDisc;

196 CGRAPH_API extern Agiodisc_t AgIoDisc;

197

198 CGRAPH_API extern Agdisc_t AgDefaultDisc;

199

200 struct Agdstate_s {

201 void *mem;

202 void *id;

203 /* IO must be initialized and finalized outside Cgraph,

204 * and channels (FILES) are passed as void* arguments. */

205 };

206

207 typedef void (*agobjfn_t) (Agraph_t * g, Agobj_t * obj, void *arg);

208 typedef void (*agobjupdfn_t) (Agraph_t * g, Agobj_t * obj, void *arg,

209 Agsym_t * sym);

210

211 struct Agcbdisc_s {

212 struct {

213 agobjfn_t ins;

214 agobjupdfn_t mod;

215 agobjfn_t del;

216 } graph, node, edge;

217 };

218

219 struct Agcbstack_s { /* object event callbacks */

220 Agcbdisc_t *f; /* methods */

221 void *state; /* closure */

222 Agcbstack_t *prev; /* kept in a stack, unlike other disciplines */

223 };

224

225 struct Agclos_s {

226 Agdisc_t disc; /* resource discipline functions */

227 Agdstate_t state; /* resource closures */

228 Dict_t *strdict; /* shared string dict */

229 uint64_t seq[3]; /* local object sequence number counter */

230 Agcbstack_t *cb; /* user and system callback function stacks */

231 unsigned char callbacks_enabled; /* issue user callbacks or hold them? */

232 Dict_t *lookup_by_name[3];

233 Dict_t *lookup_by_id[3];

234 };

235

236 struct Agraph_s {

237 Agobj_t base;

238 Agdesc_t desc;

239 Dtlink_t link;

240 Dict_t *n_seq; /* the node set in sequence */

241 Dict_t *n_id; /* the node set indexed by ID */

242 Dict_t *e_seq, *e_id; /* holders for edge sets */

243 Dict_t *g_dict; /* subgraphs - descendants */

244 Agraph_t *parent, *root; /* subgraphs - ancestors */

245 Agclos_t *clos; /* shared resources */

246 };

247

248 CGRAPH_API void agpushdisc(Agraph_t * g, Agcbdisc_t * disc, void *state);

249 CGRAPH_API int agpopdisc(Agraph_t * g, Agcbdisc_t * disc);

250 CGRAPH_API int agcallbacks(Agraph_t * g, int flag); /* return prev value */

251

252 /* graphs */

253 CGRAPH_API Agraph_t *agopen(char *name, Agdesc_t desc, Agdisc_t * disc);

254 CGRAPH_API int agclose(Agraph_t * g);

255 CGRAPH_API Agraph_t *agread(void *chan, Agdisc_t * disc);

256 CGRAPH_API Agraph_t *agmemread(const char *cp);

257 CGRAPH_API Agraph_t *agmemconcat(Agraph_t *g, const char *cp);

258 CGRAPH_API void agreadline(int);

259 CGRAPH_API void agsetfile(char *);

260 CGRAPH_API Agraph_t *agconcat(Agraph_t * g, void *chan, Agdisc_t * disc);

261 CGRAPH_API int agwrite(Agraph_t * g, void *chan);

262 CGRAPH_API int agisdirected(Agraph_t * g);

263 CGRAPH_API int agisundirected(Agraph_t * g);

264 CGRAPH_API int agisstrict(Agraph_t * g);

265 CGRAPH_API int agissimple(Agraph_t * g);

266

267 /* nodes */

268 CGRAPH_API Agnode_t *agnode(Agraph_t * g, char *name, int createflag);

269 CGRAPH_API Agnode_t *agidnode(Agraph_t * g, IDTYPE id, int createflag);

270 CGRAPH_API Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n, int createflag);

271 CGRAPH_API Agnode_t *agfstnode(Agraph_t * g);

272 CGRAPH_API Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n);

273 CGRAPH_API Agnode_t *aglstnode(Agraph_t * g);

274 CGRAPH_API Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n);

275

276 CGRAPH_API Agsubnode_t *agsubrep(Agraph_t * g, Agnode_t * n);

277 CGRAPH_API int agnodebefore(Agnode_t *u, Agnode_t *v); /* we have no shame */

278

279 /* edges */

280 CGRAPH_API Agedge_t *agedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,

281 char *name, int createflag);

282 CGRAPH_API Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,

283 IDTYPE id, int createflag);

284 CGRAPH_API Agedge_t *agsubedge(Agraph_t * g, Agedge_t * e, int createflag);

285 CGRAPH_API Agedge_t *agfstin(Agraph_t * g, Agnode_t * n);

286 CGRAPH_API Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e);

287 CGRAPH_API Agedge_t *agfstout(Agraph_t * g, Agnode_t * n);

288 CGRAPH_API Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e);

289 CGRAPH_API Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n);

290 CGRAPH_API Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n);

291

292 /* generic */

293 CGRAPH_API Agraph_t *agraphof(void* obj);

294 CGRAPH_API Agraph_t *agroot(void* obj);

295 CGRAPH_API int agcontains(Agraph_t *, void *);

296 CGRAPH_API char *agnameof(void *);

297 CGRAPH_API int agrelabel(void *obj, char *name); /* scary */

298 CGRAPH_API int agrelabel_node(Agnode_t * n, char *newname);

299 CGRAPH_API int agdelete(Agraph_t * g, void *obj);

300 CGRAPH_API int agdelsubg(Agraph_t * g, Agraph_t * sub); /* could be agclose */

301 CGRAPH_API int agdelnode(Agraph_t * g, Agnode_t * arg_n);

302 CGRAPH_API int agdeledge(Agraph_t * g, Agedge_t * arg_e);

303 CGRAPH_API int agobjkind(void *);

304

305 /* strings */

306 CGRAPH_API char *agstrdup(Agraph_t *, char *);

307 CGRAPH_API char *agstrdup_html(Agraph_t *, char *);

308 CGRAPH_API int aghtmlstr(char *);

309 CGRAPH_API char *agstrbind(Agraph_t * g, char *);

310 CGRAPH_API int agstrfree(Agraph_t *, char *);

311 CGRAPH_API char *agcanon(char *, int);

312 CGRAPH_API char *agstrcanon(char *, char *);

313 CGRAPH_API char *agcanonStr(char *str); /* manages its own buf */

314

315 /* definitions for dynamic string attributes */

316 struct Agattr_s { /* dynamic string attributes */

317 Agrec_t h; /* common data header */

318 Dict_t *dict; /* shared dict to interpret attr field */

319 char **str; /* the attribute string values */

320 };

321

322 struct Agsym_s { /* symbol in one of the above dictionaries */

323 Dtlink_t link;

324 char *name; /* attribute's name */

325 char *defval; /* its default value for initialization */

326 int id; /* its index in attr[] */

327 unsigned char kind; /* referent object type */

328 unsigned char fixed; /* immutable value */

329 unsigned char print; /* always print */

330 };

331

332 struct Agdatadict_s { /* set of dictionaries per graph */

333 Agrec_t h; /* installed in list of graph recs */

334 struct {

335 Dict_t *n, *e, *g;

336 } dict;

337 };

338

339 CGRAPH_API Agsym_t *agattr(Agraph_t * g, int kind, char *name, char *value);

340 CGRAPH_API Agsym_t *agattrsym(void *obj, char *name);

341 CGRAPH_API Agsym_t *agnxtattr(Agraph_t * g, int kind, Agsym_t * attr);

342 CGRAPH_API int agcopyattr(void *oldobj, void *newobj);

343

344 CGRAPH_API void *agbindrec(void *obj, char *name, unsigned int size,

345 int move_to_front);

346 CGRAPH_API Agrec_t *aggetrec(void *obj, char *name, int move_to_front);

347 CGRAPH_API int agdelrec(void *obj, char *name);

348 CGRAPH_API void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size,

349 int move_to_front);

350 CGRAPH_API void agclean(Agraph_t * g, int kind, char *rec_name);

351

352 CGRAPH_API char *agget(void *obj, char *name);

353 CGRAPH_API char *agxget(void *obj, Agsym_t * sym);

354 CGRAPH_API int agset(void *obj, char *name, char *value);

355 CGRAPH_API int agxset(void *obj, Agsym_t * sym, char *value);

356 CGRAPH_API int agsafeset(void* obj, char* name, char* value, char* def);

357

358 /* definitions for subgraphs */

359 CGRAPH_API Agraph_t *agsubg(Agraph_t * g, char *name, int cflag); /* constructor */

360 CGRAPH_API Agraph_t *agidsubg(Agraph_t * g, IDTYPE id, int cflag); /* constructor */

361 CGRAPH_API Agraph_t *agfstsubg(Agraph_t * g);

362 CGRAPH_API Agraph_t *agnxtsubg(Agraph_t * subg);

363 CGRAPH_API Agraph_t *agparent(Agraph_t * g);

364

365 /* set cardinality */

366 CGRAPH_API int agnnodes(Agraph_t * g);

367 CGRAPH_API int agnedges(Agraph_t * g);

368 CGRAPH_API int agnsubg(Agraph_t * g);

369 CGRAPH_API int agdegree(Agraph_t * g, Agnode_t * n, int in, int out);

370 CGRAPH_API int agcountuniqedges(Agraph_t * g, Agnode_t * n, int in, int out);

371

372 /* memory */

373 CGRAPH_API void *agalloc(Agraph_t * g, size_t size);

374 CGRAPH_API void *agrealloc(Agraph_t * g, void *ptr, size_t oldsize,

375 size_t size);

376 CGRAPH_API void agfree(Agraph_t * g, void *ptr);

377

378 /* an engineering compromise is a joy forever */

379 CGRAPH_API void aginternalmapclearlocalnames(Agraph_t * g);

380

381 #define agnew(g,t) ((t*)agalloc(g,sizeof(t)))

382 #define agnnew(g,n,t) ((t*)agalloc(g,(n)*sizeof(t)))

383

384 /* support for extra API misuse warnings if available */

385 #ifdef __GNUC__

386 #define PRINTF_LIKE(index, first) __attribute__((format(printf, index, first)))

387 #else

388 #define PRINTF_LIKE(index, first) /* nothing */

389 #endif

390

391 /* error handling */

392 typedef enum { AGWARN, AGERR, AGMAX, AGPREV } agerrlevel_t;

393 typedef int (*agusererrf) (char*);

394 CGRAPH_API agerrlevel_t agseterr(agerrlevel_t);

395 CGRAPH_API char *aglasterr(void);

396 CGRAPH_API int agerr(agerrlevel_t level, const char *fmt, ...)

397 PRINTF_LIKE(2, 3);

398 CGRAPH_API void agerrorf(const char *fmt, ...) PRINTF_LIKE(1, 2);

399 CGRAPH_API void agwarningf(const char *fmt, ...) PRINTF_LIKE(1, 2);

400 CGRAPH_API int agerrors(void);

401 CGRAPH_API int agreseterrors(void);

402 CGRAPH_API agusererrf agseterrf(agusererrf);

403

404 #undef PRINTF_LIKE

405

406 /* data access macros */

407 /* this assumes that e[0] is out and e[1] is inedge, see edgepair in edge.c */

408 #define AGIN2OUT(e) ((e)-1)

409 #define AGOUT2IN(e) ((e)+1)

410 #define AGOPP(e) ((AGTYPE(e)==AGINEDGE)?AGIN2OUT(e):AGOUT2IN(e))

411 #define AGMKOUT(e) (AGTYPE(e) == AGOUTEDGE? (e): AGIN2OUT(e))

412 #define AGMKIN(e) (AGTYPE(e) == AGINEDGE? (e): AGOUT2IN(e))

413 #define AGTAIL(e) (AGMKIN(e)->node)

414 #define AGHEAD(e) (AGMKOUT(e)->node)

415 #define AGEQEDGE(e,f) (AGMKOUT(e) == AGMKOUT(f))

416 /* These macros are also exposed as functions, so they can be linked against. */

417 #define agtail(e) AGTAIL(e)

418 #define aghead(e) AGHEAD(e)

419 #define agopp(e) AGOPP(e)

420 #define ageqedge(e,f) AGEQEDGE(e,f)

421

422 #define TAILPORT_ID "tailport"

423 #define HEADPORT_ID "headport"

424

425 CGRAPH_API extern Agdesc_t Agdirected;

426 CGRAPH_API extern Agdesc_t Agstrictdirected;

427 CGRAPH_API extern Agdesc_t Agundirected;

428 CGRAPH_API extern Agdesc_t Agstrictundirected;

429

430 /* fast graphs */

431 void agflatten(Agraph_t * g, int flag);

432 typedef Agsubnode_t Agnoderef_t;

433 typedef Dtlink_t Agedgeref_t;

434

435 #define AGHEADPOINTER(g) ((Agnoderef_t*)(g->n_seq->data->hh._head))

436 #define AGRIGHTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.right?((void*)((rep)->seq_link.right) - offsetof(Agsubnode_t,seq_link)):0))

437 #define AGLEFTPOINTER(rep) ((Agnoderef_t*)((rep)->seq_link.hl._left?((void*)((rep)->seq_link.hl._left) - offsetof(Agsubnode_t,seq_link)):0))

438

439 #define FIRSTNREF(g) (agflatten(g,1), AGHEADPOINTER(g))

440

441 #define NEXTNREF(g,rep) (AGRIGHTPOINTER(rep) == AGHEADPOINTER(g)?0:AGRIGHTPOINTER(rep))

442

443 #define PREVNREF(g,rep) (((rep)==AGHEADPOINTER(g))?0:(AGLEFTPOINTER(rep)))

444

445 #define LASTNREF(g) (agflatten(g,1), AGHEADPOINTER(g)?AGLEFTPOINTER(AGHEADPOINTER(g)):0)

446 #define NODEOF(rep) ((rep)->node)

447

448 #define FIRSTOUTREF(g,sn) (agflatten(g,1), (sn)->out_seq)

449 #define LASTOUTREF(g,sn) (agflatten(g,1), (Agedgeref_t*)dtlast(sn->out_seq))

450 #define FIRSTINREF(g,sn) (agflatten(g,1), (sn)->in_seq)

451 #define NEXTEREF(g,rep) ((rep)->right)

452 #define PREVEREF(g,rep) ((rep)->hl._left)

453 /* this is expedient but a bit slimey because it "knows" that dict entries of both nodes

454 and edges are embedded in main graph objects but allocated separately in subgraphs */

455 #define AGSNMAIN(sn) ((sn)==(&((sn)->node->mainsub)))

456 #define EDGEOF(sn,rep) (AGSNMAIN(sn)?((Agedge_t*)((unsigned char*)(rep) - offsetof(Agedge_t,seq_link))) : ((Dthold_t*)(rep))->obj)

457

458 #ifdef __cplusplus

459 }

460 #endif

461 #endif