1*b30d1939SAndy Fiddaman /***********************************************************************
2*b30d1939SAndy Fiddaman * *
3*b30d1939SAndy Fiddaman * This software is part of the ast package *
4*b30d1939SAndy Fiddaman * Copyright (c) 1985-2012 AT&T Intellectual Property *
5*b30d1939SAndy Fiddaman * and is licensed under the *
6*b30d1939SAndy Fiddaman * Eclipse Public License, Version 1.0 *
7*b30d1939SAndy Fiddaman * by AT&T Intellectual Property *
8*b30d1939SAndy Fiddaman * *
9*b30d1939SAndy Fiddaman * A copy of the License is available at *
10*b30d1939SAndy Fiddaman * http://www.eclipse.org/org/documents/epl-v10.html *
11*b30d1939SAndy Fiddaman * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12*b30d1939SAndy Fiddaman * *
13*b30d1939SAndy Fiddaman * Information and Software Systems Research *
14*b30d1939SAndy Fiddaman * AT&T Research *
15*b30d1939SAndy Fiddaman * Florham Park NJ *
16*b30d1939SAndy Fiddaman * *
17*b30d1939SAndy Fiddaman * Glenn Fowler <gsf@research.att.com> *
18*b30d1939SAndy Fiddaman * David Korn <dgk@research.att.com> *
19*b30d1939SAndy Fiddaman * Phong Vo <kpv@research.att.com> *
20*b30d1939SAndy Fiddaman * *
21*b30d1939SAndy Fiddaman ***********************************************************************/
22*b30d1939SAndy Fiddaman #include "dthdr.h"
23*b30d1939SAndy Fiddaman
24*b30d1939SAndy Fiddaman /* Ordered set/multiset
25*b30d1939SAndy Fiddaman ** dt: dictionary being searched
26*b30d1939SAndy Fiddaman ** obj: the object to look for.
27*b30d1939SAndy Fiddaman ** type: search type.
28*b30d1939SAndy Fiddaman **
29*b30d1939SAndy Fiddaman ** Written by Kiem-Phong Vo (5/25/96)
30*b30d1939SAndy Fiddaman */
31*b30d1939SAndy Fiddaman
32*b30d1939SAndy Fiddaman typedef struct _dttree_s
33*b30d1939SAndy Fiddaman { Dtdata_t data;
34*b30d1939SAndy Fiddaman Dtlink_t* root; /* tree root */
35*b30d1939SAndy Fiddaman } Dttree_t;
36*b30d1939SAndy Fiddaman
37*b30d1939SAndy Fiddaman #ifdef CDT_DEBUG
dttreeprint(Dt_t * dt,Dtlink_t * here,int lev,char * (* objprintf)(Void_t *))38*b30d1939SAndy Fiddaman int dttreeprint(Dt_t* dt, Dtlink_t* here, int lev, char* (*objprintf)(Void_t*) )
39*b30d1939SAndy Fiddaman {
40*b30d1939SAndy Fiddaman int k, rv;
41*b30d1939SAndy Fiddaman char *obj, *endb, buf[1024];
42*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
43*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
44*b30d1939SAndy Fiddaman
45*b30d1939SAndy Fiddaman if(!here && !(here = tree->root) )
46*b30d1939SAndy Fiddaman return -1;
47*b30d1939SAndy Fiddaman
48*b30d1939SAndy Fiddaman endb = buf; /* indentation */
49*b30d1939SAndy Fiddaman for(k = 0; k < lev; ++k)
50*b30d1939SAndy Fiddaman { *endb++ = ' '; *endb++ = ' '; }
51*b30d1939SAndy Fiddaman
52*b30d1939SAndy Fiddaman *endb++ = '(';
53*b30d1939SAndy Fiddaman obj = (*objprintf)(_DTOBJ(disc, here));
54*b30d1939SAndy Fiddaman k = strlen(obj); memcpy(endb, obj, k); endb += k;
55*b30d1939SAndy Fiddaman *endb++ = ')';
56*b30d1939SAndy Fiddaman *endb++ = ':';
57*b30d1939SAndy Fiddaman *endb++ = ' ';
58*b30d1939SAndy Fiddaman
59*b30d1939SAndy Fiddaman *endb++ = '<';
60*b30d1939SAndy Fiddaman if(here->_left)
61*b30d1939SAndy Fiddaman obj = (*objprintf)(_DTOBJ(disc,here->_left));
62*b30d1939SAndy Fiddaman else obj = "NIL";
63*b30d1939SAndy Fiddaman k = strlen(obj); memcpy(endb, obj, k); endb += k;
64*b30d1939SAndy Fiddaman *endb++ = '>';
65*b30d1939SAndy Fiddaman *endb++ = ' ';
66*b30d1939SAndy Fiddaman
67*b30d1939SAndy Fiddaman *endb++ = '<';
68*b30d1939SAndy Fiddaman if(here->_rght)
69*b30d1939SAndy Fiddaman obj = (*objprintf)(_DTOBJ(disc,here->_rght));
70*b30d1939SAndy Fiddaman else obj = "NIL";
71*b30d1939SAndy Fiddaman k = strlen(obj); memcpy(endb, obj, k); endb += k;
72*b30d1939SAndy Fiddaman *endb++ = '>';
73*b30d1939SAndy Fiddaman *endb++ = '\n';
74*b30d1939SAndy Fiddaman write(2, buf, endb-buf);
75*b30d1939SAndy Fiddaman
76*b30d1939SAndy Fiddaman if(here->_left)
77*b30d1939SAndy Fiddaman dttreeprint(dt, here->_left, lev+1, objprintf);
78*b30d1939SAndy Fiddaman if(here->_rght)
79*b30d1939SAndy Fiddaman dttreeprint(dt, here->_rght, lev+1, objprintf);
80*b30d1939SAndy Fiddaman
81*b30d1939SAndy Fiddaman return 0;
82*b30d1939SAndy Fiddaman }
83*b30d1939SAndy Fiddaman #endif
84*b30d1939SAndy Fiddaman
85*b30d1939SAndy Fiddaman /* terminal object: DT_FIRST|DT_LAST */
86*b30d1939SAndy Fiddaman #if __STD_C
tfirstlast(Dt_t * dt,int type)87*b30d1939SAndy Fiddaman Void_t* tfirstlast(Dt_t* dt, int type)
88*b30d1939SAndy Fiddaman #else
89*b30d1939SAndy Fiddaman Void_t* tfirstlast(dt, type)
90*b30d1939SAndy Fiddaman Dt_t* dt;
91*b30d1939SAndy Fiddaman int type;
92*b30d1939SAndy Fiddaman #endif
93*b30d1939SAndy Fiddaman {
94*b30d1939SAndy Fiddaman Dtlink_t *t, *root;
95*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
96*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
97*b30d1939SAndy Fiddaman
98*b30d1939SAndy Fiddaman if(!(root = tree->root) )
99*b30d1939SAndy Fiddaman return NIL(Void_t*);
100*b30d1939SAndy Fiddaman
101*b30d1939SAndy Fiddaman if(type&DT_LAST)
102*b30d1939SAndy Fiddaman { while((t = root->_rght) )
103*b30d1939SAndy Fiddaman LROTATE(root,t);
104*b30d1939SAndy Fiddaman }
105*b30d1939SAndy Fiddaman else /* type&DT_FIRST */
106*b30d1939SAndy Fiddaman { while((t = root->_left) )
107*b30d1939SAndy Fiddaman RROTATE(root,t);
108*b30d1939SAndy Fiddaman }
109*b30d1939SAndy Fiddaman tree->root = root;
110*b30d1939SAndy Fiddaman
111*b30d1939SAndy Fiddaman return _DTOBJ(disc, root);
112*b30d1939SAndy Fiddaman }
113*b30d1939SAndy Fiddaman
114*b30d1939SAndy Fiddaman /* DT_CLEAR */
115*b30d1939SAndy Fiddaman #if __STD_C
tclear(Dt_t * dt)116*b30d1939SAndy Fiddaman static Void_t* tclear(Dt_t* dt)
117*b30d1939SAndy Fiddaman #else
118*b30d1939SAndy Fiddaman static Void_t* tclear(dt)
119*b30d1939SAndy Fiddaman Dt_t* dt;
120*b30d1939SAndy Fiddaman #endif
121*b30d1939SAndy Fiddaman {
122*b30d1939SAndy Fiddaman Dtlink_t *root, *t;
123*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
124*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
125*b30d1939SAndy Fiddaman
126*b30d1939SAndy Fiddaman root = tree->root;
127*b30d1939SAndy Fiddaman tree->root = NIL(Dtlink_t*);
128*b30d1939SAndy Fiddaman tree->data.size = 0;
129*b30d1939SAndy Fiddaman
130*b30d1939SAndy Fiddaman if(root && (disc->link < 0 || disc->freef) )
131*b30d1939SAndy Fiddaman { do
132*b30d1939SAndy Fiddaman { while((t = root->_left) )
133*b30d1939SAndy Fiddaman RROTATE(root,t);
134*b30d1939SAndy Fiddaman t = root->_rght;
135*b30d1939SAndy Fiddaman _dtfree(dt, root, DT_DELETE);
136*b30d1939SAndy Fiddaman } while((root = t) );
137*b30d1939SAndy Fiddaman }
138*b30d1939SAndy Fiddaman
139*b30d1939SAndy Fiddaman return NIL(Void_t*);
140*b30d1939SAndy Fiddaman }
141*b30d1939SAndy Fiddaman
142*b30d1939SAndy Fiddaman #if __STD_C
tlist(Dt_t * dt,Dtlink_t * list,int type)143*b30d1939SAndy Fiddaman static Void_t* tlist(Dt_t* dt, Dtlink_t* list, int type)
144*b30d1939SAndy Fiddaman #else
145*b30d1939SAndy Fiddaman static Void_t* tlist(dt, list, type)
146*b30d1939SAndy Fiddaman Dt_t* dt;
147*b30d1939SAndy Fiddaman Dtlink_t* list;
148*b30d1939SAndy Fiddaman int type;
149*b30d1939SAndy Fiddaman #endif
150*b30d1939SAndy Fiddaman {
151*b30d1939SAndy Fiddaman Void_t *obj;
152*b30d1939SAndy Fiddaman Dtlink_t *last, *r, *t;
153*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
154*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
155*b30d1939SAndy Fiddaman
156*b30d1939SAndy Fiddaman if(type&(DT_FLATTEN|DT_EXTRACT) )
157*b30d1939SAndy Fiddaman { if((list = tree->root) )
158*b30d1939SAndy Fiddaman { while((t = list->_left) ) /* make smallest object root */
159*b30d1939SAndy Fiddaman RROTATE(list, t);
160*b30d1939SAndy Fiddaman for(r = (last = list)->_rght; r; r = (last = r)->_rght)
161*b30d1939SAndy Fiddaman { while((t = r->_left) ) /* no left children */
162*b30d1939SAndy Fiddaman RROTATE(r,t);
163*b30d1939SAndy Fiddaman last->_rght = r;
164*b30d1939SAndy Fiddaman }
165*b30d1939SAndy Fiddaman }
166*b30d1939SAndy Fiddaman
167*b30d1939SAndy Fiddaman if(type&DT_FLATTEN)
168*b30d1939SAndy Fiddaman tree->root = list;
169*b30d1939SAndy Fiddaman else
170*b30d1939SAndy Fiddaman { tree->root = NIL(Dtlink_t*);
171*b30d1939SAndy Fiddaman dt->data->size = 0;
172*b30d1939SAndy Fiddaman }
173*b30d1939SAndy Fiddaman }
174*b30d1939SAndy Fiddaman else /* if(type&DT_RESTORE) */
175*b30d1939SAndy Fiddaman { dt->data->size = 0;
176*b30d1939SAndy Fiddaman for(r = list; r; r = t)
177*b30d1939SAndy Fiddaman { t = r->_rght;
178*b30d1939SAndy Fiddaman obj = _DTOBJ(disc,r);
179*b30d1939SAndy Fiddaman if((*dt->meth->searchf)(dt, (Void_t*)r, DT_RELINK) == obj )
180*b30d1939SAndy Fiddaman dt->data->size += 1;
181*b30d1939SAndy Fiddaman }
182*b30d1939SAndy Fiddaman }
183*b30d1939SAndy Fiddaman
184*b30d1939SAndy Fiddaman return (Void_t*)list;
185*b30d1939SAndy Fiddaman }
186*b30d1939SAndy Fiddaman
187*b30d1939SAndy Fiddaman #if __STD_C /* compute tree depth and number of nodes */
tsize(Dtlink_t * root,ssize_t lev,Dtstat_t * st)188*b30d1939SAndy Fiddaman static ssize_t tsize(Dtlink_t* root, ssize_t lev, Dtstat_t* st)
189*b30d1939SAndy Fiddaman #else
190*b30d1939SAndy Fiddaman static ssize_t tsize(root, lev, st)
191*b30d1939SAndy Fiddaman Dtlink_t* root;
192*b30d1939SAndy Fiddaman ssize_t lev;
193*b30d1939SAndy Fiddaman Dtstat_t* st;
194*b30d1939SAndy Fiddaman #endif
195*b30d1939SAndy Fiddaman {
196*b30d1939SAndy Fiddaman ssize_t size, z;
197*b30d1939SAndy Fiddaman
198*b30d1939SAndy Fiddaman if(!root) /* nothing to do */
199*b30d1939SAndy Fiddaman return 0;
200*b30d1939SAndy Fiddaman
201*b30d1939SAndy Fiddaman if(lev >= DT_MAXRECURSE) /* avoid blowing the stack */
202*b30d1939SAndy Fiddaman return -1;
203*b30d1939SAndy Fiddaman
204*b30d1939SAndy Fiddaman if(st)
205*b30d1939SAndy Fiddaman { st->mlev = lev > st->mlev ? lev : st->mlev;
206*b30d1939SAndy Fiddaman if(lev < DT_MAXSIZE)
207*b30d1939SAndy Fiddaman { st->msize = lev > st->msize ? lev : st->msize;
208*b30d1939SAndy Fiddaman st->lsize[lev] += 1; /* count #objects per level */
209*b30d1939SAndy Fiddaman }
210*b30d1939SAndy Fiddaman }
211*b30d1939SAndy Fiddaman
212*b30d1939SAndy Fiddaman size = 1;
213*b30d1939SAndy Fiddaman
214*b30d1939SAndy Fiddaman if((z = tsize(root->_left, lev+1, st)) < 0)
215*b30d1939SAndy Fiddaman return -1;
216*b30d1939SAndy Fiddaman else size += z;
217*b30d1939SAndy Fiddaman
218*b30d1939SAndy Fiddaman if((z = tsize(root->_rght, lev+1, st)) < 0)
219*b30d1939SAndy Fiddaman return -1;
220*b30d1939SAndy Fiddaman else size += z;
221*b30d1939SAndy Fiddaman
222*b30d1939SAndy Fiddaman return size;
223*b30d1939SAndy Fiddaman }
224*b30d1939SAndy Fiddaman
225*b30d1939SAndy Fiddaman #if __STD_C
tstat(Dt_t * dt,Dtstat_t * st)226*b30d1939SAndy Fiddaman static Void_t* tstat(Dt_t* dt, Dtstat_t* st)
227*b30d1939SAndy Fiddaman #else
228*b30d1939SAndy Fiddaman static Void_t* tstat(dt, st)
229*b30d1939SAndy Fiddaman Dt_t* dt;
230*b30d1939SAndy Fiddaman Dtstat_t* st;
231*b30d1939SAndy Fiddaman #endif
232*b30d1939SAndy Fiddaman {
233*b30d1939SAndy Fiddaman ssize_t size;
234*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
235*b30d1939SAndy Fiddaman
236*b30d1939SAndy Fiddaman if(!st)
237*b30d1939SAndy Fiddaman return (Void_t*)dt->data->size;
238*b30d1939SAndy Fiddaman else
239*b30d1939SAndy Fiddaman { memset(st, 0, sizeof(Dtstat_t));
240*b30d1939SAndy Fiddaman size = tsize(tree->root, 0, st);
241*b30d1939SAndy Fiddaman /**/DEBUG_ASSERT((dt->data->type&DT_SHARE) || size == dt->data->size);
242*b30d1939SAndy Fiddaman st->meth = dt->meth->type;
243*b30d1939SAndy Fiddaman st->size = size;
244*b30d1939SAndy Fiddaman st->space = sizeof(Dttree_t) + (dt->disc->link >= 0 ? 0 : size*sizeof(Dthold_t));
245*b30d1939SAndy Fiddaman return (Void_t*)size;
246*b30d1939SAndy Fiddaman }
247*b30d1939SAndy Fiddaman }
248*b30d1939SAndy Fiddaman
249*b30d1939SAndy Fiddaman #if __STD_C /* make a list into a balanced tree */
tbalance(Dtlink_t * list,ssize_t size)250*b30d1939SAndy Fiddaman static Dtlink_t* tbalance(Dtlink_t* list, ssize_t size)
251*b30d1939SAndy Fiddaman #else
252*b30d1939SAndy Fiddaman static Dtlink_t* tbalance(list, size)
253*b30d1939SAndy Fiddaman Dtlink_t* list;
254*b30d1939SAndy Fiddaman ssize_t size;
255*b30d1939SAndy Fiddaman #endif
256*b30d1939SAndy Fiddaman {
257*b30d1939SAndy Fiddaman ssize_t n;
258*b30d1939SAndy Fiddaman Dtlink_t *l, *mid;
259*b30d1939SAndy Fiddaman
260*b30d1939SAndy Fiddaman if(size <= 2)
261*b30d1939SAndy Fiddaman return list;
262*b30d1939SAndy Fiddaman
263*b30d1939SAndy Fiddaman for(l = list, n = size/2 - 1; n > 0; n -= 1)
264*b30d1939SAndy Fiddaman l = l->_rght;
265*b30d1939SAndy Fiddaman
266*b30d1939SAndy Fiddaman mid = l->_rght; l->_rght = NIL(Dtlink_t*);
267*b30d1939SAndy Fiddaman mid->_left = tbalance(list, (n = size/2) );
268*b30d1939SAndy Fiddaman mid->_rght = tbalance(mid->_rght, size - (n + 1));
269*b30d1939SAndy Fiddaman return mid;
270*b30d1939SAndy Fiddaman }
271*b30d1939SAndy Fiddaman
toptimize(Dt_t * dt)272*b30d1939SAndy Fiddaman static void toptimize(Dt_t* dt)
273*b30d1939SAndy Fiddaman {
274*b30d1939SAndy Fiddaman ssize_t size;
275*b30d1939SAndy Fiddaman Dtlink_t *l, *list;
276*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
277*b30d1939SAndy Fiddaman
278*b30d1939SAndy Fiddaman if((list = (Dtlink_t*)tlist(dt, NIL(Void_t*), DT_FLATTEN)) )
279*b30d1939SAndy Fiddaman { for(size = 0, l = list; l; l = l->_rght)
280*b30d1939SAndy Fiddaman size += 1;
281*b30d1939SAndy Fiddaman tree->root = tbalance(list, size);
282*b30d1939SAndy Fiddaman }
283*b30d1939SAndy Fiddaman }
284*b30d1939SAndy Fiddaman
troot(Dt_t * dt,Dtlink_t * list,Dtlink_t * link,Void_t * obj,int type)285*b30d1939SAndy Fiddaman static Dtlink_t* troot(Dt_t* dt, Dtlink_t* list, Dtlink_t* link, Void_t* obj, int type)
286*b30d1939SAndy Fiddaman {
287*b30d1939SAndy Fiddaman Dtlink_t *root, *last, *t, *r, *l;
288*b30d1939SAndy Fiddaman Void_t *key, *o, *k;
289*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
290*b30d1939SAndy Fiddaman
291*b30d1939SAndy Fiddaman key = _DTKEY(disc, obj); /* key of object */
292*b30d1939SAndy Fiddaman
293*b30d1939SAndy Fiddaman if(type&(DT_ATMOST|DT_ATLEAST) ) /* find the left-most or right-most element */
294*b30d1939SAndy Fiddaman { list->_left = link->_rght;
295*b30d1939SAndy Fiddaman list->_rght = link->_left;
296*b30d1939SAndy Fiddaman if(type&DT_ATMOST)
297*b30d1939SAndy Fiddaman { while((l = list->_left) )
298*b30d1939SAndy Fiddaman { while((r = l->_rght) ) /* get the max elt of left subtree */
299*b30d1939SAndy Fiddaman LROTATE(l,r);
300*b30d1939SAndy Fiddaman list->_left = l;
301*b30d1939SAndy Fiddaman
302*b30d1939SAndy Fiddaman o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
303*b30d1939SAndy Fiddaman if(_DTCMP(dt, key, k, disc) != 0 )
304*b30d1939SAndy Fiddaman break;
305*b30d1939SAndy Fiddaman else RROTATE(list,l);
306*b30d1939SAndy Fiddaman }
307*b30d1939SAndy Fiddaman }
308*b30d1939SAndy Fiddaman else
309*b30d1939SAndy Fiddaman { while((r = list->_rght) )
310*b30d1939SAndy Fiddaman { while((l = r->_left) ) /* get the min elt of right subtree */
311*b30d1939SAndy Fiddaman RROTATE(r,l);
312*b30d1939SAndy Fiddaman list->_rght = r;
313*b30d1939SAndy Fiddaman
314*b30d1939SAndy Fiddaman o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
315*b30d1939SAndy Fiddaman if(_DTCMP(dt, key, k, disc) != 0 )
316*b30d1939SAndy Fiddaman break;
317*b30d1939SAndy Fiddaman else LROTATE(list,r);
318*b30d1939SAndy Fiddaman }
319*b30d1939SAndy Fiddaman }
320*b30d1939SAndy Fiddaman link->_rght = list->_left;
321*b30d1939SAndy Fiddaman link->_left = list->_rght;
322*b30d1939SAndy Fiddaman return list;
323*b30d1939SAndy Fiddaman }
324*b30d1939SAndy Fiddaman
325*b30d1939SAndy Fiddaman last = list; list->_left = list->_rght = NIL(Dtlink_t*);
326*b30d1939SAndy Fiddaman root = NIL(Dtlink_t*);
327*b30d1939SAndy Fiddaman
328*b30d1939SAndy Fiddaman while(!root && (t = link->_rght) ) /* link->_rght is the left subtree <= obj */
329*b30d1939SAndy Fiddaman { while((r = t->_rght) ) /* make t the maximum element */
330*b30d1939SAndy Fiddaman LROTATE(t,r);
331*b30d1939SAndy Fiddaman
332*b30d1939SAndy Fiddaman o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
333*b30d1939SAndy Fiddaman if(_DTCMP(dt, key, k, disc) != 0 )
334*b30d1939SAndy Fiddaman { link->_rght = t; /* no more of this group in subtree */
335*b30d1939SAndy Fiddaman break;
336*b30d1939SAndy Fiddaman }
337*b30d1939SAndy Fiddaman else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
338*b30d1939SAndy Fiddaman { link->_rght = t->_left; /* found the exact object */
339*b30d1939SAndy Fiddaman root = t;
340*b30d1939SAndy Fiddaman }
341*b30d1939SAndy Fiddaman else /* add t to equal list in an order-preserving manner */
342*b30d1939SAndy Fiddaman { link->_rght = t->_left;
343*b30d1939SAndy Fiddaman t->_left = t->_rght = NIL(Dtlink_t*);
344*b30d1939SAndy Fiddaman if(type&DT_NEXT )
345*b30d1939SAndy Fiddaman { last->_left = t; last = t; }
346*b30d1939SAndy Fiddaman else { t->_rght = list; list = t; }
347*b30d1939SAndy Fiddaman }
348*b30d1939SAndy Fiddaman }
349*b30d1939SAndy Fiddaman
350*b30d1939SAndy Fiddaman while(!root && (t = link->_left) ) /* link->_left is the right subtree >= obj */
351*b30d1939SAndy Fiddaman { while((l = t->_left) ) /* make t the minimum element */
352*b30d1939SAndy Fiddaman RROTATE(t,l);
353*b30d1939SAndy Fiddaman
354*b30d1939SAndy Fiddaman o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
355*b30d1939SAndy Fiddaman if(_DTCMP(dt, key, k, disc) != 0 )
356*b30d1939SAndy Fiddaman { link->_left = t; /* no more of this group in subtree */
357*b30d1939SAndy Fiddaman break;
358*b30d1939SAndy Fiddaman }
359*b30d1939SAndy Fiddaman else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
360*b30d1939SAndy Fiddaman { link->_left = t->_rght; /* found the exact object */
361*b30d1939SAndy Fiddaman root = t;
362*b30d1939SAndy Fiddaman }
363*b30d1939SAndy Fiddaman else /* add t to equal list in an order-preserving manner */
364*b30d1939SAndy Fiddaman { link->_left = t->_rght;
365*b30d1939SAndy Fiddaman t->_left = t->_rght = NIL(Dtlink_t*);
366*b30d1939SAndy Fiddaman if(type&DT_NEXT )
367*b30d1939SAndy Fiddaman { t->_left = list; list = t; }
368*b30d1939SAndy Fiddaman else { last->_rght = t; last = t; }
369*b30d1939SAndy Fiddaman }
370*b30d1939SAndy Fiddaman }
371*b30d1939SAndy Fiddaman
372*b30d1939SAndy Fiddaman if(!root) /* always set a non-trivial root */
373*b30d1939SAndy Fiddaman { root = list;
374*b30d1939SAndy Fiddaman if(type&DT_NEXT)
375*b30d1939SAndy Fiddaman list = list->_left;
376*b30d1939SAndy Fiddaman else list = list->_rght;
377*b30d1939SAndy Fiddaman }
378*b30d1939SAndy Fiddaman
379*b30d1939SAndy Fiddaman if(list) /* add the rest of the equal-list to the proper subtree */
380*b30d1939SAndy Fiddaman { if(type&DT_NEXT)
381*b30d1939SAndy Fiddaman { last->_left = link->_rght;
382*b30d1939SAndy Fiddaman link->_rght = list;
383*b30d1939SAndy Fiddaman }
384*b30d1939SAndy Fiddaman else
385*b30d1939SAndy Fiddaman { last->_rght = link->_left;
386*b30d1939SAndy Fiddaman link->_left = list;
387*b30d1939SAndy Fiddaman }
388*b30d1939SAndy Fiddaman }
389*b30d1939SAndy Fiddaman
390*b30d1939SAndy Fiddaman return root;
391*b30d1939SAndy Fiddaman }
392*b30d1939SAndy Fiddaman
393*b30d1939SAndy Fiddaman #if __STD_C
dttree(Dt_t * dt,Void_t * obj,int type)394*b30d1939SAndy Fiddaman static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
395*b30d1939SAndy Fiddaman #else
396*b30d1939SAndy Fiddaman static Void_t* dttree(dt,obj,type)
397*b30d1939SAndy Fiddaman Dt_t* dt;
398*b30d1939SAndy Fiddaman Void_t* obj;
399*b30d1939SAndy Fiddaman int type;
400*b30d1939SAndy Fiddaman #endif
401*b30d1939SAndy Fiddaman {
402*b30d1939SAndy Fiddaman int cmp;
403*b30d1939SAndy Fiddaman Void_t *o, *k, *key;
404*b30d1939SAndy Fiddaman Dtlink_t *root, *t, *l, *r, *me, link;
405*b30d1939SAndy Fiddaman Dtdisc_t *disc = dt->disc;
406*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
407*b30d1939SAndy Fiddaman
408*b30d1939SAndy Fiddaman type = DTTYPE(dt, type); /* map type for upward compatibility */
409*b30d1939SAndy Fiddaman if(!(type&DT_OPERATIONS) )
410*b30d1939SAndy Fiddaman return NIL(Void_t*);
411*b30d1939SAndy Fiddaman
412*b30d1939SAndy Fiddaman DTSETLOCK(dt);
413*b30d1939SAndy Fiddaman
414*b30d1939SAndy Fiddaman if(type&(DT_FIRST|DT_LAST) )
415*b30d1939SAndy Fiddaman DTRETURN(obj, tfirstlast(dt, type));
416*b30d1939SAndy Fiddaman else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))
417*b30d1939SAndy Fiddaman DTRETURN(obj, tlist(dt, (Dtlink_t*)obj, type));
418*b30d1939SAndy Fiddaman else if(type&DT_CLEAR)
419*b30d1939SAndy Fiddaman DTRETURN(obj, tclear(dt));
420*b30d1939SAndy Fiddaman else if(type&DT_STAT)
421*b30d1939SAndy Fiddaman { toptimize(dt); /* balance tree to avoid deep recursion */
422*b30d1939SAndy Fiddaman DTRETURN(obj, tstat(dt, (Dtstat_t*)obj));
423*b30d1939SAndy Fiddaman }
424*b30d1939SAndy Fiddaman
425*b30d1939SAndy Fiddaman if(!obj) /* from here on, an object prototype is required */
426*b30d1939SAndy Fiddaman DTRETURN(obj, NIL(Void_t*));
427*b30d1939SAndy Fiddaman
428*b30d1939SAndy Fiddaman if(type&DT_RELINK) /* relinking objects after some processing */
429*b30d1939SAndy Fiddaman { me = (Dtlink_t*)obj;
430*b30d1939SAndy Fiddaman obj = _DTOBJ(disc,me);
431*b30d1939SAndy Fiddaman key = _DTKEY(disc,obj);
432*b30d1939SAndy Fiddaman }
433*b30d1939SAndy Fiddaman else
434*b30d1939SAndy Fiddaman { me = NIL(Dtlink_t*);
435*b30d1939SAndy Fiddaman if(type&DT_MATCH) /* no prototype object given, just the key */
436*b30d1939SAndy Fiddaman { key = obj;
437*b30d1939SAndy Fiddaman obj = NIL(Void_t*);
438*b30d1939SAndy Fiddaman }
439*b30d1939SAndy Fiddaman else key = _DTKEY(disc,obj); /* get key from prototype object */
440*b30d1939SAndy Fiddaman }
441*b30d1939SAndy Fiddaman
442*b30d1939SAndy Fiddaman memset(&link, 0, sizeof(link));
443*b30d1939SAndy Fiddaman l = r = &link; /* link._rght(_left) will be LEFT(RIGHT) tree after splaying */
444*b30d1939SAndy Fiddaman if((root = tree->root) && _DTOBJ(disc,root) != obj) /* splay-search for a matching object */
445*b30d1939SAndy Fiddaman { while(1)
446*b30d1939SAndy Fiddaman { o = _DTOBJ(disc,root); k = _DTKEY(disc,o);
447*b30d1939SAndy Fiddaman if((cmp = _DTCMP(dt,key,k,disc)) == 0)
448*b30d1939SAndy Fiddaman break;
449*b30d1939SAndy Fiddaman else if(cmp < 0)
450*b30d1939SAndy Fiddaman { if((t = root->_left) )
451*b30d1939SAndy Fiddaman { o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
452*b30d1939SAndy Fiddaman if((cmp = _DTCMP(dt,key,k,disc)) < 0)
453*b30d1939SAndy Fiddaman { rrotate(root,t);
454*b30d1939SAndy Fiddaman rlink(r,t);
455*b30d1939SAndy Fiddaman if(!(root = t->_left) )
456*b30d1939SAndy Fiddaman break;
457*b30d1939SAndy Fiddaman }
458*b30d1939SAndy Fiddaman else if(cmp == 0)
459*b30d1939SAndy Fiddaman { rlink(r,root);
460*b30d1939SAndy Fiddaman root = t;
461*b30d1939SAndy Fiddaman break;
462*b30d1939SAndy Fiddaman }
463*b30d1939SAndy Fiddaman else /* if(cmp > 0) */
464*b30d1939SAndy Fiddaman { llink(l,t);
465*b30d1939SAndy Fiddaman rlink(r,root);
466*b30d1939SAndy Fiddaman if(!(root = t->_rght) )
467*b30d1939SAndy Fiddaman break;
468*b30d1939SAndy Fiddaman }
469*b30d1939SAndy Fiddaman }
470*b30d1939SAndy Fiddaman else
471*b30d1939SAndy Fiddaman { rlink(r,root);
472*b30d1939SAndy Fiddaman root = NIL(Dtlink_t*);
473*b30d1939SAndy Fiddaman break;
474*b30d1939SAndy Fiddaman }
475*b30d1939SAndy Fiddaman }
476*b30d1939SAndy Fiddaman else /* if(cmp > 0) */
477*b30d1939SAndy Fiddaman { if((t = root->_rght) )
478*b30d1939SAndy Fiddaman { o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
479*b30d1939SAndy Fiddaman if((cmp = _DTCMP(dt,key,k,disc)) > 0)
480*b30d1939SAndy Fiddaman { lrotate(root,t);
481*b30d1939SAndy Fiddaman llink(l,t);
482*b30d1939SAndy Fiddaman if(!(root = t->_rght) )
483*b30d1939SAndy Fiddaman break;
484*b30d1939SAndy Fiddaman }
485*b30d1939SAndy Fiddaman else if(cmp == 0)
486*b30d1939SAndy Fiddaman { llink(l,root);
487*b30d1939SAndy Fiddaman root = t;
488*b30d1939SAndy Fiddaman break;
489*b30d1939SAndy Fiddaman }
490*b30d1939SAndy Fiddaman else /* if(cmp < 0) */
491*b30d1939SAndy Fiddaman { rlink(r,t);
492*b30d1939SAndy Fiddaman llink(l,root);
493*b30d1939SAndy Fiddaman if(!(root = t->_left) )
494*b30d1939SAndy Fiddaman break;
495*b30d1939SAndy Fiddaman }
496*b30d1939SAndy Fiddaman }
497*b30d1939SAndy Fiddaman else
498*b30d1939SAndy Fiddaman { llink(l,root);
499*b30d1939SAndy Fiddaman root = NIL(Dtlink_t*);
500*b30d1939SAndy Fiddaman break;
501*b30d1939SAndy Fiddaman }
502*b30d1939SAndy Fiddaman }
503*b30d1939SAndy Fiddaman }
504*b30d1939SAndy Fiddaman }
505*b30d1939SAndy Fiddaman l->_rght = root ? root->_left : NIL(Dtlink_t*);
506*b30d1939SAndy Fiddaman r->_left = root ? root->_rght : NIL(Dtlink_t*);
507*b30d1939SAndy Fiddaman
508*b30d1939SAndy Fiddaman if(root)
509*b30d1939SAndy Fiddaman { if(dt->meth->type&DT_OBAG ) /* may need to reset root to the right object */
510*b30d1939SAndy Fiddaman { if((type&(DT_ATLEAST|DT_ATMOST)) ||
511*b30d1939SAndy Fiddaman ((type&(DT_NEXT|DT_PREV|DT_REMOVE)) && _DTOBJ(disc,root) != obj) )
512*b30d1939SAndy Fiddaman root = troot(dt, root, &link, obj, type);
513*b30d1939SAndy Fiddaman }
514*b30d1939SAndy Fiddaman
515*b30d1939SAndy Fiddaman if(type&(DT_SEARCH|DT_MATCH|DT_ATMOST|DT_ATLEAST))
516*b30d1939SAndy Fiddaman { has_root: /* reconstitute the tree */
517*b30d1939SAndy Fiddaman root->_left = link._rght;
518*b30d1939SAndy Fiddaman root->_rght = link._left;
519*b30d1939SAndy Fiddaman tree->root = root;
520*b30d1939SAndy Fiddaman DTRETURN(obj, _DTOBJ(disc,root));
521*b30d1939SAndy Fiddaman }
522*b30d1939SAndy Fiddaman else if(type&DT_NEXT)
523*b30d1939SAndy Fiddaman { root->_left = link._rght;
524*b30d1939SAndy Fiddaman root->_rght = NIL(Dtlink_t*);
525*b30d1939SAndy Fiddaman link._rght = root;
526*b30d1939SAndy Fiddaman dt_next:
527*b30d1939SAndy Fiddaman if((root = link._left) )
528*b30d1939SAndy Fiddaman { while((t = root->_left) )
529*b30d1939SAndy Fiddaman RROTATE(root,t);
530*b30d1939SAndy Fiddaman link._left = root->_rght;
531*b30d1939SAndy Fiddaman goto has_root;
532*b30d1939SAndy Fiddaman }
533*b30d1939SAndy Fiddaman else goto no_root;
534*b30d1939SAndy Fiddaman }
535*b30d1939SAndy Fiddaman else if(type&DT_PREV)
536*b30d1939SAndy Fiddaman { root->_rght = link._left;
537*b30d1939SAndy Fiddaman root->_left = NIL(Dtlink_t*);
538*b30d1939SAndy Fiddaman link._left = root;
539*b30d1939SAndy Fiddaman dt_prev:
540*b30d1939SAndy Fiddaman if((root = link._rght) )
541*b30d1939SAndy Fiddaman { while((t = root->_rght) )
542*b30d1939SAndy Fiddaman LROTATE(root,t);
543*b30d1939SAndy Fiddaman link._rght = root->_left;
544*b30d1939SAndy Fiddaman goto has_root;
545*b30d1939SAndy Fiddaman }
546*b30d1939SAndy Fiddaman else goto no_root;
547*b30d1939SAndy Fiddaman }
548*b30d1939SAndy Fiddaman else if(type&DT_REMOVE) /* remove a particular element in the tree */
549*b30d1939SAndy Fiddaman { if(_DTOBJ(disc,root) == obj)
550*b30d1939SAndy Fiddaman goto dt_delete;
551*b30d1939SAndy Fiddaman else
552*b30d1939SAndy Fiddaman { root->_left = link._rght;
553*b30d1939SAndy Fiddaman root->_rght = link._left;
554*b30d1939SAndy Fiddaman tree->root = root;
555*b30d1939SAndy Fiddaman DTRETURN(obj, NIL(Void_t*));
556*b30d1939SAndy Fiddaman }
557*b30d1939SAndy Fiddaman }
558*b30d1939SAndy Fiddaman else if(type&(DT_DELETE|DT_DETACH))
559*b30d1939SAndy Fiddaman { dt_delete: /* remove an object from the dictionary */
560*b30d1939SAndy Fiddaman obj = _DTOBJ(disc,root);
561*b30d1939SAndy Fiddaman _dtfree(dt, root, type);
562*b30d1939SAndy Fiddaman dt->data->size -= 1;
563*b30d1939SAndy Fiddaman goto no_root;
564*b30d1939SAndy Fiddaman }
565*b30d1939SAndy Fiddaman else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
566*b30d1939SAndy Fiddaman { if(dt->meth->type&DT_OSET)
567*b30d1939SAndy Fiddaman { type |= DT_SEARCH; /* for announcement */
568*b30d1939SAndy Fiddaman goto has_root;
569*b30d1939SAndy Fiddaman }
570*b30d1939SAndy Fiddaman else
571*b30d1939SAndy Fiddaman { root->_left = NIL(Dtlink_t*);
572*b30d1939SAndy Fiddaman root->_rght = link._left;
573*b30d1939SAndy Fiddaman link._left = root;
574*b30d1939SAndy Fiddaman goto dt_insert;
575*b30d1939SAndy Fiddaman }
576*b30d1939SAndy Fiddaman }
577*b30d1939SAndy Fiddaman else if(type&DT_RELINK) /* a duplicate */
578*b30d1939SAndy Fiddaman { if(dt->meth->type&DT_OSET)
579*b30d1939SAndy Fiddaman _dtfree(dt, me, DT_DELETE);
580*b30d1939SAndy Fiddaman else
581*b30d1939SAndy Fiddaman { me->_left = NIL(Dtlink_t*);
582*b30d1939SAndy Fiddaman me->_rght = link._left;
583*b30d1939SAndy Fiddaman link._left = me;
584*b30d1939SAndy Fiddaman }
585*b30d1939SAndy Fiddaman goto has_root;
586*b30d1939SAndy Fiddaman }
587*b30d1939SAndy Fiddaman }
588*b30d1939SAndy Fiddaman else /* no matching object, tree has been split to LEFT&RIGHT subtrees */
589*b30d1939SAndy Fiddaman { if(type&(DT_SEARCH|DT_MATCH))
590*b30d1939SAndy Fiddaman { no_root:
591*b30d1939SAndy Fiddaman if(!(l = link._rght) ) /* no LEFT subtree */
592*b30d1939SAndy Fiddaman tree->root = link._left; /* tree is RIGHT tree */
593*b30d1939SAndy Fiddaman else
594*b30d1939SAndy Fiddaman { while((t = l->_rght) ) /* maximize root of LEFT tree */
595*b30d1939SAndy Fiddaman { if(t->_rght)
596*b30d1939SAndy Fiddaman LLSHIFT(l,t);
597*b30d1939SAndy Fiddaman else LROTATE(l,t);
598*b30d1939SAndy Fiddaman }
599*b30d1939SAndy Fiddaman l->_rght = link._left; /* hook RIGHT tree to LEFT root */
600*b30d1939SAndy Fiddaman tree->root = l; /* LEFT tree is now the entire tree */
601*b30d1939SAndy Fiddaman }
602*b30d1939SAndy Fiddaman
603*b30d1939SAndy Fiddaman if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
604*b30d1939SAndy Fiddaman DTRETURN(obj, obj);
605*b30d1939SAndy Fiddaman else DTRETURN(obj, NIL(Void_t*));
606*b30d1939SAndy Fiddaman }
607*b30d1939SAndy Fiddaman else if(type&(DT_NEXT|DT_ATLEAST) )
608*b30d1939SAndy Fiddaman goto dt_next;
609*b30d1939SAndy Fiddaman else if(type&(DT_PREV|DT_ATMOST) )
610*b30d1939SAndy Fiddaman goto dt_prev;
611*b30d1939SAndy Fiddaman else if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
612*b30d1939SAndy Fiddaman { obj = NIL(Void_t*);
613*b30d1939SAndy Fiddaman goto no_root;
614*b30d1939SAndy Fiddaman }
615*b30d1939SAndy Fiddaman else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
616*b30d1939SAndy Fiddaman { dt_insert:
617*b30d1939SAndy Fiddaman if(!(root = _dtmake(dt, obj, type)) )
618*b30d1939SAndy Fiddaman { obj = NIL(Void_t*);
619*b30d1939SAndy Fiddaman goto no_root;
620*b30d1939SAndy Fiddaman }
621*b30d1939SAndy Fiddaman else
622*b30d1939SAndy Fiddaman { dt->data->size += 1;
623*b30d1939SAndy Fiddaman goto has_root;
624*b30d1939SAndy Fiddaman }
625*b30d1939SAndy Fiddaman }
626*b30d1939SAndy Fiddaman else if(type&DT_RELINK)
627*b30d1939SAndy Fiddaman { root = me;
628*b30d1939SAndy Fiddaman goto has_root;
629*b30d1939SAndy Fiddaman }
630*b30d1939SAndy Fiddaman }
631*b30d1939SAndy Fiddaman DTRETURN(obj, NIL(Void_t*));
632*b30d1939SAndy Fiddaman
633*b30d1939SAndy Fiddaman dt_return:
634*b30d1939SAndy Fiddaman DTANNOUNCE(dt,obj,type);
635*b30d1939SAndy Fiddaman DTCLRLOCK(dt);
636*b30d1939SAndy Fiddaman return obj;
637*b30d1939SAndy Fiddaman }
638*b30d1939SAndy Fiddaman
treeevent(Dt_t * dt,int event,Void_t * arg)639*b30d1939SAndy Fiddaman static int treeevent(Dt_t* dt, int event, Void_t* arg)
640*b30d1939SAndy Fiddaman {
641*b30d1939SAndy Fiddaman Dttree_t *tree = (Dttree_t*)dt->data;
642*b30d1939SAndy Fiddaman
643*b30d1939SAndy Fiddaman if(event == DT_OPEN)
644*b30d1939SAndy Fiddaman { if(tree) /* already initialized */
645*b30d1939SAndy Fiddaman return 0;
646*b30d1939SAndy Fiddaman if(!(tree = (Dttree_t*)(*dt->memoryf)(dt, 0, sizeof(Dttree_t), dt->disc)) )
647*b30d1939SAndy Fiddaman { DTERROR(dt, "Error in allocating a tree data structure");
648*b30d1939SAndy Fiddaman return -1;
649*b30d1939SAndy Fiddaman }
650*b30d1939SAndy Fiddaman memset(tree, 0, sizeof(Dttree_t));
651*b30d1939SAndy Fiddaman dt->data = (Dtdata_t*)tree;
652*b30d1939SAndy Fiddaman return 1;
653*b30d1939SAndy Fiddaman }
654*b30d1939SAndy Fiddaman else if(event == DT_CLOSE)
655*b30d1939SAndy Fiddaman { if(!tree)
656*b30d1939SAndy Fiddaman return 0;
657*b30d1939SAndy Fiddaman if(tree->root)
658*b30d1939SAndy Fiddaman (void)tclear(dt);
659*b30d1939SAndy Fiddaman (void)(*dt->memoryf)(dt, (Void_t*)tree, 0, dt->disc);
660*b30d1939SAndy Fiddaman dt->data = NIL(Dtdata_t*);
661*b30d1939SAndy Fiddaman return 0;
662*b30d1939SAndy Fiddaman }
663*b30d1939SAndy Fiddaman else if(event == DT_OPTIMIZE) /* balance the search tree */
664*b30d1939SAndy Fiddaman { toptimize(dt);
665*b30d1939SAndy Fiddaman return 0;
666*b30d1939SAndy Fiddaman }
667*b30d1939SAndy Fiddaman else return 0;
668*b30d1939SAndy Fiddaman }
669*b30d1939SAndy Fiddaman
670*b30d1939SAndy Fiddaman #if _UWIN
671*b30d1939SAndy Fiddaman
dtfinger(Dt_t * dt)672*b30d1939SAndy Fiddaman Void_t* dtfinger(Dt_t* dt)
673*b30d1939SAndy Fiddaman {
674*b30d1939SAndy Fiddaman return (dt && dt->meth && (dt->meth->type & DT_ORDERED)) ? (Void_t*)((Dttree_t*)dt->data)->root : NIL(Void_t*);
675*b30d1939SAndy Fiddaman }
676*b30d1939SAndy Fiddaman
677*b30d1939SAndy Fiddaman #endif
678*b30d1939SAndy Fiddaman
679*b30d1939SAndy Fiddaman /* make this method available */
680*b30d1939SAndy Fiddaman static Dtmethod_t _Dtoset = { dttree, DT_OSET, treeevent, "Dtoset" };
681*b30d1939SAndy Fiddaman static Dtmethod_t _Dtobag = { dttree, DT_OBAG, treeevent, "Dtobag" };
682*b30d1939SAndy Fiddaman __DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
683*b30d1939SAndy Fiddaman __DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
684*b30d1939SAndy Fiddaman
685*b30d1939SAndy Fiddaman /* backwards compatibility */
686*b30d1939SAndy Fiddaman #undef Dttree
687*b30d1939SAndy Fiddaman #if defined(__EXPORT__)
688*b30d1939SAndy Fiddaman __EXPORT__
689*b30d1939SAndy Fiddaman #endif
690*b30d1939SAndy Fiddaman __DEFINE__(Dtmethod_t*,Dttree,&_Dtoset);
691*b30d1939SAndy Fiddaman
692*b30d1939SAndy Fiddaman #ifdef NoF
693*b30d1939SAndy Fiddaman NoF(dttree)
694*b30d1939SAndy Fiddaman #endif
695