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
dttstat(Dtstat_t * ds,Dtlink_t * root,int depth,int * level)30 static void dttstat(Dtstat_t* ds, Dtlink_t* root, int depth, int* level)
31 #else
32 static void dttstat(ds,root,depth,level)
33 Dtstat_t* ds;
34 Dtlink_t* root;
35 int depth;
36 int* 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
dthstat(reg Dtdata_t * data,Dtstat_t * ds,reg int * count)50 static void dthstat(reg Dtdata_t* data, Dtstat_t* ds, reg int* count)
51 #else
52 static void dthstat(data, ds, count)
53 reg Dtdata_t* data;
54 Dtstat_t* ds;
55 reg 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
dtstat(reg Dt_t * dt,Dtstat_t * ds,int all)76 int dtstat(reg Dt_t* dt, Dtstat_t* ds, int all)
77 #else
78 int dtstat(dt, ds, all)
79 reg Dt_t* dt;
80 Dtstat_t* ds;
81 int 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