Graphviz  2.41.20170104.0438
dttreeset.c
Go to the documentation of this file.
1 #include "dthdr.h"
2 
3 /* Set attributes of a tree.
4 **
5 ** Written by Kiem-Phong Vo (09/17/2001)
6 */
7 
8 static Dtlink_t* treebalance(Dtlink_t* list, int size)
9 {
10  int n;
11  Dtlink_t *l, *mid;
12 
13  if(size <= 2)
14  return list;
15 
16  for(l = list, n = size/2 - 1; n > 0; n -= 1)
17  l = l->right;
18 
19  mid = l->right; l->right = NIL(Dtlink_t*);
20  mid->left = treebalance(list, (n = size/2) );
21  mid->right = treebalance(mid->right, size - (n + 1));
22  return mid;
23 }
24 
25 int dttreeset(Dt_t* dt, int minp, int balance)
26 {
27  int size;
28 
29  if(dt->meth->type != DT_OSET)
30  return -1;
31 
32  size = dtsize(dt);
33 
34  if(minp < 0)
35  { for(minp = 0; minp < DT_MINP; ++minp)
36  if((1 << minp) >= size)
37  break;
38  if(minp <= DT_MINP-4) /* use log(size) + 4 */
39  minp += 4;
40  }
41 
42  if((dt->data->minp = minp + (minp%2)) > DT_MINP)
43  dt->data->minp = DT_MINP;
44 
45  if(balance)
46  dt->data->here = treebalance(dtflatten(dt), size);
47 
48  return 0;
49 }
int type
Definition: cdt.h:58
#define NIL(t)
Definition: dthdr.h:16
#define DT_OSET
Definition: cdt.h:124
int dtsize(Dt_t *)
Definition: dtsize.c:12
int dttreeset(Dt_t *, int, int)
Definition: dttreeset.c:25
#define DT_MINP
Definition: dthdr.h:33
Dtlink_t * here
Definition: cdt.h:64
Dtmethod_t * meth
Definition: cdt.h:101
Definition: cdt.h:96
int minp
Definition: cdt.h:72
Dtdata_t * data
Definition: cdt.h:99
Dtlink_t * dtflatten(Dt_t *)
Definition: dtflatten.c:9