1N/A/***********************************************************************
1N/A* *
1N/A* This software is part of the ast package *
1N/A* Copyright (c) 1985-2011 AT&T Intellectual Property *
1N/A* and is licensed under the *
1N/A* Common Public License, Version 1.0 *
1N/A* by AT&T Intellectual Property *
1N/A* *
1N/A* A copy of the License is available at *
1N/A* http://www.opensource.org/licenses/cpl1.0.txt *
1N/A* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
1N/A* *
1N/A* Information and Software Systems Research *
1N/A* AT&T Research *
1N/A* Florham Park NJ *
1N/A* *
1N/A* Glenn Fowler <gsf@research.att.com> *
1N/A* David Korn <dgk@research.att.com> *
1N/A* Phong Vo <kpv@research.att.com> *
1N/A* *
1N/A***********************************************************************/
1N/A#include "dthdr.h"
1N/A
1N/A/* List, Stack, Queue.
1N/A**
1N/A** Written by Kiem-Phong Vo (05/25/96)
1N/A*/
1N/A
1N/A#if __STD_C
1N/Astatic Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
1N/A#else
1N/Astatic Void_t* dtlist(dt, obj, type)
1N/Areg Dt_t* dt;
1N/Areg Void_t* obj;
1N/Areg int type;
1N/A#endif
1N/A{
1N/A reg int lk, sz, ky;
1N/A reg Dtcompar_f cmpf;
1N/A reg Dtdisc_t* disc;
1N/A reg Dtlink_t *r, *t;
1N/A reg Void_t *key, *k;
1N/A
1N/A UNFLATTEN(dt);
1N/A disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
1N/A dt->type &= ~DT_FOUND;
1N/A
1N/A if(!obj)
1N/A { if(type&(DT_LAST|DT_FIRST) )
1N/A { if((r = dt->data->head) )
1N/A { if(type&DT_LAST)
1N/A r = r->left;
1N/A dt->data->here = r;
1N/A }
1N/A return r ? _DTOBJ(r,lk) : NIL(Void_t*);
1N/A }
1N/A else if(type&(DT_DELETE|DT_DETACH))
1N/A { if((dt->data->type&DT_LIST) || !(r = dt->data->head))
1N/A return NIL(Void_t*);
1N/A else goto dt_delete;
1N/A }
1N/A else if(type&DT_CLEAR)
1N/A { if(disc->freef || disc->link < 0)
1N/A { for(r = dt->data->head; r; r = t)
1N/A { t = r->right;
1N/A if(disc->freef)
1N/A (*disc->freef)(dt,_DTOBJ(r,lk),disc);
1N/A if(disc->link < 0)
1N/A (*dt->memoryf)(dt,(Void_t*)r,0,disc);
1N/A }
1N/A }
1N/A dt->data->head = dt->data->here = NIL(Dtlink_t*);
1N/A dt->data->size = 0;
1N/A return NIL(Void_t*);
1N/A }
1N/A else return NIL(Void_t*);
1N/A }
1N/A
1N/A if(type&(DT_INSERT|DT_ATTACH))
1N/A { if(disc->makef && (type&DT_INSERT) &&
1N/A !(obj = (*disc->makef)(dt,obj,disc)) )
1N/A return NIL(Void_t*);
1N/A if(lk >= 0)
1N/A r = _DTLNK(obj,lk);
1N/A else
1N/A { r = (Dtlink_t*)(*dt->memoryf)
1N/A (dt,NIL(Void_t*),sizeof(Dthold_t),disc);
1N/A if(r)
1N/A ((Dthold_t*)r)->obj = obj;
1N/A else
1N/A { if(disc->makef && disc->freef && (type&DT_INSERT))
1N/A (*disc->freef)(dt,obj,disc);
1N/A return NIL(Void_t*);
1N/A }
1N/A }
1N/A
1N/A if(dt->data->type&DT_LIST)
1N/A { if((t = dt->data->here) && t != dt->data->head)
1N/A { r->left = t->left;
1N/A t->left->right = r;
1N/A r->right = t;
1N/A t->left = r;
1N/A }
1N/A else goto dt_stack;
1N/A }
1N/A else if(dt->data->type&DT_STACK)
1N/A { dt_stack:
1N/A r->right = t = dt->data->head;
1N/A if(t)
1N/A { r->left = t->left;
1N/A t->left = r;
1N/A }
1N/A else r->left = r;
1N/A dt->data->head = r;
1N/A }
1N/A else /* if(dt->data->type&DT_QUEUE) */
1N/A { if((t = dt->data->head) )
1N/A { t->left->right = r;
1N/A r->left = t->left;
1N/A t->left = r;
1N/A }
1N/A else
1N/A { dt->data->head = r;
1N/A r->left = r;
1N/A }
1N/A r->right = NIL(Dtlink_t*);
1N/A }
1N/A
1N/A if(dt->data->size >= 0)
1N/A dt->data->size += 1;
1N/A
1N/A dt->data->here = r;
1N/A return _DTOBJ(r,lk);
1N/A }
1N/A
1N/A if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
1N/A { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
1N/A for(r = dt->data->head; r; r = r->right)
1N/A { k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
1N/A if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
1N/A break;
1N/A }
1N/A }
1N/A
1N/A if(!r)
1N/A return NIL(Void_t*);
1N/A dt->type |= DT_FOUND;
1N/A
1N/A if(type&(DT_DELETE|DT_DETACH))
1N/A { dt_delete:
1N/A if(r->right)
1N/A r->right->left = r->left;
1N/A if(r == (t = dt->data->head) )
1N/A { dt->data->head = r->right;
1N/A if(dt->data->head)
1N/A dt->data->head->left = t->left;
1N/A }
1N/A else
1N/A { r->left->right = r->right;
1N/A if(r == t->left)
1N/A t->left = r->left;
1N/A }
1N/A
1N/A dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
1N/A dt->data->size -= 1;
1N/A
1N/A obj = _DTOBJ(r,lk);
1N/A if(disc->freef && (type&DT_DELETE))
1N/A (*disc->freef)(dt,obj,disc);
1N/A if(disc->link < 0)
1N/A (*dt->memoryf)(dt,(Void_t*)r,0,disc);
1N/A return obj;
1N/A }
1N/A else if(type&DT_NEXT)
1N/A r = r->right;
1N/A else if(type&DT_PREV)
1N/A r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;
1N/A
1N/A dt->data->here = r;
1N/A return r ? _DTOBJ(r,lk) : NIL(Void_t*);
1N/A}
1N/A
1N/A#ifndef KPVDEL /* to be remove next round */
1N/A#define static
1N/A#endif
1N/Astatic Dtmethod_t _Dtlist = { dtlist, DT_LIST };
1N/Astatic Dtmethod_t _Dtstack = { dtlist, DT_STACK };
1N/Astatic Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
1N/A
1N/A__DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
1N/A__DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
1N/A__DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
1N/A
1N/A#ifdef NoF
1N/ANoF(dtlist)
1N/A#endif