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 *******************************************************************/
25 #include "ul_utmalloc.h"
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)
39 * gavl_first_node - Returns First Node of GAVL Tree
40 * @root: GAVL tree root
42 * Return Value: pointer to the first node of tree according to ordering
45 gavl_first_node(const gavl_root_t *root)
47 gavl_node_t *n=root->root_node;
55 * gavl_last_node - Returns Last Node of GAVL Tree
56 * @root: GAVL tree root
58 * Return Value: pointer to the last node of tree according to ordering
61 gavl_last_node(const gavl_root_t *root)
63 gavl_node_t *n=root->root_node;
71 * gavl_is_empty - Check for Empty GAVL Tree
72 * @root: GAVL tree root
74 * Return Value: returns non-zero value if there is no node in the tree
77 gavl_is_empty(const gavl_root_t *root)
79 return !root->root_node;
83 * gavl_search_node - Search for Node or Place for Node by Key
84 * @root: GAVL tree root
85 * @key: key value searched for
86 * @mode: mode of the search operation
87 * @nodep: pointer to place for storing of pointer to found node
88 * or pointer to node which should be parent of inserted node
90 * Core search routine for GAVL trees
91 * searches in tree starting at @root for node of item
92 * with value of item field at offset @key_off
93 * equal to provided *@key value. Values are compared by function
94 * pointed by *@cmp_fnc field in the tree @root.
95 * Integer @mode modifies search algorithm:
96 * %GAVL_FANY .. finds node of any item with field value *@key,
97 * %GAVL_FFIRST .. finds node of first item with *@key,
98 * %GAVL_FAFTER .. node points after last item with *@key value,
99 * reworded - index points at first item with higher
100 * value of field or after last item
101 * Return Value: Return of nonzero value indicates match found.
102 * If the @mode is ored with %GAVL_FCMP, result of last compare
106 gavl_search_node(const gavl_root_t *root, const void *key,
107 int mode, gavl_node_t **nodep)
114 /*If external int than equivalent to cmp=*(int*)(n)-*(int*)key;*/
115 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
118 }else if((cmp<0)||(mode&GAVL_FAFTER)){
124 if((mode&GAVL_FAFTER)&&!(mode&GAVL_FCMP)){
126 if(p) p=gavl_next_node(p);
130 if(cmp&&!(mode&GAVL_FCMP)){
134 if(mode&GAVL_FFIRST){
136 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
141 cmp=root->cmp_fnc(gavl_node2key(root,n),key);
153 return (mode&GAVL_FCMP)?cmp:1;
157 * gavl_find - Find Item for Provided Key
158 * @root: GAVL tree root
159 * @key: key value searched for
161 * Return Value: pointer to item associated to key value.
164 gavl_find(const gavl_root_t *root, const void *key)
168 ret=gavl_search_node(root, key, GAVL_FANY, &n);
169 if(!ret) return NULL;
170 return gavl_node2item(root,n);
174 * gavl_find_first - Find the First Item with Provided Key Value
175 * @root: GAVL tree root
176 * @key: key value searched for
178 * same as above, but first matching item is found.
179 * Return Value: pointer to the first item associated to key value.
182 gavl_find_first(const gavl_root_t *root, const void *key)
185 n=gavl_find_first_node(root, key);
186 return n?gavl_node2item(root,n):NULL;
190 * gavl_find_after - Find the First Item with Higher Key Value
191 * @root: GAVL tree root
192 * @key: key value searched for
194 * same as above, but points to item with first key value above searched @key.
195 * Return Value: pointer to the first item associated to key value.
198 gavl_find_after(const gavl_root_t *root, const void *key)
201 n=gavl_find_after_node(root, key);
202 return n?gavl_node2item(root,n):NULL;
206 * gavl_insert_node_at - Insert Existing Node to Already Computed Place into GAVL Tree
207 * @root: GAVL tree root
208 * @node: pointer to inserted node
209 * @where: pointer to found parent node
210 * @leftright: left (1) or right (0) branch
212 * Return Value: positive value informs about success
215 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
216 gavl_node_t *where, int leftright)
218 return gavl_insert_primitive_at(&root->root_node, node, where, leftright);
222 * gavl_insert_node - Insert Existing Node into GAVL Tree
223 * @root: GAVL tree root
224 * @node: pointer to inserted node
225 * @mode: if mode is %GAVL_FAFTER, multiple items with same key can
226 * be used, else strict ordering is required
228 * Return Value: positive value informs about success
231 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode)
236 cmp=gavl_search_node(root, gavl_node2key(root, node),
237 (mode|GAVL_FCMP), &where);
238 if((mode!=GAVL_FAFTER) && !cmp) return -1;
239 /*return gavl_insert_node_at(root, node, where, cmp);*/
240 /* insert_primitive called directly for speedup */
241 return gavl_insert_primitive_at(&root->root_node, node, where, cmp);
245 * gavl_insert - Insert New Item into GAVL Tree
246 * @root: GAVL tree root
247 * @item: pointer to inserted item
248 * @mode: if mode is GAVL_FAFTER, multiple items with same key can
249 * be used, else strict ordering is required
251 * Return Value: positive value informs about success, negative
252 * value indicates malloc fail or attempt to insert item
253 * with already defined key.
256 gavl_insert(gavl_root_t *root, void *item, int mode)
259 gavl_node_t *where, *n2add;
261 cmp=gavl_search_node(root, (char*)item+root->key_offs,
262 (mode|GAVL_FCMP), &where);
263 if((mode!=GAVL_FAFTER) && !cmp) return -1;
264 if(root->node_offs<0){
265 n2add=malloc(sizeof(gavl_node_t)+sizeof(void*));
266 if(!n2add) return -1;
267 *(void**)(n2add+1)=item;
269 n2add=(gavl_node_t*)((char*)item+root->node_offs);
271 /*return gavl_insert_node_at(root, n2add, where, cmp);*/
272 /* insert_primitive called directly for speedup */
273 return gavl_insert_primitive_at(&root->root_node, n2add, where, cmp);
277 * gavl_delete_node - Deletes/Unlinks Node from GAVL Tree
278 * @root: GAVL tree root
279 * @node: pointer to deleted node
281 * Return Value: positive value informs about success.
284 gavl_delete_node(gavl_root_t *root, gavl_node_t *node)
286 return gavl_delete_primitive(&root->root_node, node);
290 * gavl_delete - Delete/Unlink Item from GAVL Tree
291 * @root: GAVL tree root
292 * @item: pointer to deleted item
294 * Return Value: positive value informs about success, negative
295 * value indicates that item is not found in tree defined by root
298 gavl_delete(gavl_root_t *root, void *item)
303 if(root->node_offs>=0){
304 n=(gavl_node_t*)((char*)item+root->node_offs);
305 for(p=n; p->parent; p=p->parent);
306 if(p!=root->root_node)
309 if(!gavl_search_node(root, (char*)item+root->key_offs, GAVL_FFIRST, &n))
311 while(gavl_node2item(root,n)!=item){
314 if(root->cmp_fnc(gavl_node2key(root,n),(char*)item+root->key_offs))
318 /*ret=gavl_delete_node(root, n);*/
319 /* delete_primitive called directly for speedup */
320 ret=gavl_delete_primitive(&root->root_node, n);
321 if(root->node_offs<0)
327 * gavl_delete_and_next_node - Delete/Unlink Item from GAVL Tree
328 * @root: GAVL tree root
329 * @node: pointer to actual node which is unlinked from tree
330 * after function call, it can be unalocated or reused
331 * by application code after this call.
333 * This function can be used after call gavl_first_node() for destructive
334 * traversal through the tree, it cannot be combined with gavl_next_node()
335 * or gavl_prev_node() and root is emptied after the end of traversal.
336 * If the tree is used after unsuccessful/unfinished traversal, it
337 * must be balanced again. The height differences are inconsistent in other
338 * case. If traversal could be interrupted, the function gavl_cut_first()
339 * could be better choice.
340 * Return Value: pointer to next node or NULL, when all nodes are deleted
343 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node)
345 gavl_node_t *n, **np;
346 if(!node) node=gavl_first_node(root);
347 /* We are in big troubles if there is left child, somebody misused
348 this function => stop an pray, something bad happens in future */
349 if(node->left) return NULL;
350 if((n=node->parent)){
351 if(n->left==node) np=&n->left;
353 } else if(node==root->root_node) {
356 /* Cross tree arguments or corrupted tree */
361 n->parent=node->parent;
362 while(n->left) n=n->left;
368 /* Again, this cannot happen */
369 if(node->parent->left!=node) return NULL;
373 node->left=node->right=NULL;
378 /*===========================================================*/
379 /* basic types compare functions */
381 int gavl_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT
383 if (*(int*)a>*(int*)b) return 1;
384 if (*(int*)a<*(int*)b) return -1;
388 int gavl_cmp_long(const void *a, const void *b) UL_ATTR_REENTRANT
390 if (*(long*)a>*(long*)b) return 1;
391 if (*(long*)a<*(long*)b) return -1;
395 int gavl_cmp_ptr(const void *a, const void *b) UL_ATTR_REENTRANT
397 if (*(void**)a>*(void**)b) return 1;
398 if (*(void**)a<*(void**)b) return -1;
402 /*===========================================================*/
403 /* support for unbalanced trees */
405 #ifdef GAVL_UNBALANCED_SUPPORT
408 gavl_adjust_hdiff(gavl_node_t *node, int adj)
412 while((p=node->parent)&&adj){
415 /*printf("L%d ",adj);*/
419 if((adj+=hdiff)<=0) break;
422 if(adj<-hdiff) adj=-hdiff;
427 /*printf("R%d ",adj);*/
430 if((adj-=hdiff)<=0) break;
433 if(adj<hdiff) adj=hdiff;
441 /* Partial balance - reduces number of nodes with hdiff >1 or <-1 */
443 gavl_balance_enhance(gavl_node_t **subtree)
447 if(!*subtree) return 0;
449 while(p->left) p=p->left;
452 while(n->left) n=n->left;
457 if(!n || (p==*subtree)){
458 if((p->hdiff>1)||((p->hdiff<-1))){
459 gavl_balance_one(subtree);
465 if((p->hdiff>1)||((p->hdiff<-1))){
466 if(gavl_balance_one(&n->left))
467 gavl_adjust_hdiff(n->left,-1);
472 if((p->hdiff>1)||((p->hdiff<-1))){
473 if(gavl_balance_one(&n->right))
474 gavl_adjust_hdiff(n->right,-1);
485 /* Full tree balance */
487 gavl_balance(gavl_root_t *root)
493 if(!root->root_node) return 0;
494 for(n1=gavl_first_node(root);n1;n1=n2){
495 n2=gavl_delete_and_next_node(root, n1);
501 if(s->left && !s->right){
502 s->right=n1; n1->parent=s;
506 } else if(!s->parent || (s->parent->hdiff>s->hdiff+1)){
508 n1->parent=s->parent;
509 if(s->parent) s->parent->right=n1;
511 n1->hdiff=s->hdiff+1;
516 if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
523 if(s->parent->hdiff<s->hdiff+1) s->parent->hdiff=s->hdiff+1;
528 if(!n1->right) n1->hdiff=0;
529 else n1->hdiff=-n1->right->hdiff;
531 n1->hdiff+=n1->left->hdiff;
536 if(n2){ n1=n2; break;}
541 if(n1->left==n2) {np=&n1->left; n2=n1->right;}
542 else {np=&n1->right; n2=NULL;}
548 int adj,hdiff, balfl;
550 for(n1=s;n1->right;n1=n1->right);
555 if(n1) np=&n1->right;
560 if(adj>-hdiff) adj=-hdiff;
562 while((*np)->hdiff>1){
563 if(gavl_balance_one(np))
575 * gavl_cut_first - Cut First Item from Tree
576 * @root: GAVL tree root
578 * This enables fast delete of the first item without tree balancing.
579 * The resulting tree is degraded but height differences are kept consistent.
580 * Use of this function can result in height of tree maximally one greater
581 * the tree managed by optimal AVL functions.
582 * Return Value: returns the first item or NULL if the tree is empty
585 gavl_cut_first(gavl_root_t *root)
589 if(!(n=gavl_cut_first_primitive(&root->root_node)))
591 item=gavl_node2item(root,n);
592 if(root->node_offs<0)
597 #endif /*GAVL_UNBALANCED_SUPPORT*/