#pragma once #ifdef __cplusplus extern "C" { #endif /* Public interface for the dictionary library ** ** Written by Kiem-Phong Vo */ #define CDT_VERSION 20050420L #include /* size_t */ #include #ifdef _WIN32 # ifdef EXPORT_CDT # define CDT_API __declspec(dllexport) # else # define CDT_API __declspec(dllimport) # endif #else # define CDT_API /* nothing */ #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; /* for libdict compatibility */ typedef struct _dtstat_s Dtstat_t; typedef void* (*Dtmemory_f)(Dt_t*,void*,size_t,Dtdisc_t*); typedef void* (*Dtsearch_f)(Dt_t*,void*,int); typedef void* (*Dtmake_f)(Dt_t*,void*,Dtdisc_t*); typedef void (*Dtfree_f)(Dt_t*,void*,Dtdisc_t*); typedef int (*Dtcompar_f)(Dt_t*,void*,void*,Dtdisc_t*); typedef unsigned int (*Dthash_f)(Dt_t*,void*,Dtdisc_t*); typedef int (*Dtevent_f)(Dt_t*,int,void*,Dtdisc_t*); struct _dtlink_s { Dtlink_t* right; /* right child */ union { unsigned int _hash; /* hash value */ Dtlink_t* _left; /* left child */ } hl; }; /* private structure to hold an object */ struct _dthold_s { Dtlink_t hdr; /* header */ void* obj; /* user object */ }; /* method to manipulate dictionary structure */ struct _dtmethod_s { Dtsearch_f searchf; /* search function */ int type; /* type of operation */ }; /* stuff that may be in shared memory */ struct _dtdata_s { int type; /* type of dictionary */ Dtlink_t* here; /* finger to last search element */ union { Dtlink_t** _htab; /* hash table */ Dtlink_t* _head; /* linked list */ } hh; int ntab; /* number of hash slots */ int size; /* number of objects */ int loop; /* number of nested loops */ int minp; /* min path before splay, always even */ /* for hash dt, > 0: fixed table size */ }; /* structure to hold methods that manipulate an object */ struct _dtdisc_s { int key; /* where the key begins in an object */ int size; /* key size and type */ int link; /* offset to Dtlink_t field */ Dtmake_f makef; /* object constructor */ Dtfree_f freef; /* object destructor */ Dtcompar_f comparf;/* to compare two objects */ Dthash_f hashf; /* to compute hash value of an object */ Dtmemory_f memoryf;/* to allocate/free memory */ Dtevent_f eventf; /* to process events */ }; #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) ) /* the dictionary structure itself */ struct _dt_s { Dtsearch_f searchf;/* search function */ Dtdisc_t* disc; /* method to manipulate objs */ Dtdata_t* data; /* sharable data */ Dtmemory_f memoryf;/* function to alloc/free memory */ Dtmethod_t* meth; /* dictionary method */ int type; /* type information */ int nview; /* number of parent view dictionaries */ Dt_t* view; /* next on viewpath */ Dt_t* walk; /* dictionary being walked */ void* user; /* for user's usage */ }; /* structure to get status of a dictionary */ struct _dtstat_s { int dt_meth; /* method type */ int dt_size; /* number of elements */ int dt_n; /* number of chains or levels */ int dt_max; /* max size of a chain or a level */ int* dt_count; /* counts of chains or levels by size */ }; /* flag set if the last search operation actually found the object */ #define DT_FOUND 0100000 /* supported storage methods */ #define DT_SET 0000001 /* set with unique elements */ #define DT_BAG 0000002 /* multiset */ #define DT_OSET 0000004 /* ordered set (self-adjusting tree) */ #define DT_OBAG 0000010 /* ordered multiset */ #define DT_LIST 0000020 /* linked list */ #define DT_STACK 0000040 /* stack: insert/delete at top */ #define DT_QUEUE 0000100 /* queue: insert at top, delete at tail */ #define DT_DEQUE 0000200 /* deque: insert at top, append at tail */ #define DT_METHODS 0000377 /* all currently supported methods */ /* asserts to dtdisc() */ #define DT_SAMECMP 0000001 /* compare methods equivalent */ #define DT_SAMEHASH 0000002 /* hash methods equivalent */ /* types of search */ #define DT_INSERT 0000001 /* insert object if not found */ #define DT_DELETE 0000002 /* delete object if found */ #define DT_SEARCH 0000004 /* look for an object */ #define DT_NEXT 0000010 /* look for next element */ #define DT_PREV 0000020 /* find previous element */ #define DT_RENEW 0000040 /* renewing an object */ #define DT_CLEAR 0000100 /* clearing all objects */ #define DT_FIRST 0000200 /* get first object */ #define DT_LAST 0000400 /* get last object */ #define DT_MATCH 0001000 /* find object matching key */ #define DT_VSEARCH 0002000 /* search using internal representation */ #define DT_ATTACH 0004000 /* attach an object to the dictionary */ #define DT_DETACH 0010000 /* detach an object from the dictionary */ #define DT_APPEND 0020000 /* used on Dtlist to append an object */ /* events */ #define DT_OPEN 1 /* a dictionary is being opened */ #define DT_CLOSE 2 /* a dictionary is being closed */ #define DT_DISC 3 /* discipline is about to be changed */ #define DT_METH 4 /* method is about to be changed */ #define DT_ENDOPEN 5 /* dtopen() is done */ #define DT_ENDCLOSE 6 /* dtclose() is done */ #define DT_HASHSIZE 7 /* setting hash table size */ CDT_API extern Dtmethod_t* Dtset; CDT_API extern Dtmethod_t* Dtbag; CDT_API extern Dtmethod_t* Dtoset; CDT_API extern Dtmethod_t* Dtobag; CDT_API extern Dtmethod_t* Dtlist; CDT_API extern Dtmethod_t* Dtstack; CDT_API extern Dtmethod_t* Dtqueue; CDT_API extern Dtmethod_t* Dtdeque; CDT_API extern Dtmethod_t* Dtorder; CDT_API extern Dtmethod_t* Dttree; CDT_API extern Dtmethod_t* Dthash; CDT_API extern Dtmethod_t _Dttree; CDT_API extern Dtmethod_t _Dthash; CDT_API extern Dtmethod_t _Dtlist; CDT_API extern Dtmethod_t _Dtqueue; CDT_API extern Dtmethod_t _Dtstack; CDT_API Dt_t* dtopen(Dtdisc_t*, Dtmethod_t*); CDT_API int dtclose(Dt_t*); CDT_API Dt_t* dtview(Dt_t*, Dt_t*); CDT_API Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t*, int); CDT_API Dtmethod_t* dtmethod(Dt_t*, Dtmethod_t*); CDT_API Dtlink_t* dtflatten(Dt_t*); CDT_API Dtlink_t* dtextract(Dt_t*); CDT_API int dtrestore(Dt_t*, Dtlink_t*); CDT_API int dtwalk(Dt_t*, int(*)(Dt_t*,void*,void*), void*); CDT_API void* dtrenew(Dt_t*, void*); CDT_API int dtsize(Dt_t*); CDT_API int dtstat(Dt_t*, Dtstat_t*, int); CDT_API unsigned int dtstrhash(unsigned int, void*, int); /* internal functions for translating among holder, object and key */ #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*)((char*)(e) - lk) ) #define _DTKEY(o,ky,sz) (void*)(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,(size_t)sz)) ) #define _DTHSH(dt,ky,dc,sz) (dc->hashf ? (*dc->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) ) /* special search function for tree structure only */ #define _DTMTCH(dt,key,action) \ do { Dtlink_t* _e; void *_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*)0); \ } while(0) #define _DTSRCH(dt,obj,action) \ do { Dtlink_t* _e; void *_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*)0); \ } while(0) #define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(void*)(key),action) #define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(void*)(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*)(0)) #define dtfirst(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_FIRST) #define dtnext(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_NEXT) #define dtleast(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH|DT_NEXT) #define dtlast(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_LAST) #define dtprev(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_PREV) #define dtmost(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH|DT_PREV) #define dtsearch(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_SEARCH) #define dtmatch(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_MATCH) #define dtinsert(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT) #define dtappend(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_INSERT|DT_APPEND) #define dtdelete(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_DELETE) #define dtattach(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_ATTACH) #define dtdetach(d,o) (*(_DT(d)->searchf))((d),(void*)(o),DT_DETACH) #define dtclear(d) (*(_DT(d)->searchf))((d),(void*)(0),DT_CLEAR) #define dtfound(d) (_DT(d)->type & DT_FOUND) #define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */ #define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME ) #ifdef __cplusplus } #endif