1 /* 2 * BEGIN illumos section 3 * This is an unstable interface; changes may be made 4 * without notice. 5 * END illumos section 6 */ 7 /*********************************************************************** 8 * * 9 * This software is part of the ast package * 10 * Copyright (c) 1985-2011 AT&T Intellectual Property * 11 * and is licensed under the * 12 * Eclipse Public License, Version 1.0 * 13 * by AT&T Intellectual Property * 14 * * 15 * A copy of the License is available at * 16 * http://www.eclipse.org/org/documents/epl-v10.html * 17 * (with md5 checksum b35adb5213ca9657e911e9befb180842) * 18 * * 19 * Information and Software Systems Research * 20 * AT&T Research * 21 * Florham Park NJ * 22 * * 23 * Glenn Fowler <gsf@research.att.com> * 24 * David Korn <dgk@research.att.com> * 25 * Phong Vo <kpv@research.att.com> * 26 * * 27 ***********************************************************************/ 28 #ifndef _CDT_H 29 #define _CDT_H 1 30 31 /* Public interface for the dictionary library 32 ** 33 ** Written by Kiem-Phong Vo 34 */ 35 36 #ifndef CDT_VERSION 37 #ifdef _API_ast 38 #define CDT_VERSION _API_ast 39 #else 40 #define CDT_VERSION 20111111L 41 #endif /*_AST_api*/ 42 #endif /*CDT_VERSION*/ 43 #ifndef AST_PLUGIN_VERSION 44 #define AST_PLUGIN_VERSION(v) (v) 45 #endif 46 #define CDT_PLUGIN_VERSION AST_PLUGIN_VERSION(20111111L) 47 48 #if _PACKAGE_ast 49 #include <ast_std.h> 50 #else 51 #include <ast_common.h> 52 #include <string.h> 53 #endif 54 55 /* commonly used integers */ 56 #define DT_ZERO ((unsigned int)0) /* all zero bits */ 57 #define DT_ONES (~DT_ZERO) /* all one bits */ 58 #define DT_HIBIT (~(DT_ONES >> 1) ) /* highest 1 bit */ 59 #define DT_LOBIT ((unsigned int)1) /* lowest 1 bit */ 60 #define DT_NBITS (sizeof(unsigned int)*8) /* #bits */ 61 62 /* type of an integer with the same size as a pointer */ 63 #define Dtuint_t uintptr_t 64 65 /* various types used by CDT */ 66 typedef struct _dtlink_s Dtlink_t; 67 typedef struct _dthold_s Dthold_t; 68 typedef struct _dtdisc_s Dtdisc_t; 69 typedef struct _dtmethod_s Dtmethod_t; 70 typedef struct _dtdata_s Dtdata_t; 71 typedef struct _dtuser_s Dtuser_t; 72 typedef struct _dt_s Dt_t; 73 typedef struct _dtstat_s Dtstat_t; 74 typedef Void_t* (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int)); 75 typedef Void_t* (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 76 typedef void (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 77 typedef int (*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*)); 78 typedef unsigned int (*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 79 typedef Void_t* (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*)); 80 typedef int (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*)); 81 typedef int (*Dttype_f)_ARG_((Dt_t*,int)); 82 83 struct _dtuser_s /* for application to access and use */ 84 { unsigned int lock; /* used by dtapplock */ 85 Void_t* data; /* for whatever data */ 86 }; 87 88 struct _dtlink_s 89 { 90 #if CDT_VERSION < 20111111L 91 Dtlink_t* right; /* right child */ 92 union 93 { unsigned int _hash; /* hash value */ 94 Dtlink_t* _left; /* left child */ 95 } hl; 96 #else 97 union 98 { Dtlink_t* __rght; /* right child or next */ 99 Dtlink_t* __ptbl; /* Dtrehash parent tbl */ 100 } rh; 101 union 102 { Dtlink_t* __left; /* left child or prev */ 103 unsigned int __hash; /* hash value of object */ 104 } lh; 105 #endif 106 }; 107 108 /* private structure to hold an object */ 109 struct _dthold_s 110 { Dtlink_t hdr; /* header to hold obj */ 111 Void_t* obj; /* application object */ 112 }; 113 114 /* method to manipulate dictionary structure */ 115 struct _dtmethod_s 116 { Dtsearch_f searchf; /* search function */ 117 unsigned int type; /* type of operation */ 118 int (*eventf)_ARG_((Dt_t*, int, Void_t*)); 119 char* name; /* name of method */ 120 char* description; /* description */ 121 }; 122 123 /* structure to hold methods that manipulate an object */ 124 struct _dtdisc_s 125 { int key; /* where the key resides */ 126 int size; /* key size and type */ 127 int link; /* offset to Dtlink_t field */ 128 Dtmake_f makef; /* object constructor */ 129 Dtfree_f freef; /* object destructor */ 130 Dtcompar_f comparf;/* to compare two objects */ 131 Dthash_f hashf; /* to compute hash value */ 132 Dtmemory_f memoryf;/* to allocate/free memory */ 133 Dtevent_f eventf; /* to process events */ 134 }; 135 136 #define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \ 137 ( (dc)->key = (int)(ky), (dc)->size = (int)(sz), (dc)->link = (int)(lk), \ 138 (dc)->makef = (mkf), (dc)->freef = (frf), \ 139 (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \ 140 (dc)->memoryf = (memf), (dc)->eventf = (evf) ) 141 142 #ifdef offsetof 143 #define DTOFFSET(struct_s, member) offsetof(struct_s, member) 144 #else 145 #define DTOFFSET(struct_s, member) ((int)(&((struct_s*)0)->member)) 146 #endif 147 148 /* the dictionary structure itself */ 149 struct _dt_s 150 { Dtsearch_f searchf;/* search function */ 151 Dtdisc_t* disc; /* object type definitition */ 152 Dtdata_t* data; /* sharable data */ 153 Dtmemory_f memoryf;/* for memory allocation */ 154 Dtmethod_t* meth; /* storage method */ 155 ssize_t nview; /* #parent view dictionaries */ 156 Dt_t* view; /* next on viewpath */ 157 Dt_t* walk; /* dictionary being walked */ 158 Dtuser_t* user; /* for user's usage */ 159 Dttype_f typef; /* for binary compatibility */ 160 }; 161 162 /* structure to get status of a dictionary */ 163 #define DT_MAXRECURSE 1024 /* limit to avoid stack overflow */ 164 #define DT_MAXSIZE 256 /* limit for size of below arrays */ 165 struct _dtstat_s 166 { unsigned int meth; /* method type */ 167 ssize_t size; /* total # of elements in dictionary */ 168 ssize_t space; /* memory usage of data structure */ 169 ssize_t mlev; /* max #levels in tree or hash table */ 170 ssize_t msize; /* max #defined elts in below arrays */ 171 ssize_t lsize[DT_MAXSIZE]; /* #objects by level */ 172 ssize_t tsize[DT_MAXSIZE]; /* #tables by level */ 173 }; 174 175 /* supported storage methods */ 176 #define DT_SET 0000000001 /* unordered set, unique elements */ 177 #define DT_BAG 0000000002 /* unordered set, repeated elements */ 178 #define DT_OSET 0000000004 /* ordered set */ 179 #define DT_OBAG 0000000010 /* ordered multiset */ 180 #define DT_LIST 0000000020 /* linked list */ 181 #define DT_STACK 0000000040 /* stack: insert/delete at top */ 182 #define DT_QUEUE 0000000100 /* queue: insert top, delete at tail */ 183 #define DT_DEQUE 0000000200 /* deque: insert top, append at tail */ 184 #define DT_RHSET 0000000400 /* rhset: sharable unique objects */ 185 #define DT_RHBAG 0000001000 /* rhbag: sharable repeated objects */ 186 #define DT_METHODS 0000001777 /* all currently supported methods */ 187 #define DT_ORDERED (DT_OSET|DT_OBAG) 188 189 /* asserts to dtdisc() to improve performance when changing disciplines */ 190 #define DT_SAMECMP 0000000001 /* compare functions are equivalent */ 191 #define DT_SAMEHASH 0000000002 /* hash functions are equivalent */ 192 193 /* operation types */ 194 #define DT_INSERT 0000000001 /* insert object if not found */ 195 #define DT_DELETE 0000000002 /* delete a matching object if any */ 196 #define DT_SEARCH 0000000004 /* look for an object */ 197 #define DT_NEXT 0000000010 /* look for next element */ 198 #define DT_PREV 0000000020 /* find previous element */ 199 #define DT_FIRST 0000000200 /* get first object */ 200 #define DT_LAST 0000000400 /* get last object */ 201 #define DT_MATCH 0000001000 /* find object matching key */ 202 #define DT_ATTACH 0000004000 /* attach an object to dictionary */ 203 #define DT_DETACH 0000010000 /* detach an object from dictionary */ 204 #define DT_APPEND 0000020000 /* append an object */ 205 #define DT_ATLEAST 0000040000 /* find the least elt >= object */ 206 #define DT_ATMOST 0000100000 /* find the biggest elt <= object */ 207 #define DT_REMOVE 0002000000 /* remove a specific object */ 208 #define DT_TOANNOUNCE (DT_INSERT|DT_DELETE|DT_SEARCH|DT_NEXT|DT_PREV|DT_FIRST|DT_LAST|DT_MATCH|DT_ATTACH|DT_DETACH|DT_APPEND|DT_ATLEAST|DT_ATMOST|DT_REMOVE) 209 210 #define DT_RELINK 0000002000 /* re-inserting (dtdisc,dtmethod...) */ 211 #define DT_FLATTEN 0000000040 /* flatten objects into a list */ 212 #define DT_CLEAR 0000000100 /* clearing all objects */ 213 #define DT_EXTRACT 0000200000 /* FLATTEN and clear dictionary */ 214 #define DT_RESTORE 0000400000 /* reinsert a list of elements */ 215 #define DT_STAT 0001000000 /* get statistics of dictionary */ 216 #define DT_OPERATIONS (DT_TOANNOUNCE|DT_RELINK|DT_FLATTEN|DT_CLEAR|DT_EXTRACT|DT_RESTORE|DT_STAT) 217 218 /* these bits may combine with the DT_METHODS and DT_OPERATIONS bits */ 219 #define DT_INDATA 0010000000 /* Dt_t was allocated with Dtdata_t */ 220 #define DT_SHARE 0020000000 /* concurrent access mode */ 221 #define DT_ANNOUNCE 0040000000 /* announcing a successful operation */ 222 /* the actual event will be this bit */ 223 /* combined with the operation bit */ 224 #define DT_OPTIMIZE 0100000000 /* optimizing data structure */ 225 226 /* events for discipline and method event-handling functions */ 227 #define DT_OPEN 1 /* a dictionary is being opened */ 228 #define DT_ENDOPEN 5 /* end of dictionary opening */ 229 #define DT_CLOSE 2 /* a dictionary is being closed */ 230 #define DT_ENDCLOSE 6 /* end of dictionary closing */ 231 #define DT_DISC 3 /* discipline is about to be changed */ 232 #define DT_METH 4 /* method is about to be changed */ 233 #define DT_HASHSIZE 7 /* initialize hash table size */ 234 #define DT_ERROR 0xbad /* announcing an error */ 235 236 _BEGIN_EXTERNS_ /* data structures and functions */ 237 #if _BLD_cdt && defined(__EXPORT__) 238 #define extern __EXPORT__ 239 #endif 240 #if !_BLD_cdt && defined(__IMPORT__) 241 #define extern __IMPORT__ 242 #endif 243 244 extern Dtmethod_t* Dtset; 245 extern Dtmethod_t* Dtbag; 246 extern Dtmethod_t* Dtoset; 247 extern Dtmethod_t* Dtobag; 248 extern Dtmethod_t* Dtlist; 249 extern Dtmethod_t* Dtstack; 250 extern Dtmethod_t* Dtqueue; 251 extern Dtmethod_t* Dtdeque; 252 253 #if _PACKAGE_ast /* dtplugin() for proprietary and non-standard methods -- requires -ldll */ 254 255 #define dtplugin(name) ((Dtmethod_t*)dllmeth("cdt", name, CDT_PLUGIN_VERSION)) 256 257 #define Dtrhbag dtplugin("rehash:Dtrhbag") 258 #define Dtrhset dtplugin("rehash:Dtrhset") 259 260 #else 261 262 #if CDTPROPRIETARY 263 264 extern Dtmethod_t* Dtrhset; 265 extern Dtmethod_t* Dtrhbag; 266 267 #endif /*CDTPROPRIETARY*/ 268 269 #endif /*_PACKAGE_ast*/ 270 271 #undef extern 272 273 #if _BLD_cdt && defined(__EXPORT__) 274 #define extern __EXPORT__ 275 #endif 276 277 extern Dt_t* dtopen _ARG_((Dtdisc_t*, Dtmethod_t*)); 278 extern int dtclose _ARG_((Dt_t*)); 279 extern Dt_t* dtview _ARG_((Dt_t*, Dt_t*)); 280 extern Dtdisc_t* dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int)); 281 extern Dtmethod_t* dtmethod _ARG_((Dt_t*, Dtmethod_t*)); 282 extern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*)); 283 extern int dtcustomize _ARG_((Dt_t*, int, int)); 284 extern unsigned int dtstrhash _ARG_((unsigned int, Void_t*, ssize_t)); 285 extern int dtuserlock _ARG_((Dt_t*, unsigned int, int)); 286 extern Void_t* dtuserdata _ARG_((Dt_t*, Void_t*, unsigned int)); 287 288 /* deal with upward binary compatibility (operation bit translation, etc.) */ 289 extern Dt_t* _dtopen _ARG_((Dtdisc_t*, Dtmethod_t*, unsigned long)); 290 #define dtopen(dc,mt) _dtopen((dc), (mt), CDT_VERSION) 291 292 #undef extern 293 294 #if _PACKAGE_ast && !defined(_CDTLIB_H) 295 296 #if _BLD_dll && defined(__EXPORT__) 297 #define extern __EXPORT__ 298 #endif 299 300 extern void* dllmeth(const char*, const char*, unsigned long); 301 302 #undef extern 303 304 #endif 305 306 _END_EXTERNS_ 307 308 /* internal functions for translating among holder, object and key */ 309 #define _DT(dt) ((Dt_t*)(dt)) 310 311 #define _DTLNK(dc,o) ((Dtlink_t*)((char*)(o) + (dc)->link) ) /* get link from obj */ 312 313 #define _DTO(dc,l) (Void_t*)((char*)(l) - (dc)->link) /* get object from link */ 314 #define _DTOBJ(dc,l) ((dc)->link >= 0 ? _DTO(dc,l) : ((Dthold_t*)(l))->obj ) 315 316 #define _DTK(dc,o) ((char*)(o) + (dc)->key) /* get key from object */ 317 #define _DTKEY(dc,o) (Void_t*)((dc)->size >= 0 ? _DTK(dc,o) : *((char**)_DTK(dc,o)) ) 318 319 #define _DTCMP(dt,k1,k2,dc) \ 320 ((dc)->comparf ? (*(dc)->comparf)((dt), (k1), (k2), (dc)) : \ 321 (dc)->size > 0 ? memcmp((Void_t*)(k1), ((Void_t*)k2), (dc)->size) : \ 322 strcmp((char*)(k1), ((char*)k2)) ) 323 324 #define _DTHSH(dt,ky,dc) ((dc)->hashf ? (*(dc)->hashf)((dt), (ky), (dc)) : \ 325 dtstrhash(0, (ky), (dc)->size) ) 326 327 #define dtvnext(d) (_DT(d)->view) 328 #define dtvcount(d) (_DT(d)->nview) 329 #define dtvhere(d) (_DT(d)->walk) 330 331 #define dtlink(d,e) (((Dtlink_t*)(e))->rh.__rght) 332 #define dtobj(d,e) _DTOBJ(_DT(d)->disc, (e)) 333 334 #define dtfirst(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST) 335 #define dtnext(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT) 336 #define dtatleast(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATLEAST) 337 #define dtlast(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST) 338 #define dtprev(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV) 339 #define dtatmost(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATMOST) 340 #define dtsearch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH) 341 #define dtmatch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH) 342 #define dtinsert(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT) 343 #define dtappend(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_APPEND) 344 #define dtdelete(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE) 345 #define dtremove(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_REMOVE) 346 #define dtattach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH) 347 #define dtdetach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH) 348 #define dtclear(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR) 349 350 #define dtflatten(d) (Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FLATTEN) 351 #define dtextract(d) (Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_EXTRACT) 352 #define dtrestore(d,l) (Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(l),DT_RESTORE) 353 354 #define dtstat(d,s) (ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(s),DT_STAT) 355 #define dtsize(d) (ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_STAT) 356 357 #define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */ 358 #define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME ) 359 360 #endif /* _CDT_H */ 361