14887Schin /*********************************************************************** 24887Schin * * 34887Schin * This software is part of the ast package * 4*8462SApril.Chin@Sun.COM * Copyright (c) 1985-2008 AT&T Intellectual Property * 54887Schin * and is licensed under the * 64887Schin * Common Public License, Version 1.0 * 7*8462SApril.Chin@Sun.COM * by AT&T Intellectual Property * 84887Schin * * 94887Schin * A copy of the License is available at * 104887Schin * http://www.opensource.org/licenses/cpl1.0.txt * 114887Schin * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 124887Schin * * 134887Schin * Information and Software Systems Research * 144887Schin * AT&T Research * 154887Schin * Florham Park NJ * 164887Schin * * 174887Schin * Glenn Fowler <gsf@research.att.com> * 184887Schin * David Korn <dgk@research.att.com> * 194887Schin * Phong Vo <kpv@research.att.com> * 204887Schin * * 214887Schin ***********************************************************************/ 224887Schin #include "dthdr.h" 234887Schin 244887Schin /* Flatten a dictionary into a linked list. 254887Schin ** This may be used when many traversals are likely. 264887Schin ** 274887Schin ** Written by Kiem-Phong Vo (5/25/96). 284887Schin */ 294887Schin 304887Schin #if __STD_C 314887Schin Dtlink_t* dtflatten(Dt_t* dt) 324887Schin #else 334887Schin Dtlink_t* dtflatten(dt) 344887Schin Dt_t* dt; 354887Schin #endif 364887Schin { 374887Schin reg Dtlink_t *t, *r, *list, *last, **s, **ends; 384887Schin 394887Schin /* already flattened */ 404887Schin if(dt->data->type&DT_FLATTEN ) 414887Schin return dt->data->here; 424887Schin 434887Schin list = last = NIL(Dtlink_t*); 444887Schin if(dt->data->type&(DT_SET|DT_BAG)) 454887Schin { for(ends = (s = dt->data->htab) + dt->data->ntab; s < ends; ++s) 464887Schin { if((t = *s) ) 474887Schin { if(last) 484887Schin last->right = t; 494887Schin else list = last = t; 504887Schin while(last->right) 514887Schin last = last->right; 524887Schin *s = last; 534887Schin } 544887Schin } 554887Schin } 564887Schin else if(dt->data->type&(DT_LIST|DT_STACK|DT_QUEUE) ) 574887Schin list = dt->data->head; 584887Schin else if((r = dt->data->here) ) /*if(dt->data->type&(DT_OSET|DT_OBAG))*/ 594887Schin { while((t = r->left) ) 604887Schin RROTATE(r,t); 614887Schin for(list = last = r, r = r->right; r; last = r, r = r->right) 624887Schin { if((t = r->left) ) 634887Schin { do RROTATE(r,t); 644887Schin while((t = r->left) ); 654887Schin 664887Schin last->right = r; 674887Schin } 684887Schin } 694887Schin } 704887Schin 714887Schin dt->data->here = list; 724887Schin dt->data->type |= DT_FLATTEN; 734887Schin 744887Schin return list; 754887Schin } 76