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