cdt.h File Reference

container data types API More...

#include <stddef.h>
#include <string.h>

Include dependency graph for cdt.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	dtlink_s_
struct	Dthold_t
struct	Dtmethod_t
struct	Dtdata_t
struct	dtdisc_s_
struct	dt_s_
struct	Dtstat_t

Macros
#define	CDT_VERSION   20050420L
#define	CDT_API   /* nothing */
#define	DTDISC(dc, ky, sz, lk, mkf, frf, cmpf)
#define	DT_SET   0000001 /* set with unique elements */
#define	DT_OSET   0000004 /* ordered set (self-adjusting tree) */
#define	DT_OBAG   0000010 /* ordered multiset */
#define	DT_METHODS   0000377 /* all currently supported methods */
#define	DT_INSERT   0000001 /* insert object if not found */
#define	DT_DELETE   0000002 /* delete object if found */
#define	DT_SEARCH   0000004 /* look for an object */
#define	DT_NEXT   0000010 /* look for next element */
#define	DT_PREV   0000020 /* find previous element */
#define	DT_RENEW   0000040 /* renewing an object */
#define	DT_CLEAR   0000100 /* clearing all objects */
#define	DT_FIRST   0000200 /* get first object */
#define	DT_LAST   0000400 /* get last object */
#define	DT_MATCH   0001000 /* find object matching key */
#define	DT_VSEARCH   0002000 /* search using internal representation */
#define	DT_DETACH   0010000 /* detach an object from the dictionary */
#define	_DT(dt)   ((Dt_t*)(dt))
#define	_DTDSC(dc, ky, sz, lk, cmpf)    (ky = dc->key, sz = dc->size, lk = dc->link, cmpf = dc->comparf)
#define	_DTLNK(o, lk)   ((Dtlink_t*)((char*)(o) + lk) )
#define	_DTOBJ(e, lk)   (lk < 0 ? ((Dthold_t*)(e))->obj : (void*)((char*)(e) - lk) )
#define	_DTKEY(o, ky, sz)   (void*)(sz < 0 ? *((char**)((char*)(o)+ky)) : ((char*)(o)+ky))
#define	_DTCMP(k1, k2, cmpf, sz)
#define	dtlink(d, e)   (((Dtlink_t*)(e))->right)
#define	dtobj(d, e)   _DTOBJ((e), _DT(d)->disc->link)
#define	dtfinger(d)   (_DT(d)->data.here ? dtobj((d), _DT(d)->data.here) : NULL)
#define	dtfirst(d)   (*(_DT(d)->searchf))((d),(void*)(0),DT_FIRST)
#define	dtnext(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_NEXT)
#define	dtlast(d)   (*(_DT(d)->searchf))((d),(void*)(0),DT_LAST)
#define	dtprev(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_PREV)
#define	dtsearch(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH)
#define	dtmatch(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_MATCH)
#define	dtinsert(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT)
#define	dtdelete(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_DELETE)
#define	dtdetach(d, o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_DETACH)
#define	dtclear(d)   (*(_DT(d)->searchf))((d),(void*)(0),DT_CLEAR)

Typedefs
typedef struct dtlink_s_	Dtlink_t
typedef struct dtdisc_s_	Dtdisc_t
typedef struct dt_s_	Dt_t
typedef struct dt_s_	Dict_t
typedef void *(*	Dtsearch_f) (Dt_t *, void *, int)
typedef void *(*	Dtmake_f) (void *, Dtdisc_t *)
typedef void(*	Dtfree_f) (void *)
typedef int(*	Dtcompar_f) (void *, void *)

Functions
CDT_API Dt_t *	dtopen (Dtdisc_t *, Dtmethod_t *)
CDT_API int	dtclose (Dt_t *)
CDT_API Dt_t *	dtview (Dt_t *, Dt_t *)
CDT_API Dtdisc_t *	dtdisc (Dt_t *dt, Dtdisc_t *)
CDT_API Dtmethod_t *	dtmethod (Dt_t *, Dtmethod_t *)
CDT_API Dtlink_t *	dtflatten (Dt_t *)
CDT_API Dtlink_t *	dtextract (Dt_t *)
CDT_API int	dtrestore (Dt_t *, Dtlink_t *)
CDT_API int	dtwalk (Dt_t *, int(*)(void *, void *), void *)
CDT_API void *	dtrenew (Dt_t *, void *)
CDT_API int	dtsize (Dt_t *)
CDT_API int	dtstat (Dt_t *, Dtstat_t *, int)
CDT_API unsigned int	dtstrhash (void *, int)

