1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2009 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 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 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 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