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