Variables
CDT_API Dtmethod_t *	Dtset
	set with unique elements
CDT_API Dtmethod_t *	Dtoset
	ordered set (self-adjusting tree)
CDT_API Dtmethod_t *	Dtobag
	ordered multiset
CDT_API Dtmethod_t *	Dttree

Detailed Description

CDT manages run-time dictionaries using standard container data types: unordered set/multiset, ordered set/multiset, list, and stack.

man 3 cdt

Definition in file cdt.h.

Macro Definition Documentation

_DT

#define _DT

(

dt

)

((Dt_t*)(dt))

Definition at line 164 of file cdt.h.

_DTCMP

#define _DTCMP	(		k1,
			k2,
			cmpf,
			sz
	)

Value:

                        (cmpf ? (cmpf)(k1, k2) : \
                         (sz <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,(size_t)sz)) )

Definition at line 171 of file cdt.h.

_DTDSC

#define _DTDSC	(		dc,
			ky,
			sz,
			lk,
			cmpf
	)		(ky = dc->key, sz = dc->size, lk = dc->link, cmpf = dc->comparf)

Definition at line 165 of file cdt.h.

_DTKEY

#define _DTKEY	(		o,
			ky,
			sz
	)		(void*)(sz < 0 ? *((char**)((char*)(o)+ky)) : ((char*)(o)+ky))

Definition at line 169 of file cdt.h.

_DTLNK

#define _DTLNK	(		o,
			lk
	)		((Dtlink_t*)((char*)(o) + lk) )

Definition at line 167 of file cdt.h.

_DTOBJ

#define _DTOBJ	(		e,
			lk
	)		(lk < 0 ? ((Dthold_t*)(e))->obj : (void*)((char*)(e) - lk) )

Definition at line 168 of file cdt.h.

CDT_API

#define CDT_API   /* nothing */

Definition at line 38 of file cdt.h.

CDT_VERSION

#define CDT_VERSION   20050420L

Definition at line 24 of file cdt.h.

DT_CLEAR

#define DT_CLEAR   0000100 /* clearing all objects */

Definition at line 132 of file cdt.h.

DT_DELETE

#define DT_DELETE   0000002 /* delete object if found */

Definition at line 127 of file cdt.h.

DT_DETACH

#define DT_DETACH   0010000 /* detach an object from the dictionary */

Definition at line 137 of file cdt.h.

DT_FIRST

#define DT_FIRST   0000200 /* get first object */

Definition at line 133 of file cdt.h.

DT_INSERT

#define DT_INSERT   0000001 /* insert object if not found */

Definition at line 126 of file cdt.h.

DT_LAST

#define DT_LAST   0000400 /* get last object */

Definition at line 134 of file cdt.h.

DT_MATCH

#define DT_MATCH   0001000 /* find object matching key */

Definition at line 135 of file cdt.h.

DT_METHODS

#define DT_METHODS   0000377 /* all currently supported methods */

Definition at line 123 of file cdt.h.

DT_NEXT

#define DT_NEXT   0000010 /* look for next element */

Definition at line 129 of file cdt.h.

DT_OBAG

#define DT_OBAG   0000010 /* ordered multiset */

Definition at line 122 of file cdt.h.

DT_OSET

#define DT_OSET   0000004 /* ordered set (self-adjusting tree) */

Definition at line 121 of file cdt.h.

DT_PREV

#define DT_PREV   0000020 /* find previous element */

Definition at line 130 of file cdt.h.

DT_RENEW

#define DT_RENEW   0000040 /* renewing an object */

Definition at line 131 of file cdt.h.

DT_SEARCH

#define DT_SEARCH   0000004 /* look for an object */

Definition at line 128 of file cdt.h.

DT_SET

#define DT_SET   0000001 /* set with unique elements */

Definition at line 120 of file cdt.h.

DT_VSEARCH

