usr/src/lib/libast/common/cdt/dttree.c

   1 /***********************************************************************
   2 *                                                                      *
   3 *               This software is part of the ast package               *
   4 *          Copyright (c) 1985-2010 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