|
Graphviz
2.31.20130524.0447
|
00001 #ifndef _CDT_H 00002 #define _CDT_H 1 00003 00004 /* Public interface for the dictionary library 00005 ** 00006 ** Written by Kiem-Phong Vo 00007 */ 00008 00009 #define CDT_VERSION 20050420L 00010 00011 #ifndef Void_t 00012 #define Void_t void 00013 #endif 00014 00015 #ifndef _ARG_ 00016 #define _ARG_(x) x 00017 #endif 00018 00019 #include <stddef.h> /* size_t */ 00020 00021 #ifndef _BEGIN_EXTERNS_ 00022 #define _BEGIN_EXTERNS_ 00023 #endif 00024 #ifndef _END_EXTERNS_ 00025 #define _END_EXTERNS_ 00026 #endif 00027 00028 #ifdef WIN32 00029 #define __EXPORT__ __declspec (dllexport) 00030 #define __IMPORT__ __declspec (dllimport) 00031 #endif 00032 00033 00034 #if !_DLL_BLD && _dll_import 00035 #define __EXTERN__(T,obj) extern T obj; T* _imp__ ## obj = &obj 00036 #define __DEFINE__(T,obj,val) T obj = val; T* _imp__ ## obj = &obj 00037 #else 00038 #define __EXTERN__(T,obj) extern T obj 00039 #define __DEFINE__(T,obj,val) T obj = val 00040 #endif 00041 00042 typedef struct _dtlink_s Dtlink_t; 00043 typedef struct _dthold_s Dthold_t; 00044 typedef struct _dtdisc_s Dtdisc_t; 00045 typedef struct _dtmethod_s Dtmethod_t; 00046 typedef struct _dtdata_s Dtdata_t; 00047 typedef struct _dt_s Dt_t; 00048 typedef struct _dt_s Dict_t; /* for libdict compatibility */ 00049 typedef struct _dtstat_s Dtstat_t; 00050 typedef Void_t* (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*)); 00051 typedef Void_t* (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int)); 00052 typedef Void_t* (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 00053 typedef void (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 00054 typedef int (*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*)); 00055 typedef unsigned int (*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 00056 typedef int (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*)); 00057 00058 struct _dtlink_s 00059 { Dtlink_t* right; /* right child */ 00060 union 00061 { unsigned int _hash; /* hash value */ 00062 Dtlink_t* _left; /* left child */ 00063 } hl; 00064 }; 00065 00066 /* private structure to hold an object */ 00067 struct _dthold_s 00068 { Dtlink_t hdr; /* header */ 00069 Void_t* obj; /* user object */ 00070 }; 00071 00072 /* method to manipulate dictionary structure */ 00073 struct _dtmethod_s 00074 { Dtsearch_f searchf; /* search function */ 00075 int type; /* type of operation */ 00076 }; 00077 00078 /* stuff that may be in shared memory */ 00079 struct _dtdata_s 00080 { int type; /* type of dictionary */ 00081 Dtlink_t* here; /* finger to last search element */ 00082 union 00083 { Dtlink_t** _htab; /* hash table */ 00084 Dtlink_t* _head; /* linked list */ 00085 } hh; 00086 int ntab; /* number of hash slots */ 00087 int size; /* number of objects */ 00088 int loop; /* number of nested loops */ 00089 int minp; /* min path before splay, always even */ 00090 /* for hash dt, > 0: fixed table size */ 00091 }; 00092 00093 /* structure to hold methods that manipulate an object */ 00094 struct _dtdisc_s 00095 { int key; /* where the key begins in an object */ 00096 int size; /* key size and type */ 00097 int link; /* offset to Dtlink_t field */ 00098 Dtmake_f makef; /* object constructor */ 00099 Dtfree_f freef; /* object destructor */ 00100 Dtcompar_f comparf;/* to compare two objects */ 00101 Dthash_f hashf; /* to compute hash value of an object */ 00102 Dtmemory_f memoryf;/* to allocate/free memory */ 00103 Dtevent_f eventf; /* to process events */ 00104 }; 00105 00106 #define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \ 00107 ( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \ 00108 (dc)->makef = (mkf), (dc)->freef = (frf), \ 00109 (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \ 00110 (dc)->memoryf = (memf), (dc)->eventf = (evf) ) 00111 00112 #ifdef offsetof 00113 #define DTOFFSET(struct_s, member) offsetof(struct_s, member) 00114 #else 00115 #define DTOFFSET(struct_s, member) ((int)(&((struct_s*)0)->member)) 00116 #endif 00117 00118 /* the dictionary structure itself */ 00119 struct _dt_s 00120 { Dtsearch_f searchf;/* search function */ 00121 Dtdisc_t* disc; /* method to manipulate objs */ 00122 Dtdata_t* data; /* sharable data */ 00123 Dtmemory_f memoryf;/* function to alloc/free memory */ 00124 Dtmethod_t* meth; /* dictionary method */ 00125 int type; /* type information */ 00126 int nview; /* number of parent view dictionaries */ 00127 Dt_t* view; /* next on viewpath */ 00128 Dt_t* walk; /* dictionary being walked */ 00129 Void_t* user; /* for user's usage */ 00130 }; 00131 00132 /* structure to get status of a dictionary */ 00133 struct _dtstat_s 00134 { int dt_meth; /* method type */ 00135 int dt_size; /* number of elements */ 00136 int dt_n; /* number of chains or levels */ 00137 int dt_max; /* max size of a chain or a level */ 00138 int* dt_count; /* counts of chains or levels by size */ 00139 }; 00140 00141 /* flag set if the last search operation actually found the object */ 00142 #define DT_FOUND 0100000 00143 00144 /* supported storage methods */ 00145 #define DT_SET 0000001 /* set with unique elements */ 00146 #define DT_BAG 0000002 /* multiset */ 00147 #define DT_OSET 0000004 /* ordered set (self-adjusting tree) */ 00148 #define DT_OBAG 0000010 /* ordered multiset */ 00149 #define DT_LIST 0000020 /* linked list */ 00150 #define DT_STACK 0000040 /* stack: insert/delete at top */ 00151 #define DT_QUEUE 0000100 /* queue: insert at top, delete at tail */ 00152 #define DT_DEQUE 0000200 /* deque: insert at top, append at tail */ 00153 #define DT_METHODS 0000377 /* all currently supported methods */ 00154 00155 /* asserts to dtdisc() */ 00156 #define DT_SAMECMP 0000001 /* compare methods equivalent */ 00157 #define DT_SAMEHASH 0000002 /* hash methods equivalent */ 00158 00159 /* types of search */ 00160 #define DT_INSERT 0000001 /* insert object if not found */ 00161 #define DT_DELETE 0000002 /* delete object if found */ 00162 #define DT_SEARCH 0000004 /* look for an object */ 00163 #define DT_NEXT 0000010 /* look for next element */ 00164 #define DT_PREV 0000020 /* find previous element */ 00165 #define DT_RENEW 0000040 /* renewing an object */ 00166 #define DT_CLEAR 0000100 /* clearing all objects */ 00167 #define DT_FIRST 0000200 /* get first object */ 00168 #define DT_LAST 0000400 /* get last object */ 00169 #define DT_MATCH 0001000 /* find object matching key */ 00170 #define DT_VSEARCH 0002000 /* search using internal representation */ 00171 #define DT_ATTACH 0004000 /* attach an object to the dictionary */ 00172 #define DT_DETACH 0010000 /* detach an object from the dictionary */ 00173 #define DT_APPEND 0020000 /* used on Dtlist to append an object */ 00174 00175 /* events */ 00176 #define DT_OPEN 1 /* a dictionary is being opened */ 00177 #define DT_CLOSE 2 /* a dictionary is being closed */ 00178 #define DT_DISC 3 /* discipline is about to be changed */ 00179 #define DT_METH 4 /* method is about to be changed */ 00180 #define DT_ENDOPEN 5 /* dtopen() is done */ 00181 #define DT_ENDCLOSE 6 /* dtclose() is done */ 00182 #define DT_HASHSIZE 7 /* setting hash table size */ 00183 00184 _BEGIN_EXTERNS_ /* public data */ 00185 #if _BLD_cdt && defined(__EXPORT__) 00186 #define extern __EXPORT__ 00187 #endif 00188 #if !_BLD_cdt && defined(__IMPORT__) 00189 #define extern __IMPORT__ 00190 #endif 00191 00192 extern Dtmethod_t* Dtset; 00193 extern Dtmethod_t* Dtbag; 00194 extern Dtmethod_t* Dtoset; 00195 extern Dtmethod_t* Dtobag; 00196 extern Dtmethod_t* Dtlist; 00197 extern Dtmethod_t* Dtstack; 00198 extern Dtmethod_t* Dtqueue; 00199 extern Dtmethod_t* Dtdeque; 00200 00201 /* compatibility stuff; will go away */ 00202 #ifndef KPVDEL 00203 extern Dtmethod_t* Dtorder; 00204 extern Dtmethod_t* Dttree; 00205 extern Dtmethod_t* Dthash; 00206 extern Dtmethod_t _Dttree; 00207 extern Dtmethod_t _Dthash; 00208 extern Dtmethod_t _Dtlist; 00209 extern Dtmethod_t _Dtqueue; 00210 extern Dtmethod_t _Dtstack; 00211 #endif 00212 00213 #undef extern 00214 _END_EXTERNS_ 00215 00216 _BEGIN_EXTERNS_ /* public functions */ 00217 #if _BLD_cdt && defined(__EXPORT__) 00218 #define extern __EXPORT__ 00219 #endif 00220 00221 extern Dt_t* dtopen _ARG_((Dtdisc_t*, Dtmethod_t*)); 00222 extern int dtclose _ARG_((Dt_t*)); 00223 extern Dt_t* dtview _ARG_((Dt_t*, Dt_t*)); 00224 extern Dtdisc_t* dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int)); 00225 extern Dtmethod_t* dtmethod _ARG_((Dt_t*, Dtmethod_t*)); 00226 00227 extern Dtlink_t* dtflatten _ARG_((Dt_t*)); 00228 extern Dtlink_t* dtextract _ARG_((Dt_t*)); 00229 extern int dtrestore _ARG_((Dt_t*, Dtlink_t*)); 00230 00231 extern int dttreeset _ARG_((Dt_t*, int, int)); 00232 00233 extern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*)); 00234 00235 extern Void_t* dtrenew _ARG_((Dt_t*, Void_t*)); 00236 00237 extern int dtsize _ARG_((Dt_t*)); 00238 extern int dtstat _ARG_((Dt_t*, Dtstat_t*, int)); 00239 extern unsigned int dtstrhash _ARG_((unsigned int, Void_t*, int)); 00240 00241 #if !_PACKAGE_ast 00242 extern int memcmp _ARG_((const Void_t*, const Void_t*, size_t)); 00243 extern int strcmp _ARG_((const char*, const char*)); 00244 #endif 00245 00246 #undef extern 00247 _END_EXTERNS_ 00248 00249 /* internal functions for translating among holder, object and key */ 00250 #define _DT(dt) ((Dt_t*)(dt)) 00251 #define _DTDSC(dc,ky,sz,lk,cmpf) \ 00252 (ky = dc->key, sz = dc->size, lk = dc->link, cmpf = dc->comparf) 00253 #define _DTLNK(o,lk) ((Dtlink_t*)((char*)(o) + lk) ) 00254 #define _DTOBJ(e,lk) (lk < 0 ? ((Dthold_t*)(e))->obj : (Void_t*)((char*)(e) - lk) ) 00255 #define _DTKEY(o,ky,sz) (Void_t*)(sz < 0 ? *((char**)((char*)(o)+ky)) : ((char*)(o)+ky)) 00256 00257 #define _DTCMP(dt,k1,k2,dc,cmpf,sz) \ 00258 (cmpf ? (*cmpf)(dt,k1,k2,dc) : \ 00259 (sz <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) ) 00260 #define _DTHSH(dt,ky,dc,sz) (dc->hashf ? (*dc->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) ) 00261 00262 /* special search function for tree structure only */ 00263 #define _DTMTCH(dt,key,action) \ 00264 do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \ 00265 int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \ 00266 _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \ 00267 _key = (key); \ 00268 for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \ 00269 { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \ 00270 if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \ 00271 break; \ 00272 } \ 00273 action (_e ? _o : (Void_t*)0); \ 00274 } while(0) 00275 00276 #define _DTSRCH(dt,obj,action) \ 00277 do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \ 00278 int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \ 00279 _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \ 00280 _key = _DTKEY(obj, _ky, _sz); \ 00281 for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \ 00282 { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \ 00283 if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \ 00284 break; \ 00285 } \ 00286 action (_e ? _o : (Void_t*)0); \ 00287 } while(0) 00288 00289 #define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(Void_t*)(key),action) 00290 #define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(Void_t*)(obj),action) 00291 00292 #define dtvnext(d) (_DT(d)->view) 00293 #define dtvcount(d) (_DT(d)->nview) 00294 #define dtvhere(d) (_DT(d)->walk) 00295 00296 #define dtlink(d,e) (((Dtlink_t*)(e))->right) 00297 #define dtobj(d,e) _DTOBJ((e), _DT(d)->disc->link) 00298 #define dtfinger(d) (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(Void_t*)(0)) 00299 00300 #define dtfirst(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST) 00301 #define dtnext(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT) 00302 #define dtleast(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_NEXT) 00303 #define dtlast(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST) 00304 #define dtprev(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV) 00305 #define dtmost(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_PREV) 00306 #define dtsearch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH) 00307 #define dtmatch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH) 00308 #define dtinsert(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT) 00309 #define dtappend(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT|DT_APPEND) 00310 #define dtdelete(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE) 00311 #define dtattach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH) 00312 #define dtdetach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH) 00313 #define dtclear(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR) 00314 #define dtfound(d) (_DT(d)->type & DT_FOUND) 00315 00316 #define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */ 00317 #define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME ) 00318 00319 #endif /* _CDT_H */
1.7.5