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