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