1/*********************************************************************** 2* * 3* This software is part of the ast package * 4* Copyright (c) 1985-2011 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 30static Dtlink_t* treebalance(Dtlink_t* list, int size) 31#else 32static Dtlink_t* treebalance(list, size) 33Dtlink_t* list; 34int 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 53int dttreeset(Dt_t* dt, int minp, int balance) 54#else 55int dttreeset(dt, minp, balance) 56Dt_t* dt; 57int minp; 58int 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} 84