1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gavl.c - generic AVL tree
6 (C) Copyright 2003-2004 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 *******************************************************************/
26 //#include "ul_utmalloc.h"
31 gavl_hdiff_check(gavl_node_t *node, int mode);
34 #define GAVL_HDIFF_DEBUG(tree, mode) gavl_hdiff_check(tree, mode)
36 #define GAVL_HDIFF_DEBUG(tree, mode)
41 * gavl_first_node - Returns First Node of GAVL Tree
42 * @root: GAVL tree root
44 * Return Value: pointer to the first node of tree according to ordering
47 gavl_first_node(const gavl_root_t *root)
49 gavl_node_t *n=root->root_node;
57 * gavl_last_node - Returns Last Node of GAVL Tree
58 * @root: GAVL tree root
60 * Return Value: pointer to the last node of tree according to ordering
63 gavl_last_node(const gavl_root_t *root)
65 gavl_node_t *n=root->root_node;
73 * gavl_is_empty - Check for Empty GAVL Tree
74 * @root: GAVL tree root
76 * Return Value: returns non-zero value if there is no node in the tree
79 gavl_is_empty(const gavl_root_t *root)
81 return !root->root_node;
85 * gavl_search_node - Search for Node or Place for Node by Key
86 * @root: GAVL tree root
87 * @key: key value searched for
88 * @mode: mode of the search operation
89 * @nodep: pointer to place for storing of pointer to found node
90 * or pointer to node which should be parent of inserted node
92 * Core search routine for GAVL trees
93 * searches in tree starting at @root for node of item
94 * with value of item field at offset @key_off
95 * equal to provided *@key value. Values are compared by function
96 * pointed by *@cmp_fnc field in the tree @root.
97 * Integer @mode modifies search algorithm:
98 * %GAVL_FANY .. finds node of any item with field value *@key,
99 * %GAVL_FFIRST .. finds node of first item with *@key,
100 * %GAVL_FAFTER .. node points after last item with *@key value,
101 * reworded - index points at first item with higher
102 * value of field or after last item
103 * Return Value: Return of nonzero value indicates match found.
104 * If the @mode is ored with %GAVL_FCMP, result of last compare
108 gavl_search_node(const gavl_root_t *root, const void *key,
109 int mode, gavl_node_t **nodep)
116 /*If external int than equivalent to cmp=*(int*)(n)-*(int*)key;*/
117 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
120 }else if((cmp<0)||(mode&GAVL_FAFTER)){
126 if((mode&GAVL_FAFTER)&&!(mode&GAVL_FCMP)){
128 if(p) p=gavl_next_node(p);
132 if(cmp&&!(mode&GAVL_FCMP)){
136 if(mode&GAVL_FFIRST){
138 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
143 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
155 return (mode&GAVL_FCMP)?cmp:1;
159 * gavl_find - Find Item for Provided Key
160 * @root: GAVL tree root
161 * @key: key value searched for
163 * Return Value: pointer to item associated to key value.
166 gavl_find(const gavl_root_t *root, const void *key)
170 ret=gavl_search_node(root, key, GAVL_FANY, &n);
171 if(!ret) return NULL;
172 return gavl_node2item(root,n);
176 * gavl_find_first - Find the First Item with Provided Key Value
177 * @root: GAVL tree root
178 * @key: key value searched for
180 * same as above, but first matching item is found.
181 * Return Value: pointer to the first item associated to key value.
184 gavl_find_first(const gavl_root_t *root, const void *key)
187 n=gavl_find_first_node(root, key);
188 return n?gavl_node2item(root,n):NULL;
192 * gavl_find_after - Find the First Item with Higher Key Value
193 * @root: GAVL tree root
194 * @key: key value searched for
196 * same as above, but points to item with first key value above searched @key.
197 * Return Value: pointer to the first item associated to key value.
200 gavl_find_after(const gavl_root_t *root, const void *key)
203 n=gavl_find_after_node(root, key);
204 return n?gavl_node2item(root,n):NULL;
208 * gavl_insert_node_at - Insert Existing Node to Already Computed Place into GAVL Tree
209 * @root: GAVL tree root
210 * @node: pointer to inserted node
211 * @where: pointer to found parent node
212 * @leftright: left (1) or right (0) branch
214 * Return Value: positive value informs about success
217 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
218 gavl_node_t *where, int leftright)
220 return gavl_insert_primitive_at(&root->root_node, node, where, leftright);
224 * gavl_insert_node - Insert Existing Node into GAVL Tree
225 * @root: GAVL tree root
226 * @node: pointer to inserted node
227 * @mode: if mode is %GAVL_FAFTER, multiple items with same key can
228 * be used, else strict ordering is required
230 * Return Value: positive value informs about success
233 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode)
238 cmp=gavl_search_node(root, gavl_node2key(root, node),
239 (mode|GAVL_FCMP), &where);
240 if((mode!=GAVL_FAFTER) && !cmp) return -1;
241 /*return gavl_insert_node_at(root, node, where, cmp);*/
242 /* insert_primitive called directly for speedup */
243 return gavl_insert_primitive_at(&root->root_node, node, where, cmp);
247 * gavl_insert - Insert New Item into GAVL Tree
248 * @root: GAVL tree root
249 * @item: pointer to inserted item
250 * @mode: if mode is GAVL_FAFTER, multiple items with same key can
251 * be used, else strict ordering is required
253 * Return Value: positive value informs about success, negative
254 * value indicates malloc fail or attempt to insert item
255 * with already defined key.
258 gavl_insert(gavl_root_t *root, void *item, int mode)
261 gavl_node_t *where, *n2add;
263 cmp=gavl_search_node(root, (char*)item+root->key_offs,
264 (mode|GAVL_FCMP), &where);
265 if((mode!=GAVL_FAFTER) && !cmp) return -1;
266 if(root->node_offs<0){
267 n2add=malloc(sizeof(gavl_node_t)+sizeof(void*));
268 if(!n2add) return -1;
269 *(void**)(n2add+1)=item;
271 n2add=(gavl_node_t*)((char*)item+root->node_offs);
273 /*return gavl_insert_node_at(root, n2add, where, cmp);*/
274 /* insert_primitive called directly for speedup */
275 return gavl_insert_primitive_at(&root->root_node, n2add, where, cmp);
279 * gavl_delete_node - Deletes/Unlinks Node from GAVL Tree
280 * @root: GAVL tree root
281 * @node: pointer to deleted node
283 * Return Value: positive value informs about success.
286 gavl_delete_node(gavl_root_t *root, gavl_node_t *node)
288 return gavl_delete_primitive(&root->root_node, node);
292 * gavl_delete - Delete/Unlink Item from GAVL Tree
293 * @root: GAVL tree root
294 * @item: pointer to deleted item
296 * Return Value: positive value informs about success, negative
297 * value indicates that item is not found in tree defined by root
300 gavl_delete(gavl_root_t *root, void *item)
305 if(root->node_offs>=0){
306 n=(gavl_node_t*)((char*)item+root->node_offs);
307 for(p=n; p->parent; p=p->parent);
308 if(p!=root->root_node)
311 if(!gavl_search_node(root, (char*)item+root->key_offs, GAVL_FFIRST, &n))
313 while(gavl_node2item(root,n)!=item){
316 if(root->cmp_fnc(gavl_node2key(root,n),(char*)item+root->key_offs))
320 /*ret=gavl_delete_node(root, n);*/
321 /* delete_primitive called directly for speedup */
322 ret=gavl_delete_primitive(&root->root_node, n);
323 if(root->node_offs<0)
329 * gavl_delete_and_next_node - Delete/Unlink Item from GAVL Tree
330 * @root: GAVL tree root
331 * @node: pointer to actual node which is unlinked from tree
332 * after function call, it can be unalocated or reused
333 * by application code after this call.
335 * This function can be used after call gavl_first_node() for destructive
336 * traversal through the tree, it cannot be combined with gavl_next_node()
337 * or gavl_prev_node() and root is emptied after the end of traversal.
338 * If the tree is used after unsuccessful/unfinished traversal, it
339 * must be balanced again. The height differences are inconsistent in other
340 * case. If traversal could be interrupted, the function gavl_cut_first()
341 * could be better choice.
342 * Return Value: pointer to next node or NULL, when all nodes are deleted
345 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node)
347 gavl_node_t *n, **np;
348 if(!node) node=gavl_first_node(root);
349 /* We are in big troubles if there is left child, somebody misused
350 this function => stop an pray, something bad happens in future */
351 if(node->left) return NULL;
352 if((n=node->parent)){
353 if(n->left==node) np=&n->left;
355 } else if(node==root->root_node) {
358 /* Cross tree arguments or corrupted tree */
363 n->parent=node->parent;
364 while(n->left) n=n->left;
370 /* Again, this cannot happen */
371 if(node->parent->left!=node) return NULL;
375 node->left=node->right=NULL;
380 /*===========================================================*/
381 /* basic types compare functions */
383 int gavl_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT
385 if (*(int*)a>*(int*)b) return 1;
386 if (*(int*)a<*(int*)b) return -1;
390 int gavl_cmp_long(const void *a, const void *b) UL_ATTR_REENTRANT
392 if (*(long*)a>*(long*)b) return 1;
393 if (*(long*)a<*(long*)b) return -1;
397 int gavl_cmp_ptr(const void *a, const void *b) UL_ATTR_REENTRANT
399 if (*(void**)a>*(void**)b) return 1;
400 if (*(void**)a<*(void**)b) return -1;
404 /*===========================================================*/
405 /* support for unbalanced trees */
407 #ifdef GAVL_UNBALANCED_SUPPORT
410 gavl_adjust_hdiff(gavl_node_t *node, int adj)
414 while((p=node->parent)&&adj){
417 /*printf("L%d ",adj);*/
421 if((adj+=hdiff)<=0) break;
424 if(adj<-hdiff) adj=-hdiff;
429 /*printf("R%d ",adj);*/
432 if((adj-=hdiff)<=0) break;
435 if(adj<hdiff) adj=hdiff;
443 /* Partial balance - reduces number of nodes with hdiff >1 or <-1 */
445 gavl_balance_enhance(gavl_node_t **subtree)
449 if(!*subtree) return 0;
451 while(p->left) p=p->left;
454 while(n->left) n=n->left;
459 if(!n || (p==*subtree)){
460 if((p->hdiff>1)||((p->hdiff<-1))){
461 gavl_balance_one(subtree);
467 if((p->hdiff>1)||((p->hdiff<-1))){
468 if(gavl_balance_one(&n->left))
469 gavl_adjust_hdiff(n->left,-1);
474 if((p->hdiff>1)||((p->hdiff<-1))){
475 if(gavl_balance_one(&n->right))
476 gavl_adjust_hdiff(n->right,-1);
487 /* Full tree balance */
489 gavl_balance(gavl_root_t *root)
495 if(!root->root_node) return 0;
496 for(n1=gavl_first_node(root);n1;n1=n2){
497 n2=gavl_delete_and_next_node(root, n1);
503 if(s->left && !s->right){
504 s->right=n1; n1->parent=s;
508 } else if(!s->parent || (s->parent->hdiff>s->hdiff+1)){
510 n1->parent=s->parent;
511 if(s->parent) s->parent->right=n1;
513 n1->hdiff=s->hdiff+1;
518 if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
525 if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
530 if(!n1->right) n1->hdiff=0;
531 else n1->hdiff=-n1->right->hdiff;
533 n1->hdiff+=n1->left->hdiff;
538 if(n2){ n1=n2; break;}
543 if(n1->left==n2) {np=&n1->left; n2=n1->right;}
544 else {np=&n1->right; n2=NULL;}
550 int adj,hdiff, balfl;
552 for(n1=s;n1->right;n1=n1->right);
557 if(n1) np=&n1->right;
562 if(adj>-hdiff) adj=-hdiff;
564 while((*np)->hdiff>1){
565 if(gavl_balance_one(np))
577 * gavl_cut_first - Cut First Item from Tree
578 * @root: GAVL tree root
580 * This enables fast delete of the first item without tree balancing.
581 * The resulting tree is degraded but height differences are kept consistent.
582 * Use of this function can result in height of tree maximally one greater
583 * the tree managed by optimal AVL functions.
584 * Return Value: returns the first item or NULL if the tree is empty
587 gavl_cut_first(gavl_root_t *root)
591 if(!(n=gavl_cut_first_primitive(&root->root_node)))
593 item=gavl_node2item(root,n);
594 if(root->node_offs<0)
599 #endif /*GAVL_UNBALANCED_SUPPORT*/