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