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
25 /* Renew the object at the current finger.
26 **
27 ** Written by Kiem-Phong Vo (5/25/96)
28 */
29
30 #if __STD_C
dtrenew(Dt_t * dt,reg Void_t * obj)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