wolffd@0: /* $Id: cdt.h,v 1.11 2009/07/24 21:10:19 arif Exp $ $Revision: 1.11 $ */
wolffd@0: /* vim:set shiftwidth=4 ts=8: */
wolffd@0: 
wolffd@0: /**********************************************************
wolffd@0: *      This software is part of the graphviz package      *
wolffd@0: *                http://www.graphviz.org/                 *
wolffd@0: *                                                         *
wolffd@0: *            Copyright (c) 1994-2004 AT&T Corp.           *
wolffd@0: *                and is licensed under the                *
wolffd@0: *            Common Public License, Version 1.0           *
wolffd@0: *                      by AT&T Corp.                      *
wolffd@0: *                                                         *
wolffd@0: *        Information and Software Systems Research        *
wolffd@0: *              AT&T Research, Florham Park NJ             *
wolffd@0: **********************************************************/
wolffd@0: 
wolffd@0: #ifndef _CDT_H
wolffd@0: #define _CDT_H		1
wolffd@0: 
wolffd@0: /*	Public interface for the dictionary library
wolffd@0: **
wolffd@0: **      Written by Kiem-Phong Vo (05/25/96)
wolffd@0: */
wolffd@0: 
wolffd@0: #define CDT_VERSION	19991101L
wolffd@0: 
wolffd@0: #define Void_t		void
wolffd@0: #define _ARG_(x)	x
wolffd@0: #ifndef NIL
wolffd@0: #define NIL(type) ((type)0)
wolffd@0: #endif
wolffd@0: 
wolffd@0: #include <string.h>
wolffd@0: 
wolffd@0: #if _PACKAGE_ast
wolffd@0: #  include	<ast_std.h>
wolffd@0: #elif _BLD_cdt
wolffd@0: #  include	"ast_common.h"
wolffd@0: #endif
wolffd@0: 
wolffd@0: #ifdef __cplusplus
wolffd@0: extern "C" {
wolffd@0: #endif
wolffd@0: 
wolffd@0:     typedef struct _dtlink_s Dtlink_t;
wolffd@0:     typedef struct _dthold_s Dthold_t;
wolffd@0:     typedef struct _dtdisc_s Dtdisc_t;
wolffd@0:     typedef struct _dtmethod_s Dtmethod_t;
wolffd@0:     typedef struct _dtdata_s Dtdata_t;
wolffd@0:     typedef struct _dt_s Dt_t;
wolffd@0:     typedef struct _dt_s Dict_t;	/* for libdict compatibility */
wolffd@0:     typedef struct _dtstat_s Dtstat_t;
wolffd@0:     typedef Void_t *(*Dtsearch_f) _ARG_((Dt_t *, Void_t *, int));
wolffd@0:     typedef Void_t *(*Dtmake_f) _ARG_((Dt_t *, Void_t *, Dtdisc_t *));
wolffd@0:     typedef void (*Dtfree_f) _ARG_((Dt_t *, Void_t *, Dtdisc_t *));
wolffd@0:     typedef int (*Dtcompar_f)
wolffd@0: 	_ARG_((Dt_t *, Void_t *, Void_t *, Dtdisc_t *));
wolffd@0:     typedef unsigned int (*Dthash_f) _ARG_((Dt_t *, Void_t *, Dtdisc_t *));
wolffd@0:     typedef Void_t *(*Dtmemory_f)
wolffd@0: 	_ARG_((Dt_t *, Void_t *, size_t, Dtdisc_t *));
wolffd@0:     typedef int (*Dtevent_f) _ARG_((Dt_t *, int, Void_t *, Dtdisc_t *));
wolffd@0: 
wolffd@0:     struct _dtlink_s {
wolffd@0: 	Dtlink_t *right;	/* right child          */
wolffd@0: 	union {
wolffd@0: 	    unsigned int _hash;	/* hash value           */
wolffd@0: 	    Dtlink_t *_left;	/* left child           */
wolffd@0: 	} hl;
wolffd@0:     };
wolffd@0: 
wolffd@0: /* private structure to hold an object */
wolffd@0:     struct _dthold_s {
wolffd@0: 	Dtlink_t hdr;		/* header               */
wolffd@0: 	Void_t *obj;		/* user object          */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* method to manipulate dictionary structure */
wolffd@0:     struct _dtmethod_s {
wolffd@0: 	Dtsearch_f searchf;	/* search function     */
wolffd@0: 	int type;		/* type of operation    */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* stuff that may be in shared memory */
wolffd@0:     struct _dtdata_s {
wolffd@0: 	int type;		/* type of dictionary                   */
wolffd@0: 	Dtlink_t *here;		/* finger to last search element        */
wolffd@0: 	union {
wolffd@0: 	    Dtlink_t **_htab;	/* hash table                           */
wolffd@0: 	    Dtlink_t *_head;	/* linked list                          */
wolffd@0: 	} hh;
wolffd@0: 	int ntab;		/* number of hash slots                 */
wolffd@0: 	int size;		/* number of objects                    */
wolffd@0: 	int loop;		/* number of nested loops               */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* structure to hold methods that manipulate an object */
wolffd@0:     struct _dtdisc_s {
wolffd@0: 	int key;		/* where the key begins in an object    */
wolffd@0: 	int size;		/* key size and type                    */
wolffd@0: 	int link;		/* offset to Dtlink_t field             */
wolffd@0: 	Dtmake_f makef;		/* object constructor                   */
wolffd@0: 	Dtfree_f freef;		/* object destructor                    */
wolffd@0: 	Dtcompar_f comparf;	/* to compare two objects               */
wolffd@0: 	Dthash_f hashf;		/* to compute hash value of an object   */
wolffd@0: 	Dtmemory_f memoryf;	/* to allocate/free memory              */
wolffd@0: 	Dtevent_f eventf;	/* to process events                    */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* the dictionary structure itself */
wolffd@0:     struct _dt_s {
wolffd@0: 	Dtsearch_f searchf;	/* search function                      */
wolffd@0: 	Dtdisc_t *disc;		/* method to manipulate objs            */
wolffd@0: 	Dtdata_t *data;		/* sharable data                        */
wolffd@0: 	Dtmemory_f memoryf;	/* function to alloc/free memory        */
wolffd@0: 	Dtmethod_t *meth;	/* dictionary method                    */
wolffd@0: 	int type;		/* type information                     */
wolffd@0: 	int nview;		/* number of parent view dictionaries   */
wolffd@0: 	Dt_t *view;		/* next on viewpath                     */
wolffd@0: 	Dt_t *walk;		/* dictionary being walked              */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* structure to get status of a dictionary */
wolffd@0:     struct _dtstat_s {
wolffd@0: 	int dt_meth;		/* method type                          */
wolffd@0: 	int dt_size;		/* number of elements                   */
wolffd@0: 	int dt_n;		/* number of chains or levels           */
wolffd@0: 	int dt_max;		/* max size of a chain or a level       */
wolffd@0: 	int *dt_count;		/* counts of chains or levels by size   */
wolffd@0:     };
wolffd@0: 
wolffd@0: /* supported storage methods */
wolffd@0: #define DT_SET		0000001	/* set with unique elements             */
wolffd@0: #define DT_BAG		0000002	/* multiset                             */
wolffd@0: #define DT_OSET		0000004	/* ordered set (self-adjusting tree)    */
wolffd@0: #define DT_OBAG		0000010	/* ordered multiset                     */
wolffd@0: #define DT_LIST		0000020	/* linked list                          */
wolffd@0: #define DT_STACK	0000040	/* stack                                */
wolffd@0: #define DT_QUEUE	0000100	/* queue                                */
wolffd@0: #define DT_METHODS	0000177	/* all currently supported methods      */
wolffd@0: 
wolffd@0: /* asserts to dtdisc() */
wolffd@0: #define DT_SAMECMP	0000001	/* compare methods equivalent           */
wolffd@0: #define DT_SAMEHASH	0000002	/* hash methods equivalent              */
wolffd@0: 
wolffd@0: /* types of search */
wolffd@0: #define DT_INSERT	0000001	/* insert object if not found           */
wolffd@0: #define DT_DELETE	0000002	/* delete object if found               */
wolffd@0: #define DT_SEARCH	0000004	/* look for an object                   */
wolffd@0: #define DT_NEXT		0000010	/* look for next element                */
wolffd@0: #define DT_PREV		0000020	/* find previous element                */
wolffd@0: #define DT_RENEW	0000040	/* renewing an object                   */
wolffd@0: #define DT_CLEAR	0000100	/* clearing all objects                 */
wolffd@0: #define DT_FIRST	0000200	/* get first object                     */
wolffd@0: #define DT_LAST		0000400	/* get last object                      */
wolffd@0: #define DT_MATCH	0001000	/* find object matching key             */
wolffd@0: #define DT_VSEARCH	0002000	/* search using internal representation */
wolffd@0: #define DT_ATTACH	0004000	/* attach an object to the dictionary   */
wolffd@0: #define DT_DETACH	0010000	/* attach an object to the dictionary   */
wolffd@0: 
wolffd@0: /* events */
wolffd@0: #define DT_OPEN		1	/* a dictionary is being opened         */
wolffd@0: #define DT_CLOSE	2	/* a dictionary is being closed         */
wolffd@0: #define DT_DISC		3	/* discipline is about to be changed    */
wolffd@0: #define DT_METH		4	/* method is about to be changed        */
wolffd@0: 
wolffd@0: 
wolffd@0: #if _BLD_cdt && defined(__EXPORT__)
wolffd@0: #define extern	__EXPORT__
wolffd@0: #endif
wolffd@0: #if !_BLD_cdt && defined(GVDLL)
wolffd@0: #define extern	__declspec(dllimport)
wolffd@0: #endif
wolffd@0: #if !_BLD_cdt && defined(__IMPORT__)
wolffd@0: #define extern	__IMPORT__
wolffd@0: #endif
wolffd@0: /*visual studio*/
wolffd@0: #ifdef WIN32_DLL
wolffd@0: #ifndef CDT_EXPORTS
wolffd@0: #define extern __declspec(dllimport)
wolffd@0: #else
wolffd@0: #define extern __declspec(dllexport)
wolffd@0: #endif
wolffd@0: #endif
wolffd@0: /*end visual studio*/
wolffd@0: 
wolffd@0: 	
wolffd@0: 	extern Dtmethod_t *Dtset;
wolffd@0:     extern Dtmethod_t *Dtbag;
wolffd@0:     extern Dtmethod_t *Dtoset;
wolffd@0:     extern Dtmethod_t *Dtobag;
wolffd@0:     extern Dtmethod_t *Dtlist;
wolffd@0:     extern Dtmethod_t *Dtstack;
wolffd@0:     extern Dtmethod_t *Dtqueue;
wolffd@0: 
wolffd@0: /* compatibility stuff; will go away */
wolffd@0: #ifndef KPVDEL
wolffd@0: 	extern Dtmethod_t *Dtorder;
wolffd@0:     extern Dtmethod_t *Dttree;
wolffd@0:     extern Dtmethod_t *Dthash;
wolffd@0:     extern Dtmethod_t _Dttree;
wolffd@0:     extern Dtmethod_t _Dthash;
wolffd@0:     extern Dtmethod_t _Dtlist;
wolffd@0:     extern Dtmethod_t _Dtqueue;
wolffd@0:     extern Dtmethod_t _Dtstack;
wolffd@0: #endif
wolffd@0: 
wolffd@0: #undef extern
wolffd@0: #if _BLD_cdt && defined(__EXPORT__)
wolffd@0: #define extern	__EXPORT__
wolffd@0: #endif
wolffd@0: #if !_BLD_cdt && defined(__IMPORT__) && defined(__EXPORT__)
wolffd@0: #define extern	__IMPORT__
wolffd@0: #endif
wolffd@0:      extern Dt_t *dtopen _ARG_((Dtdisc_t *, Dtmethod_t *));
wolffd@0:     extern int dtclose _ARG_((Dt_t *));
wolffd@0:     extern Dt_t *dtview _ARG_((Dt_t *, Dt_t *));
wolffd@0:     extern Dtdisc_t *dtdisc _ARG_((Dt_t * dt, Dtdisc_t *, int));
wolffd@0:     extern Dtmethod_t *dtmethod _ARG_((Dt_t *, Dtmethod_t *));
wolffd@0: 
wolffd@0:     extern Dtlink_t *dtflatten _ARG_((Dt_t *));
wolffd@0:     extern Dtlink_t *dtextract _ARG_((Dt_t *));
wolffd@0:     extern int dtrestore _ARG_((Dt_t *, Dtlink_t *));
wolffd@0: 
wolffd@0:     extern int dtwalk
wolffd@0: 	_ARG_((Dt_t *, int (*)(Dt_t *, Void_t *, Void_t *), Void_t *));
wolffd@0: 
wolffd@0:     extern Void_t *dtrenew _ARG_((Dt_t *, Void_t *));
wolffd@0: 
wolffd@0:     extern int dtsize _ARG_((Dt_t *));
wolffd@0:     extern int dtstat _ARG_((Dt_t *, Dtstat_t *, int));
wolffd@0:     extern unsigned int dtstrhash _ARG_((unsigned int, Void_t *, int));
wolffd@0: 
wolffd@0: #undef extern
wolffd@0: 
wolffd@0: #define _DT_(d)		((Dt_t*)(d))
wolffd@0: #define dtvnext(d)	(_DT_(d)->view)
wolffd@0: #define dtvcount(d)	(_DT_(d)->nview)
wolffd@0: #define dtvhere(d)	(_DT_(d)->walk)
wolffd@0: #define dtlink(d,e)	(((Dtlink_t*)(e))->right)
wolffd@0: #define dtobj(d,e)	((_DT_(d)->disc->link < 0) ? (((Dthold_t*)(e))->obj) : \
wolffd@0: 				(Void_t*)((char*)(e) - _DT_(d)->disc->link) )
wolffd@0: #define dtfinger(d)	(_DT_(d)->data->here ? dtobj((d),_DT_(d)->data->here) : \
wolffd@0: 				(Void_t*)(0) )
wolffd@0: #define dtfirst(d)	(*(_DT_(d)->searchf))((d),(Void_t*)(0),DT_FIRST)
wolffd@0: #define dtnext(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_NEXT)
wolffd@0: #define dtlast(d)	(*(_DT_(d)->searchf))((d),(Void_t*)(0),DT_LAST)
wolffd@0: #define dtprev(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_PREV)
wolffd@0: #define dtsearch(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_SEARCH)
wolffd@0: #define dtmatch(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_MATCH)
wolffd@0: #define dtinsert(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_INSERT)
wolffd@0: #define dtdelete(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
wolffd@0: #define dtattach(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_ATTACH)
wolffd@0: #define dtdetach(d,o)	(*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_DETACH)
wolffd@0: #define dtclear(d)	(*(_DT_(d)->searchf))((d),(Void_t*)(0),DT_CLEAR)
wolffd@0: /* A linear congruential hash: h*17 + c + 97531 */
wolffd@0: #define dtcharhash(h,c)	((((unsigned int)(h))<<4) + ((unsigned int)(h)) + \
wolffd@0: 			 ((unsigned char)(c)) + 97531 )
wolffd@0: #ifdef __cplusplus
wolffd@0: }
wolffd@0: #endif
wolffd@0: #endif				/* _CDT_H */