1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 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 /* Flatten a dictionary into a linked list. 25 ** This may be used when many traversals are likely. 26 ** 27 ** Written by Kiem-Phong Vo (5/25/96). 28 */ 29 30 #if __STD_C 31 Dtlink_t* dtflatten(Dt_t* dt) 32 #else 33 Dtlink_t* dtflatten(dt) 34 Dt_t* dt; 35 #endif 36 { 37 reg Dtlink_t *t, *r, *list, *last, **s, **ends; 38 39 /* already flattened */ 40 if(dt->data->type&DT_FLATTEN ) 41 return dt->data->here; 42 43 list = last = NIL(Dtlink_t*); 44 if(dt->data->type&(DT_SET|DT_BAG)) 45 { for(ends = (s = dt->data->htab) + dt->data->ntab; s < ends; ++s) 46 { if((t = *s) ) 47 { if(last) 48 last->right = t; 49 else list = last = t; 50 while(last->right) 51 last = last->right; 52 *s = last; 53 } 54 } 55 } 56 else if(dt->data->type&(DT_LIST|DT_STACK|DT_QUEUE) ) 57 list = dt->data->head; 58 else if((r = dt->data->here) ) /*if(dt->data->type&(DT_OSET|DT_OBAG))*/ 59 { while((t = r->left) ) 60 RROTATE(r,t); 61 for(list = last = r, r = r->right; r; last = r, r = r->right) 62 { if((t = r->left) ) 63 { do RROTATE(r,t); 64 while((t = r->left) ); 65 66 last->right = r; 67 } 68 } 69 } 70 71 dt->data->here = list; 72 dt->data->type |= DT_FLATTEN; 73 74 return list; 75 } 76