usr/src/lib/libast/i386/include/ast/cdt.h

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 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
  38 typedef struct _dtlink_s        Dtlink_t;
  39 typedef struct _dthold_s        Dthold_t;
  40 typedef struct _dtdisc_s        Dtdisc_t;
  41 typedef struct _dtmethod_s      Dtmethod_t;
  42 typedef struct _dtdata_s        Dtdata_t;
  43 typedef struct _dt_s            Dt_t;
  44 typedef struct _dt_s            Dict_t; /* for libdict compatibility */
  45 typedef struct _dtstat_s        Dtstat_t;
  46 typedef Void_t*                 (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int));
  47 typedef Void_t*                 (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
  48 typedef void                    (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
  49 typedef int                     (*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*));
  50 typedef unsigned int            (*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
  51 typedef Void_t*                 (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*));
  52 typedef int                     (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*));
  53
  54 struct _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 */
  63 struct _dthold_s
  64 {       Dtlink_t        hdr;    /* header               */
  65         Void_t*         obj;    /* user object          */
  66 };
  67
  68 /* method to manipulate dictionary structure */
  69 struct _dtmethod_s
  70 {       Dtsearch_f      searchf; /* search function     */
  71         int             type;   /* type of operation    */
  72 };
  73
  74 /* stuff that may be in shared memory */
  75 struct _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 */
  90 struct _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 */
 115 struct _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 */
 129 struct _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
 186 extern Dtmethod_t*      Dtset;
 187 extern Dtmethod_t*      Dtbag;
 188 extern Dtmethod_t*      Dtoset;
 189 extern Dtmethod_t*      Dtobag;
 190 extern Dtmethod_t*      Dtlist;
 191 extern Dtmethod_t*      Dtstack;
 192 extern Dtmethod_t*      Dtqueue;
 193
 194 /* compatibility stuff; will go away */
 195 #ifndef KPVDEL
 196 extern Dtmethod_t*      Dtorder;
 197 extern Dtmethod_t*      Dttree;
 198 extern Dtmethod_t*      Dthash;
 199 extern Dtmethod_t       _Dttree;
 200 extern Dtmethod_t       _Dthash;
 201 extern Dtmethod_t       _Dtlist;
 202 extern Dtmethod_t       _Dtqueue;
 203 extern 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
 214 extern Dt_t*            dtopen _ARG_((Dtdisc_t*, Dtmethod_t*));
 215 extern int              dtclose _ARG_((Dt_t*));
 216 extern Dt_t*            dtview _ARG_((Dt_t*, Dt_t*));
 217 extern Dtdisc_t*        dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int));
 218 extern Dtmethod_t*      dtmethod _ARG_((Dt_t*, Dtmethod_t*));
 219
 220 extern Dtlink_t*        dtflatten _ARG_((Dt_t*));
 221 extern Dtlink_t*        dtextract _ARG_((Dt_t*));
 222 extern int              dtrestore _ARG_((Dt_t*, Dtlink_t*));
 223
 224 extern int              dttreeset _ARG_((Dt_t*, int, int));
 225
 226 extern int              dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
 227
 228 extern Void_t*          dtrenew _ARG_((Dt_t*, Void_t*));
 229
 230 extern int              dtsize _ARG_((Dt_t*));
 231 extern int              dtstat _ARG_((Dt_t*, Dtstat_t*, int));
 232 extern unsigned int     dtstrhash _ARG_((unsigned int, Void_t*, int));
 233
 234 #if !_PACKAGE_ast
 235 extern int              memcmp _ARG_((const Void_t*, const Void_t*, size_t));
 236 extern 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 */