#define DT_VSEARCH   0002000 /* search using internal representation */

Definition at line 136 of file cdt.h.

dtclear

#define dtclear

(

d

)

(*(_DT(d)->searchf))((d),(void*)(0),DT_CLEAR)

Definition at line 188 of file cdt.h.

dtdelete

#define dtdelete	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_DELETE)

Definition at line 186 of file cdt.h.

dtdetach

#define dtdetach	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_DETACH)

Definition at line 187 of file cdt.h.

DTDISC

#define DTDISC	(		dc,
			ky,
			sz,
			lk,
			mkf,
			frf,
			cmpf
	)

Value:

        ( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
          (dc)->makef = (mkf), (dc)->freef = (frf), \
          (dc)->comparf = (cmpf) )

Definition at line 93 of file cdt.h.

dtfinger

#define dtfinger

(

d

)

(_DT(d)->data.here ? dtobj((d), _DT(d)->data.here) : NULL)

Definition at line 177 of file cdt.h.

dtfirst

#define dtfirst

(

d

)

(*(_DT(d)->searchf))((d),(void*)(0),DT_FIRST)

Definition at line 179 of file cdt.h.

dtinsert

#define dtinsert	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT)

Definition at line 185 of file cdt.h.

dtlast

#define dtlast

(

d

)

(*(_DT(d)->searchf))((d),(void*)(0),DT_LAST)

Definition at line 181 of file cdt.h.

dtlink

#define dtlink	(		d,
			e
	)		(((Dtlink_t*)(e))->right)

Definition at line 175 of file cdt.h.

dtmatch

#define dtmatch	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_MATCH)

Definition at line 184 of file cdt.h.

dtnext

#define dtnext	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_NEXT)

Definition at line 180 of file cdt.h.

dtobj

#define dtobj	(		d,
			e
	)		_DTOBJ((e), _DT(d)->disc->link)

Definition at line 176 of file cdt.h.

dtprev

#define dtprev	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_PREV)

Definition at line 182 of file cdt.h.

dtsearch

#define dtsearch	(		d,
			o
	)		(*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH)

Definition at line 183 of file cdt.h.

Typedef Documentation

Dict_t

typedef struct dt_s_ Dict_t

Definition at line 44 of file cdt.h.

Dt_t

typedef struct dt_s_ Dt_t

Definition at line 43 of file cdt.h.

Dtcompar_f

typedef int(* Dtcompar_f) (void *, void *)

Definition at line 48 of file cdt.h.

Dtdisc_t

typedef struct dtdisc_s_ Dtdisc_t

Definition at line 42 of file cdt.h.

Dtfree_f

typedef void(* Dtfree_f) (void *)

Definition at line 47 of file cdt.h.

Dtlink_t

typedef struct dtlink_s_ Dtlink_t

Definition at line 41 of file cdt.h.

Dtmake_f

typedef void *(* Dtmake_f) (void *, Dtdisc_t *)

Definition at line 46 of file cdt.h.

Dtsearch_f

typedef void *(* Dtsearch_f) (Dt_t *, void *, int)

Definition at line 45 of file cdt.h.

Function Documentation

dtclose()

CDT_API int dtclose

(

Dt_t *

dt

)

Definition at line 8 of file dtclose.c.

References dt_s_::data, DT_CLEAR, dtsize(), dtview(), free(), dt_s_::meth, Dtdata_t::ntab, NULL, dt_s_::nview, Dtmethod_t::searchf, and dt_s_::view.

Referenced by agdtclose(), cloneGraph(), closeit(), constrainX(), constrainY(), delGrid(), dot_compoundEdges(), emit_once_reset(), free_edgelist(), freeChanItem(), freeMaze(), freePM(), freePS(), freeRouter(), freeState(), gvusershape_size(), mkMazeGraph(), mkPoly(), processClusterEdges(), splineEdges(), textfont_dict_close(), write_graph(), and xlinitialize().

Here is the call graph for this function:

Here is the caller graph for this function:

dtdisc()

CDT_API Dtdisc_t * dtdisc	(	Dt_t *	dt,
		Dtdisc_t *	disc
	)

Definition at line 11 of file dtdisc.c.

