1#include "dthdr.h"
2
3/* Ordered set/multiset
4** dt: dictionary being searched
5** obj: the object to look for.
6** type: search type.
7**
8** Written by Kiem-Phong Vo (5/25/96)
9*/
10
11static void* dttree(Dt_t* dt, void* obj, int type)
12{
13 Dtlink_t *root, *t;
14 int cmp, lk, sz, ky;
15 void *o, *k, *key;
16 Dtlink_t *l, *r, *me = NULL, link;
17 int n, minp, turn[DT_MINP];
18 Dtcompar_f cmpf;
19 Dtdisc_t* disc;
20
21 UNFLATTEN(dt);
22 disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
23 dt->type &= ~DT_FOUND;
24
25 root = dt->data->here;
26 if(!obj)
27 { if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
28 return NIL(void*);
29
30 if(type&DT_CLEAR) /* delete all objects */
31 { if(disc->freef || disc->link < 0)
32 { do
33 { while((t = root->left) )
34 RROTATE(root,t);
35 t = root->right;
36 if(disc->freef)
37 (*disc->freef)(dt,_DTOBJ(root,lk),disc);
38 if(disc->link < 0)
39 (*dt->memoryf)(dt,(void*)root,0,disc);
40 } while((root = t) );
41 }
42
43 dt->data->size = 0;
44 dt->data->here = NIL(Dtlink_t*);
45 return NIL(void*);
46 }
47 else /* computing largest/smallest element */
48 { if(type&DT_LAST)
49 { while((t = root->right) )
50 LROTATE(root,t);
51 }
52 else /* type&DT_FIRST */
53 { while((t = root->left) )
54 RROTATE(root,t);
55 }
56
57 dt->data->here = root;
58 return _DTOBJ(root,lk);
59 }
60 }
61
62 /* note that link.right is LEFT tree and link.left is RIGHT tree */
63 l = r = &link;
64
65 /* allow apps to delete an object "actually" in the dictionary */
66 if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
67 { key = _DTKEY(obj,ky,sz);
68 for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
69 { k = _DTKEY(o,ky,sz);
70 if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
71 break;
72 if(o == obj)
73 { root = dt->data->here;
74 l->right = root->left;
75 r->left = root->right;
76 goto dt_delete;
77 }
78 }
79 }
80
81 if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH))
82 { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
83 if(root)
84 goto do_search;
85 }
86 else if(type&DT_RENEW)
87 { me = (Dtlink_t*)obj;
88 obj = _DTOBJ(me,lk);
89 key = _DTKEY(obj,ky,sz);
90 if(root)
91 goto do_search;
92 }
93 else if(root && _DTOBJ(root,lk) != obj)
94 { key = _DTKEY(obj,ky,sz);
95 do_search:
96 if(dt->meth->type == DT_OSET &&
97 (minp = dt->data->minp) != 0 && (type&(DT_MATCH|DT_SEARCH)) )
98 { /* simple search, note that minp should be even */
99 for(t = root, n = 0; n < minp; ++n)
100 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
101 if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
102 return _DTOBJ(t,lk);
103 else
104 { turn[n] = cmp;
105 if(!(t = cmp < 0 ? t->left : t->right) )
106 return NIL(void*);
107 }
108 }
109
110 /* exceed search length, top-down splay now */
111 for(n = 0; n < minp; n += 2)
112 { if(turn[n] < 0)
113 { t = root->left;
114 if(turn[n+1] < 0)
115 { rrotate(root,t);
116 rlink(r,t);
117 root = t->left;
118 }
119 else
120 { llink(l,t);
121 rlink(r,root);
122 root = t->right;
123 }
124 }
125 else
126 { t = root->right;
127 if(turn[n+1] > 0)
128 { lrotate(root,t);
129 llink(l,t);
130 root = t->right;
131 }
132 else
133 { rlink(r,t);
134 llink(l,root);
135 root = t->left;
136 }
137 }
138 }
139 }
140
141 while(1)
142 { k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
143 if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
144 break;
145 else if(cmp < 0)
146 { if((t = root->left) )
147 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
148 if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) < 0)
149 { rrotate(root,t);
150 rlink(r,t);
151 if(!(root = t->left) )
152 break;
153 }
154 else if(cmp == 0)
155 { rlink(r,root);
156 root = t;
157 break;
158 }
159 else /* if(cmp > 0) */
160 { llink(l,t);
161 rlink(r,root);
162 if(!(root = t->right) )
163 break;
164 }
165 }
166 else
167 { rlink(r,root);
168 root = NIL(Dtlink_t*);
169 break;
170 }
171 }
172 else /* if(cmp > 0) */
173 { if((t = root->right) )
174 { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
175 if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) > 0)
176 { lrotate(root,t);
177 llink(l,t);
178 if(!(root = t->right) )
179 break;
180 }
181 else if(cmp == 0)
182 { llink(l,root);
183 root = t;
184 break;
185 }
186 else /* if(cmp < 0) */
187 { rlink(r,t);
188 llink(l,root);
189 if(!(root = t->left) )
190 break;
191 }
192 }
193 else
194 { llink(l,root);
195 root = NIL(Dtlink_t*);
196 break;
197 }
198 }
199 }
200 }
201
202 if(root)
203 { /* found it, now isolate it */
204 dt->type |= DT_FOUND;
205 l->right = root->left;
206 r->left = root->right;
207
208 if(type&(DT_SEARCH|DT_MATCH))
209 { has_root:
210 root->left = link.right;
211 root->right = link.left;
212 if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
213 { key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
214 while((t = root->left) )
215 { /* find max of left subtree */
216 while((r = t->right) )
217 LROTATE(t,r);
218 root->left = t;
219
220 /* now see if it's in the same group */
221 k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
222 if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
223 break;
224 RROTATE(root,t);
225 }
226 }
227 dt->data->here = root;
228 return _DTOBJ(root,lk);
229 }
230 else if(type&DT_NEXT)
231 { root->left = link.right;
232 root->right = NIL(Dtlink_t*);
233 link.right = root;
234 dt_next:
235 if((root = link.left) )
236 { while((t = root->left) )
237 RROTATE(root,t);
238 link.left = root->right;
239 goto has_root;
240 }
241 else goto no_root;
242 }
243 else if(type&DT_PREV)
244 { root->right = link.left;
245 root->left = NIL(Dtlink_t*);
246 link.left = root;
247 dt_prev:
248 if((root = link.right) )
249 { while((t = root->right) )
250 LROTATE(root,t);
251 link.right = root->left;
252 goto has_root;
253 }
254 else goto no_root;
255 }
256 else if(type&(DT_DELETE|DT_DETACH))
257 { /* taking an object out of the dictionary */
258 dt_delete:
259 obj = _DTOBJ(root,lk);
260 if(disc->freef && (type&DT_DELETE))
261 (*disc->freef)(dt,obj,disc);
262 if(disc->link < 0)
263 (*dt->memoryf)(dt,(void*)root,0,disc);
264 if((dt->data->size -= 1) < 0)
265 dt->data->size = -1;
266 goto no_root;
267 }
268 else if(type&(DT_INSERT|DT_ATTACH))
269 { if(dt->meth->type&DT_OSET)
270 goto has_root;
271 else
272 { root->left = NIL(Dtlink_t*);
273 root->right = link.left;
274 link.left = root;
275 goto dt_insert;
276 }
277 }
278 else if(type&DT_RENEW) /* a duplicate */
279 { if(dt->meth->type&DT_OSET)
280 { if(disc->freef)
281 (*disc->freef)(dt,obj,disc);
282 if(disc->link < 0)
283 (*dt->memoryf)(dt,(void*)me,0,disc);
284 }
285 else
286 { me->left = NIL(Dtlink_t*);
287 me->right = link.left;
288 link.left = me;
289 dt->data->size += 1;
290 }
291 goto has_root;
292 }
293 }
294 else
295 { /* not found, finish up LEFT and RIGHT trees */
296 r->left = NIL(Dtlink_t*);
297 l->right = NIL(Dtlink_t*);
298
299 if(type&DT_NEXT)
300 goto dt_next;
301 else if(type&DT_PREV)
302 goto dt_prev;
303 else if(type&(DT_SEARCH|DT_MATCH))
304 { no_root:
305 while((t = r->left) )
306 r = t;
307 r->left = link.right;
308 dt->data->here = link.left;
309 return (type&DT_DELETE) ? obj : NIL(void*);
310 }
311 else if(type&(DT_INSERT|DT_ATTACH))
312 { dt_insert:
313 if(disc->makef && (type&DT_INSERT))
314 obj = (*disc->makef)(dt,obj,disc);
315 if(obj)
316 { if(lk >= 0)
317 root = _DTLNK(obj,lk);
318 else
319 { root = (Dtlink_t*)(*dt->memoryf)
320 (dt,NIL(void*),sizeof(Dthold_t),disc);
321 if(root)
322 ((Dthold_t*)root)->obj = obj;
323 else if(disc->makef && disc->freef &&
324 (type&DT_INSERT))
325 (*disc->freef)(dt,obj,disc);
326 }
327 }
328 if(root)
329 { if(dt->data->size >= 0)
330 dt->data->size += 1;
331 goto has_root;
332 }
333 else goto no_root;
334 }
335 else if(type&DT_RENEW)
336 { root = me;
337 dt->data->size += 1;
338 goto has_root;
339 }
340 else /*if(type&DT_DELETE)*/
341 { obj = NIL(void*);
342 goto no_root;
343 }
344 }
345
346 return NIL(void*);
347}
348
349/* make this method available */
350static Dtmethod_t _Dtoset = { dttree, DT_OSET };
351static Dtmethod_t _Dtobag = { dttree, DT_OBAG };
352Dtmethod_t* Dtoset = &_Dtoset;
353Dtmethod_t* Dtobag = &_Dtobag;
354
355#ifndef KPVDEL /* backward compatibility - delete next time around */
356Dtmethod_t _Dttree = { dttree, DT_OSET };
357Dtmethod_t* Dtorder = &_Dttree;
358Dtmethod_t* Dttree = &_Dttree;
359#endif
360
361#ifdef NoF
362NoF(dttree)
363#endif
364