1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gavlprim.c - primitives for generic AVL tree
6 (C) Copyright 2003 by Pavel Pisa - Originator
8 The uLan utilities library can be used, copied and modified under
10 - GPL - GNU General Public License
11 - LGPL - GNU Lesser General Public License
12 - MPL - Mozilla Public License
13 - and other licenses added by project originators
14 Code can be modified and re-distributed under any combination
15 of the above listed licenses. If contributor does not agree with
16 some of the licenses, he/she can delete appropriate line.
17 Warning, if you delete all lines, you are not allowed to
18 distribute source code and/or binaries utilizing code.
20 See files COPYING and README for details.
22 *******************************************************************/
29 gavl_hdiff_check(gavl_node_t *node, int mode);
32 #define GAVL_HDIFF_DEBUG(tree, mode) gavl_hdiff_check(tree, mode)
34 #define GAVL_HDIFF_DEBUG(tree, mode)
38 * gavl_next_node - Returns Next Node of GAVL Tree
39 * @node: node for which accessor is looked for
41 * Return Value: pointer to next node of tree according to ordering
44 gavl_next_node(const gavl_node_t *node)
48 while(n->left) n=n->left;
51 while((n=node->parent)){
52 if(n->right!=node) break;
60 * gavl_prev_node - Returns Previous Node of GAVL Tree
61 * @node: node for which predecessor is looked for
63 * Return Value: pointer to previous node of tree according to ordering
66 gavl_prev_node(const gavl_node_t *node)
70 while(n->right) n=n->right;
73 while((n=node->parent)){
74 if(n->left!=node) break;
82 * gavl_balance_one - Balance One Node to Enhance Balance Factor
83 * @subtree: pointer to pointer to node for which balance is enhanced
85 * Return Value: returns nonzero value if height of subtree is lowered by one
88 gavl_balance_one(gavl_node_t **subtree)
91 gavl_node_t *n, *p, *parent;
93 #ifdef GAVL_UNBALANCED_SUPPORT
94 if(!*subtree) return 0;
95 #endif /* GAVL_UNBALANCED_SUPPORT */
96 parent=(*subtree)->parent;
97 shdiff=(*subtree)->hdiff;
102 #ifdef GAVL_UNBALANCED_SUPPORT
104 #endif /* GAVL_UNBALANCED_SUPPORT */
107 /* if(ds>dn) dn1=dn-1; else dn1=ds-2; */
108 (*subtree)->hdiff=shdiff-n->hdiff-1;
110 #ifdef GAVL_UNBALANCED_SUPPORT
114 #endif /* GAVL_UNBALANCED_SUPPORT */
117 n->right=*subtree; (*subtree)->parent=n;
118 (*subtree)->left=p; if(p) p->parent=*subtree;
119 *subtree=n; n->parent=parent;
120 GAVL_HDIFF_DEBUG(*subtree, 0);
123 #ifdef GAVL_UNBALANCED_SUPPORT
125 #endif /* GAVL_UNBALANCED_SUPPORT */
128 /* ds1=ds-2-dp; dn1=dn+1; dp1=min(dp;ds-2); */
129 (*subtree)->hdiff=shdiff-p->hdiff;
131 #ifndef GAVL_UNBALANCED_SUPPORT
133 #else /* GAVL_UNBALANCED_SUPPORT */
134 if (p->hdiff>shdiff) p->hdiff=shdiff;
135 #endif /* GAVL_UNBALANCED_SUPPORT */
137 /* ds1=ds-2; dn1=dn+1-dp; dp1=max(dn+1;dp); */
138 (*subtree)->hdiff=shdiff;
139 shdiff=n->hdiff; /* shdiff reused for nhdiff */
140 n->hdiff=shdiff+1-p->hdiff;
141 #ifndef GAVL_UNBALANCED_SUPPORT
143 #else /* GAVL_UNBALANCED_SUPPORT */
144 if (p->hdiff<=shdiff) p->hdiff=shdiff+1;
145 #endif /* GAVL_UNBALANCED_SUPPORT */
147 n->right=p->left; if(p->left) p->left->parent=n;
148 (*subtree)->left=p->right; if(p->right) p->right->parent=*subtree;
149 p->left=n; n->parent=p;
150 p->right=*subtree; (*subtree)->parent=p;
151 *subtree=p; p->parent=parent;
152 GAVL_HDIFF_DEBUG(*subtree, 0);
159 #ifdef GAVL_UNBALANCED_SUPPORT
161 #endif /* GAVL_UNBALANCED_SUPPORT */
164 /* if(ds<dn) dn1=dn+1; else dn1=ds+2; */
165 (*subtree)->hdiff=shdiff-n->hdiff+1;
167 #ifdef GAVL_UNBALANCED_SUPPORT
171 #endif /* GAVL_UNBALANCED_SUPPORT */
174 n->left=*subtree; (*subtree)->parent=n;
175 (*subtree)->right=p; if(p) p->parent=*subtree;
176 *subtree=n; n->parent=parent;
177 GAVL_HDIFF_DEBUG(*subtree, 0);
180 #ifdef GAVL_UNBALANCED_SUPPORT
182 #endif /* GAVL_UNBALANCED_SUPPORT */
185 /* ds1=ds+2-dp; dn1=dn-1; dp1=max(dp;ds+2); */
186 (*subtree)->hdiff=shdiff-p->hdiff;
188 #ifndef GAVL_UNBALANCED_SUPPORT
190 #else /* GAVL_UNBALANCED_SUPPORT */
191 if (p->hdiff<shdiff) p->hdiff=shdiff;
192 #endif /* GAVL_UNBALANCED_SUPPORT */
194 /* ds1=ds+2; dn1=dn-1-dp; dp1=min(dn-1;dp); */
195 (*subtree)->hdiff=shdiff;
196 shdiff=n->hdiff; /* shdiff reused for nhdiff */
197 n->hdiff=shdiff-1-p->hdiff;
198 #ifndef GAVL_UNBALANCED_SUPPORT
200 #else /* GAVL_UNBALANCED_SUPPORT */
201 if (p->hdiff>=shdiff) p->hdiff=shdiff-1;
202 #endif /* GAVL_UNBALANCED_SUPPORT */
204 n->left=p->right; if(p->right) p->right->parent=n;
205 (*subtree)->right=p->left; if(p->left) p->left->parent=*subtree;
206 p->right=n; n->parent=p;
207 p->left=*subtree; (*subtree)->parent=p;
208 *subtree=p; p->parent=parent;
209 GAVL_HDIFF_DEBUG(*subtree, 0);
214 /*printf("#%d",ret);*/
219 * gavl_insert_primitive_at - Low Lewel Routine to Insert Node into Tree
220 * @root_nodep: pointer to pointer to GAVL tree root node
221 * @node: pointer to inserted node
222 * @where: pointer to found parent node
223 * @leftright: left (>=1) or right (<=0) branch
225 * This function can be used for implementing AVL trees with custom
226 * root definition. The value of the selected @left or @right pointer
227 * of provided @node has to be NULL before insert operation,
228 * i.e. node has to be end node in the selected direction.
229 * Return Value: positive value informs about success
232 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
233 gavl_node_t *where, int leftright)
238 node->left=node->right=0;
246 where->left=node; /* where->avl+=1 */
248 where->right=node; /* where->avl-=1 */
252 if(where->left==node){
253 /* break if balance enhanced */
254 if(where->hdiff++ <0) break;
256 /* break if balance enhanced */
257 if(where->hdiff-- >0) break;
265 else if(where->left==node)
269 /* if only balanced trees are supposed, then next operation
270 leads to loop break for all possible cases */
271 if(gavl_balance_one(np)) break;
279 * gavl_delete_primitive - Low Lewel Deletes/Unlinks Node from GAVL Tree
280 * @root_nodep: pointer to pointer to GAVL tree root node
281 * @node: pointer to deleted node
283 * Return Value: positive value informs about success.
286 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node)
295 if(node==*root_nodep){
298 }else if(p->left==node){
310 /* Right child only */
312 node->right->parent=p;
316 /* Left child only */
318 node->left->parent=p;
323 /* Use nearest left node for top of subtree */
324 np=&node->left; n=*np;
325 while(n->right) {np=&n->right; n=*np;}
327 if((*np=n->left)) n->left->parent=n->parent;
328 while(n->parent!=node){
332 if(!gavl_balance_one(&n->right)) {hdiff=0; break;}
334 if(n->hdiff++ ==0) {hdiff=0; break;}
338 if(!gavl_balance_one(&node->left)) hdiff=0;
340 neigh->hdiff=node->hdiff;
342 if(!(neigh->hdiff--)) hdiff=0;
346 /* Use nearest right node for top of subtree */
347 np=&node->right; n=*np;
348 while(n->left) {np=&n->left; n=*np;}
350 if((*np=n->right)) n->right->parent=n->parent;
351 while(n->parent!=node){
355 if(!gavl_balance_one(&n->left)) {hdiff=0; break;}
357 if(n->hdiff-- ==0) {hdiff=0; break;}
361 if(!gavl_balance_one(&node->right)) hdiff=0;
363 neigh->hdiff=node->hdiff;
365 if(!(neigh->hdiff++)) hdiff=0;
368 if((neigh->left=node->left)) neigh->left->parent=neigh;
369 if((neigh->right=node->right)) neigh->right->parent=neigh;
370 neigh->parent=node->parent;
380 gavl_balance_one(root_nodep);
384 if(!gavl_balance_one(&p->left)) break;
385 /* three cases for hdiff--
388 * -1 -> -2 => balance and recurse
391 if(!p->hdiff--) break;
394 if(!gavl_balance_one(&p->right)) break;
395 /* three cases for hdiff++
398 * +1 -> +2 => balance and recurse
401 if(!p->hdiff++) break;
405 if(p) left_fl=(p->left==n);
408 node->parent=node->left=node->right=NULL;
412 #ifdef GAVL_UNBALANCED_SUPPORT
415 * gavl_cut_first_primitive - Low Lewel Routine to Cut First Node from Tree
416 * @root_nodep: pointer to pointer to GAVL tree root node
418 * This enables fast delete of the first node without tree balancing.
419 * The resulting tree is degraded but height differences are kept consistent.
420 * Use of this function can result in height of tree maximally one greater
421 * the tree managed by optimal AVL functions.
422 * Return Value: returns the first node or NULL if the tree is empty
425 gavl_cut_first_primitive(gavl_node_t **root_nodep)
428 gavl_node_t **np=root_nodep;
429 if(!*np) return NULL;
432 if((*np=n->right)) n->right->parent=n->parent;
433 for(p=n->parent;p;p=p->parent)
434 if(p->hdiff++<0) break;
435 n->parent=n->left=n->right=NULL;
439 #endif /*GAVL_UNBALANCED_SUPPORT*/