References _DTKEY, _DTOBJ, dt_s_::data, dt_s_::disc, disc, DT_RENEW, DT_SET, dtflatten(), dtstrhash(), Dtdata_t::here, dtdisc_s_::key, dtdisc_s_::link, dt_s_::meth, Dtdata_t::ntab, NULL, dtlink_s_::right, Dtmethod_t::searchf, Dtdata_t::size, dtdisc_s_::size, Dtdata_t::type, and UNFLATTEN.

Referenced by agdtclose(), agdtdisc(), and dtopen().

Here is the call graph for this function:

Here is the caller graph for this function:

dtextract()

CDT_API Dtlink_t * dtextract

(

Dt_t *

dt

)

Definition at line 9 of file dtextract.c.

References dt_s_::data, DT_OBAG, DT_OSET, DT_SET, dtflatten(), Dtdata_t::here, Dtdata_t::ntab, NULL, Dtdata_t::size, and Dtdata_t::type.

Referenced by agfindedge_by_key(), agfstin(), agfstout(), agnxtin(), agnxtout(), cnt(), del(), and ins().

Here is the call graph for this function:

Here is the caller graph for this function:

dtflatten()

CDT_API Dtlink_t * dtflatten

(

Dt_t *

dt

)

Definition at line 10 of file dtflatten.c.

References dt_s_::data, DT_FLATTEN, DT_SET, Dtdata_t::here, last, Dtdata_t::ntab, NULL, dtlink_s_::right, RROTATE, and Dtdata_t::type.

Referenced by add_np_edges(), add_p_edges(), assignTrackNo(), create_graphs(), dtdisc(), dtextract(), dtmethod(), mkConstraintG(), mkNConstraintG(), and pointsOf().

Here is the caller graph for this function:

dtmethod()

CDT_API Dtmethod_t * dtmethod	(	Dt_t *	dt,
		Dtmethod_t *	meth
	)

Definition at line 9 of file dtmethod.c.

References _DTKEY, _DTOBJ, dt_s_::data, dt_s_::disc, disc, DT_FLATTEN, DT_METHODS, DT_OBAG, DT_OSET, DT_RENEW, DT_SET, dtflatten(), dtstrhash(), free(), Dtdata_t::here, dtdisc_s_::key, dtdisc_s_::link, Dtdata_t::loop, dt_s_::meth, Dtdata_t::ntab, NULL, dtlink_s_::right, Dtmethod_t::searchf, dt_s_::searchf, Dtdata_t::size, dtdisc_s_::size, Dtmethod_t::type, and Dtdata_t::type.

Here is the call graph for this function:

dtopen()

CDT_API Dt_t * dtopen	(	Dtdisc_t *	disc,
		Dtmethod_t *	meth
	)

Definition at line 9 of file dtopen.c.

References dt_s_::data, dt_s_::disc, disc, dtdisc(), malloc(), dt_s_::meth, NULL, dt_s_::nview, Dtmethod_t::searchf, dt_s_::searchf, Dtmethod_t::type, Dtdata_t::type, dt_s_::user, dt_s_::view, and dt_s_::walk.

Referenced by addChan(), agdtopen(), cloneGraph(), constrainX(), constrainY(), emit_once(), exopen(), extractHChans(), extractVChans(), gvusershape_open(), if(), init_edgelist(), initState(), main(), mapSegToTri(), mkClustMap(), mkGrid(), mkMazeGraph(), mkPoly(), newPM(), newPS(), processClusterEdges(), splineEdges(), textfont_dict_open(), user_init(), write_graph(), and xlnew().

Here is the call graph for this function:

Here is the caller graph for this function:

dtrenew()

CDT_API void * dtrenew	(	Dt_t *	dt,
		void *	obj
	)

Definition at line 9 of file dtrenew.c.

References _DTKEY, _DTOBJ, dt_s_::data, dt_s_::disc, disc, DT_OBAG, DT_OSET, DT_RENEW, dtstrhash(), Dtdata_t::here, HINDEX, dtdisc_s_::key, dtdisc_s_::link, dt_s_::meth, Dtdata_t::ntab, NULL, dtlink_s_::right, Dtmethod_t::searchf, Dtdata_t::size, dtdisc_s_::size, Dtdata_t::type, and UNFLATTEN.

