1*4887Schin /*********************************************************************** 2*4887Schin * * 3*4887Schin * This software is part of the ast package * 4*4887Schin * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5*4887Schin * and is licensed under the * 6*4887Schin * Common Public License, Version 1.0 * 7*4887Schin * by AT&T Knowledge Ventures * 8*4887Schin * * 9*4887Schin * A copy of the License is available at * 10*4887Schin * http://www.opensource.org/licenses/cpl1.0.txt * 11*4887Schin * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12*4887Schin * * 13*4887Schin * Information and Software Systems Research * 14*4887Schin * AT&T Research * 15*4887Schin * Florham Park NJ * 16*4887Schin * * 17*4887Schin * Glenn Fowler <gsf@research.att.com> * 18*4887Schin * David Korn <dgk@research.att.com> * 19*4887Schin * Phong Vo <kpv@research.att.com> * 20*4887Schin * * 21*4887Schin ***********************************************************************/ 22*4887Schin #include "dthdr.h" 23*4887Schin 24*4887Schin /* Flatten a dictionary into a linked list. 25*4887Schin ** This may be used when many traversals are likely. 26*4887Schin ** 27*4887Schin ** Written by Kiem-Phong Vo (5/25/96). 28*4887Schin */ 29*4887Schin 30*4887Schin #if __STD_C 31*4887Schin Dtlink_t* dtflatten(Dt_t* dt) 32*4887Schin #else 33*4887Schin Dtlink_t* dtflatten(dt) 34*4887Schin Dt_t* dt; 35*4887Schin #endif 36*4887Schin { 37*4887Schin reg Dtlink_t *t, *r, *list, *last, **s, **ends; 38*4887Schin 39*4887Schin /* already flattened */ 40*4887Schin if(dt->data->type&DT_FLATTEN ) 41*4887Schin return dt->data->here; 42*4887Schin 43*4887Schin list = last = NIL(Dtlink_t*); 44*4887Schin if(dt->data->type&(DT_SET|DT_BAG)) 45*4887Schin { for(ends = (s = dt->data->htab) + dt->data->ntab; s < ends; ++s) 46*4887Schin { if((t = *s) ) 47*4887Schin { if(last) 48*4887Schin last->right = t; 49*4887Schin else list = last = t; 50*4887Schin while(last->right) 51*4887Schin last = last->right; 52*4887Schin *s = last; 53*4887Schin } 54*4887Schin } 55*4887Schin } 56*4887Schin else if(dt->data->type&(DT_LIST|DT_STACK|DT_QUEUE) ) 57*4887Schin list = dt->data->head; 58*4887Schin else if((r = dt->data->here) ) /*if(dt->data->type&(DT_OSET|DT_OBAG))*/ 59*4887Schin { while((t = r->left) ) 60*4887Schin RROTATE(r,t); 61*4887Schin for(list = last = r, r = r->right; r; last = r, r = r->right) 62*4887Schin { if((t = r->left) ) 63*4887Schin { do RROTATE(r,t); 64*4887Schin while((t = r->left) ); 65*4887Schin 66*4887Schin last->right = r; 67*4887Schin } 68*4887Schin } 69*4887Schin } 70*4887Schin 71*4887Schin dt->data->here = list; 72*4887Schin dt->data->type |= DT_FLATTEN; 73*4887Schin 74*4887Schin return list; 75*4887Schin } 76