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/*	Get statistics of a dictionary
25**
26**	Written by Kiem-Phong Vo (5/25/96)
27*/
28
29#if __STD_C
30static void dttstat(Dtstat_t* ds, Dtlink_t* root, int depth, int* level)
31#else
32static void dttstat(ds,root,depth,level)
33Dtstat_t*	ds;
34Dtlink_t*	root;
35int		depth;
36int*		level;
37#endif
38{
39	if(root->left)
40		dttstat(ds,root->left,depth+1,level);
41	if(root->right)
42		dttstat(ds,root->right,depth+1,level);
43	if(depth > ds->dt_n)
44		ds->dt_n = depth;
45	if(level)
46		level[depth] += 1;
47}
48
49#if __STD_C
50static void dthstat(reg Dtdata_t* data, Dtstat_t* ds, reg int* count)
51#else
52static void dthstat(data, ds, count)
53reg Dtdata_t*	data;
54Dtstat_t*	ds;
55reg int*	count;
56#endif
57{
58	reg Dtlink_t*	t;
59	reg int		n, h;
60
61	for(h = data->ntab-1; h >= 0; --h)
62	{	n = 0;
63		for(t = data->htab[h]; t; t = t->right)
64			n += 1;
65		if(count)
66			count[n] += 1;
67		else if(n > 0)
68		{	ds->dt_n += 1;
69			if(n > ds->dt_max)
70				ds->dt_max = n;
71		}
72	}
73}
74
75#if __STD_C
76int dtstat(reg Dt_t* dt, Dtstat_t* ds, int all)
77#else
78int dtstat(dt, ds, all)
79reg Dt_t*	dt;
80Dtstat_t*	ds;
81int		all;
82#endif
83{
84	reg int		i;
85	static int	*Count, Size;
86
87	UNFLATTEN(dt);
88
89	ds->dt_n = ds->dt_max = 0;
90	ds->dt_count = NIL(int*);
91	ds->dt_size = dtsize(dt);
92	ds->dt_meth = dt->data->type&DT_METHODS;
93
94	if(!all)
95		return 0;
96
97	if(dt->data->type&(DT_SET|DT_BAG))
98	{	dthstat(dt->data,ds,NIL(int*));
99		if(ds->dt_max+1 > Size)
100		{	if(Size > 0)
101				free(Count);
102			if(!(Count = (int*)malloc((ds->dt_max+1)*sizeof(int))) )
103				return -1;
104			Size = ds->dt_max+1;
105		}
106		for(i = ds->dt_max; i >= 0; --i)
107			Count[i] = 0;
108		dthstat(dt->data,ds,Count);
109	}
110	else if(dt->data->type&(DT_OSET|DT_OBAG))
111	{	if(dt->data->here)
112		{	dttstat(ds,dt->data->here,0,NIL(int*));
113			if(ds->dt_n+1 > Size)
114			{	if(Size > 0)
115					free(Count);
116				if(!(Count = (int*)malloc((ds->dt_n+1)*sizeof(int))) )
117					return -1;
118				Size = ds->dt_n+1;
119			}
120
121			for(i = ds->dt_n; i >= 0; --i)
122				Count[i] = 0;
123			dttstat(ds,dt->data->here,0,Count);
124			for(i = ds->dt_n; i >= 0; --i)
125				if(Count[i] > ds->dt_max)
126					ds->dt_max = Count[i];
127		}
128	}
129	ds->dt_count = Count;
130
131	return 0;
132}
133