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 /* 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
dtflatten(Dt_t * dt)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