Graphviz  2.41.20170921.2350
cdt.h
Go to the documentation of this file.
1 #ifndef _CDT_H
2 #define _CDT_H 1
3 
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7 
8 /* Public interface for the dictionary library
9 **
10 ** Written by Kiem-Phong Vo
11 */
12 
13 #define CDT_VERSION 20050420L
14 
15 #include <stddef.h> /* size_t */
16 #include <string.h>
17 
18 #ifdef _WIN32
19 # ifdef EXPORT_CDT
20 # define CDT_API __declspec(dllexport)
21 # else
22 # define CDT_API __declspec(dllimport)
23 # endif
24 #else
25 # define CDT_API extern
26 #endif
27 
28 typedef struct _dtlink_s Dtlink_t;
29 typedef struct _dthold_s Dthold_t;
30 typedef struct _dtdisc_s Dtdisc_t;
31 typedef struct _dtmethod_s Dtmethod_t;
32 typedef struct _dtdata_s Dtdata_t;
33 typedef struct _dt_s Dt_t;
34 typedef struct _dt_s Dict_t; /* for libdict compatibility */
35 typedef struct _dtstat_s Dtstat_t;
36 typedef void* (*Dtmemory_f)(Dt_t*,void*,size_t,Dtdisc_t*);
37 typedef void* (*Dtsearch_f)(Dt_t*,void*,int);
38 typedef void* (*Dtmake_f)(Dt_t*,void*,Dtdisc_t*);
39 typedef void (*Dtfree_f)(Dt_t*,void*,Dtdisc_t*);
40 typedef int (*Dtcompar_f)(Dt_t*,void*,void*,Dtdisc_t*);
41 typedef unsigned int (*Dthash_f)(Dt_t*,void*,Dtdisc_t*);
42 typedef int (*Dtevent_f)(Dt_t*,int,void*,Dtdisc_t*);
43 
44 struct _dtlink_s
45 { Dtlink_t* right; /* right child */
46  union
47  { unsigned int _hash; /* hash value */
48  Dtlink_t* _left; /* left child */
49  } hl;
50 };
51 
52 /* private structure to hold an object */
53 struct _dthold_s
54 { Dtlink_t hdr; /* header */
55  void* obj; /* user object */
56 };
57 
58 /* method to manipulate dictionary structure */
60 { Dtsearch_f searchf; /* search function */
61  int type; /* type of operation */
62 };
63 
64 /* stuff that may be in shared memory */
65 struct _dtdata_s
66 { int type; /* type of dictionary */
67  Dtlink_t* here; /* finger to last search element */
68  union
69  { Dtlink_t** _htab; /* hash table */
70  Dtlink_t* _head; /* linked list */
71  } hh;
72  int ntab; /* number of hash slots */
73  int size; /* number of objects */
74  int loop; /* number of nested loops */
75  int minp; /* min path before splay, always even */
76  /* for hash dt, > 0: fixed table size */
77 };
78 
79 /* structure to hold methods that manipulate an object */
80 struct _dtdisc_s
81 { int key; /* where the key begins in an object */
82  int size; /* key size and type */
83  int link; /* offset to Dtlink_t field */
84  Dtmake_f makef; /* object constructor */
85  Dtfree_f freef; /* object destructor */
86  Dtcompar_f comparf;/* to compare two objects */
87  Dthash_f hashf; /* to compute hash value of an object */
88  Dtmemory_f memoryf;/* to allocate/free memory */
89  Dtevent_f eventf; /* to process events */
90 };
91 
92 #define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \
93  ( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
94  (dc)->makef = (mkf), (dc)->freef = (frf), \
95  (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \
96  (dc)->memoryf = (memf), (dc)->eventf = (evf) )
97 
98 /* the dictionary structure itself */
99 struct _dt_s
100 { Dtsearch_f searchf;/* search function */
101  Dtdisc_t* disc; /* method to manipulate objs */
102  Dtdata_t* data; /* sharable data */
103  Dtmemory_f memoryf;/* function to alloc/free memory */
104  Dtmethod_t* meth; /* dictionary method */
105  int type; /* type information */
106  int nview; /* number of parent view dictionaries */
107  Dt_t* view; /* next on viewpath */
108  Dt_t* walk; /* dictionary being walked */
109  void* user; /* for user's usage */
110 };
111 
112 /* structure to get status of a dictionary */
113 struct _dtstat_s
114 { int dt_meth; /* method type */
115  int dt_size; /* number of elements */
116  int dt_n; /* number of chains or levels */
117  int dt_max; /* max size of a chain or a level */
118  int* dt_count; /* counts of chains or levels by size */
119 };
120 
121 /* flag set if the last search operation actually found the object */
122 #define DT_FOUND 0100000
123 
124 /* supported storage methods */
125 #define DT_SET 0000001 /* set with unique elements */
126 #define DT_BAG 0000002 /* multiset */
127 #define DT_OSET 0000004 /* ordered set (self-adjusting tree) */
128 #define DT_OBAG 0000010 /* ordered multiset */
129 #define DT_LIST 0000020 /* linked list */
130 #define DT_STACK 0000040 /* stack: insert/delete at top */
131 #define DT_QUEUE 0000100 /* queue: insert at top, delete at tail */
132 #define DT_DEQUE 0000200 /* deque: insert at top, append at tail */
133 #define DT_METHODS 0000377 /* all currently supported methods */
134 
135 /* asserts to dtdisc() */
136 #define DT_SAMECMP 0000001 /* compare methods equivalent */
137 #define DT_SAMEHASH 0000002 /* hash methods equivalent */
138 
139 /* types of search */
140 #define DT_INSERT 0000001 /* insert object if not found */
141 #define DT_DELETE 0000002 /* delete object if found */
142 #define DT_SEARCH 0000004 /* look for an object */
143 #define DT_NEXT 0000010 /* look for next element */
144 #define DT_PREV 0000020 /* find previous element */
145 #define DT_RENEW 0000040 /* renewing an object */
146 #define DT_CLEAR 0000100 /* clearing all objects */
147 #define DT_FIRST 0000200 /* get first object */
148 #define DT_LAST 0000400 /* get last object */
149 #define DT_MATCH 0001000 /* find object matching key */
150 #define DT_VSEARCH 0002000 /* search using internal representation */
151 #define DT_ATTACH 0004000 /* attach an object to the dictionary */
152 #define DT_DETACH 0010000 /* detach an object from the dictionary */
153 #define DT_APPEND 0020000 /* used on Dtlist to append an object */
154 
155 /* events */
156 #define DT_OPEN 1 /* a dictionary is being opened */
157 #define DT_CLOSE 2 /* a dictionary is being closed */
158 #define DT_DISC 3 /* discipline is about to be changed */
159 #define DT_METH 4 /* method is about to be changed */
160 #define DT_ENDOPEN 5 /* dtopen() is done */
161 #define DT_ENDCLOSE 6 /* dtclose() is done */
162 #define DT_HASHSIZE 7 /* setting hash table size */
163 
172 
173 /* compatibility stuff; will go away */
174 #ifndef KPVDEL
183 #endif
184 
186 CDT_API int dtclose(Dt_t*);
187 CDT_API Dt_t* dtview(Dt_t*, Dt_t*);
188 CDT_API Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t*, int);
190 
191 CDT_API Dtlink_t* dtflatten(Dt_t*);
192 CDT_API Dtlink_t* dtextract(Dt_t*);
193 CDT_API int dtrestore(Dt_t*, Dtlink_t*);
194 
195 CDT_API int dtwalk(Dt_t*, int(*)(Dt_t*,void*,void*), void*);
196 
197 CDT_API void* dtrenew(Dt_t*, void*);
198 
199 CDT_API int dtsize(Dt_t*);
200 CDT_API int dtstat(Dt_t*, Dtstat_t*, int);
201 CDT_API unsigned int dtstrhash(unsigned int, void*, int);
202 
203 /* internal functions for translating among holder, object and key */
204 #define _DT(dt) ((Dt_t*)(dt))
205 #define _DTDSC(dc,ky,sz,lk,cmpf) \
206  (ky = dc->key, sz = dc->size, lk = dc->link, cmpf = dc->comparf)
207 #define _DTLNK(o,lk) ((Dtlink_t*)((char*)(o) + lk) )
208 #define _DTOBJ(e,lk) (lk < 0 ? ((Dthold_t*)(e))->obj : (void*)((char*)(e) - lk) )
209 #define _DTKEY(o,ky,sz) (void*)(sz < 0 ? *((char**)((char*)(o)+ky)) : ((char*)(o)+ky))
210 
211 #define _DTCMP(dt,k1,k2,dc,cmpf,sz) \
212  (cmpf ? (*cmpf)(dt,k1,k2,dc) : \
213  (sz <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) )
214 #define _DTHSH(dt,ky,dc,sz) (dc->hashf ? (*dc->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) )
215 
216 /* special search function for tree structure only */
217 #define _DTMTCH(dt,key,action) \
218  do { Dtlink_t* _e; void *_o, *_k, *_key; Dtdisc_t* _dc; \
219  int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
220  _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
221  _key = (key); \
222  for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
223  { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
224  if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
225  break; \
226  } \
227  action (_e ? _o : (void*)0); \
228  } while(0)
229 
230 #define _DTSRCH(dt,obj,action) \
231  do { Dtlink_t* _e; void *_o, *_k, *_key; Dtdisc_t* _dc; \
232  int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
233  _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
234  _key = _DTKEY(obj, _ky, _sz); \
235  for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
236  { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
237  if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
238  break; \
239  } \
240  action (_e ? _o : (void*)0); \
241  } while(0)
242 
243 #define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(void*)(key),action)
244 #define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(void*)(obj),action)
245 
246 #define dtvnext(d) (_DT(d)->view)
247 #define dtvcount(d) (_DT(d)->nview)
248 #define dtvhere(d) (_DT(d)->walk)
249 
250 #define dtlink(d,e) (((Dtlink_t*)(e))->right)
251 #define dtobj(d,e) _DTOBJ((e), _DT(d)->disc->link)
252 #define dtfinger(d) (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(void*)(0))
253 
254 #define dtfirst(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_FIRST)
255 #define dtnext(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_NEXT)
256 #define dtleast(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH|DT_NEXT)
257 #define dtlast(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_LAST)
258 #define dtprev(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_PREV)
259 #define dtmost(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH|DT_PREV)
260 #define dtsearch(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH)
261 #define dtmatch(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_MATCH)
262 #define dtinsert(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT)
263 #define dtappend(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT|DT_APPEND)
264 #define dtdelete(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_DELETE)
265 #define dtattach(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_ATTACH)
266 #define dtdetach(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_DETACH)
267 #define dtclear(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_CLEAR)
268 #define dtfound(d) (_DT(d)->type & DT_FOUND)
269 
270 #define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */
271 #define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
272 
273 #ifdef __cplusplus
274 }
275 #endif
276 
277 #endif /* _CDT_H */
Dtdisc_t * disc
Definition: cdt.h:101
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
Dtcompar_f comparf
Definition: cdt.h:86
CDT_API int dtclose(Dt_t *)
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
Dtsearch_f searchf
Definition: cdt.h:100
int link
Definition: cdt.h:83
int key
Definition: cdt.h:81
int type
Definition: cdt.h:105
CDT_API Dtlink_t * dtextract(Dt_t *)
Dtfree_f freef
Definition: cdt.h:85
Dtlink_t hdr
Definition: cdt.h:54
CDT_API Dtlink_t * dtflatten(Dt_t *)
Definition: dtflatten.c:9
Dtmemory_f memoryf
Definition: cdt.h:88
int type
Definition: cdt.h:61
CDT_API Dtmethod_t * Dtoset
Definition: cdt.h:166
CDT_API unsigned int dtstrhash(unsigned int, void *, int)
CDT_API Dtmethod_t * Dtbag
Definition: cdt.h:165
CDT_API Dt_t * dtview(Dt_t *, Dt_t *)
Dtevent_f eventf
Definition: cdt.h:89
Definition: cdt.h:65
CDT_API Dtmethod_t _Dtqueue
Definition: cdt.h:181
CDT_API Dtmethod_t * Dtstack
Definition: cdt.h:169
CDT_API Dtdisc_t * dtdisc(Dt_t *dt, Dtdisc_t *, int)
Definition: dtdisc.c:22
Definition: cdt.h:80
CDT_API Dtmethod_t _Dtstack
Definition: cdt.h:182
int dt_size
Definition: cdt.h:115
#define CDT_API
Definition: cdt.h:25
CDT_API void * dtrenew(Dt_t *, void *)
CDT_API Dtmethod_t _Dtlist
Definition: cdt.h:180
CDT_API Dtmethod_t * Dtdeque
Definition: cdt.h:171
Dtlink_t ** _htab
Definition: cdt.h:69
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
CDT_API Dtmethod_t * Dtqueue
Definition: cdt.h:170
int dt_n
Definition: cdt.h:116
Definition: cdt.h:53
int dt_max
Definition: cdt.h:117
CDT_API Dtmethod_t * Dtorder
Definition: cdt.h:175
int dt_meth
Definition: cdt.h:114
Dt_t * walk
Definition: cdt.h:108
union _dtdata_s::@1 hh
int size
Definition: cdt.h:73
int
Definition: grammar.c:1264
CDT_API Dtmethod_t _Dthash
Definition: cdt.h:179
CDT_API Dtmethod_t * Dtset
Definition: cdt.h:164
int size
Definition: cdt.h:82
Dthash_f hashf
Definition: cdt.h:87
void *(* Dtmemory_f)(Dt_t *, void *, size_t, Dtdisc_t *)
Definition: cdt.h:36
Dtlink_t * _head
Definition: cdt.h:70
CDT_API Dtmethod_t * dtmethod(Dt_t *, Dtmethod_t *)
Definition: dtmethod.c:8
void * user
Definition: cdt.h:109
CDT_API int dtsize(Dt_t *)
Definition: dtsize.c:12
void *(* Dtsearch_f)(Dt_t *, void *, int)
Definition: cdt.h:37
int * dt_count
Definition: cdt.h:118
Dtsearch_f searchf
Definition: cdt.h:60
CDT_API Dtmethod_t _Dttree
Definition: cdt.h:178
CDT_API Dtmethod_t * Dttree
Definition: cdt.h:176
Definition: cdt.h:113
Dt_t * view
Definition: cdt.h:107
int nview
Definition: cdt.h:106
CDT_API int dtrestore(Dt_t *, Dtlink_t *)
CDT_API int dtwalk(Dt_t *, int(*)(Dt_t *, void *, void *), void *)
Dtlink_t * here
Definition: cdt.h:67
CDT_API Dtmethod_t * Dthash
Definition: cdt.h:177
CDT_API Dtmethod_t * Dtlist
Definition: cdt.h:168
void * obj
Definition: cdt.h:55
Dtmethod_t * meth
Definition: cdt.h:104
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
CDT_API int dtstat(Dt_t *, Dtstat_t *, int)
int ntab
Definition: cdt.h:72
Definition: cdt.h:99
int minp
Definition: cdt.h:75
Dtdata_t * data
Definition: cdt.h:102
int type
Definition: cdt.h:66
int loop
Definition: cdt.h:74
Dtmemory_f memoryf
Definition: cdt.h:103
CDT_API Dtmethod_t * Dtobag
Definition: cdt.h:167
Dtmake_f makef
Definition: cdt.h:84