1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2009 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 25 /* Renew the object at the current finger. 26 ** 27 ** Written by Kiem-Phong Vo (5/25/96) 28 */ 29 30 #if __STD_C 31 Void_t* dtrenew(Dt_t* dt, reg Void_t* obj) 32 #else 33 Void_t* dtrenew(dt, obj) 34 Dt_t* dt; 35 reg Void_t* obj; 36 #endif 37 { 38 reg Void_t* key; 39 reg Dtlink_t *e, *t, **s; 40 reg Dtdisc_t* disc = dt->disc; 41 42 UNFLATTEN(dt); 43 44 if(!(e = dt->data->here) || _DTOBJ(e,disc->link) != obj) 45 return NIL(Void_t*); 46 47 if(dt->data->type&(DT_STACK|DT_QUEUE|DT_LIST)) 48 return obj; 49 else if(dt->data->type&(DT_OSET|DT_OBAG) ) 50 { if(!e->right ) /* make left child the new root */ 51 dt->data->here = e->left; 52 else /* make right child the new root */ 53 { dt->data->here = e->right; 54 55 /* merge left subtree to right subtree */ 56 if(e->left) 57 { for(t = e->right; t->left; t = t->left) 58 ; 59 t->left = e->left; 60 } 61 } 62 } 63 else /*if(dt->data->type&(DT_SET|DT_BAG))*/ 64 { s = dt->data->htab + HINDEX(dt->data->ntab,e->hash); 65 if((t = *s) == e) 66 *s = e->right; 67 else 68 { for(; t->right != e; t = t->right) 69 ; 70 t->right = e->right; 71 } 72 key = _DTKEY(obj,disc->key,disc->size); 73 e->hash = _DTHSH(dt,key,disc,disc->size); 74 dt->data->here = NIL(Dtlink_t*); 75 } 76 77 dt->data->size -= 1; 78 return (*dt->meth->searchf)(dt,(Void_t*)e,DT_RENEW) ? obj : NIL(Void_t*); 79 } 80