1#include "dthdr.h"
2
3/* Flatten a dictionary into a linked list.
4** This may be used when many traversals are likely.
5**
6** Written by Kiem-Phong Vo (5/25/96).
7*/
8
9Dtlink_t* dtflatten(Dt_t* dt)
10{
11 reg Dtlink_t *t, *r, *list, *last, **s, **ends;
12
13 /* already flattened */
14 if(dt->data->type&DT_FLATTEN )
15 return dt->data->here;
16
17 list = last = NIL(Dtlink_t*);
18 if(dt->data->type&(DT_SET|DT_BAG))
19 { for(ends = (s = dt->data->htab) + dt->data->ntab; s < ends; ++s)
20 { if((t = *s) )
21 { if(last)
22 last->right = t;
23 else list = last = t;
24 while(last->right)
25 last = last->right;
26 *s = last;
27 }
28 }
29 }
30 else if(dt->data->type&(DT_LIST|DT_STACK|DT_QUEUE) )
31 list = dt->data->head;
32 else if((r = dt->data->here) ) /*if(dt->data->type&(DT_OSET|DT_OBAG))*/
33 { while((t = r->left) )
34 RROTATE(r,t);
35 for(list = last = r, r = r->right; r; last = r, r = r->right)
36 { if((t = r->left) )
37 { do RROTATE(r,t);
38 while((t = r->left) );
39
40 last->right = r;
41 }
42 }
43 }
44
45 dt->data->here = list;
46 dt->data->type |= DT_FLATTEN;
47
48 return list;
49}
50