cdt.h

Go to the documentation of this file.

 
#pragma once
 
#ifdef __cplusplus
extern "C" {
#endif
 
/*      Public interface for the dictionary library
**
**      Written by Kiem-Phong Vo
*/
 
#define CDT_VERSION     20050420L
 
#include <stddef.h>     /* size_t */
#include <string.h>
 
#ifdef GVDLL
#ifdef EXPORT_CDT
#define CDT_API __declspec(dllexport)
#else
#define CDT_API __declspec(dllimport)
#endif
#endif
 
#ifndef CDT_API
#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*                   (*Dtsearch_f)(Dt_t*,void*,int);
typedef void*           (*Dtmake_f)(void*,Dtdisc_t*);
typedef void                    (*Dtfree_f)(void *);
typedef int                     (*Dtcompar_f)(void *,void *);
 
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               */
};
 
/* 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               */
};
 
#define DTDISC(dc, ky, sz, lk, mkf, frf, cmpf) \
        ( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
          (dc)->makef = (mkf), (dc)->freef = (frf), \
          (dc)->comparf = (cmpf) )
 
/* the dictionary structure itself */
struct _dt_s
{       Dtsearch_f      searchf;/* search function                      */
        Dtdisc_t*       disc;   /* method to manipulate objs            */
        Dtdata_t*       data;   /* sharable data                        */
        Dtmethod_t*     meth;   /* dictionary method                    */
        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                   */
        size_t dt_n; // number of chains or levels
        size_t dt_max; // max size of a chain or a level
        size_t* dt_count; // counts of chains or levels by size
};
 
/* supported storage methods */
#define DT_SET          0000001 /* set with unique elements             */
#define DT_OSET         0000004 /* ordered set (self-adjusting tree)    */
#define DT_OBAG         0000010 /* ordered multiset                     */
#define DT_QUEUE        0000100 /* queue: insert at top, delete at tail */
#define DT_METHODS      0000377 /* all currently supported methods      */
 
/* 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_DETACH       0010000 /* detach an object from the dictionary */
 
CDT_API extern Dtmethod_t*      Dtset; 
CDT_API extern Dtmethod_t*      Dtoset; 
CDT_API extern Dtmethod_t*      Dtobag; 
CDT_API extern Dtmethod_t*      Dtqueue; 
 
CDT_API extern Dtmethod_t*      Dttree;
CDT_API extern Dtmethod_t       _Dttree;
CDT_API extern Dtmethod_t       _Dtqueue;
 
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*);
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(*)(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(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(k1, k2, cmpf, sz) \
                        (cmpf ? (cmpf)(k1, k2) : \
                         (sz <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,(size_t)sz)) )
 
#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 dtlast(d)       (*(_DT(d)->searchf))((d),(void*)(0),DT_LAST)
#define dtprev(d,o)     (*(_DT(d)->searchf))((d),(void*)(o),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 dtdelete(d,o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_DELETE)
#define dtdetach(d,o)   (*(_DT(d)->searchf))((d),(void*)(o),DT_DETACH)
#define dtclear(d)      (*(_DT(d)->searchf))((d),(void*)(0),DT_CLEAR)
 
#define DT_PRIME        17109811 /* 2#00000001 00000101 00010011 00110011 */
 
#ifdef __cplusplus
}
#endif