ulut/ul_gavl.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gavl.h     - generic AVL tree
   5
   6   (C) Copyright 2001 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  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.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #ifndef _UL_GAVL_H
  25 #define _UL_GAVL_H
  26
  27 #include "ul_utdefs.h"
  28 #include "ul_itbase.h"
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  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.
  39  */
  40 #define GAVL_UNBALANCED_SUPPORT
  41
  42 /* function to compare fields of two items */
  43 typedef int gavl_cmp_fnc_t(const void *a, const void *b) UL_ATTR_REENTRANT;
  44
  45 /**
  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
  51  *
  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);
  60  */
  61 typedef struct gavl_node {
  62   struct gavl_node *left;
  63   struct gavl_node *right;
  64   struct gavl_node *parent;
  65   int hdiff;
  66 } gavl_node_t;
  67
  68 /**
  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
  77  *              @key_offs.
  78  */
  79
  80 typedef struct gavl_root {
  81   gavl_node_t *root_node;
  82   int node_offs;
  83   int key_offs;
  84   gavl_cmp_fnc_t *cmp_fnc;
  85 } gavl_root_t;
  86
  87 #define GAVL_FANY 0
  88 #define GAVL_FFIRST 1
  89 #define GAVL_FAFTER 2
  90 #define GAVL_FCMP 0x80
  91
  92 gavl_node_t *
  93 gavl_first_node(const gavl_root_t *root);
  94
  95 gavl_node_t *
  96 gavl_last_node(const gavl_root_t *root);
  97
  98 gavl_node_t *
  99 gavl_next_node(const gavl_node_t *node);
 100
 101 gavl_node_t *
 102 gavl_prev_node(const gavl_node_t *node);
 103
 104 #if !defined(SDCC) && !defined(__SDCC)
 105
 106 int
 107 gavl_is_empty(const gavl_root_t *root);
 108
 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
 113    "*cmp_fnc".
 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
 122  */
 123
 124 int
 125 gavl_search_node(const gavl_root_t *root, const void *key,
 126             int mode, gavl_node_t **nodep);
 127
 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)
 131 {
 132   gavl_node_t *node;
 133   gavl_search_node(root, key, GAVL_FFIRST, &node);
 134   return node;
 135 }
 136
 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)
 141 {
 142   gavl_node_t *node;
 143   gavl_search_node(root, key, GAVL_FAFTER, &node);
 144   return node;
 145 }
 146
 147 /* returns item with key field value equal to "*key" or NULL */
 148 void *
 149 gavl_find(const gavl_root_t *root, const void *key);
 150
 151 /* same as above, but first matching item is found */
 152 void *
 153 gavl_find_first(const gavl_root_t *root, const void *key);
 154
 155 /* same as above, but first nonmatching higher item is found */
 156 void *
 157 gavl_find_after(const gavl_root_t *root, const void *key);
 158
 159
 160 /**
 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
 164  *
 165  * Return Value: pointer to item corresponding to node
 166  */
 167 static inline void *
 168 gavl_node2item(const gavl_root_t *root, const gavl_node_t *node)
 169 {
 170   if(root->node_offs<0) return *(void**)(node+1);
 171   return (void*)((char*)node-root->node_offs);
 172 }
 173
 174 /**
 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
 178  *
 179  * Return Value: pointer to item corresponding to node
 180  */
 181 static inline void *
 182 gavl_node2item_safe(const gavl_root_t *root, const gavl_node_t *node)
 183 {
 184   if(!node) return 0;
 185   return gavl_node2item(root, node);
 186 }
 187
 188 /**
 189  * gavl_node2key - Conversion from GAVL Tree Node to Ordering Key
 190  * @root:       GAVL tree root
 191  * @node:       node belonging to @root GAVL tree
 192  *
 193  * Return Value: pointer to key corresponding to node
 194  */
 195 static inline void *
 196 gavl_node2key(const gavl_root_t *root, const gavl_node_t *node)
 197 {
 198   char *p;
 199   p=(char*)gavl_node2item(root, node);
 200   return (void*)(p+root->key_offs);
 201 }
 202
 203 #endif /*SDCC*/
 204
 205 int
 206 gavl_balance_one(gavl_node_t **subtree);
 207
 208 /* This function can be used for defining AVL trees with custom
 209    root definition. Use gavl_insert or gavl_insert_node for
 210    standard trees */
 211 int
 212 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
 213                     gavl_node_t *where, int leftright);
 214
 215 int
 216 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
 217                     gavl_node_t *where, int leftright);
 218
 219 int
 220 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode);
 221
 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
 226    and return value <0
 227  */
 228 int
 229 gavl_insert(gavl_root_t *root, void *item, int mode);
 230
 231 /* delete node from AVL tree */
 232 int
 233 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node);
 234
 235 /* delete node from AVL tree */
 236 int
 237 gavl_delete_node(gavl_root_t *root, gavl_node_t *node);
 238
 239 /* delete item from AVL tree */
 240 int
 241 gavl_delete(gavl_root_t *root, void *item);
 242
 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 */
 248 gavl_node_t *
 249 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node);
 250
 251 /*===========================================================*/
 252 /* iterators for generic GAVL type */
 253
 254 #if !defined(SDCC) && !defined(__SDCC)
 255
 256 typedef struct {
 257   gavl_root_t *container;
 258   gavl_node_t *node;
 259 } gavl_it_t;
 260
 261 static inline void *
 262 gavl_it2item(const gavl_it_t *it)
 263 {
 264   return gavl_node2item_safe(it->container,it->node);
 265 }
 266
 267 static inline void
 268 gavl_first_it(gavl_root_t *container, gavl_it_t *it)
 269 {
 270   it->container=container;
 271   it->node=gavl_first_node(container);
 272 }
 273
 274 static inline void
 275 gavl_last_it(gavl_root_t *container, gavl_it_t *it)
 276 {
 277   it->container=container;
 278   it->node=gavl_last_node(container);
 279 }
 280
 281 static inline void
 282 gavl_next_it(gavl_it_t *it)
 283 {
 284   if(it->node) it->node=gavl_next_node(it->node);
 285   else it->node=gavl_first_node(it->container);
 286 }
 287
 288 static inline void
 289 gavl_prev_it(gavl_it_t *it)
 290 {
 291   if(it->node) it->node=gavl_prev_node(it->node);
 292   else it->node=gavl_last_node(it->container);
 293 }
 294
 295 static inline int
 296 gavl_is_end_it(gavl_it_t *it)
 297 {
 298   return !it->node;
 299 }
 300
 301 static inline void
 302 gavl_delete_it(gavl_it_t *it)
 303 {
 304   gavl_node_t *n;
 305   if(!(n=it->node)) return;
 306   it->node=gavl_next_node(it->node);
 307   gavl_delete_node(it->container,n);
 308 }
 309
 310 static inline int
 311 gavl_find_it(gavl_root_t *container, const void *key, gavl_it_t *it)
 312 {
 313   it->container=container;
 314   return (it->node=gavl_find_first_node(container, key))!=0;
 315 }
 316
 317 static inline int
 318 gavl_find_first_it(gavl_root_t *container, const void *key, gavl_it_t *it)
 319 {
 320   it->container=container;
 321   return (it->node=gavl_find_first_node(container, key))!=0;
 322 }
 323
 324 static inline int
 325 gavl_find_after_it(gavl_root_t *container, const void *key, gavl_it_t *it)
 326 {
 327   it->container=container;
 328   return (it->node=gavl_find_after_node(container, key))!=0;
 329 }
 330
 331 /* The next implementation of foreaach is elegant, but can not
 332    be used in C99 non-conformant C compiler */
 333 #ifdef WITH_C99
 334
 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))
 339
 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))
 344
 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))
 349
 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))
 354
 355 #endif /*WITH_C99*/
 356
 357 #define gavl_generic_for_each_cut(item_t, root, ptr) \
 358         for(;(ptr=(item_t*)gavl_cut_first(root));)
 359
 360 #endif /*SDCC*/
 361
 362 /*===========================================================*/
 363 /* basic types compare functions */
 364
 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;
 368
 369 /*===========================================================*/
 370 /* More functions useful for partially balanced trees */
 371
 372 /* Adjust hdiff in parent nodes after change of height of
 373    branch starting at node */
 374 int
 375 gavl_adjust_hdiff(gavl_node_t *node, int adj);
 376
 377 /* Partial balance - reduces number of nodes with hdiff >1 or <-1,
 378    return zero if none unbalanced node is found */
 379 int
 380 gavl_balance_enhance(gavl_node_t **subtree);
 381
 382 /* Full tree balance to state correct for AVL tree
 383    => hdiff is in range <-1,0,1> */
 384 int
 385 gavl_balance(gavl_root_t *root);
 386
 387 /* take and delete first node without balancing but keep tree consistent */
 388 gavl_node_t *
 389 gavl_cut_first_primitive(gavl_node_t **root_nodep);
 390
 391 /* take and delete first item without balancing but keep tree consistent */
 392 void *
 393 gavl_cut_first(gavl_root_t *root);
 394
 395
 396 /*===========================================================*/
 397 /* Declarations of root fields for typesafe custom trees     */
 398
 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;
 404
 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      */
 408 typedef struct{
 409   gavl_node_t *root;
 410   gavl_node_t *first;
 411   gavl_node_t *last;
 412   long count;
 413 } gavl_fles_int_root_field_t;
 414
 415 /*===========================================================*/
 416 /* Macrodefinitions to prepare custom fast AVL trees with
 417    fast possibly inlined search */
 418
 419 /* User must provide his/her own compare routine with
 420     int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
 421
 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) \
 425 \
 426 static inline cust_item_t * \
 427 cust_prefix##_node2item(const cust_root_t *root, const gavl_node_t *node) \
 428 {\
 429   (void)root;\
 430   return UL_CONTAINEROF(node, cust_item_t, cust_item_node);\
 431 }\
 432 \
 433 static inline cust_key_t *\
 434 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
 435   { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
 436 \
 437 cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
 438 cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
 439 cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
 440 cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
 441 cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
 442 cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
 443 cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
 444 cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
 445 cust_scope gavl_node_t *cust_prefix##_first_node(const cust_root_t *root);\
 446 cust_scope gavl_node_t *cust_prefix##_last_node(const cust_root_t *root);\
 447 \
 448 static inline void \
 449 cust_prefix##_init_detached(cust_item_t *item){\
 450   item->cust_item_node.parent=NULL;\
 451 }\
 452 static inline cust_item_t *\
 453 cust_prefix##_first(const cust_root_t *root)\
 454 {\
 455   gavl_node_t *n=cust_prefix##_first_node(root);\
 456   return n?cust_prefix##_node2item(root,n):NULL;\
 457 }\
 458 static inline cust_item_t *\
 459 cust_prefix##_last(const cust_root_t *root)\
 460 {\
 461   gavl_node_t *n=cust_prefix##_last_node(root);\
 462   return n?cust_prefix##_node2item(root,n):NULL;\
 463 }\
 464 static inline cust_item_t *\
 465 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
 466 {\
 467   gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
 468   return n?cust_prefix##_node2item(root,n):NULL;\
 469 }\
 470 static inline cust_item_t *\
 471 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
 472 {\
 473   gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
 474   return n?cust_prefix##_node2item(root,n):NULL;\
 475 }\
 476 static inline int \
 477 cust_prefix##_is_empty(const cust_root_t *root)\
 478 {\
 479   return !root->cust_root_node;\
 480 }\
 481 static inline cust_item_t *\
 482 cust_prefix##_cut_first(cust_root_t *root)\
 483 {\
 484   gavl_node_t *n=gavl_cut_first_primitive(&root->cust_root_node);\
 485   return n?cust_prefix##_node2item(root,n):NULL;\
 486 }\
 487 /*** Iterators ***/\
 488 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
 489
 490 #define GAVL_CUST_NODE_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 491                 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
 492         GAVL_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 493                 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc)
 494
 495 #define gavl_cust_for_each(cust_prefix, root, ptr) \
 496         for(ptr=cust_prefix##_first(root);ptr;ptr=cust_prefix##_next((root),ptr))
 497
 498 #define gavl_cust_for_each_rev(cust_prefix, root, ptr) \
 499         for(ptr=cust_prefix##_last(root);ptr;ptr=cust_prefix##_prev((root),ptr))
 500
 501 #define gavl_cust_for_each_from(cust_prefix, root, key, ptr) \
 502         for(ptr=cust_prefix##_find_first(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
 503
 504 #define gavl_cust_for_each_after(cust_prefix, root, key, ptr) \
 505         for(ptr=cust_prefix##_find_after(root,key);ptr;ptr=cust_prefix##_next((root),ptr))
 506
 507 #define gavl_cust_for_each_cut(cust_prefix, root, ptr) \
 508         for(;(ptr=cust_prefix##_cut_first(root));)
 509
 510 #ifdef __cplusplus
 511 } /* extern "C"*/
 512 #endif
 513
 514 #endif /* _UL_GAVL_H */