#ifndef _CDT_H
#define _CDT_H 1
#define CDT_VERSION 20050420L
#if _PACKAGE_ast
#include <ast_std.h>
#else
#include <ast_common.h>
#endif
typedef struct _dtlink_s Dtlink_t;
typedef struct _dthold_s Dthold_t;
typedef struct _dtdisc_s Dtdisc_t;
typedef struct _dtmethod_s Dtmethod_t;
typedef struct _dtdata_s Dtdata_t;
typedef struct _dt_s Dt_t;
typedef struct _dt_s Dict_t;
typedef struct _dtstat_s Dtstat_t;
typedef Void_t* (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int));
typedef Void_t* (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
typedef void (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
typedef int (*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*));
typedef unsigned int (*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
typedef Void_t* (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*));
typedef int (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*));
struct _dtlink_s
{ Dtlink_t* right;
union
{ unsigned int _hash;
Dtlink_t* _left;
} hl;
};
struct _dthold_s
{ Dtlink_t hdr;
Void_t* obj;
};
struct _dtmethod_s
{ Dtsearch_f searchf;
int type;
};
struct _dtdata_s
{ int type;
Dtlink_t* here;
union
{ Dtlink_t** _htab;
Dtlink_t* _head;
} hh;
int ntab;
int size;
int loop;
int minp;
};
struct _dtdisc_s
{ int key;
int size;
int link;
Dtmake_f makef;
Dtfree_f freef;
Dtcompar_f comparf;
Dthash_f hashf;
Dtmemory_f memoryf;
Dtevent_f eventf;
};
#define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \
( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
(dc)->makef = (mkf), (dc)->freef = (frf), \
(dc)->comparf = (cmpf), (dc)->hashf = (hshf), \
(dc)->memoryf = (memf), (dc)->eventf = (evf) )
#ifdef offsetof
#define DTOFFSET(struct_s, member) offsetof(struct_s, member)
#else
#define DTOFFSET(struct_s, member) ((int)(&((struct_s*)0)->member))
#endif
struct _dt_s
{ Dtsearch_f searchf;
Dtdisc_t* disc;
Dtdata_t* data;
Dtmemory_f memoryf;
Dtmethod_t* meth;
int type;
int nview;
Dt_t* view;
Dt_t* walk;
Void_t* user;
};
struct _dtstat_s
{ int dt_meth;
int dt_size;
int dt_n;
int dt_max;
int* dt_count;
};
#define DT_FOUND 0100000
#define DT_SET 0000001
#define DT_BAG 0000002
#define DT_OSET 0000004
#define DT_OBAG 0000010
#define DT_LIST 0000020
#define DT_STACK 0000040
#define DT_QUEUE 0000100
#define DT_METHODS 0000177
#define DT_SAMECMP 0000001
#define DT_SAMEHASH 0000002
#define DT_INSERT 0000001
#define DT_DELETE 0000002
#define DT_SEARCH 0000004
#define DT_NEXT 0000010
#define DT_PREV 0000020
#define DT_RENEW 0000040
#define DT_CLEAR 0000100
#define DT_FIRST 0000200
#define DT_LAST 0000400
#define DT_MATCH 0001000
#define DT_VSEARCH 0002000
#define DT_ATTACH 0004000
#define DT_DETACH 0010000
#define DT_OPEN 1
#define DT_CLOSE 2
#define DT_DISC 3
#define DT_METH 4
#define DT_ENDOPEN 5
#define DT_ENDCLOSE 6
#define DT_HASHSIZE 7
_BEGIN_EXTERNS_
#if _BLD_cdt && defined(__EXPORT__)
#define extern __EXPORT__
#endif
#if !_BLD_cdt && defined(__IMPORT__)
#define extern __IMPORT__
#endif
extern Dtmethod_t* Dtset;
extern Dtmethod_t* Dtbag;
extern Dtmethod_t* Dtoset;
extern Dtmethod_t* Dtobag;
extern Dtmethod_t* Dtlist;
extern Dtmethod_t* Dtstack;
extern Dtmethod_t* Dtqueue;
#ifndef KPVDEL
extern Dtmethod_t* Dtorder;
extern Dtmethod_t* Dttree;
extern Dtmethod_t* Dthash;
extern Dtmethod_t _Dttree;
extern Dtmethod_t _Dthash;
extern Dtmethod_t _Dtlist;
extern Dtmethod_t _Dtqueue;
extern Dtmethod_t _Dtstack;
#endif
#undef extern
_END_EXTERNS_
_BEGIN_EXTERNS_
#if _BLD_cdt && defined(__EXPORT__)
#define extern __EXPORT__
#endif
extern Dt_t* dtopen _ARG_((Dtdisc_t*, Dtmethod_t*));
extern int dtclose _ARG_((Dt_t*));
extern Dt_t* dtview _ARG_((Dt_t*, Dt_t*));
extern Dtdisc_t* dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int));
extern Dtmethod_t* dtmethod _ARG_((Dt_t*, Dtmethod_t*));
extern Dtlink_t* dtflatten _ARG_((Dt_t*));
extern Dtlink_t* dtextract _ARG_((Dt_t*));
extern int dtrestore _ARG_((Dt_t*, Dtlink_t*));
extern int dttreeset _ARG_((Dt_t*, int, int));
extern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
extern Void_t* dtrenew _ARG_((Dt_t*, Void_t*));
extern int dtsize _ARG_((Dt_t*));
extern int dtstat _ARG_((Dt_t*, Dtstat_t*, int));
extern unsigned int dtstrhash _ARG_((unsigned int, Void_t*, int));
#if !_PACKAGE_ast
extern int memcmp _ARG_((const Void_t*, const Void_t*, size_t));
extern int strcmp _ARG_((const char*, const char*));
#endif
#undef extern
_END_EXTERNS_
#define _DT(dt) ((Dt_t*)(dt))
#define _DTDSC(dc,ky,sz,lk,cmpf) \
(ky = (dc)->key, sz = (dc)->size, lk = (dc)->link, cmpf = (dc)->comparf)
#define _DTLNK(o,lk) ((Dtlink_t*)((char*)(o) + lk) )
#define _DTOBJ(e,lk) ((lk) < 0 ? ((Dthold_t*)(e))->obj : (Void_t*)((char*)(e) - (lk)) )
#define _DTKEY(o,ky,sz) (Void_t*)((sz) < 0 ? *((char**)((char*)(o)+(ky))) : ((char*)(o)+(ky)))
#define _DTCMP(dt,k1,k2,dc,cmpf,sz) \
((cmpf) ? (*cmpf)(dt,k1,k2,dc) : \
((sz) <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) )
#define _DTHSH(dt,ky,dc,sz) ((dc)->hashf ? (*(dc)->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) )
#define _DTMTCH(dt,key,action) \
do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
_dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
_key = (key); \
for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
{ _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
break; \
} \
action (_e ? _o : (Void_t*)0); \
} while(0)
#define _DTSRCH(dt,obj,action) \
do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
_dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
_key = _DTKEY(obj, _ky, _sz); \
for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
{ _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
break; \
} \
action (_e ? _o : (Void_t*)0); \
} while(0)
#define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(Void_t*)(key),action)
#define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(Void_t*)(obj),action)
#define dtvnext(d) (_DT(d)->view)
#define dtvcount(d) (_DT(d)->nview)
#define dtvhere(d) (_DT(d)->walk)
#define dtlink(d,e) (((Dtlink_t*)(e))->right)
#define dtobj(d,e) _DTOBJ((e), _DT(d)->disc->link)
#define dtfinger(d) (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(Void_t*)(0))
#define dtfirst(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST)
#define dtnext(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT)
#define dtleast(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_NEXT)
#define dtlast(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST)
#define dtprev(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV)
#define dtmost(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_PREV)
#define dtsearch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH)
#define dtmatch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH)
#define dtinsert(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT)
#define dtdelete(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
#define dtattach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH)
#define dtdetach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH)
#define dtclear(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR)
#define dtfound(d) (_DT(d)->type & DT_FOUND)
#define DT_PRIME 17109811
#define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
#endif