Logo Search packages:      
Sourcecode: ksh version File versions  Download package

dtlist.c

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#include    "dthdr.h"

/*    List, Stack, Queue.
**
**    Written by Kiem-Phong Vo (05/25/96)
*/

#if __STD_C
static Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
#else
static Void_t* dtlist(dt, obj, type)
reg Dt_t*   dt;
reg Void_t* obj;
reg int           type;
#endif
{
      reg int           lk, sz, ky;
      reg Dtcompar_f    cmpf;
      reg Dtdisc_t*     disc;
      reg Dtlink_t      *r, *t;
      reg Void_t  *key, *k;

      UNFLATTEN(dt);
      disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
      dt->type &= ~DT_FOUND;

      if(!obj)
      {     if(type&(DT_LAST|DT_FIRST) )
            {     if((r = dt->data->head) )
                  {     if(type&DT_LAST)
                              r = r->left;
                        dt->data->here = r;
                  }
                  return r ? _DTOBJ(r,lk) : NIL(Void_t*);
            }
            else if(type&(DT_DELETE|DT_DETACH))
            {     if((dt->data->type&DT_LIST) || !(r = dt->data->head))
                        return NIL(Void_t*);
                  else  goto dt_delete;
            }
            else if(type&DT_CLEAR)
            {     if(disc->freef || disc->link < 0)
                  {     for(r = dt->data->head; r; r = t)
                        {     t = r->right;
                              if(disc->freef)
                                    (*disc->freef)(dt,_DTOBJ(r,lk),disc);
                              if(disc->link < 0)
                                    (*dt->memoryf)(dt,(Void_t*)r,0,disc);
                        }
                  }
                  dt->data->head = dt->data->here = NIL(Dtlink_t*);
                  dt->data->size = 0;
                  return NIL(Void_t*);
            }
            else  return NIL(Void_t*);
      }

      if(type&(DT_INSERT|DT_ATTACH))
      {     if(disc->makef && (type&DT_INSERT) &&
               !(obj = (*disc->makef)(dt,obj,disc)) )
                  return NIL(Void_t*);
            if(lk >= 0)
                  r = _DTLNK(obj,lk);
            else
            {     r = (Dtlink_t*)(*dt->memoryf)
                        (dt,NIL(Void_t*),sizeof(Dthold_t),disc);
                  if(r)
                        ((Dthold_t*)r)->obj = obj;
                  else
                  {     if(disc->makef && disc->freef && (type&DT_INSERT))
                              (*disc->freef)(dt,obj,disc);
                        return NIL(Void_t*);
                  }
            }

            if(dt->data->type&DT_LIST)
            {     if((t = dt->data->here) && t != dt->data->head)
                  {     r->left = t->left;
                        t->left->right = r;
                        r->right = t;
                        t->left = r;
                  }
                  else  goto dt_stack;
            }
            else if(dt->data->type&DT_STACK)
            { dt_stack:
                  r->right = t = dt->data->head;
                  if(t)
                  {     r->left = t->left;
                        t->left = r;
                  }
                  else  r->left = r;
                  dt->data->head = r;
            }
            else /* if(dt->data->type&DT_QUEUE) */
            {     if((t = dt->data->head) )
                  {     t->left->right = r;
                        r->left = t->left;
                        t->left = r;
                  }
                  else
                  {     dt->data->head = r;
                        r->left = r;
                  }
                  r->right = NIL(Dtlink_t*);
            }

            if(dt->data->size >= 0)
                  dt->data->size += 1;

            dt->data->here = r;
            return _DTOBJ(r,lk);
      }

      if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
      {     key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
            for(r = dt->data->head; r; r = r->right)
            {     k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
                  if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
                        break;
            }
      }

      if(!r)
            return NIL(Void_t*);
      dt->type |= DT_FOUND;

      if(type&(DT_DELETE|DT_DETACH))
      { dt_delete:
            if(r->right)
                  r->right->left = r->left;
            if(r == (t = dt->data->head) )
            {     dt->data->head = r->right;
                  if(dt->data->head)
                        dt->data->head->left = t->left;
            }
            else
            {     r->left->right = r->right;
                  if(r == t->left)
                        t->left = r->left;
            }

            dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
            dt->data->size -= 1;

            obj = _DTOBJ(r,lk);
            if(disc->freef && (type&DT_DELETE))
                  (*disc->freef)(dt,obj,disc);
            if(disc->link < 0)
                  (*dt->memoryf)(dt,(Void_t*)r,0,disc);
            return obj;
      }
      else if(type&DT_NEXT)
            r = r->right;
      else if(type&DT_PREV)
            r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;

      dt->data->here = r;
      return r ? _DTOBJ(r,lk) : NIL(Void_t*);
}

#ifndef KPVDEL    /* to be remove next round */
#define static 
#endif
static Dtmethod_t _Dtlist  = { dtlist, DT_LIST  };
static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };

__DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
__DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
__DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);

#ifdef NoF
NoF(dtlist)
#endif

Generated by  Doxygen 1.6.0   Back to index