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