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);
  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 int
 105 gavl_is_empty(const gavl_root_t *root);
 106
 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
 111    "*cmp_fnc".
 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
 120  */
 121
 122 int
 123 gavl_search_node(const gavl_root_t *root, const void *key,
 124             int mode, gavl_node_t **nodep);
 125
 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)
 129 {
 130   gavl_node_t *node;
 131   gavl_search_node(root, key, GAVL_FFIRST, &node);
 132   return node;
 133 }
 134
 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)
 139 {
 140   gavl_node_t *node;
 141   gavl_search_node(root, key, GAVL_FAFTER, &node);
 142   return node;
 143 }
 144
 145 /* returns item with key field value equal to "*key" or NULL */
 146 void *
 147 gavl_find(const gavl_root_t *root, const void *key);
 148
 149 /* same as above, but first matching item is found */
 150 void *
 151 gavl_find_first(const gavl_root_t *root, const void *key);
 152
 153 /* same as above, but first nonmatching higher item is found */
 154 void *
 155 gavl_find_after(const gavl_root_t *root, const void *key);
 156
 157
 158 /**
 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
 162  *
 163  * Return Value: pointer to item corresponding to node
 164  */
 165 static inline void *
 166 gavl_node2item(const gavl_root_t *root, const gavl_node_t *node)
 167 {
 168   if(root->node_offs<0) return *(void**)(node+1);
 169   return (void*)((char*)node-root->node_offs);
 170 }
 171
 172 /**
 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
 176  *
 177  * Return Value: pointer to item corresponding to node
 178  */
 179 static inline void *
 180 gavl_node2item_safe(const gavl_root_t *root, const gavl_node_t *node)
 181 {
 182   if(!node) return 0;
 183   return gavl_node2item(root, node);
 184 }
 185
 186 /**
 187  * gavl_node2key - Conversion from GAVL Tree Node to Ordering Key
 188  * @root:       GAVL tree root
 189  * @node:       node belonging to @root GAVL tree
 190  *
 191  * Return Value: pointer to key corresponding to node
 192  */
 193 static inline void *
 194 gavl_node2key(const gavl_root_t *root, const gavl_node_t *node)
 195 {
 196   char *p;
 197   p=(char*)gavl_node2item(root, node);
 198   return (void*)(p+root->key_offs);
 199 }
 200
 201 int
 202 gavl_balance_one(gavl_node_t **subtree);
 203
 204 /* This function can be used for defining AVL trees with custom
 205    root definition. Use gavl_insert or gavl_insert_node for
 206    standard trees */
 207 int
 208 gavl_insert_primitive_at(gavl_node_t **root_nodep, gavl_node_t *node,
 209                     gavl_node_t *where, int leftright);
 210
 211 int
 212 gavl_insert_node_at(gavl_root_t *root, gavl_node_t *node,
 213                     gavl_node_t *where, int leftright);
 214
 215 int
 216 gavl_insert_node(gavl_root_t *root, gavl_node_t *node, int mode);
 217
 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
 222    and return value <0
 223  */
 224 int
 225 gavl_insert(gavl_root_t *root, void *item, int mode);
 226
 227 /* delete node from AVL tree */
 228 int
 229 gavl_delete_primitive(gavl_node_t **root_nodep, gavl_node_t *node);
 230
 231 /* delete node from AVL tree */
 232 int
 233 gavl_delete_node(gavl_root_t *root, gavl_node_t *node);
 234
 235 /* delete item from AVL tree */
 236 int
 237 gavl_delete(gavl_root_t *root, void *item);
 238
 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 */
 244 gavl_node_t *
 245 gavl_delete_and_next_node(gavl_root_t *root, gavl_node_t *node);
 246
 247 /*===========================================================*/
 248 /* iterators for generic GAVL type */
 249
 250 typedef struct {
 251   gavl_root_t *container;
 252   gavl_node_t *node;
 253 } gavl_it_t;
 254
 255 static inline void *
 256 gavl_it2item(const gavl_it_t *it)
 257 {
 258   return gavl_node2item_safe(it->container,it->node);
 259 }
 260
 261 static inline void
 262 gavl_first_it(gavl_root_t *container, gavl_it_t *it)
 263 {
 264   it->container=container;
 265   it->node=gavl_first_node(container);
 266 }
 267
 268 static inline void
 269 gavl_last_it(gavl_root_t *container, gavl_it_t *it)
 270 {
 271   it->container=container;
 272   it->node=gavl_last_node(container);
 273 }
 274
 275 static inline void
 276 gavl_next_it(gavl_it_t *it)
 277 {
 278   if(it->node) it->node=gavl_next_node(it->node);
 279   else it->node=gavl_first_node(it->container);
 280 }
 281
 282 static inline void
 283 gavl_prev_it(gavl_it_t *it)
 284 {
 285   if(it->node) it->node=gavl_prev_node(it->node);
 286   else it->node=gavl_last_node(it->container);
 287 }
 288
 289 static inline int
 290 gavl_is_end_it(gavl_it_t *it)
 291 {
 292   return !it->node;
 293 }
 294
 295 static inline void
 296 gavl_delete_it(gavl_it_t *it)
 297 {
 298   gavl_node_t *n;
 299   if(!(n=it->node)) return;
 300   it->node=gavl_next_node(it->node);
 301   gavl_delete_node(it->container,n);
 302 }
 303
 304 static inline int
 305 gavl_find_it(gavl_root_t *container, void *key, gavl_it_t *it)
 306 {
 307   it->container=container;
 308   return (it->node=gavl_find_first_node(container, key))!=0;
 309 }
 310
 311 static inline int
 312 gavl_find_first_it(gavl_root_t *container, void *key, gavl_it_t *it)
 313 {
 314   it->container=container;
 315   return (it->node=gavl_find_first_node(container, key))!=0;
 316 }
 317
 318 static inline int
 319 gavl_find_after_it(gavl_root_t *container, void *key, gavl_it_t *it)
 320 {
 321   it->container=container;
 322   return (it->node=gavl_find_after_node(container, key))!=0;
 323 }
 324
 325 /* The next implementation of foreaach is elegant, but can not
 326    be used in C99 non-conformant C compiler */
 327 #ifdef WITH_C99
 328
 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))
 333
 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))
 338
 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))
 343
 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))
 348
 349 #endif /*WITH_C99*/
 350
 351 #define gavl_generic_for_each_cut(item_t, root, ptr) \
 352         for(;(ptr=(item_t*)gavl_cut_first(root));)
 353
 354 /*===========================================================*/
 355 /* basic types compare functions */
 356
 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);
 360
 361 /*===========================================================*/
 362 /* More functions useful for partially balanced trees */
 363
 364 /* Adjust hdiff in parent nodes after change of height of
 365    branch starting at node */
 366 int
 367 gavl_adjust_hdiff(gavl_node_t *node, int adj);
 368
 369 /* Partial balance - reduces number of nodes with hdiff >1 or <-1,
 370    return zero if none unbalanced node is found */
 371 int
 372 gavl_balance_enhance(gavl_node_t **subtree);
 373
 374 /* Full tree balance to state correct for AVL tree
 375    => hdiff is in range <-1,0,1> */
 376 int
 377 gavl_balance(gavl_root_t *root);
 378
 379 /* take and delete first node without balancing but keep tree consistent */
 380 gavl_node_t *
 381 gavl_cut_first_primitive(gavl_node_t **root_nodep);
 382
 383 /* take and delete first item without balancing but keep tree consistent */
 384 void *
 385 gavl_cut_first(gavl_root_t *root);
 386
 387
 388 /*===========================================================*/
 389 /* Declarations of root fields for typesafe custom trees     */
 390
 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;
 396
 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      */
 400 typedef struct{
 401   gavl_node_t *root;
 402   gavl_node_t *first;
 403   gavl_node_t *last;
 404   long count;
 405 } gavl_fles_int_root_field_t;
 406
 407 /*===========================================================*/
 408 /* Macrodefinitions to prepare custom fast AVL trees with
 409    fast possibly inlined search */
 410
 411 /* User must provide his/her own compare routine with
 412     int cust_cmp_fnc(cust_key_t *a, cust_key_t *b) */
 413
 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) \
 417 \
 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);}\
 421 \
 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);}\
 425 \
 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);\
 436 \
 437 static inline void \
 438 cust_prefix##_init_detached(cust_item_t *item){\
 439   item->cust_item_node.parent=NULL;\
 440 }\
 441 static inline cust_item_t *\
 442 cust_prefix##_first(const cust_root_t *root)\
 443 {\
 444   gavl_node_t *n=cust_prefix##_first_node(root);\
 445   return n?cust_prefix##_node2item(root,n):NULL;\
 446 }\
 447 static inline cust_item_t *\
 448 cust_prefix##_last(const cust_root_t *root)\
 449 {\
 450   gavl_node_t *n=cust_prefix##_last_node(root);\
 451   return n?cust_prefix##_node2item(root,n):NULL;\
 452 }\
 453 static inline cust_item_t *\
 454 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
 455 {\
 456   gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
 457   return n?cust_prefix##_node2item(root,n):NULL;\
 458 }\
 459 static inline cust_item_t *\
 460 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
 461 {\
 462   gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
 463   return n?cust_prefix##_node2item(root,n):NULL;\
 464 }\
 465 static inline int \
 466 cust_prefix##_is_empty(const cust_root_t *root)\
 467 {\
 468   return !root->cust_root_node;\
 469 }\
 470 static inline cust_item_t *\
 471 cust_prefix##_cut_first(cust_root_t *root)\
 472 {\
 473   gavl_node_t *n=gavl_cut_first_primitive(&root->cust_root_node);\
 474   return n?cust_prefix##_node2item(root,n):NULL;\
 475 }\
 476 /*** Iterators ***/\
 477 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
 478
 479 #define gavl_cust_for_each(cust_prefix, root, ptr) \
 480         for(ptr=cust_prefix##_first(root);ptr;ptr=cust_prefix##_next((root),ptr))
 481
 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))
 484
 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))
 487
 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))
 490
 491 #define gavl_cust_for_each_cut(cust_prefix, root, ptr) \
 492         for(;(ptr=cust_prefix##_cut_first(root));)
 493
 494 #ifdef __cplusplus
 495 } /* extern "C"*/
 496 #endif
 497
 498 #endif /* _UL_GAVL_H */