Graphviz 12.0.1~dev.20240715.2254
Loading...
Searching...
No Matches
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_s
 
struct  _dtmethod_s
 
struct  _dtdata_s
 
struct  _dtdisc_s
 
struct  _dt_s
 
struct  _dtstat_s
 

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_QUEUE   0000100 /* queue: insert at top, delete at tail */
 
#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):(void*)(0))
 
#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)
 
#define DT_PRIME   17109811 /* 2#00000001 00000101 00010011 00110011 */
 

Typedefs

typedef struct _dtlink_s Dtlink_t
 
typedef struct _dthold_s Dthold_t
 
typedef struct _dtdisc_s Dtdisc_t
 
typedef struct _dtmethod_s Dtmethod_t
 
typedef struct _dtdata_s Dtdata_t
 
typedef struct _dt_s Dt_t
 
typedef struct _dt_s Dict_t
 
typedef struct _dtstat_s Dtstat_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_tdtopen (Dtdisc_t *, Dtmethod_t *)
 
CDT_API int dtclose (Dt_t *)
 
CDT_API Dt_tdtview (Dt_t *, Dt_t *)
 
CDT_API Dtdisc_tdtdisc (Dt_t *dt, Dtdisc_t *)
 
CDT_API Dtmethod_tdtmethod (Dt_t *, Dtmethod_t *)
 
CDT_API Dtlink_tdtflatten (Dt_t *)
 
CDT_API Dtlink_tdtextract (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_tDtset
 set with unique elements
 
CDT_API Dtmethod_tDtoset
 ordered set (self-adjusting tree)
 
CDT_API Dtmethod_tDtobag
 ordered multiset
 
CDT_API Dtmethod_tDtqueue
 queue: insert at top, delete at tail
 
CDT_API Dtmethod_tDttree
 
CDT_API Dtmethod_t _Dttree
 
CDT_API Dtmethod_t _Dtqueue
 

Detailed Description

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

man 3 cdt

Definition in file cdt.h.

Macro Definition Documentation

◆ _DT

#define _DT (   dt)    ((Dt_t*)(dt))

Definition at line 172 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)) )
static int cmpf(void *key1, void *key2)
Definition dijkstra.c:81

Definition at line 179 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 173 of file cdt.h.

◆ _DTKEY

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

Definition at line 177 of file cdt.h.

◆ _DTLNK

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

Definition at line 175 of file cdt.h.

◆ _DTOBJ

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

Definition at line 176 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 137 of file cdt.h.

◆ DT_DELETE

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

Definition at line 132 of file cdt.h.

◆ DT_DETACH

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

Definition at line 142 of file cdt.h.

◆ DT_FIRST

#define DT_FIRST   0000200 /* get first object */

Definition at line 138 of file cdt.h.

◆ DT_INSERT

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

Definition at line 131 of file cdt.h.

◆ DT_LAST

#define DT_LAST   0000400 /* get last object */

Definition at line 139 of file cdt.h.

◆ DT_MATCH

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

Definition at line 140 of file cdt.h.

◆ DT_METHODS

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

Definition at line 128 of file cdt.h.

◆ DT_NEXT

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

Definition at line 134 of file cdt.h.

◆ DT_OBAG

#define DT_OBAG   0000010 /* ordered multiset */

Definition at line 126 of file cdt.h.

◆ DT_OSET

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

Definition at line 125 of file cdt.h.

◆ DT_PREV

#define DT_PREV   0000020 /* find previous element */

Definition at line 135 of file cdt.h.

◆ DT_PRIME

#define DT_PRIME   17109811 /* 2#00000001 00000101 00010011 00110011 */

Definition at line 198 of file cdt.h.

◆ DT_QUEUE

#define DT_QUEUE   0000100 /* queue: insert at top, delete at tail */

Definition at line 127 of file cdt.h.

◆ DT_RENEW

#define DT_RENEW   0000040 /* renewing an object */

Definition at line 136 of file cdt.h.

◆ DT_SEARCH

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

Definition at line 133 of file cdt.h.

◆ DT_SET

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

Definition at line 124 of file cdt.h.

◆ DT_VSEARCH

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

Definition at line 141 of file cdt.h.

◆ dtclear

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

Definition at line 196 of file cdt.h.

◆ dtdelete

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

Definition at line 194 of file cdt.h.

◆ dtdetach

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

Definition at line 195 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) )
disc key
Definition exparse.y:214
static void freef(void *ident)

Definition at line 97 of file cdt.h.

◆ dtfinger

#define dtfinger (   d)    (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(void*)(0))

Definition at line 185 of file cdt.h.

◆ dtfirst

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

Definition at line 187 of file cdt.h.

◆ dtinsert

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

Definition at line 193 of file cdt.h.

◆ dtlast

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

Definition at line 189 of file cdt.h.

◆ dtlink

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

Definition at line 183 of file cdt.h.

◆ dtmatch

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

Definition at line 192 of file cdt.h.

◆ dtnext

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

Definition at line 188 of file cdt.h.

◆ dtobj

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

Definition at line 184 of file cdt.h.

◆ dtprev

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

Definition at line 190 of file cdt.h.

◆ dtsearch

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

Definition at line 191 of file cdt.h.

Typedef Documentation

◆ Dict_t

typedef struct _dt_s Dict_t

Definition at line 47 of file cdt.h.

◆ Dt_t

typedef struct _dt_s Dt_t

Definition at line 46 of file cdt.h.

◆ Dtcompar_f

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

Definition at line 52 of file cdt.h.

◆ Dtdata_t

typedef struct _dtdata_s Dtdata_t

