1da2e3ebchin/***********************************************************************
2da2e3ebchin*                                                                      *
3da2e3ebchin*               This software is part of the ast package               *
43e14f97Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
5da2e3ebchin*                      and is licensed under the                       *
6da2e3ebchin*                  Common Public License, Version 1.0                  *
77c2fbfbApril Chin*                    by AT&T Intellectual Property                     *
8da2e3ebchin*                                                                      *
9da2e3ebchin*                A copy of the License is available at                 *
10da2e3ebchin*            http://www.opensource.org/licenses/cpl1.0.txt             *
11da2e3ebchin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12da2e3ebchin*                                                                      *
13da2e3ebchin*              Information and Software Systems Research               *
14da2e3ebchin*                            AT&T Research                             *
15da2e3ebchin*                           Florham Park NJ                            *
16da2e3ebchin*                                                                      *
17da2e3ebchin*                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebchin*                  David Korn <dgk@research.att.com>                   *
19da2e3ebchin*                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebchin*                                                                      *
21da2e3ebchin***********************************************************************/
22da2e3ebchin#ifndef _CDT_H
23da2e3ebchin#define _CDT_H		1
24da2e3ebchin
25da2e3ebchin/*	Public interface for the dictionary library
26da2e3ebchin**
27da2e3ebchin**      Written by Kiem-Phong Vo
28da2e3ebchin*/
29da2e3ebchin
30da2e3ebchin#define CDT_VERSION	20050420L
31da2e3ebchin
32da2e3ebchin#if _PACKAGE_ast
33da2e3ebchin#include	<ast_std.h>
34da2e3ebchin#else
35da2e3ebchin#include	<ast_common.h>
36da2e3ebchin#endif
37da2e3ebchin
38da2e3ebchintypedef struct _dtlink_s	Dtlink_t;
39da2e3ebchintypedef struct _dthold_s	Dthold_t;
40da2e3ebchintypedef struct _dtdisc_s	Dtdisc_t;
41da2e3ebchintypedef struct _dtmethod_s	Dtmethod_t;
42da2e3ebchintypedef struct _dtdata_s	Dtdata_t;
43da2e3ebchintypedef struct _dt_s		Dt_t;
44da2e3ebchintypedef struct _dt_s		Dict_t;	/* for libdict compatibility */
45da2e3ebchintypedef struct _dtstat_s	Dtstat_t;
46da2e3ebchintypedef Void_t*			(*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int));
47da2e3ebchintypedef Void_t* 		(*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
48da2e3ebchintypedef void 			(*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
49da2e3ebchintypedef int			(*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*));
50da2e3ebchintypedef unsigned int		(*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
51da2e3ebchintypedef Void_t*			(*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*));
52da2e3ebchintypedef int			(*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*));
53da2e3ebchin
54da2e3ebchinstruct _dtlink_s
55da2e3ebchin{	Dtlink_t*	right;	/* right child		*/
56da2e3ebchin	union
57da2e3ebchin	{ unsigned int	_hash;	/* hash value		*/
58da2e3ebchin	  Dtlink_t*	_left;	/* left child		*/
59da2e3ebchin	} hl;
60da2e3ebchin};
61da2e3ebchin
62da2e3ebchin/* private structure to hold an object */
63da2e3ebchinstruct _dthold_s
64da2e3ebchin{	Dtlink_t	hdr;	/* header		*/
65da2e3ebchin	Void_t*		obj;	/* user object		*/
66da2e3ebchin};
67da2e3ebchin
68da2e3ebchin/* method to manipulate dictionary structure */
69da2e3ebchinstruct _dtmethod_s
70da2e3ebchin{	Dtsearch_f	searchf; /* search function	*/
71da2e3ebchin	int		type;	/* type of operation	*/
72da2e3ebchin};
73da2e3ebchin
74da2e3ebchin/* stuff that may be in shared memory */
75da2e3ebchinstruct _dtdata_s
76da2e3ebchin{	int		type;	/* type of dictionary			*/
77da2e3ebchin	Dtlink_t*	here;	/* finger to last search element	*/
78da2e3ebchin	union
79da2e3ebchin	{ Dtlink_t**	_htab;	/* hash table				*/
80da2e3ebchin	  Dtlink_t*	_head;	/* linked list				*/
81da2e3ebchin	} hh;
82da2e3ebchin	int		ntab;	/* number of hash slots			*/
83da2e3ebchin	int		size;	/* number of objects			*/
84da2e3ebchin	int		loop;	/* number of nested loops		*/
85da2e3ebchin	int		minp;	/* min path before splay, always even	*/
86da2e3ebchin				/* for hash dt, > 0: fixed table size 	*/
87da2e3ebchin};
88da2e3ebchin
89da2e3ebchin/* structure to hold methods that manipulate an object */
90da2e3ebchinstruct _dtdisc_s
91da2e3ebchin{	int		key;	/* where the key begins in an object	*/
92da2e3ebchin	int		size;	/* key size and type			*/
93da2e3ebchin	int		link;	/* offset to Dtlink_t field		*/
94da2e3ebchin	Dtmake_f	makef;	/* object constructor			*/
95da2e3ebchin	Dtfree_f	freef;	/* object destructor			*/
96da2e3ebchin	Dtcompar_f	comparf;/* to compare two objects		*/
97da2e3ebchin	Dthash_f	hashf;	/* to compute hash value of an object	*/
98da2e3ebchin	Dtmemory_f	memoryf;/* to allocate/free memory		*/
99da2e3ebchin	Dtevent_f	eventf;	/* to process events			*/
100da2e3ebchin};
101da2e3ebchin
102da2e3ebchin#define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \
103da2e3ebchin	( (dc)->key = (ky), (dc)->size = (sz), (dc)->link = (lk), \
104da2e3ebchin	  (dc)->makef = (mkf), (dc)->freef = (frf), \
105da2e3ebchin	  (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \
106da2e3ebchin	  (dc)->memoryf = (memf), (dc)->eventf = (evf) )
107da2e3ebchin
108da2e3ebchin#ifdef offsetof
109da2e3ebchin#define DTOFFSET(struct_s, member)	offsetof(struct_s, member)
110da2e3ebchin#else
111da2e3ebchin#define DTOFFSET(struct_s, member)	((int)(&((struct_s*)0)->member))
112da2e3ebchin#endif
113da2e3ebchin
114da2e3ebchin/* the dictionary structure itself */
115da2e3ebchinstruct _dt_s
116da2e3ebchin{	Dtsearch_f	searchf;/* search function			*/
117da2e3ebchin	Dtdisc_t*	disc;	/* method to manipulate objs		*/
118da2e3ebchin	Dtdata_t*	data;	/* sharable data			*/
119da2e3ebchin	Dtmemory_f	memoryf;/* function to alloc/free memory	*/
120da2e3ebchin	Dtmethod_t*	meth;	/* dictionary method			*/
121da2e3ebchin	int		type;	/* type information			*/
122da2e3ebchin	int		nview;	/* number of parent view dictionaries	*/
123da2e3ebchin	Dt_t*		view;	/* next on viewpath			*/
124da2e3ebchin	Dt_t*		walk;	/* dictionary being walked		*/
125da2e3ebchin	Void_t*		user;	/* for user's usage			*/
126da2e3ebchin};
127da2e3ebchin
128da2e3ebchin/* structure to get status of a dictionary */
129da2e3ebchinstruct _dtstat_s
130da2e3ebchin{	int	dt_meth;	/* method type				*/
131da2e3ebchin	int	dt_size;	/* number of elements			*/
132da2e3ebchin	int	dt_n;		/* number of chains or levels		*/
133da2e3ebchin	int	dt_max;		/* max size of a chain or a level	*/
134da2e3ebchin	int*	dt_count;	/* counts of chains or levels by size	*/
135da2e3ebchin};
136da2e3ebchin
137da2e3ebchin/* flag set if the last search operation actually found the object */
138da2e3ebchin#define DT_FOUND	0100000
139da2e3ebchin
140da2e3ebchin/* supported storage methods */
141da2e3ebchin#define DT_SET		0000001	/* set with unique elements		*/
142da2e3ebchin#define DT_BAG		0000002	/* multiset				*/
143da2e3ebchin#define DT_OSET		0000004	/* ordered set (self-adjusting tree)	*/
144da2e3ebchin#define DT_OBAG		0000010	/* ordered multiset			*/
145da2e3ebchin#define DT_LIST		0000020	/* linked list				*/
146da2e3ebchin#define DT_STACK	0000040	/* stack				*/
147da2e3ebchin#define DT_QUEUE	0000100	/* queue				*/
148da2e3ebchin#define DT_METHODS	0000177	/* all currently supported methods	*/
149da2e3ebchin
150da2e3ebchin/* asserts to dtdisc() */
151da2e3ebchin#define DT_SAMECMP	0000001	/* compare methods equivalent		*/
152da2e3ebchin#define DT_SAMEHASH	0000002	/* hash methods equivalent		*/
153da2e3ebchin
154da2e3ebchin/* types of search */
155da2e3ebchin#define DT_INSERT	0000001	/* insert object if not found		*/
156da2e3ebchin#define DT_DELETE	0000002	/* delete object if found		*/
157da2e3ebchin#define DT_SEARCH	0000004	/* look for an object			*/
158da2e3ebchin#define DT_NEXT		0000010	/* look for next element		*/
159da2e3ebchin#define DT_PREV		0000020	/* find previous element		*/
160da2e3ebchin#define DT_RENEW	0000040	/* renewing an object			*/
161da2e3ebchin#define DT_CLEAR	0000100	/* clearing all objects			*/
162da2e3ebchin#define DT_FIRST	0000200	/* get first object			*/
163da2e3ebchin#define DT_LAST		0000400	/* get last object			*/
164da2e3ebchin#define DT_MATCH	0001000	/* find object matching key		*/
165da2e3ebchin#define DT_VSEARCH	0002000	/* search using internal representation	*/
166da2e3ebchin#define DT_ATTACH	0004000	/* attach an object to the dictionary	*/
167da2e3ebchin#define DT_DETACH	0010000	/* detach an object from the dictionary	*/
168da2e3ebchin
169da2e3ebchin/* events */
170da2e3ebchin#define DT_OPEN		1	/* a dictionary is being opened		*/
171da2e3ebchin#define DT_CLOSE	2	/* a dictionary is being closed		*/
172da2e3ebchin#define DT_DISC		3	/* discipline is about to be changed	*/
173da2e3ebchin#define DT_METH		4	/* method is about to be changed	*/
174da2e3ebchin#define DT_ENDOPEN	5	/* dtopen() is done			*/
175da2e3ebchin#define DT_ENDCLOSE	6	/* dtclose() is done			*/
176da2e3ebchin#define DT_HASHSIZE	7	/* setting hash table size		*/
177da2e3ebchin
178da2e3ebchin_BEGIN_EXTERNS_	/* public data */
179da2e3ebchin#if _BLD_cdt && defined(__EXPORT__)
180da2e3ebchin#define extern	__EXPORT__
181da2e3ebchin#endif
182da2e3ebchin#if !_BLD_cdt && defined(__IMPORT__)
183da2e3ebchin#define extern	__IMPORT__
184da2e3ebchin#endif
185da2e3ebchin
186da2e3ebchinextern Dtmethod_t* 	Dtset;
187da2e3ebchinextern Dtmethod_t* 	Dtbag;
188da2e3ebchinextern Dtmethod_t* 	Dtoset;
189da2e3ebchinextern Dtmethod_t* 	Dtobag;
190da2e3ebchinextern Dtmethod_t*	Dtlist;
191da2e3ebchinextern Dtmethod_t*	Dtstack;
192da2e3ebchinextern Dtmethod_t*	Dtqueue;
193da2e3ebchin
194da2e3ebchin/* compatibility stuff; will go away */
195da2e3ebchin#ifndef KPVDEL
196da2e3ebchinextern Dtmethod_t*	Dtorder;
197da2e3ebchinextern Dtmethod_t*	Dttree;
198da2e3ebchinextern Dtmethod_t*	Dthash;
199da2e3ebchinextern Dtmethod_t	_Dttree;
200da2e3ebchinextern Dtmethod_t	_Dthash;
201da2e3ebchinextern Dtmethod_t	_Dtlist;
202da2e3ebchinextern Dtmethod_t	_Dtqueue;
203da2e3ebchinextern Dtmethod_t	_Dtstack;
204da2e3ebchin#endif
205da2e3ebchin
206da2e3ebchin#undef extern
207da2e3ebchin_END_EXTERNS_
208da2e3ebchin
209da2e3ebchin_BEGIN_EXTERNS_	/* public functions */
210da2e3ebchin#if _BLD_cdt && defined(__EXPORT__)
211da2e3ebchin#define extern	__EXPORT__
212da2e3ebchin#endif
213da2e3ebchin
214da2e3ebchinextern Dt_t*		dtopen _ARG_((Dtdisc_t*, Dtmethod_t*));
215da2e3ebchinextern int		dtclose _ARG_((Dt_t*));
216da2e3ebchinextern Dt_t*		dtview _ARG_((Dt_t*, Dt_t*));
217da2e3ebchinextern Dtdisc_t*	dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int));
218da2e3ebchinextern Dtmethod_t*	dtmethod _ARG_((Dt_t*, Dtmethod_t*));
219da2e3ebchin
220da2e3ebchinextern Dtlink_t*	dtflatten _ARG_((Dt_t*));
221da2e3ebchinextern Dtlink_t*	dtextract _ARG_((Dt_t*));
222da2e3ebchinextern int		dtrestore _ARG_((Dt_t*, Dtlink_t*));
223da2e3ebchin
224da2e3ebchinextern int		dttreeset _ARG_((Dt_t*, int, int));
225da2e3ebchin
226da2e3ebchinextern int		dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
227da2e3ebchin
228da2e3ebchinextern Void_t*		dtrenew _ARG_((Dt_t*, Void_t*));
229da2e3ebchin
230da2e3ebchinextern int		dtsize _ARG_((Dt_t*));
231da2e3ebchinextern int		dtstat _ARG_((Dt_t*, Dtstat_t*, int));
232da2e3ebchinextern unsigned int	dtstrhash _ARG_((unsigned int, Void_t*, int));
233da2e3ebchin
234da2e3ebchin#if !_PACKAGE_ast
235da2e3ebchinextern int		memcmp _ARG_((const Void_t*, const Void_t*, size_t));
236da2e3ebchinextern int		strcmp _ARG_((const char*, const char*));
237da2e3ebchin#endif
238da2e3ebchin
239da2e3ebchin#undef extern
240da2e3ebchin_END_EXTERNS_
241da2e3ebchin
242da2e3ebchin/* internal functions for translating among holder, object and key */
243da2e3ebchin#define _DT(dt)		((Dt_t*)(dt))
244da2e3ebchin#define _DTDSC(dc,ky,sz,lk,cmpf) \
245da2e3ebchin			(ky = (dc)->key, sz = (dc)->size, lk = (dc)->link, cmpf = (dc)->comparf)
246da2e3ebchin#define _DTLNK(o,lk)	((Dtlink_t*)((char*)(o) + lk) )
247da2e3ebchin#define _DTOBJ(e,lk)	((lk) < 0 ? ((Dthold_t*)(e))->obj : (Void_t*)((char*)(e) - (lk)) )
248da2e3ebchin#define _DTKEY(o,ky,sz)	(Void_t*)((sz) < 0 ? *((char**)((char*)(o)+(ky))) : ((char*)(o)+(ky)))
249da2e3ebchin
250da2e3ebchin#define _DTCMP(dt,k1,k2,dc,cmpf,sz) \
251da2e3ebchin			((cmpf) ? (*cmpf)(dt,k1,k2,dc) : \
252da2e3ebchin			 ((sz) <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) )
253da2e3ebchin#define _DTHSH(dt,ky,dc,sz) ((dc)->hashf ? (*(dc)->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) )
254da2e3ebchin
255da2e3ebchin/* special search function for tree structure only */
256da2e3ebchin#define _DTMTCH(dt,key,action) \
257da2e3ebchin	do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
258da2e3ebchin	     int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
259da2e3ebchin	     _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
260da2e3ebchin	     _key = (key); \
261da2e3ebchin	     for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
262da2e3ebchin	     {	_o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
263da2e3ebchin		if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
264da2e3ebchin			break; \
265da2e3ebchin	     } \
266da2e3ebchin	     action (_e ? _o : (Void_t*)0); \
267da2e3ebchin	} while(0)
268da2e3ebchin
269da2e3ebchin#define _DTSRCH(dt,obj,action) \
270da2e3ebchin	do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
271da2e3ebchin	     int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
272da2e3ebchin	     _dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
273da2e3ebchin	     _key = _DTKEY(obj, _ky, _sz); \
274da2e3ebchin	     for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
275da2e3ebchin	     {	_o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
276da2e3ebchin		if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
277da2e3ebchin			break; \
278da2e3ebchin	     } \
279da2e3ebchin	     action (_e ? _o : (Void_t*)0); \
280da2e3ebchin	} while(0)
281da2e3ebchin
282da2e3ebchin#define DTTREEMATCH(dt,key,action)	_DTMTCH(_DT(dt),(Void_t*)(key),action)
283da2e3ebchin#define DTTREESEARCH(dt,obj,action)	_DTSRCH(_DT(dt),(Void_t*)(obj),action)
284da2e3ebchin
285da2e3ebchin#define dtvnext(d)	(_DT(d)->view)
286da2e3ebchin#define dtvcount(d)	(_DT(d)->nview)
287da2e3ebchin#define dtvhere(d)	(_DT(d)->walk)
288da2e3ebchin
289da2e3ebchin#define dtlink(d,e)	(((Dtlink_t*)(e))->right)
290da2e3ebchin#define dtobj(d,e)	_DTOBJ((e), _DT(d)->disc->link)
291da2e3ebchin#define dtfinger(d)	(_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(Void_t*)(0))
292da2e3ebchin
293da2e3ebchin#define dtfirst(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST)
294da2e3ebchin#define dtnext(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT)
295da2e3ebchin#define dtleast(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_NEXT)
296da2e3ebchin#define dtlast(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST)
297da2e3ebchin#define dtprev(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV)
298da2e3ebchin#define dtmost(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_PREV)
299da2e3ebchin#define dtsearch(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH)
300da2e3ebchin#define dtmatch(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH)
301da2e3ebchin#define dtinsert(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT)
302da2e3ebchin#define dtdelete(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
303da2e3ebchin#define dtattach(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH)
304da2e3ebchin#define dtdetach(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH)
305da2e3ebchin#define dtclear(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR)
306da2e3ebchin#define dtfound(d)	(_DT(d)->type & DT_FOUND)
307da2e3ebchin
308da2e3ebchin#define DT_PRIME	17109811 /* 2#00000001 00000101 00010011 00110011 */
309da2e3ebchin#define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
310da2e3ebchin
311da2e3ebchin#endif /* _CDT_H */
312