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;
81 #if defined(SDCC) || defined(__SDCC)
86 * gavl_balance_one - Balance One Node to Enhance Balance Factor
87 * @subtree: pointer to pointer to node for which balance is enhanced
89 * Return Value: returns nonzero value if height of subtree is lowered by one
92 gavl_balance_one(gavl_node_t **subtree)
95 gavl_node_t *n, *p, *parent;
97 #ifdef GAVL_UNBALANCED_SUPPORT
98 if(!*subtree) return 0;
99 #endif /* GAVL_UNBALANCED_SUPPORT */
100 parent=(*subtree)->parent;
101 shdiff=(*subtree)->hdiff;
106 #ifdef GAVL_UNBALANCED_SUPPORT
108 #endif /* GAVL_UNBALANCED_SUPPORT */
111 /* if(ds>dn) dn1=dn-1; else dn1=ds-2; */
112 (*subtree)->hdiff=shdiff-n->hdiff-1;
114 #ifdef GAVL_UNBALANCED_SUPPORT
118 #endif /* GAVL_UNBALANCED_SUPPORT */
121 n->right=*subtree; (*subtree)->parent=n;
122 (*subtree)->left=p; if(p) p->parent=*subtree;
123 *subtree=n; n->parent=parent;
124 GAVL_HDIFF_DEBUG(*subtree, 0);
127 #ifdef GAVL_UNBALANCED_SUPPORT
129 #endif /* GAVL_UNBALANCED_SUPPORT */
132 /* ds1=ds-2-dp; dn1=dn+1; dp1=min(dp;ds-2); */
133 (*subtree)->hdiff=shdiff-p->hdiff;
135 #ifndef GAVL_UNBALANCED_SUPPORT
137 #else /* GAVL_UNBALANCED_SUPPORT */
138 if (p->hdiff>shdiff) p->hdiff=shdiff;
139 #endif /* GAVL_UNBALANCED_SUPPORT */
141 /* ds1=ds-2; dn1=dn+1-dp; dp1=max(dn+1;dp); */
142 (*subtree)->hdiff=shdiff;
143 shdiff=n->hdiff; /* shdiff reused for nhdiff */
144 n->hdiff=shdiff+1-p->hdiff;
145 #ifndef GAVL_UNBALANCED_SUPPORT
147 #else /* GAVL_UNBALANCED_SUPPORT */
148 if (p->hdiff<=shdiff) p->hdiff=shdiff+1;
149 #endif /* GAVL_UNBALANCED_SUPPORT */
151 n->right=p->left; if(p->left) p->left->parent=n;
152 (*subtree)->left=p->right; if(p->right) p->right->parent=*subtree;
153 p->left=n; n->parent=p;
154 p->right=*subtree; (*subtree)->parent=p;
155 *subtree=p; p->parent=parent;
156 GAVL_HDIFF_DEBUG(*subtree, 0);
163 #ifdef GAVL_UNBALANCED_SUPPORT
165 #endif /* GAVL_UNBALANCED_SUPPORT */
168 /* if(ds<dn) dn1=dn+1; else dn1=ds+2; */
169 (*subtree)->hdiff=shdiff-n->hdiff+1;
171 #ifdef GAVL_UNBALANCED_SUPPORT
175 #endif /* GAVL_UNBALANCED_SUPPORT */
178 n->left=*subtree; (*subtree)->parent=n;
179 (*subtree)->right=p; if(p) p->parent=*subtree;
180 *subtree=n; n->parent=parent;
181 GAVL_HDIFF_DEBUG(*subtree, 0);
184 #ifdef GAVL_UNBALANCED_SUPPORT
186 #endif /* GAVL_UNBALANCED_SUPPORT */
189 /* ds1=ds+2-dp; dn1=dn-1; dp1=max(dp;ds+2); */
190 (*subtree)->hdiff=shdiff-p->hdiff;
192 #ifndef GAVL_UNBALANCED_SUPPORT
194 #else /* GAVL_UNBALANCED_SUPPORT */
195 if (p->hdiff<shdiff) p->hdiff=shdiff;
196 #endif /* GAVL_UNBALANCED_SUPPORT */
198 /* ds1=ds+2; dn1=dn-1-dp; dp1=min(dn-1;dp); */
199 (*subtree)->hdiff=shdiff;
200 shdiff=n->hdiff; /* shdiff reused for nhdiff */
201 n->hdiff=shdiff-1-p->hdiff;
202 #ifndef GAVL_UNBALANCED_SUPPORT
204 #else /* GAVL_UNBALANCED_SUPPORT */
205 if (p->hdiff>=shdiff) p->hdiff=shdiff-1;
206 #endif /* GAVL_UNBALANCED_SUPPORT */
208 n->left=p->right; if(p->right) p->right->parent=n;
209 (*subtree)->right=p->left; if(p->left) p->left->parent=*subtree;
210 p->right=n; n->parent=p;
211 p->left=*subtree; (*subtree)->parent=p;
212 *subtree=p; p->parent=parent;
213 GAVL_HDIFF_DEBUG(*subtree, 0);
218 /*printf("#%d",ret);*/
221 #if defined(SDCC) || defined(__SDCC)
226 * gavl_insert_primitive_at - Low Lewel Routine to Insert Node into Tree
227 * @root_nodep: pointer to pointer to GAVL tree root node
228 * @node: pointer to inserted node
229 * @where: pointer to found parent node
230 * @leftright: left (>=1) or right (<=0) branch
232 * This function can be used for implementing AVL trees with custom
233 * root definition. The value of the selected @left or @right pointer
234 * of provided @node has to be NULL before insert operation,
235 * i.e. node has to be end node in the selected direction.
236 * Return Value: positive value informs about success
239 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
240 gavl_node_t *where, int leftright)
245 node->left=node->right=0;
253 where->left=node; /* where->avl+=1 */
255 where->right=node; /* where->avl-=1 */
259 if(where->left==node){
260 /* break if balance enhanced */
261 if(where->hdiff++ <0) break;
263 /* break if balance enhanced */
264 if(where->hdiff-- >0) break;
272 else if(where->left==node)
276 /* if only balanced trees are supposed, then next operation
277 leads to loop break for all possible cases */
278 if(gavl_balance_one(np)) break;
286 * gavl_delete_primitive - Low Lewel Deletes/Unlinks Node from GAVL Tree
287 * @root_nodep: pointer to pointer to GAVL tree root node
288 * @node: pointer to deleted node
290 * Return Value: positive value informs about success.
293 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node)
302 if(node==*root_nodep){
305 }else if(p->left==node){
317 /* Right child only */
319 node->right->parent=p;
323 /* Left child only */
325 node->left->parent=p;
330 /* Use nearest left node for top of subtree */
331 np=&node->left; n=*np;
332 while(n->right) {np=&n->right; n=*np;}
334 if((*np=n->left)) n->left->parent=n->parent;
335 while(n->parent!=node){
339 if(!gavl_balance_one(&n->right)) {hdiff=0; break;}
341 if(n->hdiff++ ==0) {hdiff=0; break;}
345 if(!gavl_balance_one(&node->left)) hdiff=0;
347 neigh->hdiff=node->hdiff;
349 if(!(neigh->hdiff--)) hdiff=0;
353 /* Use nearest right node for top of subtree */
354 np=&node->right; n=*np;
355 while(n->left) {np=&n->left; n=*np;}
357 if((*np=n->right)) n->right->parent=n->parent;
358 while(n->parent!=node){
362 if(!gavl_balance_one(&n->left)) {hdiff=0; break;}
364 if(n->hdiff-- ==0) {hdiff=0; break;}
368 if(!gavl_balance_one(&node->right)) hdiff=0;
370 neigh->hdiff=node->hdiff;
372 if(!(neigh->hdiff++)) hdiff=0;
375 if((neigh->left=node->left)) neigh->left->parent=neigh;
376 if((neigh->right=node->right)) neigh->right->parent=neigh;
377 neigh->parent=node->parent;
387 gavl_balance_one(root_nodep);
391 if(!gavl_balance_one(&p->left)) break;
392 /* three cases for hdiff--
395 * -1 -> -2 => balance and recurse
398 if(!p->hdiff--) break;
401 if(!gavl_balance_one(&p->right)) break;
402 /* three cases for hdiff++
405 * +1 -> +2 => balance and recurse
408 if(!p->hdiff++) break;
412 if(p) left_fl=(p->left==n);
415 node->parent=node->left=node->right=NULL;
419 #ifdef GAVL_UNBALANCED_SUPPORT
422 * gavl_cut_first_primitive - Low Lewel Routine to Cut First Node from Tree
423 * @root_nodep: pointer to pointer to GAVL tree root node
425 * This enables fast delete of the first node without tree balancing.
426 * The resulting tree is degraded but height differences are kept consistent.
427 * Use of this function can result in height of tree maximally one greater
428 * the tree managed by optimal AVL functions.
429 * Return Value: returns the first node or NULL if the tree is empty
432 gavl_cut_first_primitive(gavl_node_t **root_nodep)
435 gavl_node_t **np=root_nodep;
436 if(!*np) return NULL;
439 if((*np=n->right)) n->right->parent=n->parent;
440 for(p=n->parent;p;p=p->parent)
441 if(p->hdiff++<0) break;
442 n->parent=n->left=n->right=NULL;
446 #endif /*GAVL_UNBALANCED_SUPPORT*/