/**
 * @file
 * @brief container data types API
 * @ingroup public_apis
 *
 * **CDT** manages run-time dictionaries using standard container data types:
 * unordered set/multiset, ordered set/multiset, list, and stack.
 *
 * [man 3 cdt](https://graphviz.org/pdf/cdt.3.pdf)
 *
 */

#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;      ///< 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 */
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;  ///< set with unique elements
CDT_API extern Dtmethod_t *Dtoset; ///< ordered set (self-adjusting tree)
CDT_API extern Dtmethod_t *Dtobag; ///< ordered multiset

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)

/**
 * @dir lib/cdt
 * @brief container data types, API cdt.h
 *
 * [man 3 cdt](https://graphviz.org/pdf/cdt.3.pdf)
 *
 */

#ifdef __cplusplus
}
#endif