Referenced by agnoderenew().

Here is the call graph for this function:

Here is the caller graph for this function:

dtrestore()

CDT_API int dtrestore	(	Dt_t *	dt,
		Dtlink_t *	list
	)

Definition at line 11 of file dtrestore.c.

References dt_s_::data, DT_FLATTEN, DT_OBAG, DT_OSET, DT_RENEW, DT_SET, Dtdata_t::here, dt_s_::meth, Dtdata_t::ntab, NULL, dtlink_s_::right, Dtmethod_t::searchf, Dtdata_t::size, Dtdata_t::type, and type.

Referenced by agfindedge_by_key(), agfstin(), agfstout(), agnxtin(), agnxtout(), cnt(), del(), and ins().

Here is the caller graph for this function:

dtsize()

CDT_API int dtsize

(

Dt_t *

dt

)

Definition at line 12 of file dtsize.c.

References dt_s_::data, DT_OBAG, DT_OSET, Dtdata_t::here, Dtdata_t::size, treecount(), Dtdata_t::type, and UNFLATTEN.

Referenced by agclose(), agcopydict(), agnsubg(), cnt(), dtclose(), dtstat(), eval(), installnode(), irrelevant_subgraph(), pointsOf(), setattr(), sizeOf(), topdictsize(), and xlhdxunload().

Here is the call graph for this function:

Here is the caller graph for this function:

dtstat()

CDT_API int dtstat	(	Dt_t *	dt,
		Dtstat_t *	ds,
		int	all
	)

Definition at line 38 of file dtstat.c.

References dt_s_::data, Dtstat_t::dt_count, Dtstat_t::dt_max, Dtstat_t::dt_meth, DT_METHODS, Dtstat_t::dt_n, DT_OBAG, DT_OSET, DT_SET, Dtstat_t::dt_size, dthstat(), dtsize(), dttstat(), free(), Dtdata_t::here, malloc(), NULL, Dtdata_t::type, and UNFLATTEN.

Here is the call graph for this function:

dtstrhash()

CDT_API unsigned int dtstrhash	(	void *	args,
		int	n
	)

Definition at line 21 of file dtstrhash.c.

References DT_PRIME.

Referenced by dtdisc(), dthash(), dtmethod(), and dtrenew().

Here is the caller graph for this function:

dtview()

CDT_API Dt_t * dtview	(	Dt_t *	dt,
		Dt_t *	view
	)

Definition at line 91 of file dtview.c.

References dtvsearch(), dt_s_::meth, NULL, dt_s_::nview, Dtmethod_t::searchf, dt_s_::searchf, UNFLATTEN, view, dt_s_::view, and dt_s_::walk.

Referenced by aglocaldictsym(), agmakedatadict(), dtclose(), extoken_fn(), if(), if(), write_dict(), and writeDict().

Here is the call graph for this function:

Here is the caller graph for this function:

dtwalk()

CDT_API int dtwalk	(	Dt_t *	dt,
		int(*)(void *, void *)	userf,
		void *	data
	)

Definition at line 9 of file dtwalk.c.

References dtfirst, dtnext, and dt_s_::walk.

Referenced by walkGrid().

Here is the caller graph for this function:

Variable Documentation

Dtobag

CDT_API Dtmethod_t* Dtobag

extern

Definition at line 305 of file dttree.c.

Referenced by constrainX(), constrainY(), and xlnew().

Dtoset

CDT_API Dtmethod_t* Dtoset

extern

Definition at line 304 of file dttree.c.

Referenced by addChan(), cloneGraph(), emit_once(), extractHChans(), extractVChans(), init_edgelist(), initState(), main(), mapSegToTri(), mkClustMap(), mkGrid(), mkMazeGraph(), mkPoly(), newPM(), newPS(), processClusterEdges(), splineEdges(), textfont_dict_open(), user_init(), and write_graph().

Dtset

CDT_API Dtmethod_t* Dtset

extern

Definition at line 277 of file dthash.c.

Referenced by exopen(), and if().

Dttree

CDT_API Dtmethod_t* Dttree

extern

Definition at line 308 of file dttree.c.

Referenced by aginternalmapinsert(), agmakedatadict(), agopen1(), gvusershape_open(), and refdict().