1 /***********************************************************************
2 * *
3 * This software is part of the BSD package *
4 *Copyright (c) 1978-1996 The Regents of the University of California an*
5 * *
6 * Redistribution and use in source and binary forms, with or *
7 * without modification, are permitted provided that the following *
8 * conditions are met: *
9 * *
10 * 1. Redistributions of source code must retain the above *
11 * copyright notice, this list of conditions and the *
12 * following disclaimer. *
13 * *
14 * 2. Redistributions in binary form must reproduce the above *
15 * copyright notice, this list of conditions and the *
16 * following disclaimer in the documentation and/or other *
17 * materials provided with the distribution. *
18 * *
19 * 3. Neither the name of The Regents of the University of California*
20 * names of its contributors may be used to endorse or *
21 * promote products derived from this software without *
22 * specific prior written permission. *
23 * *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND *
25 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, *
26 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF *
27 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE *
28 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS *
29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
30 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED *
31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON *
33 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, *
34 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY *
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE *
36 * POSSIBILITY OF SUCH DAMAGE. *
37 * *
38 * Redistribution and use in source and binary forms, with or without *
39 * modification, are permitted provided that the following conditions *
40 * are met: *
41 * 1. Redistributions of source code must retain the above copyright *
42 * notice, this list of conditions and the following disclaimer. *
43 * 2. Redistributions in binary form must reproduce the above copyright *
44 * notice, this list of conditions and the following disclaimer in *
45 * the documentation and/or other materials provided with the *
46 * distribution. *
47 * 3. Neither the name of the University nor the names of its *
48 * contributors may be used to endorse or promote products derived *
49 * from this software without specific prior written permission. *
50 * *
51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" *
52 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
53 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
54 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS *
55 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
56 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
57 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF *
58 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND *
59 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, *
60 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT *
61 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF *
62 * SUCH DAMAGE. *
63 * *
64 * Kurt Shoens (UCB) *
65 * gsf *
66 * *
67 ***********************************************************************/
68 #include "dthdr.h"
69
70 /*
71 ** Get statistics of a dictionary
72 **
73 ** Written by Kiem-Phong Vo (7/15/95)
74 */
75
76 #if __STD_C
dttstat(Dtstat_t * ds,Dtlink_t * root,int depth,int * level)77 static void dttstat(Dtstat_t* ds, Dtlink_t* root, int depth, int* level)
78 #else
79 static void dttstat(ds,root,depth,level)
80 Dtstat_t* ds;
81 Dtlink_t* root;
82 int depth;
83 int* level;
84 #endif
85 {
86 if(root->left)
87 dttstat(ds,root->left,depth+1,level);
88 if(root->right)
89 dttstat(ds,root->right,depth+1,level);
90 if(depth > ds->dt_n)
91 ds->dt_n = depth;
92 if(level)
93 level[depth] += 1;
94 }
95
96 #if __STD_C
dthstat(reg Dtdata_t * data,Dtstat_t * ds,reg int * count)97 static void dthstat(reg Dtdata_t* data, Dtstat_t* ds, reg int* count)
98 #else
99 static void dthstat(data, ds, count)
100 reg Dtdata_t* data;
101 Dtstat_t* ds;
102 reg int* count;
103 #endif
104 {
105 reg Dtlink_t* t;
106 reg int n, h;
107
108 for(h = data->ntab-1; h >= 0; --h)
109 { n = 0;
110 for(t = data->htab[h]; t; t = t->right)
111 n += 1;
112 if(count)
113 count[n] += 1;
114 else if(n > 0)
115 { ds->dt_n += 1;
116 if(n > ds->dt_max)
117 ds->dt_max = n;
118 }
119 }
120 }
121
122 #if __STD_C
dtstat(reg Dt_t * dt,Dtstat_t * ds,int all)123 int dtstat(reg Dt_t* dt, Dtstat_t* ds, int all)
124 #else
125 int dtstat(dt, ds, all)
126 reg Dt_t* dt;
127 Dtstat_t* ds;
128 int all;
129 #endif
130 {
131 reg int i;
132 static int *Count, Size;
133
134 UNFLATTEN(dt);
135
136 ds->dt_n = ds->dt_max = 0;
137 ds->dt_count = NIL(int*);
138 ds->dt_size = dtsize(dt);
139 ds->dt_meth = dt->data->type&DT_METHODS;
140
141 if(!all)
142 return 0;
143
144 if(dt->data->type&DT_HASH)
145 { dthstat(dt->data,ds,NIL(int*));
146 if(ds->dt_max+1 > Size)
147 { if(Size > 0)
148 free(Count);
149 if(!(Count = (int*)malloc((ds->dt_max+1)*sizeof(int))) )
150 return -1;
151 Size = ds->dt_max+1;
152 }
153 for(i = ds->dt_max; i >= 0; --i)
154 Count[i] = 0;
155 dthstat(dt->data,ds,Count);
156 }
157 else if(dt->data->type&DT_TREE)
158 { if(dt->data->here)
159 { dttstat(ds,dt->data->here,0,NIL(int*));
160 if(ds->dt_n+1 > Size)
161 { if(Size > 0)
162 free(Count);
163 if(!(Count = (int*)malloc((ds->dt_n+1)*sizeof(int))) )
164 return -1;
165 Size = ds->dt_n+1;
166 }
167
168 for(i = ds->dt_n; i >= 0; --i)
169 Count[i] = 0;
170 dttstat(ds,dt->data->here,0,Count);
171 for(i = ds->dt_n; i >= 0; --i)
172 if(Count[i] > ds->dt_max)
173 ds->dt_max = Count[i];
174 }
175 }
176 ds->dt_count = Count;
177
178 return 0;
179 }
180