da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "dthdr.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Get statistics of a dictionary
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin**
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo (5/25/96)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void dttstat(Dtstat_t* ds, Dtlink_t* root, int depth, int* level)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void dttstat(ds,root,depth,level)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtstat_t* ds;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtlink_t* root;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint depth;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint* level;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(root->left)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dttstat(ds,root->left,depth+1,level);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(root->right)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dttstat(ds,root->right,depth+1,level);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(depth > ds->dt_n)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_n = depth;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(level)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin level[depth] += 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void dthstat(reg Dtdata_t* data, Dtstat_t* ds, reg int* count)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void dthstat(data, ds, count)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Dtdata_t* data;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtstat_t* ds;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg int* count;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg Dtlink_t* t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg int n, h;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(h = data->ntab-1; h >= 0; --h)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { n = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(t = data->htab[h]; t; t = t->right)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin n += 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(count)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin count[n] += 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if(n > 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { ds->dt_n += 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(n > ds->dt_max)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_max = n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtstat(reg Dt_t* dt, Dtstat_t* ds, int all)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint dtstat(dt, ds, all)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Dt_t* dt;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDtstat_t* ds;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinint all;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg int i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin static int *Count, Size;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin UNFLATTEN(dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_n = ds->dt_max = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_count = NIL(int*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_size = dtsize(dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_meth = dt->data->type&DT_METHODS;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!all)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(dt->data->type&(DT_SET|DT_BAG))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { dthstat(dt->data,ds,NIL(int*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(ds->dt_max+1 > Size)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(Size > 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(Count);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(Count = (int*)malloc((ds->dt_max+1)*sizeof(int))) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return -1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Size = ds->dt_max+1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(i = ds->dt_max; i >= 0; --i)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Count[i] = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dthstat(dt->data,ds,Count);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if(dt->data->type&(DT_OSET|DT_OBAG))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(dt->data->here)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { dttstat(ds,dt->data->here,0,NIL(int*));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(ds->dt_n+1 > Size)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(Size > 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin free(Count);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(Count = (int*)malloc((ds->dt_n+1)*sizeof(int))) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return -1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Size = ds->dt_n+1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(i = ds->dt_n; i >= 0; --i)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Count[i] = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dttstat(ds,dt->data->here,0,Count);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(i = ds->dt_n; i >= 0; --i)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(Count[i] > ds->dt_max)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_max = Count[i];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ds->dt_count = Count;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}