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