Definition at line 45 of file cdt.h.

◆ Dtdisc_t

typedef struct _dtdisc_s Dtdisc_t

Definition at line 43 of file cdt.h.

◆ Dtfree_f

typedef void(* Dtfree_f) (void *)

Definition at line 51 of file cdt.h.

◆ Dthold_t

typedef struct _dthold_s Dthold_t

Definition at line 42 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 50 of file cdt.h.

◆ Dtmethod_t

typedef struct _dtmethod_s Dtmethod_t

Definition at line 44 of file cdt.h.

◆ Dtsearch_f

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

Definition at line 49 of file cdt.h.

◆ Dtstat_t

typedef struct _dtstat_s Dtstat_t

Definition at line 48 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_s::ntab, NULL, _dt_s::nview, _dtmethod_s::searchf, and _dt_s::view.

Referenced by agdtclose(), cleanTbl(), cleanup(), cloneGraph(), closeit(), constrainX(), constrainY(), delGrid(), dot_compoundEdges(), emit_once_reset(), free_attr(), free_attr(), free_edge(), free_edgelist(), free_graph(), free_graph(), free_html_tbl(), free_node(), free_ritem(), freeChanItem(), freeMaze(), freePM(), freePS(), freeRouter(), freeState(), gvusershape_size(), mkAttr(), mkMazeGraph(), mkPoly(), parseHTML(), processClusterEdges(), processTbl(), 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, DT_QUEUE, DT_RENEW, DT_SET, dtflatten(), dtstrhash(), _dtdata_s::here, _dtdisc_s::key, _dtdisc_s::link, _dt_s::meth, _dtdata_s::ntab, NULL, _dtlink_s::right, _dtmethod_s::searchf, _dtdata_s::size, _dtdisc_s::size, _dtdata_s::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_s::here, _dtdata_s::ntab, NULL, _dtdata_s::size, and _dtdata_s::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_QUEUE, DT_SET, _dtdata_s::here, last, _dtdata_s::ntab, NULL, _dtlink_s::right, RROTATE, and _dtdata_s::type.

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

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, DT_FLATTEN, DT_METHODS, DT_OBAG, DT_OSET, DT_QUEUE, DT_RENEW, DT_SET, dtflatten(), dtstrhash(), free(), _dtdata_s::here, _dtdisc_s::key, key, _dtdisc_s::link, _dtdata_s::loop, _dt_s::meth, _dtdata_s::ntab, NULL, _dtlink_s::right, _dtmethod_s::searchf, _dt_s::searchf, _dtdata_s::size, _dtdisc_s::size, _dtmethod_s::type, and _dtdata_s::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, dtdisc(), free(), malloc(), _dt_s::meth, NULL, _dt_s::nview, _dtmethod_s::searchf, _dt_s::searchf, _dtmethod_s::type, _dt_s::user, _dt_s::view, and _dt_s::walk.

Referenced by addChan(), addRow(), agdtopen(), cloneGraph(), constrainX(), constrainY(), emit_once(), exopen(), extractHChans(), extractVChans(), gvusershape_open(), if(), init_edgelist(), initState(), main(), mapSegToTri(), mkClustMap(), mkEdge(), mkGrid(), mkMazeGraph(), mkNode(), mkPoly(), newPM(), newPS(), openIntSet(), parseHTML(), processClusterEdges(), pushAlist(), pushG(), 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, DT_OBAG, DT_OSET, DT_QUEUE, DT_RENEW, dtstrhash(), _dtdata_s::here, HINDEX, _dtdisc_s::key, key, _dtdisc_s::link, _dt_s::meth, _dtdata_s::ntab, NULL, _dtlink_s::right, _dtmethod_s::searchf, _dtdata_s::size, _dtdisc_s::size, _dtdata_s::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_s::here, _dt_s::meth, _dtdata_s::ntab, NULL, _dtlink_s::right, _dtmethod_s::searchf, _dtdata_s::size, _dtdata_s::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, DT_QUEUE, _dtdata_s::here, _dtlink_s::right, _dtdata_s::size, treecount(), _dtdata_s::type, and UNFLATTEN.

Referenced by agclose(), agcopydict(), agnsubg(), appendFLineList(), cnt(), dtclose(), dtstat(), dumpChanG(), eval(), installnode(), irrelevant_subgraph(), mkAttr(), mkText(), 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_s::dt_count, _dtstat_s::dt_max, _dtstat_s::dt_meth, DT_METHODS, _dtstat_s::dt_n, DT_OBAG, DT_OSET, DT_SET, _dtstat_s::dt_size, dthstat(), dtsize(), dttstat(), free(), _dtdata_s::here, malloc(), NULL, _dtdata_s::type, and UNFLATTEN.

Here is the call graph for this function:

◆ dtstrhash()

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

Definition at line 19 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_s::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 exccopen(), and walkGrid().

Here is the caller graph for this function:

Variable Documentation

◆ _Dtqueue

CDT_API Dtmethod_t _Dtqueue
extern

Definition at line 132 of file dtlist.c.

◆ _Dttree

CDT_API Dtmethod_t _Dttree
extern

Definition at line 307 of file dttree.c.

◆ Dtobag

CDT_API Dtmethod_t* Dtobag
extern

Definition at line 305 of file dttree.c.

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

◆ Dtoset

◆ Dtqueue

CDT_API Dtmethod_t* Dtqueue
extern

Definition at line 134 of file dtlist.c.

Referenced by addRow(), mkEdge(), mkNode(), parseHTML(), pushAlist(), and pushG().

◆ 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().