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