1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                 Eclipse Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *          http://www.eclipse.org/org/documents/epl-v10.html           *
11 *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
12 *                                                                      *
13 *              Information and Software Systems Research               *
14 *                            AT&T Research                             *
15 *                           Florham Park NJ                            *
16 *                                                                      *
17 *                 Glenn Fowler <gsf@research.att.com>                  *
18 *                  David Korn <dgk@research.att.com>                   *
19 *                   Phong Vo <kpv@research.att.com>                    *
20 *                                                                      *
21 ***********************************************************************/
22 #ifndef _CDT_H
23 #define _CDT_H		1
24 
25 /*	Public interface for the dictionary library
26 **
27 **      Written by Kiem-Phong Vo
28 */
29 
30 #ifndef CDT_VERSION
31 #ifdef _API_ast
32 #define CDT_VERSION		_API_ast
33 #else
34 #define CDT_VERSION		20111111L
35 #endif /*_AST_api*/
36 #endif /*CDT_VERSION*/
37 #ifndef AST_PLUGIN_VERSION
38 #define AST_PLUGIN_VERSION(v)	(v)
39 #endif
40 #define CDT_PLUGIN_VERSION	AST_PLUGIN_VERSION(20111111L)
41 
42 #if _PACKAGE_ast
43 #include	<ast_std.h>
44 #else
45 #include	<ast_common.h>
46 #include	<string.h>
47 #endif
48 
49 /* commonly used integers */
50 #define DT_ZERO		((unsigned int)0)  /* all zero bits	*/
51 #define DT_ONES		(~DT_ZERO)	   /* all one bits	*/
52 #define DT_HIBIT	(~(DT_ONES >> 1) ) /* highest 1 bit	*/
53 #define DT_LOBIT	((unsigned int)1)  /* lowest 1 bit	*/
54 #define DT_NBITS	(sizeof(unsigned int)*8) /* #bits	*/
55 
56 /* type of an integer with the same size as a pointer */
57 #define Dtuint_t	uintptr_t
58 
59 /* various types used by CDT */
60 typedef struct _dtlink_s	Dtlink_t;
61 typedef struct _dthold_s	Dthold_t;
62 typedef struct _dtdisc_s	Dtdisc_t;
63 typedef struct _dtmethod_s	Dtmethod_t;
64 typedef struct _dtdata_s	Dtdata_t;
65 typedef struct _dtuser_s	Dtuser_t;
66 typedef struct _dt_s		Dt_t;
67 typedef struct _dtstat_s	Dtstat_t;
68 typedef Void_t*			(*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int));
69 typedef Void_t* 		(*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
70 typedef void 			(*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
71 typedef int			(*Dtcompar_f)_ARG_((Dt_t*,Void_t*,Void_t*,Dtdisc_t*));
72 typedef unsigned int		(*Dthash_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*));
73 typedef Void_t*			(*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*));
74 typedef int			(*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*));
75 typedef int			(*Dttype_f)_ARG_((Dt_t*,int));
76 
77 struct _dtuser_s /* for application to access and use */
78 {	unsigned int	lock;	/* used by dtapplock	*/
79 	Void_t*		data;	/* for whatever data	*/
80 };
81 
82 struct _dtlink_s
83 {
84 #if CDT_VERSION < 20111111L
85 	Dtlink_t*	right;	/* right child		*/
86 	union
87 	{ unsigned int	_hash;	/* hash value		*/
88 	  Dtlink_t*	_left;	/* left child		*/
89 	} hl;
90 #else
91 	union
92 	{ Dtlink_t*	__rght;	/* right child or next	*/
93 	  Dtlink_t*	__ptbl;	/* Dtrehash parent tbl	*/
94 	} rh;
95 	union
96 	{ Dtlink_t*	__left;	/* left child or prev	*/
97 	  unsigned int	__hash;	/* hash value of object	*/
98 	} lh;
99 #endif
100 };
101 
102 /* private structure to hold an object */
103 struct _dthold_s
104 {	Dtlink_t	hdr;	/* header to hold obj	*/
105 	Void_t*		obj;	/* application object	*/
106 };
107 
108 /* method to manipulate dictionary structure */
109 struct _dtmethod_s
110 {	Dtsearch_f	searchf; /* search function	*/
111 	unsigned int	type;	 /* type of operation	*/
112 	int		(*eventf)_ARG_((Dt_t*, int, Void_t*));
113 	char*		name;	 /* name of method	*/
114 	char*		description; /* description */
115 };
116 
117 /* structure to hold methods that manipulate an object */
118 struct _dtdisc_s
119 {	int		key;	/* where the key resides 	*/
120 	int		size;	/* key size and type		*/
121 	int		link;	/* offset to Dtlink_t field	*/
122 	Dtmake_f	makef;	/* object constructor		*/
123 	Dtfree_f	freef;	/* object destructor		*/
124 	Dtcompar_f	comparf;/* to compare two objects	*/
125 	Dthash_f	hashf;	/* to compute hash value 	*/
126 	Dtmemory_f	memoryf;/* to allocate/free memory	*/
127 	Dtevent_f	eventf;	/* to process events		*/
128 };
129 
130 #define DTDISC(dc,ky,sz,lk,mkf,frf,cmpf,hshf,memf,evf) \
131 	( (dc)->key = (int)(ky), (dc)->size = (int)(sz), (dc)->link = (int)(lk), \
132 	  (dc)->makef = (mkf), (dc)->freef = (frf), \
133 	  (dc)->comparf = (cmpf), (dc)->hashf = (hshf), \
134 	  (dc)->memoryf = (memf), (dc)->eventf = (evf) )
135 
136 #ifdef offsetof
137 #define DTOFFSET(struct_s, member)	offsetof(struct_s, member)
138 #else
139 #define DTOFFSET(struct_s, member)	((int)(&((struct_s*)0)->member))
140 #endif
141 
142 /* the dictionary structure itself */
143 struct _dt_s
144 {	Dtsearch_f	searchf;/* search function		*/
145 	Dtdisc_t*	disc;	/* object type definitition	*/
146 	Dtdata_t*	data;	/* sharable data		*/
147 	Dtmemory_f	memoryf;/* for memory allocation	*/
148 	Dtmethod_t*	meth;	/* storage method		*/
149 	ssize_t		nview;	/* #parent view dictionaries	*/
150 	Dt_t*		view;	/* next on viewpath		*/
151 	Dt_t*		walk;	/* dictionary being walked	*/
152 	Dtuser_t*	user;	/* for user's usage		*/
153 	Dttype_f	typef;	/* for binary compatibility	*/
154 };
155 
156 /* structure to get status of a dictionary */
157 #define DT_MAXRECURSE	1024	/* limit to avoid stack overflow	*/
158 #define DT_MAXSIZE	256	/* limit for size of below arrays	*/
159 struct _dtstat_s
160 {	unsigned int	meth;	/* method type				*/
161 	ssize_t		size;	/* total # of elements in dictionary	*/
162 	ssize_t		space;	/* memory usage of data structure	*/
163 	ssize_t		mlev;	/* max #levels in tree or hash table	*/
164 	ssize_t		msize;	/* max #defined elts in below arrays	*/
165 	ssize_t		lsize[DT_MAXSIZE]; /* #objects by level		*/
166 	ssize_t		tsize[DT_MAXSIZE]; /* #tables by level		*/
167 };
168 
169 /* supported storage methods */
170 #define DT_SET		0000000001 /* unordered set, unique elements	*/
171 #define DT_BAG		0000000002 /* unordered set, repeated elements	*/
172 #define DT_OSET		0000000004 /* ordered set			*/
173 #define DT_OBAG		0000000010 /* ordered multiset			*/
174 #define DT_LIST		0000000020 /* linked list			*/
175 #define DT_STACK	0000000040 /* stack: insert/delete at top	*/
176 #define DT_QUEUE	0000000100 /* queue: insert top, delete at tail	*/
177 #define DT_DEQUE	0000000200 /* deque: insert top, append at tail	*/
178 #define DT_RHSET	0000000400 /* rhset: sharable unique objects	*/
179 #define DT_RHBAG	0000001000 /* rhbag: sharable repeated objects	*/
180 #define DT_METHODS	0000001777 /* all currently supported methods	*/
181 #define DT_ORDERED	(DT_OSET|DT_OBAG)
182 
183 /* asserts to dtdisc() to improve performance when changing disciplines */
184 #define DT_SAMECMP	0000000001 /* compare functions are equivalent	*/
185 #define DT_SAMEHASH	0000000002 /* hash functions are equivalent	*/
186 
187 /* operation types */
188 #define DT_INSERT	0000000001 /* insert object if not found	*/
189 #define DT_DELETE	0000000002 /* delete a matching object if any	*/
190 #define DT_SEARCH	0000000004 /* look for an object		*/
191 #define DT_NEXT		0000000010 /* look for next element		*/
192 #define DT_PREV		0000000020 /* find previous element		*/
193 #define DT_FIRST	0000000200 /* get first object			*/
194 #define DT_LAST		0000000400 /* get last object			*/
195 #define DT_MATCH	0000001000 /* find object matching key		*/
196 #define DT_ATTACH	0000004000 /* attach an object to dictionary	*/
197 #define DT_DETACH	0000010000 /* detach an object from dictionary	*/
198 #define DT_APPEND	0000020000 /* append an object			*/
199 #define DT_ATLEAST	0000040000 /* find the least elt >= object	*/
200 #define DT_ATMOST	0000100000 /* find the biggest elt <= object	*/
201 #define DT_REMOVE	0002000000 /* remove a specific object		*/
202 #define DT_TOANNOUNCE	(DT_INSERT|DT_DELETE|DT_SEARCH|DT_NEXT|DT_PREV|DT_FIRST|DT_LAST|DT_MATCH|DT_ATTACH|DT_DETACH|DT_APPEND|DT_ATLEAST|DT_ATMOST|DT_REMOVE)
203 
204 #define DT_RELINK	0000002000 /* re-inserting (dtdisc,dtmethod...)	*/
205 #define DT_FLATTEN	0000000040 /* flatten objects into a list	*/
206 #define DT_CLEAR	0000000100 /* clearing all objects		*/
207 #define DT_EXTRACT	0000200000 /* FLATTEN and clear dictionary	*/
208 #define DT_RESTORE	0000400000 /* reinsert a list of elements	*/
209 #define DT_STAT		0001000000 /* get statistics of dictionary	*/
210 #define DT_OPERATIONS	(DT_TOANNOUNCE|DT_RELINK|DT_FLATTEN|DT_CLEAR|DT_EXTRACT|DT_RESTORE|DT_STAT)
211 
212 /* these bits may combine with the DT_METHODS and DT_OPERATIONS bits */
213 #define DT_INDATA	0010000000 /* Dt_t was allocated with Dtdata_t	*/
214 #define DT_SHARE	0020000000 /* concurrent access mode 		*/
215 #define DT_ANNOUNCE	0040000000 /* announcing a successful operation	*/
216 				   /* the actual event will be this bit */
217 				   /* combined with the operation bit	*/
218 #define DT_OPTIMIZE	0100000000 /* optimizing data structure		*/
219 
220 /* events for discipline and method event-handling functions */
221 #define DT_OPEN		1	/* a dictionary is being opened		*/
222 #define DT_ENDOPEN	5	/* end of dictionary opening		*/
223 #define DT_CLOSE	2	/* a dictionary is being closed		*/
224 #define DT_ENDCLOSE	6	/* end of dictionary closing		*/
225 #define DT_DISC		3	/* discipline is about to be changed	*/
226 #define DT_METH		4	/* method is about to be changed	*/
227 #define DT_HASHSIZE	7	/* initialize hash table size		*/
228 #define DT_ERROR	0xbad	/* announcing an error			*/
229 
230 _BEGIN_EXTERNS_	/* data structures and functions */
231 #if _BLD_cdt && defined(__EXPORT__)
232 #define extern	__EXPORT__
233 #endif
234 #if !_BLD_cdt && defined(__IMPORT__)
235 #define extern	__IMPORT__
236 #endif
237 
238 extern Dtmethod_t* 	Dtset;
239 extern Dtmethod_t* 	Dtbag;
240 extern Dtmethod_t* 	Dtoset;
241 extern Dtmethod_t* 	Dtobag;
242 extern Dtmethod_t*	Dtlist;
243 extern Dtmethod_t*	Dtstack;
244 extern Dtmethod_t*	Dtqueue;
245 extern Dtmethod_t*	Dtdeque;
246 
247 #if _PACKAGE_ast /* dtplugin() for proprietary and non-standard methods -- requires -ldll */
248 
249 #define dtplugin(name)	((Dtmethod_t*)dllmeth("cdt", name, CDT_PLUGIN_VERSION))
250 
251 #define Dtrhbag		dtplugin("rehash:Dtrhbag")
252 #define Dtrhset		dtplugin("rehash:Dtrhset")
253 
254 #else
255 
256 #if CDTPROPRIETARY
257 
258 extern Dtmethod_t*	Dtrhset;
259 extern Dtmethod_t*	Dtrhbag;
260 
261 #endif /*CDTPROPRIETARY*/
262 
263 #endif /*_PACKAGE_ast*/
264 
265 #undef extern
266 
267 #if _BLD_cdt && defined(__EXPORT__)
268 #define extern	__EXPORT__
269 #endif
270 
271 extern Dt_t*		dtopen _ARG_((Dtdisc_t*, Dtmethod_t*));
272 extern int		dtclose _ARG_((Dt_t*));
273 extern Dt_t*		dtview _ARG_((Dt_t*, Dt_t*));
274 extern Dtdisc_t*	dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int));
275 extern Dtmethod_t*	dtmethod _ARG_((Dt_t*, Dtmethod_t*));
276 extern int		dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
277 extern int		dtcustomize _ARG_((Dt_t*, int, int));
278 extern unsigned int	dtstrhash _ARG_((unsigned int, Void_t*, ssize_t));
279 extern int		dtuserlock _ARG_((Dt_t*, unsigned int, int));
280 extern Void_t*		dtuserdata _ARG_((Dt_t*, Void_t*, unsigned int));
281 
282 /* deal with upward binary compatibility (operation bit translation, etc.) */
283 extern Dt_t*		_dtopen _ARG_((Dtdisc_t*, Dtmethod_t*, unsigned long));
284 #define dtopen(dc,mt)	_dtopen((dc), (mt), CDT_VERSION)
285 
286 #undef extern
287 
288 #if _PACKAGE_ast && !defined(_CDTLIB_H)
289 
290 #if _BLD_dll && defined(__EXPORT__)
291 #define extern	__EXPORT__
292 #endif
293 
294 extern void*		dllmeth(const char*, const char*, unsigned long);
295 
296 #undef	extern
297 
298 #endif
299 
300 _END_EXTERNS_
301 
302 /* internal functions for translating among holder, object and key */
303 #define _DT(dt)		((Dt_t*)(dt))
304 
305 #define _DTLNK(dc,o)	((Dtlink_t*)((char*)(o) + (dc)->link) ) /* get link from obj */
306 
307 #define _DTO(dc,l)	(Void_t*)((char*)(l) - (dc)->link) /* get object from link */
308 #define _DTOBJ(dc,l)	((dc)->link >= 0 ? _DTO(dc,l) : ((Dthold_t*)(l))->obj )
309 
310 #define _DTK(dc,o)	((char*)(o) + (dc)->key) /* get key from object */
311 #define _DTKEY(dc,o)	(Void_t*)((dc)->size >= 0 ? _DTK(dc,o) : *((char**)_DTK(dc,o)) )
312 
313 #define _DTCMP(dt,k1,k2,dc) \
314 			((dc)->comparf  ? (*(dc)->comparf)((dt), (k1), (k2), (dc)) : \
315 			 (dc)->size > 0 ? memcmp((Void_t*)(k1), ((Void_t*)k2), (dc)->size) : \
316 					  strcmp((char*)(k1), ((char*)k2)) )
317 
318 #define _DTHSH(dt,ky,dc) ((dc)->hashf   ? (*(dc)->hashf)((dt), (ky), (dc)) : \
319 					  dtstrhash(0, (ky), (dc)->size) )
320 
321 #define dtvnext(d)	(_DT(d)->view)
322 #define dtvcount(d)	(_DT(d)->nview)
323 #define dtvhere(d)	(_DT(d)->walk)
324 
325 #define dtlink(d,e)	(((Dtlink_t*)(e))->rh.__rght)
326 #define dtobj(d,e)	_DTOBJ(_DT(d)->disc, (e))
327 
328 #define dtfirst(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FIRST)
329 #define dtnext(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_NEXT)
330 #define dtatleast(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATLEAST)
331 #define dtlast(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_LAST)
332 #define dtprev(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_PREV)
333 #define dtatmost(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATMOST)
334 #define dtsearch(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH)
335 #define dtmatch(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_MATCH)
336 #define dtinsert(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_INSERT)
337 #define dtappend(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_APPEND)
338 #define dtdelete(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
339 #define dtremove(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_REMOVE)
340 #define dtattach(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_ATTACH)
341 #define dtdetach(d,o)	(*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DETACH)
342 #define dtclear(d)	(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_CLEAR)
343 
344 #define dtflatten(d)	(Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_FLATTEN)
345 #define dtextract(d)	(Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_EXTRACT)
346 #define dtrestore(d,l)	(Dtlink_t*)(*(_DT(d)->searchf))((d),(Void_t*)(l),DT_RESTORE)
347 
348 #define dtstat(d,s)	(ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(s),DT_STAT)
349 #define dtsize(d)	(ssize_t)(*(_DT(d)->searchf))((d),(Void_t*)(0),DT_STAT)
350 
351 #define DT_PRIME	17109811 /* 2#00000001 00000101 00010011 00110011 */
352 #define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
353 
354 #endif /* _CDT_H */
355