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);
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);
105 gavl_is_empty(const gavl_root_t *root);
107 /* Core search routine for GAVL trees
108 searches in "root" for node "node" of item
109 with value of item field at offset "key_offs"
110 equal to "*key". Values are compared by function
112 Integer "mode" modifies search algorithm
113 GAVL_FANY .. finds index of any item with field value "*key"
114 GAVL_FFIRST .. finds index of first item with "*key"
115 GAVL_FAFTER .. index points after last item with "*key" value
116 reworded - index points at first item with higher
117 value of field or after last item
118 Return of nonzero value indicates match found.
119 If the mode is ored with GAVL_FCMP, result of last compare is returned
123 gavl_search_node(const gavl_root_t *root, const void *key,
124 int mode, gavl_node_t **nodep);
126 /* returns first node with associated key field value equal to "*key" or NULL */
127 static inline gavl_node_t *
128 gavl_find_first_node(const gavl_root_t *root, const void *key)
131 gavl_search_node(root, key, GAVL_FFIRST, &node);
135 /* returns first node after node with associated key
136 field value equal to "*key" or NULL */
137 static inline gavl_node_t *
138 gavl_find_after_node(const gavl_root_t *root, const void *key)
141 gavl_search_node(root, key, GAVL_FAFTER, &node);
145 /* returns item with key field value equal to "*key" or NULL */
147 gavl_find(const gavl_root_t *root, const void *key);
149 /* same as above, but first matching item is found */
151 gavl_find_first(const gavl_root_t *root, const void *key);
153 /* same as above, but first nonmatching higher item is found */
155 gavl_find_after(const gavl_root_t *root, const void *key);
159 * gavl_node2item - Conversion from GAVL Tree Node to User Defined Item
160 * @root: GAVL tree root
161 * @node: node belonging to @root GAVL tree
163 * Return Value: pointer to item corresponding to node
166 gavl_node2item(const gavl_root_t *root, const gavl_node_t *node)
168 if(root->node_offs<0) return *(void**)(node+1);
169 return (void*)((char*)node-root->node_offs);
173 * gavl_node2item_safe - Conversion from GAVL Tree Node to User Defined Item
174 * @root: GAVL tree root
175 * @node: node belonging to @root GAVL tree
177 * Return Value: pointer to item corresponding to node
180 gavl_node2item_safe(const gavl_root_t *root, const gavl_node_t *node)
183 return gavl_node2item(root, node);
187 * gavl_node2key - Conversion from GAVL Tree Node to Ordering Key
188 * @root: GAVL tree root
189 * @node: node belonging to @root GAVL tree
191 * Return Value: pointer to key corresponding to node
194 gavl_node2key(const gavl_root_t *root, const gavl_node_t *node)
197 p=(char*)gavl_node2item(root, node);
198 return (void*)(p+root->key_offs);
202 gavl_balance_one(gavl_node_t **subtree);
204 /* This function can be used for defining AVL trees with custom
205 root definition. Use gavl_insert or gavl_insert_node for
208 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
209 gavl_node_t *where, int leftright);
212 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
213 gavl_node_t *where, int leftright);
216 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode);
218 /* insert new item at the right position,
219 "mode" has same meaning as in "gavl_search_node"
220 if mode==0 then strict sorting is required
221 and violation result in ignore of new item
225 gavl_insert(gavl_root_t *root, void *item, int mode);
227 /* delete node from AVL tree */
229 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node);
231 /* delete node from AVL tree */
233 gavl_delete_node(gavl_root_t *root, gavl_node_t *node);
235 /* delete item from AVL tree */
237 gavl_delete(gavl_root_t *root, void *item);
239 /* This function can be used after call gavl_first_node to destructive
240 traversal through the tree, it cannot be combined with gavl_next_node
241 or gavl_prev_node and root is emptied after the end of traversal.
242 If the tree is used after unsuccessful/unfinished traversal, it
243 must be balanced again */
245 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node);
247 /*===========================================================*/
248 /* iterators for generic GAVL type */
251 gavl_root_t *container;
256 gavl_it2item(const gavl_it_t *it)
258 return gavl_node2item_safe(it->container,it->node);
262 gavl_first_it(gavl_root_t *container, gavl_it_t *it)
264 it->container=container;
265 it->node=gavl_first_node(container);
269 gavl_last_it(gavl_root_t *container, gavl_it_t *it)
271 it->container=container;
272 it->node=gavl_last_node(container);
276 gavl_next_it(gavl_it_t *it)
278 if(it->node) it->node=gavl_next_node(it->node);
279 else it->node=gavl_first_node(it->container);
283 gavl_prev_it(gavl_it_t *it)
285 if(it->node) it->node=gavl_prev_node(it->node);
286 else it->node=gavl_last_node(it->container);
290 gavl_is_end_it(gavl_it_t *it)
296 gavl_delete_it(gavl_it_t *it)
299 if(!(n=it->node)) return;
300 it->node=gavl_next_node(it->node);
301 gavl_delete_node(it->container,n);
305 gavl_find_it(gavl_root_t *container, void *key, gavl_it_t *it)
307 it->container=container;
308 return (it->node=gavl_find_first_node(container, key))!=0;
312 gavl_find_first_it(gavl_root_t *container, void *key, gavl_it_t *it)
314 it->container=container;
315 return (it->node=gavl_find_first_node(container, key))!=0;
319 gavl_find_after_it(gavl_root_t *container, void *key, gavl_it_t *it)
321 it->container=container;
322 return (it->node=gavl_find_after_node(container, key))!=0;
325 /* The next implementation of foreaach is elegant, but can not
326 be used in C99 non-conformant C compiler */
329 #define gavl_generic_for_each(item_t, root, ptr) \
330 for(gavl_node_t *__fe_node=gavl_first_node(root);\
331 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node));\
332 __fe_node=gavl_next_node(__fe_node))
334 #define gavl_generic_for_each_rev(item_t, root, ptr) \
335 for(gavl_node_t *__fe_node=gavl_last_node(root);\
336 (ptr=__(item_t*)gavl_node2item_safe(root,__fe_node));\
337 __fe_node=gavl_prev_node(__fe_node))
339 #define gavl_generic_for_each_from(item_t, root, key, ptr) \
340 for(gavl_node_t *__fe_node=gavl_find_first_node(root, key); \
341 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node)); \
342 __fe_node=gavl_next_node(__fe_node))
344 #define gavl_generic_for_each_after(item_t, root, key, ptr) \
345 for(gavl_node_t *__fe_node=gavl_find_after_node(root, key); \
346 (ptr=(item_t*)gavl_node2item_safe(root,__fe_node)); \
347 __fe_node=gavl_next_node(__fe_node))
351 #define gavl_generic_for_each_cut(item_t, root, ptr) \
352 for(;(ptr=(item_t*)gavl_cut_first(root));)
354 /*===========================================================*/
355 /* basic types compare functions */
357 int gavl_cmp_int(const void *a, const void *b);
358 int gavl_cmp_long(const void *a, const void *b);
359 int gavl_cmp_ptr(const void *a, const void *b);
361 /*===========================================================*/
362 /* More functions useful for partially balanced trees */
364 /* Adjust hdiff in parent nodes after change of height of
365 branch starting at node */
367 gavl_adjust_hdiff(gavl_node_t *node, int adj);
369 /* Partial balance - reduces number of nodes with hdiff >1 or <-1,
370 return zero if none unbalanced node is found */
372 gavl_balance_enhance(gavl_node_t **subtree);
374 /* Full tree balance to state correct for AVL tree
375 => hdiff is in range <-1,0,1> */
377 gavl_balance(gavl_root_t *root);
379 /* take and delete first node without balancing but keep tree consistent */
381 gavl_cut_first_primitive(gavl_node_t **root_nodep);
383 /* take and delete first item without balancing but keep tree consistent */
385 gavl_cut_first(gavl_root_t *root);
388 /*===========================================================*/
389 /* Declarations of root fields for typesafe custom trees */
391 /* Root type for GAVL_CUST_NODE_INT_DEC tree declaration */
392 /* implementation uses "ul_gavlcust.h" or ul_gavlrepcust.h" */
393 /* with implementation macro GAVL_CUST_NODE_INT_IMP */
394 /* or GAVL_CUST_NODE_INT_REP_IMP */
395 typedef gavl_node_t * gavl_cust_root_field_t;
397 /* Forward declaration of tree root for GAVL_FLES_INT_DEC */
398 /* function declarations and implementations require */
399 /* inclusion of ul_gavlflesint.h" and GAVL_FLES_INT_IMP */
405 } gavl_fles_int_root_field_t;
407 /*===========================================================*/
408 /* Macrodefinitions to prepare custom fast AVL trees with
409 fast possibly inlined search */
411 /* User must provide his/her own compare routine with
412 int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
414 /* Declaration of new custom tree with internal node */
415 #define GAVL_CUST_NODE_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
416 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
418 static inline cust_item_t * \
419 cust_prefix##_node2item(const cust_root_t *root, const gavl_node_t *node) \
420 {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
422 static inline cust_key_t *\
423 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
424 { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
426 void cust_prefix##_init_root_field(cust_root_t *root);\
427 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep);\
428 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key);\
429 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key);\
430 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key);\
431 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
432 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
433 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
434 gavl_node_t *cust_prefix##_first_node(const cust_root_t *root);\
435 gavl_node_t *cust_prefix##_last_node(const cust_root_t *root);\
438 cust_prefix##_init_detached(cust_item_t *item){\
439 item->cust_item_node.parent=NULL;\
441 static inline cust_item_t *\
442 cust_prefix##_first(const cust_root_t *root)\
444 gavl_node_t *n=cust_prefix##_first_node(root);\
445 return n?cust_prefix##_node2item(root,n):NULL;\
447 static inline cust_item_t *\
448 cust_prefix##_last(const cust_root_t *root)\
450 gavl_node_t *n=cust_prefix##_last_node(root);\
451 return n?cust_prefix##_node2item(root,n):NULL;\
453 static inline cust_item_t *\
454 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
456 gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
457 return n?cust_prefix##_node2item(root,n):NULL;\
459 static inline cust_item_t *\
460 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
462 gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
463 return n?cust_prefix##_node2item(root,n):NULL;\
466 cust_prefix##_is_empty(const cust_root_t *root)\
468 return !root->cust_root_node;\
470 static inline cust_item_t *\
471 cust_prefix##_cut_first(cust_root_t *root)\
473 gavl_node_t *n=gavl_cut_first_primitive(&root->cust_root_node);\
474 return n?cust_prefix##_node2item(root,n):NULL;\
477 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
479 #define gavl_cust_for_each(cust_prefix, root, ptr) \
480 for(ptr=cust_prefix##_first(root);ptr;ptr=cust_prefix##_next((root),ptr))
482 #define gavl_cust_for_each_rev(cust_prefix, root, ptr) \
483 for(ptr=cust_prefix##_last(root);ptr;ptr=cust_prefix##_prev((root),ptr))
485 #define gavl_cust_for_each_from(cust_prefix, root, key, ptr) \
486 for(ptr=cust_prefix##_find_first(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
488 #define gavl_cust_for_each_after(cust_prefix, root, key, ptr) \
489 for(ptr=cust_prefix##_find_after(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
491 #define gavl_cust_for_each_cut(cust_prefix, root, ptr) \
492 for(;(ptr=cust_prefix##_cut_first(root));)
498 #endif /* _UL_GAVL_H */