1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gavl.h - generic AVL tree
6 (C) Copyright 2001 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 *******************************************************************/
27 #include "ul_utdefs.h"
28 #include "ul_itbase.h"
34 /* Add support to work correctly even with unbalamced tree
35 with hdiff out of range <-1,0,+1>, else unbalanced tree
36 results in continuous tree degradation and even fatal errors.
37 This option does not solve errors caused by incorrectly
38 assigned hdiff values.
40 #define GAVL_UNBALANCED_SUPPORT
42 /* function to compare fields of two items */
43 typedef int gavl_cmp_fnc_t(const void *a, const void *b) UL_ATTR_REENTRANT;
46 * struct gavl_node - Structure Representing Node of Generic AVL Tree
47 * @left: pointer to left child or NULL
48 * @right: pointer to right child or NULL
49 * @parent: pointer to parent node, NULL for root
50 * @hdiff: difference of height between left and right child
52 * This structure represents one node in the tree and links @left and @right
53 * to nodes with lower and higher value of order criterion.
54 * Each tree is built from one type of items defined by user.
55 * User can decide to include node structure inside item representation
56 * or GAVL can malloc node structures for each inserted item.
57 * The GAVL allocates memory space with capacity
58 * sizeof(gavl_node_t)+sizeof(void*) in the second case. The item pointer
59 * is stored following node structure (void**)(node+1);
61 typedef struct gavl_node {
62 struct gavl_node *left;
63 struct gavl_node *right;
64 struct gavl_node *parent;
69 * struct gavl_root - Structure Representing Root of Generic AVL Tree
70 * @root_node: pointer to root node of GAVL tree
71 * @node_offs: offset between start of user defined item representation
72 * and included GAVL node structure. If negative value
73 * is stored there, user item does not contain node structure
74 * and GAVL manages standalone ones with item pointers.
75 * @key_offs: offset to compared (ordered) fields in the item representation
76 * @cmp_fnc: function defining order of items by comparing fields at offset
80 typedef struct gavl_root {
81 gavl_node_t *root_node;
84 gavl_cmp_fnc_t *cmp_fnc;
90 #define GAVL_FCMP 0x80
93 gavl_first_node(const gavl_root_t *root);
96 gavl_last_node(const gavl_root_t *root);
99 gavl_next_node(const gavl_node_t *node);
102 gavl_prev_node(const gavl_node_t *node);
107 gavl_is_empty(const gavl_root_t *root);
109 /* Core search routine for GAVL trees
110 searches in "root" for node "node" of item
111 with value of item field at offset "key_offs"
112 equal to "*key". Values are compared by function
114 Integer "mode" modifies search algorithm
115 GAVL_FANY .. finds index of any item with field value "*key"
116 GAVL_FFIRST .. finds index of first item with "*key"
117 GAVL_FAFTER .. index points after last item with "*key" value
118 reworded - index points at first item with higher
119 value of field or after last item
120 Return of nonzero value indicates match found.
121 If the mode is ored with GAVL_FCMP, result of last compare is returned
125 gavl_search_node(const gavl_root_t *root, const void *key,
126 int mode, gavl_node_t **nodep);
128 /* returns first node with associated key field value equal to "*key" or NULL */
129 static inline gavl_node_t *
130 gavl_find_first_node(const gavl_root_t *root, const void *key)
133 gavl_search_node(root, key, GAVL_FFIRST, &node);
137 /* returns first node after node with associated key
138 field value equal to "*key" or NULL */
139 static inline gavl_node_t *
140 gavl_find_after_node(const gavl_root_t *root, const void *key)
143 gavl_search_node(root, key, GAVL_FAFTER, &node);
147 /* returns item with key field value equal to "*key" or NULL */
149 gavl_find(const gavl_root_t *root, const void *key);
151 /* same as above, but first matching item is found */
153 gavl_find_first(const gavl_root_t *root, const void *key);
155 /* same as above, but first nonmatching higher item is found */
157 gavl_find_after(const gavl_root_t *root, const void *key);
161 * gavl_node2item - Conversion from GAVL Tree Node to User Defined Item
162 * @root: GAVL tree root
163 * @node: node belonging to @root GAVL tree
165 * Return Value: pointer to item corresponding to node
168 gavl_node2item(const gavl_root_t *root, const gavl_node_t *node)
170 if(root->node_offs<0) return *(void**)(node+1);
171 return (void*)((char*)node-root->node_offs);
175 * gavl_node2item_safe - Conversion from GAVL Tree Node to User Defined Item
176 * @root: GAVL tree root
177 * @node: node belonging to @root GAVL tree
179 * Return Value: pointer to item corresponding to node
182 gavl_node2item_safe(const gavl_root_t *root, const gavl_node_t *node)
185 return gavl_node2item(root, node);
189 * gavl_node2key - Conversion from GAVL Tree Node to Ordering Key
190 * @root: GAVL tree root
191 * @node: node belonging to @root GAVL tree
193 * Return Value: pointer to key corresponding to node
196 gavl_node2key(const gavl_root_t *root, const gavl_node_t *node)
199 p=(char*)gavl_node2item(root, node);
200 return (void*)(p+root->key_offs);
206 gavl_balance_one(gavl_node_t **subtree);
208 /* This function can be used for defining AVL trees with custom
209 root definition. Use gavl_insert or gavl_insert_node for
212 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
213 gavl_node_t *where, int leftright);
216 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
217 gavl_node_t *where, int leftright);
220 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode);
222 /* insert new item at the right position,
223 "mode" has same meaning as in "gavl_search_node"
224 if mode==0 then strict sorting is required
225 and violation result in ignore of new item
229 gavl_insert(gavl_root_t *root, void *item, int mode);
231 /* delete node from AVL tree */
233 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node);
235 /* delete node from AVL tree */
237 gavl_delete_node(gavl_root_t *root, gavl_node_t *node);
239 /* delete item from AVL tree */
241 gavl_delete(gavl_root_t *root, void *item);
243 /* This function can be used after call gavl_first_node to destructive
244 traversal through the tree, it cannot be combined with gavl_next_node
245 or gavl_prev_node and root is emptied after the end of traversal.
246 If the tree is used after unsuccessful/unfinished traversal, it
247 must be balanced again */
249 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node);
251 /*===========================================================*/
252 /* iterators for generic GAVL type */
257 gavl_root_t *container;
262 gavl_it2item(const gavl_it_t *it)
264 return gavl_node2item_safe(it->container,it->node);
268 gavl_first_it(gavl_root_t *container, gavl_it_t *it)
270 it->container=container;
271 it->node=gavl_first_node(container);
275 gavl_last_it(gavl_root_t *container, gavl_it_t *it)
277 it->container=container;
278 it->node=gavl_last_node(container);
282 gavl_next_it(gavl_it_t *it)
284 if(it->node) it->node=gavl_next_node(it->node);
285 else it->node=gavl_first_node(it->container);
289 gavl_prev_it(gavl_it_t *it)
291 if(it->node) it->node=gavl_prev_node(it->node);
292 else it->node=gavl_last_node(it->container);
296 gavl_is_end_it(gavl_it_t *it)
302 gavl_delete_it(gavl_it_t *it)
305 if(!(n=it->node)) return;
306 it->node=gavl_next_node(it->node);
307 gavl_delete_node(it->container,n);
311 gavl_find_it(gavl_root_t *container, const void *key, gavl_it_t *it)
313 it->container=container;
314 return (it->node=gavl_find_first_node(container, key))!=0;
318 gavl_find_first_it(gavl_root_t *container, const void *key, gavl_it_t *it)
320 it->container=container;
321 return (it->node=gavl_find_first_node(container, key))!=0;
325 gavl_find_after_it(gavl_root_t *container, const void *key, gavl_it_t *it)
327 it->container=container;
328 return (it->node=gavl_find_after_node(container, key))!=0;
331 /* The next implementation of foreaach is elegant, but can not
332 be used in C99 non-conformant C compiler */
335 #define gavl_generic_for_each(item_t, root, ptr) \
336 for(gavl_node_t *__fe_node=gavl_first_node(root);\
337 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node));\
338 __fe_node=gavl_next_node(__fe_node))
340 #define gavl_generic_for_each_rev(item_t, root, ptr) \
341 for(gavl_node_t *__fe_node=gavl_last_node(root);\
342 (ptr=__(item_t*)gavl_node2item_safe(root,__fe_node));\
343 __fe_node=gavl_prev_node(__fe_node))
345 #define gavl_generic_for_each_from(item_t, root, key, ptr) \
346 for(gavl_node_t *__fe_node=gavl_find_first_node(root, key); \
347 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node)); \
348 __fe_node=gavl_next_node(__fe_node))
350 #define gavl_generic_for_each_after(item_t, root, key, ptr) \
351 for(gavl_node_t *__fe_node=gavl_find_after_node(root, key); \
352 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node)); \
353 __fe_node=gavl_next_node(__fe_node))
357 #define gavl_generic_for_each_cut(item_t, root, ptr) \
358 for(;(ptr=(item_t*)gavl_cut_first(root));)
362 /*===========================================================*/
363 /* basic types compare functions */
365 int gavl_cmp_int(const void *a, const void *b) UL_ATTR_REENTRANT;
366 int gavl_cmp_long(const void *a, const void *b) UL_ATTR_REENTRANT;
367 int gavl_cmp_ptr(const void *a, const void *b) UL_ATTR_REENTRANT;
369 /*===========================================================*/
370 /* More functions useful for partially balanced trees */
372 /* Adjust hdiff in parent nodes after change of height of
373 branch starting at node */
375 gavl_adjust_hdiff(gavl_node_t *node, int adj);
377 /* Partial balance - reduces number of nodes with hdiff >1 or <-1,
378 return zero if none unbalanced node is found */
380 gavl_balance_enhance(gavl_node_t **subtree);
382 /* Full tree balance to state correct for AVL tree
383 => hdiff is in range <-1,0,1> */
385 gavl_balance(gavl_root_t *root);
387 /* take and delete first node without balancing but keep tree consistent */
389 gavl_cut_first_primitive(gavl_node_t **root_nodep);
391 /* take and delete first item without balancing but keep tree consistent */
393 gavl_cut_first(gavl_root_t *root);
396 /*===========================================================*/
397 /* Declarations of root fields for typesafe custom trees */
399 /* Root type for GAVL_CUST_NODE_INT_DEC tree declaration */
400 /* implementation uses "ul_gavlcust.h" or ul_gavlrepcust.h" */
401 /* with implementation macro GAVL_CUST_NODE_INT_IMP */
402 /* or GAVL_CUST_NODE_INT_REP_IMP */
403 typedef gavl_node_t * gavl_cust_root_field_t;
405 /* Forward declaration of tree root for GAVL_FLES_INT_DEC */
406 /* function declarations and implementations require */
407 /* inclusion of ul_gavlflesint.h" and GAVL_FLES_INT_IMP */
413 } gavl_fles_int_root_field_t;
415 /*===========================================================*/
416 /* Macrodefinitions to prepare custom fast AVL trees with
417 fast possibly inlined search */
419 /* User must provide his/her own compare routine with
420 int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
422 /* Declaration of new custom tree with internal node */
423 #define GAVL_CUST_NODE_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
424 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
426 static inline cust_item_t * \
427 cust_prefix##_node2item(const cust_root_t *root, const gavl_node_t *node) \
428 {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
430 static inline cust_key_t *\
431 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
432 { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
434 cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
435 cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
436 cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
437 cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
438 cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
439 cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
440 cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
441 cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
442 cust_scope gavl_node_t *cust_prefix##_first_node(const cust_root_t *root);\
443 cust_scope gavl_node_t *cust_prefix##_last_node(const cust_root_t *root);\
446 cust_prefix##_init_detached(cust_item_t *item){\
447 item->cust_item_node.parent=NULL;\
449 static inline cust_item_t *\
450 cust_prefix##_first(const cust_root_t *root)\
452 gavl_node_t *n=cust_prefix##_first_node(root);\
453 return n?cust_prefix##_node2item(root,n):NULL;\
455 static inline cust_item_t *\
456 cust_prefix##_last(const cust_root_t *root)\
458 gavl_node_t *n=cust_prefix##_last_node(root);\
459 return n?cust_prefix##_node2item(root,n):NULL;\
461 static inline cust_item_t *\
462 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
464 gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
465 return n?cust_prefix##_node2item(root,n):NULL;\
467 static inline cust_item_t *\
468 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
470 gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
471 return n?cust_prefix##_node2item(root,n):NULL;\
474 cust_prefix##_is_empty(const cust_root_t *root)\
476 return !root->cust_root_node;\
478 static inline cust_item_t *\
479 cust_prefix##_cut_first(cust_root_t *root)\
481 gavl_node_t *n=gavl_cut_first_primitive(&root->cust_root_node);\
482 return n?cust_prefix##_node2item(root,n):NULL;\
485 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
487 #define GAVL_CUST_NODE_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
488 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
489 GAVL_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
490 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc)
492 #define gavl_cust_for_each(cust_prefix, root, ptr) \
493 for(ptr=cust_prefix##_first(root);ptr;ptr=cust_prefix##_next((root),ptr))
495 #define gavl_cust_for_each_rev(cust_prefix, root, ptr) \
496 for(ptr=cust_prefix##_last(root);ptr;ptr=cust_prefix##_prev((root),ptr))
498 #define gavl_cust_for_each_from(cust_prefix, root, key, ptr) \
499 for(ptr=cust_prefix##_find_first(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
501 #define gavl_cust_for_each_after(cust_prefix, root, key, ptr) \
502 for(ptr=cust_prefix##_find_after(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
504 #define gavl_cust_for_each_cut(cust_prefix, root, ptr) \
505 for(;(ptr=cust_prefix##_cut_first(root));)
511 #endif /* _UL_GAVL_H */