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 20241216L
 
#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 dtdisc_s_ Dtdisc_t;
typedef struct dt_s_ Dt_t;
typedef struct dt_s_ Dict_t; /* for libdict compatibility */
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 */
typedef struct {
  Dtlink_t hdr; /* header               */
  void *obj;    /* user object          */
} Dthold_t;
 
/* method to manipulate dictionary structure */
typedef struct {
  Dtsearch_f searchf; /* search function        */
  int type;           /* type of operation      */
} Dtmethod_t;
 
/* stuff that may be in shared memory */
typedef struct {
  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           */
} Dtdata_t;
 
/* 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;      
  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 */
typedef struct {
  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
} Dtstat_t;
 
/* 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_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 *Dttree;
 
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) : NULL)
 
#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)
 
#ifdef __cplusplus
}
#endif