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
31Dtlink_t* dtflatten(Dt_t* dt)
32#else
33Dtlink_t* dtflatten(dt)
34Dt_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