usr/src/lib/libast/common/cdt/dttreeset.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 /* Set attributes of a tree.
  25 **
  26 ** Written by Kiem-Phong Vo (09/17/2001)
  27 */
  28
  29 #if __STD_C
  30 static Dtlink_t* treebalance(Dtlink_t* list, int size)
  31 #else
  32 static Dtlink_t* treebalance(list, size)
  33 Dtlink_t*       list;
  34 int             size;
  35 #endif
  36 {
  37         int             n;
  38         Dtlink_t        *l, *mid;
  39
  40         if(size <= 2)
  41                 return list;
  42
  43         for(l = list, n = size/2 - 1; n > 0; n -= 1)
  44                 l = l->right;
  45
  46         mid = l->right; l->right = NIL(Dtlink_t*);
  47         mid->left  = treebalance(list, (n = size/2) );
  48         mid->right = treebalance(mid->right, size - (n + 1));
  49         return mid;
  50 }
  51
  52 #if __STD_C
  53 int dttreeset(Dt_t* dt, int minp, int balance)
  54 #else
  55 int dttreeset(dt, minp, balance)
  56 Dt_t*   dt;
  57 int     minp;
  58 int     balance;
  59 #endif
  60 {
  61         int     size;
  62
  63         if(dt->meth->type != DT_OSET)
  64                 return -1;
  65
  66         size = dtsize(dt);
  67
  68         if(minp < 0)
  69         {       for(minp = 0; minp < DT_MINP; ++minp)
  70                         if((1 << minp) >= size)
  71                                 break;
  72                 if(minp <= DT_MINP-4)   /* use log(size) + 4 */
  73                         minp += 4;
  74         }
  75
  76         if((dt->data->minp = minp + (minp%2)) > DT_MINP)
  77                 dt->data->minp = DT_MINP;
  78
  79         if(balance)
  80                 dt->data->here = treebalance(dtflatten(dt), size);
  81
  82         return 0;
  83 }