1#include "dthdr.h"
2
3/* Get statistics of a dictionary
4**
5** Written by Kiem-Phong Vo (5/25/96)
6*/
7
8static void dttstat(Dtstat_t* ds, Dtlink_t* root, int depth, int* level)
9{
10 if(root->left)
11 dttstat(ds,root->left,depth+1,level);
12 if(root->right)
13 dttstat(ds,root->right,depth+1,level);
14 if(depth > ds->dt_n)
15 ds->dt_n = depth;
16 if(level)
17 level[depth] += 1;
18}
19
20static void dthstat(reg Dtdata_t* data, Dtstat_t* ds, reg int* count)
21{
22 reg Dtlink_t* t;
23 reg int n, h;
24
25 for(h = data->ntab-1; h >= 0; --h)
26 { n = 0;
27 for(t = data->htab[h]; t; t = t->right)
28 n += 1;
29 if(count)
30 count[n] += 1;
31 else if(n > 0)
32 { ds->dt_n += 1;
33 if(n > ds->dt_max)
34 ds->dt_max = n;
35 }
36 }
37}
38
39int dtstat(reg Dt_t* dt, Dtstat_t* ds, int all)
40{
41 reg int i;
42 static int *Count, Size;
43
44 UNFLATTEN(dt);
45
46 ds->dt_n = ds->dt_max = 0;
47 ds->dt_count = NIL(int*);
48 ds->dt_size = dtsize(dt);
49 ds->dt_meth = dt->data->type&DT_METHODS;
50
51 if(!all)
52 return 0;
53
54 if(dt->data->type&(DT_SET|DT_BAG))
55 { dthstat(dt->data,ds,NIL(int*));
56 if(ds->dt_max+1 > Size)
57 { if(Size > 0)
58 free(Count);
59 if(!(Count = (int*)malloc((ds->dt_max+1)*sizeof(int))) )
60 return -1;
61 Size = ds->dt_max+1;
62 }
63 for(i = ds->dt_max; i >= 0; --i)
64 Count[i] = 0;
65 dthstat(dt->data,ds,Count);
66 }
67 else if(dt->data->type&(DT_OSET|DT_OBAG))
68 { if(dt->data->here)
69 { dttstat(ds,dt->data->here,0,NIL(int*));
70 if(ds->dt_n+1 > Size)
71 { if(Size > 0)
72 free(Count);
73 if(!(Count = (int*)malloc((ds->dt_n+1)*sizeof(int))) )
74 return -1;
75 Size = ds->dt_n+1;
76 }
77
78 for(i = ds->dt_n; i >= 0; --i)
79 Count[i] = 0;
80 dttstat(ds,dt->data->here,0,Count);
81 for(i = ds->dt_n; i >= 0; --i)
82 if(Count[i] > ds->dt_max)
83 ds->dt_max = Count[i];
84 }
85 }
86 ds->dt_count = Count;
87
88 return 0;
89}
90