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
|
/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 1985-2010 AT&T Intellectual Property *
* and is licensed under the *
* Common Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.opensource.org/licenses/cpl1.0.txt *
* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
* *
* 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
*/
#define CDT_VERSION 20050420L
#if _PACKAGE_ast
#include <ast_std.h>
#else
#include <ast_common.h>
#endif
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 _dt_s Dt_t;
typedef struct _dt_s Dict_t; /* for libdict compatibility */
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*));
struct _dtlink_s
{ Dtlink_t* right; /* right child */
union
{ unsigned int _hash; /* hash value */
Dtlink_t* _left; /* left child */
} hl;
};
/* private structure to hold an object */
struct _dthold_s
{ Dtlink_t hdr; /* header */
Void_t* obj; /* user object */
};
/* method to manipulate dictionary structure */
struct _dtmethod_s
{ Dtsearch_f searchf; /* search function */
int type; /* type of operation */
};
/* stuff that may be in shared memory */
struct _dtdata_s
{ int type; /* type of dictionary */
Dtlink_t* here; /* finger to last search element */
union
{ Dtlink_t** _htab; /* hash table */
Dtlink_t* _head; /* linked list */
} hh;
int ntab; /* number of hash slots */
int size; /* number of objects */
int loop; /* number of nested loops */
int minp; /* min path before splay, always even */
/* for hash dt, > 0: fixed table size */
};
/* structure to hold methods that manipulate an object */
struct _dtdisc_s
{ int key; /* where the key begins in an object */
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 of an object */
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 = (ky), (dc)->size = (sz), (dc)->link = (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; /* method to manipulate objs */
Dtdata_t* data; /* sharable data */
Dtmemory_f memoryf;/* function to alloc/free memory */
Dtmethod_t* meth; /* dictionary method */
int type; /* type information */
int nview; /* number of parent view dictionaries */
Dt_t* view; /* next on viewpath */
Dt_t* walk; /* dictionary being walked */
Void_t* user; /* for user's usage */
};
/* structure to get status of a dictionary */
struct _dtstat_s
{ int dt_meth; /* method type */
int dt_size; /* number of elements */
int dt_n; /* number of chains or levels */
int dt_max; /* max size of a chain or a level */
int* dt_count; /* counts of chains or levels by size */
};
/* flag set if the last search operation actually found the object */
#define DT_FOUND 0100000
/* supported storage methods */
#define DT_SET 0000001 /* set with unique elements */
#define DT_BAG 0000002 /* multiset */
#define DT_OSET 0000004 /* ordered set (self-adjusting tree) */
#define DT_OBAG 0000010 /* ordered multiset */
#define DT_LIST 0000020 /* linked list */
#define DT_STACK 0000040 /* stack */
#define DT_QUEUE 0000100 /* queue */
#define DT_METHODS 0000177 /* all currently supported methods */
/* asserts to dtdisc() */
#define DT_SAMECMP 0000001 /* compare methods equivalent */
#define DT_SAMEHASH 0000002 /* hash methods equivalent */
/* types of search */
#define DT_INSERT 0000001 /* insert object if not found */
#define DT_DELETE 0000002 /* delete object if found */
#define DT_SEARCH 0000004 /* look for an object */
#define DT_NEXT 0000010 /* look for next element */
#define DT_PREV 0000020 /* find previous element */
#define DT_RENEW 0000040 /* renewing an object */
#define DT_CLEAR 0000100 /* clearing all objects */
#define DT_FIRST 0000200 /* get first object */
#define DT_LAST 0000400 /* get last object */
#define DT_MATCH 0001000 /* find object matching key */
#define DT_VSEARCH 0002000 /* search using internal representation */
#define DT_ATTACH 0004000 /* attach an object to the dictionary */
#define DT_DETACH 0010000 /* detach an object from the dictionary */
/* events */
#define DT_OPEN 1 /* a dictionary is being opened */
#define DT_CLOSE 2 /* a dictionary is being closed */
#define DT_DISC 3 /* discipline is about to be changed */
#define DT_METH 4 /* method is about to be changed */
#define DT_ENDOPEN 5 /* dtopen() is done */
#define DT_ENDCLOSE 6 /* dtclose() is done */
#define DT_HASHSIZE 7 /* setting hash table size */
_BEGIN_EXTERNS_ /* public data */
#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;
/* compatibility stuff; will go away */
#ifndef KPVDEL
extern Dtmethod_t* Dtorder;
extern Dtmethod_t* Dttree;
extern Dtmethod_t* Dthash;
extern Dtmethod_t _Dttree;
extern Dtmethod_t _Dthash;
extern Dtmethod_t _Dtlist;
extern Dtmethod_t _Dtqueue;
extern Dtmethod_t _Dtstack;
#endif
#undef extern
_END_EXTERNS_
_BEGIN_EXTERNS_ /* public functions */
#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 Dtlink_t* dtflatten _ARG_((Dt_t*));
extern Dtlink_t* dtextract _ARG_((Dt_t*));
extern int dtrestore _ARG_((Dt_t*, Dtlink_t*));
extern int dttreeset _ARG_((Dt_t*, int, int));
extern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*));
extern Void_t* dtrenew _ARG_((Dt_t*, Void_t*));
extern int dtsize _ARG_((Dt_t*));
extern int dtstat _ARG_((Dt_t*, Dtstat_t*, int));
extern unsigned int dtstrhash _ARG_((unsigned int, Void_t*, int));
#if !_PACKAGE_ast
extern int memcmp _ARG_((const Void_t*, const Void_t*, size_t));
extern int strcmp _ARG_((const char*, const char*));
#endif
#undef extern
_END_EXTERNS_
/* internal functions for translating among holder, object and key */
#define _DT(dt) ((Dt_t*)(dt))
#define _DTDSC(dc,ky,sz,lk,cmpf) \
(ky = (dc)->key, sz = (dc)->size, lk = (dc)->link, cmpf = (dc)->comparf)
#define _DTLNK(o,lk) ((Dtlink_t*)((char*)(o) + lk) )
#define _DTOBJ(e,lk) ((lk) < 0 ? ((Dthold_t*)(e))->obj : (Void_t*)((char*)(e) - (lk)) )
#define _DTKEY(o,ky,sz) (Void_t*)((sz) < 0 ? *((char**)((char*)(o)+(ky))) : ((char*)(o)+(ky)))
#define _DTCMP(dt,k1,k2,dc,cmpf,sz) \
((cmpf) ? (*cmpf)(dt,k1,k2,dc) : \
((sz) <= 0 ? strcmp(k1,k2) : memcmp(k1,k2,sz)) )
#define _DTHSH(dt,ky,dc,sz) ((dc)->hashf ? (*(dc)->hashf)(dt,ky,dc) : dtstrhash(0,ky,sz) )
/* special search function for tree structure only */
#define _DTMTCH(dt,key,action) \
do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
_dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
_key = (key); \
for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
{ _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
break; \
} \
action (_e ? _o : (Void_t*)0); \
} while(0)
#define _DTSRCH(dt,obj,action) \
do { Dtlink_t* _e; Void_t *_o, *_k, *_key; Dtdisc_t* _dc; \
int _ky, _sz, _lk, _cmp; Dtcompar_f _cmpf; \
_dc = (dt)->disc; _DTDSC(_dc, _ky, _sz, _lk, _cmpf); \
_key = _DTKEY(obj, _ky, _sz); \
for(_e = (dt)->data->here; _e; _e = _cmp < 0 ? _e->hl._left : _e->right) \
{ _o = _DTOBJ(_e, _lk); _k = _DTKEY(_o, _ky, _sz); \
if((_cmp = _DTCMP((dt), _key, _k, _dc, _cmpf, _sz)) == 0) \
break; \
} \
action (_e ? _o : (Void_t*)0); \
} while(0)
#define DTTREEMATCH(dt,key,action) _DTMTCH(_DT(dt),(Void_t*)(key),action)
#define DTTREESEARCH(dt,obj,action) _DTSRCH(_DT(dt),(Void_t*)(obj),action)
#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))->right)
#define dtobj(d,e) _DTOBJ((e), _DT(d)->disc->link)
#define dtfinger(d) (_DT(d)->data->here ? dtobj((d),_DT(d)->data->here):(Void_t*)(0))
#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 dtleast(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_NEXT)
#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 dtmost(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_SEARCH|DT_PREV)
#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 dtdelete(d,o) (*(_DT(d)->searchf))((d),(Void_t*)(o),DT_DELETE)
#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 dtfound(d) (_DT(d)->type & DT_FOUND)
#define DT_PRIME 17109811 /* 2#00000001 00000101 00010011 00110011 */
#define dtcharhash(h,c) (((unsigned int)(h) + (unsigned int)(c)) * DT_PRIME )
#endif /* _CDT_H */
|
