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