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