usr/src/lib/libast/common/cdt/dtlist.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 /*      List, Stack, Queue.
  25 **
  26 **      Written by Kiem-Phong Vo (05/25/96)
  27 */
  28
  29 #if __STD_C
  30 static Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
  31 #else
  32 static Void_t* dtlist(dt, obj, type)
  33 reg Dt_t*       dt;
  34 reg Void_t*     obj;
  35 reg int         type;
  36 #endif
  37 {
  38         reg int         lk, sz, ky;
  39         reg Dtcompar_f  cmpf;
  40         reg Dtdisc_t*   disc;
  41         reg Dtlink_t    *r, *t;
  42         reg Void_t      *key, *k;
  43
  44         UNFLATTEN(dt);
  45         disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
  46         dt->type &= ~DT_FOUND;
  47
  48         if(!obj)
  49         {       if(type&(DT_LAST|DT_FIRST) )
  50                 {       if((r = dt->data->head) )
  51                         {       if(type&DT_LAST)
  52                                         r = r->left;
  53                                 dt->data->here = r;
  54                         }
  55                         return r ? _DTOBJ(r,lk) : NIL(Void_t*);
  56                 }
  57                 else if(type&(DT_DELETE|DT_DETACH))
  58                 {       if((dt->data->type&DT_LIST) || !(r = dt->data->head))
  59                                 return NIL(Void_t*);
  60                         else    goto dt_delete;
  61                 }
  62                 else if(type&DT_CLEAR)
  63                 {       if(disc->freef || disc->link < 0)
  64                         {       for(r = dt->data->head; r; r = t)
  65                                 {       t = r->right;
  66                                         if(disc->freef)
  67                                                 (*disc->freef)(dt,_DTOBJ(r,lk),disc);
  68                                         if(disc->link < 0)
  69                                                 (*dt->memoryf)(dt,(Void_t*)r,0,disc);
  70                                 }
  71                         }
  72                         dt->data->head = dt->data->here = NIL(Dtlink_t*);
  73                         dt->data->size = 0;
  74                         return NIL(Void_t*);
  75                 }
  76                 else    return NIL(Void_t*);
  77         }
  78
  79         if(type&(DT_INSERT|DT_ATTACH))
  80         {       if(disc->makef && (type&DT_INSERT) &&
  81                    !(obj = (*disc->makef)(dt,obj,disc)) )
  82                         return NIL(Void_t*);
  83                 if(lk >= 0)
  84                         r = _DTLNK(obj,lk);
  85                 else
  86                 {       r = (Dtlink_t*)(*dt->memoryf)
  87                                 (dt,NIL(Void_t*),sizeof(Dthold_t),disc);
  88                         if(r)
  89                                 ((Dthold_t*)r)->obj = obj;
  90                         else
  91                         {       if(disc->makef && disc->freef && (type&DT_INSERT))
  92                                         (*disc->freef)(dt,obj,disc);
  93                                 return NIL(Void_t*);
  94                         }
  95                 }
  96
  97                 if(dt->data->type&DT_LIST)
  98                 {       if((t = dt->data->here) && t != dt->data->head)
  99                         {       r->left = t->left;
 100                                 t->left->right = r;
 101                                 r->right = t;
 102                                 t->left = r;
 103                         }
 104                         else    goto dt_stack;
 105                 }
 106                 else if(dt->data->type&DT_STACK)
 107                 { dt_stack:
 108                         r->right = t = dt->data->head;
 109                         if(t)
 110                         {       r->left = t->left;
 111                                 t->left = r;
 112                         }
 113                         else    r->left = r;
 114                         dt->data->head = r;
 115                 }
 116                 else /* if(dt->data->type&DT_QUEUE) */
 117                 {       if((t = dt->data->head) )
 118                         {       t->left->right = r;
 119                                 r->left = t->left;
 120                                 t->left = r;
 121                         }
 122                         else
 123                         {       dt->data->head = r;
 124                                 r->left = r;
 125                         }
 126                         r->right = NIL(Dtlink_t*);
 127                 }
 128
 129                 if(dt->data->size >= 0)
 130                         dt->data->size += 1;
 131
 132                 dt->data->here = r;
 133                 return _DTOBJ(r,lk);
 134         }
 135
 136         if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
 137         {       key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
 138                 for(r = dt->data->head; r; r = r->right)
 139                 {       k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
 140                         if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
 141                                 break;
 142                 }
 143         }
 144
 145         if(!r)
 146                 return NIL(Void_t*);
 147         dt->type |= DT_FOUND;
 148
 149         if(type&(DT_DELETE|DT_DETACH))
 150         { dt_delete:
 151                 if(r->right)
 152                         r->right->left = r->left;
 153                 if(r == (t = dt->data->head) )
 154                 {       dt->data->head = r->right;
 155                         if(dt->data->head)
 156                                 dt->data->head->left = t->left;
 157                 }
 158                 else
 159                 {       r->left->right = r->right;
 160                         if(r == t->left)
 161                                 t->left = r->left;
 162                 }
 163
 164                 dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
 165                 dt->data->size -= 1;
 166
 167                 obj = _DTOBJ(r,lk);
 168                 if(disc->freef && (type&DT_DELETE))
 169                         (*disc->freef)(dt,obj,disc);
 170                 if(disc->link < 0)
 171                         (*dt->memoryf)(dt,(Void_t*)r,0,disc);
 172                 return obj;
 173         }
 174         else if(type&DT_NEXT)
 175                 r = r->right;
 176         else if(type&DT_PREV)
 177                 r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;
 178
 179         dt->data->here = r;
 180         return r ? _DTOBJ(r,lk) : NIL(Void_t*);
 181 }
 182
 183 #ifndef KPVDEL  /* to be remove next round */
 184 #define static
 185 #endif
 186 static Dtmethod_t _Dtlist  = { dtlist, DT_LIST  };
 187 static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
 188 static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
 189
 190 __DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
 191 __DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
 192 __DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
 193
 194 #ifdef NoF
 195 NoF(dtlist)
 196 #endif