usr/src/lib/libast/common/cdt/dtstat.c

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