da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifndef _CDT_H
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _CDT_H 1
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Public interface for the dictionary library
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin**
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define CDT_VERSION 20050420L
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if _PACKAGE_ast
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <ast_std.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <ast_common.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dtlink_s Dtlink_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dthold_s Dthold_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dtdisc_s Dtdisc_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dtmethod_s Dtmethod_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dtdata_s Dtdata_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dt_s Dt_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dt_s Dict_t; /* for libdict compatibility */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct _dtstat_s Dtstat_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Void_t* (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Void_t* (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef void (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef int (*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef unsigned int (*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef Void_t* (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef int (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dtlink_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ Dtlink_t* right; /* right child */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin union
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { unsigned int _hash; /* hash value */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtlink_t* _left; /* left child */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } hl;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* private structure to hold an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dthold_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ Dtlink_t hdr; /* header */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Void_t* obj; /* user object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* method to manipulate dictionary structure */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dtmethod_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ Dtsearch_f searchf; /* search function */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int type; /* type of operation */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* stuff that may be in shared memory */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dtdata_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ int type; /* type of dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtlink_t* here; /* finger to last search element */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin union
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { Dtlink_t** _htab; /* hash table */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtlink_t* _head; /* linked list */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } hh;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int ntab; /* number of hash slots */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int size; /* number of objects */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int loop; /* number of nested loops */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int minp; /* min path before splay, always even */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* for hash dt, > 0: fixed table size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* structure to hold methods that manipulate an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dtdisc_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ int key; /* where the key begins in an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int size; /* key size and type */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int link; /* offset to Dtlink_t field */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmake_f makef; /* object constructor */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtfree_f freef; /* object destructor */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtcompar_f comparf;/* to compare two objects */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dthash_f hashf; /* to compute hash value of an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmemory_f memoryf;/* to allocate/free memory */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtevent_f eventf; /* to process events */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (dc)->makef = (mkf), (dc)->freef = (frf), \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (dc)->memoryf = (memf), (dc)->eventf = (evf) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifdef offsetof
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTOFFSET(struct_s, member) offsetof(struct_s, member)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTOFFSET(struct_s, member) ((int)(&((struct_s*)0)->member))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* the dictionary structure itself */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dt_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ Dtsearch_f searchf;/* search function */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtdisc_t* disc; /* method to manipulate objs */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtdata_t* data; /* sharable data */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmemory_f memoryf;/* function to alloc/free memory */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtmethod_t* meth; /* dictionary method */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int type; /* type information */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int nview; /* number of parent view dictionaries */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dt_t* view; /* next on viewpath */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dt_t* walk; /* dictionary being walked */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Void_t* user; /* for user's usage */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* structure to get status of a dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct _dtstat_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{ int dt_meth; /* method type */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int dt_size; /* number of elements */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int dt_n; /* number of chains or levels */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int dt_max; /* max size of a chain or a level */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int* dt_count; /* counts of chains or levels by size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* flag set if the last search operation actually found the object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_FOUND 0100000
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* supported storage methods */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_SET 0000001 /* set with unique elements */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_BAG 0000002 /* multiset */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_OSET 0000004 /* ordered set (self-adjusting tree) */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_OBAG 0000010 /* ordered multiset */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_LIST 0000020 /* linked list */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_STACK 0000040 /* stack */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_QUEUE 0000100 /* queue */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_METHODS 0000177 /* all currently supported methods */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* asserts to dtdisc() */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_SAMECMP 0000001 /* compare methods equivalent */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_SAMEHASH 0000002 /* hash methods equivalent */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* types of search */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_INSERT 0000001 /* insert object if not found */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_DELETE 0000002 /* delete object if found */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_SEARCH 0000004 /* look for an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_NEXT 0000010 /* look for next element */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_PREV 0000020 /* find previous element */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_RENEW 0000040 /* renewing an object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_CLEAR 0000100 /* clearing all objects */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_FIRST 0000200 /* get first object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_LAST 0000400 /* get last object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_MATCH 0001000 /* find object matching key */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_VSEARCH 0002000 /* search using internal representation */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_ATTACH 0004000 /* attach an object to the dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_DETACH 0010000 /* detach an object from the dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* events */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_OPEN 1 /* a dictionary is being opened */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_CLOSE 2 /* a dictionary is being closed */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_DISC 3 /* discipline is about to be changed */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_METH 4 /* method is about to be changed */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_ENDOPEN 5 /* dtopen() is done */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_ENDCLOSE 6 /* dtclose() is done */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_HASHSIZE 7 /* setting hash table size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin_BEGIN_EXTERNS_ /* public data */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if _BLD_cdt && defined(__EXPORT__)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define extern __EXPORT__
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if !_BLD_cdt && defined(__IMPORT__)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define extern __IMPORT__
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtset;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtbag;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtoset;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtobag;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtlist;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtstack;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtqueue;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* compatibility stuff; will go away */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifndef KPVDEL
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dtorder;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dttree;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* Dthash;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t _Dttree;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t _Dthash;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t _Dtlist;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t _Dtqueue;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t _Dtstack;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#undef extern
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin_END_EXTERNS_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin_BEGIN_EXTERNS_ /* public functions */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if _BLD_cdt && defined(__EXPORT__)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define extern __EXPORT__
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dt_t* dtopen _ARG_((Dtdisc_t*, Dtmethod_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dtclose _ARG_((Dt_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dt_t* dtview _ARG_((Dt_t*, Dt_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtdisc_t* dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtmethod_t* dtmethod _ARG_((Dt_t*, Dtmethod_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtlink_t* dtflatten _ARG_((Dt_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Dtlink_t* dtextract _ARG_((Dt_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dtrestore _ARG_((Dt_t*, Dtlink_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dttreeset _ARG_((Dt_t*, int, int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Void_t* dtrenew _ARG_((Dt_t*, Void_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dtsize _ARG_((Dt_t*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int dtstat _ARG_((Dt_t*, Dtstat_t*, int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern unsigned int dtstrhash _ARG_((unsigned int, Void_t*, int));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if !_PACKAGE_ast
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int memcmp _ARG_((const Void_t*, const Void_t*, size_t));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int strcmp _ARG_((const char*, const char*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#undef extern
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin_END_EXTERNS_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* internal functions for translating among holder, object and key */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DT(dt) ((Dt_t*)(dt))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTDSC(dc,ky,sz,lk,cmpf) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin (ky = (dc)->key, sz = (dc)->size, lk = (dc)->link, cmpf = (dc)->comparf)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTLNK(o,lk) ((Dtlink_t*)((char*)(o) + lk) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTOBJ(e,lk) ((lk) < 0 ? ((Dthold_t*)(e))->obj : (Void_t*)((char*)(e) - (lk)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTKEY(o,ky,sz) (Void_t*)((sz) < 0 ? *((char**)((char*)(o)+(ky))) : ((char*)(o)+(ky)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTCMP(dt,k1,k2,dc,cmpf,sz) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((cmpf) ? (*cmpf)(dt,k1,k2,dc) : \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((sz) <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTHSH(dt,ky,dc,sz) ((dc)->hashf ? (*(dc)->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* special search function for tree structure only */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTMTCH(dt,key,action) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _key = (key); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin action (_e ? _o : (Void_t*)0); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } while(0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _DTSRCH(dt,obj,action) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _key = _DTKEY(obj, _ky, _sz); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break; \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin action (_e ? _o : (Void_t*)0); \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin } while(0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(Void_t*)(key),action)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(Void_t*)(obj),action)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtvnext(d) (_DT(d)->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtvcount(d) (_DT(d)->nview)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtvhere(d) (_DT(d)->walk)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtlink(d,e) (((Dtlink_t*)(e))->right)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtobj(d,e) _DTOBJ((e), _DT(d)->disc->link)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtfinger(d) (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(Void_t*)(0))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtfirst(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtnext(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtleast(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_NEXT)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtlast(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtprev(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtmost(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_PREV)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtsearch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtmatch(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtinsert(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtdelete(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtattach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtdetach(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtclear(d) (*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtfound(d) (_DT(d)->type & DT_FOUND)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif /* _CDT_H */