da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "dthdr.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Renew the object at the current finger.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin**
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo (5/25/96)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtrenew(Dt_t* dt, reg Void_t* obj)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinVoid_t* dtrenew(dt, obj)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dt;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Void_t* obj;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg Void_t* key;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg Dtlink_t *e, *t, **s;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg Dtdisc_t* disc = dt->disc;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin UNFLATTEN(dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(e = dt->data->here) || _DTOBJ(e,disc->link) != obj)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(dt->data->type&(DT_STACK|DT_QUEUE|DT_LIST))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return obj;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if(dt->data->type&(DT_OSET|DT_OBAG) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(!e->right ) /* make left child the new root */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->data->here = e->left;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else /* make right child the new root */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { dt->data->here = e->right;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* merge left subtree to right subtree */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(e->left)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { for(t = e->right; t->left; t = t->left)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin t->left = e->left;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else /*if(dt->data->type&(DT_SET|DT_BAG))*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { s = dt->data->htab + HINDEX(dt->data->ntab,e->hash);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((t = *s) == e)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *s = e->right;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { for(; t->right != e; t = t->right)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin t->right = e->right;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin key = _DTKEY(obj,disc->key,disc->size);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin e->hash = _DTHSH(dt,key,disc,disc->size);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->data->here = NIL(Dtlink_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->data->size -= 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return (*dt->meth->searchf)(dt,(Void_t*)e,DT_RENEW) ? obj : NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}