ulut/ul_gavlflesint.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gavlflesint.h  - custom trees with allowed repeat of keys
   5                       and fast access to the first and last item
   6
   7   (C) Copyright 2003-2004 by Pavel Pisa - Originator
   8
   9   The uLan utilities library can be used, copied and modified under
  10   next licenses
  11     - GPL - GNU General Public License
  12     - LGPL - GNU Lesser General Public License
  13     - MPL - Mozilla Public License
  14     - and other licenses added by project originators
  15   Code can be modified and re-distributed under any combination
  16   of the above listed licenses. If contributor does not agree with
  17   some of the licenses, he/she can delete appropriate line.
  18   Warning, if you delete all lines, you are not allowed to
  19   distribute source code and/or binaries utilizing code.
  20
  21   See files COPYING and README for details.
  22
  23  *******************************************************************/
  24
  25 #ifndef _UL_GAVLFLESINT_H
  26 #define _UL_GAVLFLESINT_H
  27
  28 #include "ul_gavl.h"
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 /* Declaration of tree with first/last enhanced speed functions with internal node */
  35 #define GAVL_FLES_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  36                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
  37 \
  38 static inline cust_item_t * \
  39 cust_prefix##_node2item(const cust_root_t *root, const gavl_node_t *node) \
  40 {\
  41   (void)root;\
  42   return UL_CONTAINEROF(node, cust_item_t, cust_item_node);\
  43 }\
  44 \
  45 static inline cust_key_t *\
  46 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
  47   { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
  48 \
  49 cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
  50 cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
  51 cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
  52 cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
  53 cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
  54 cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
  55 cust_scope cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
  56 cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
  57 cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
  58 \
  59 static inline void \
  60 cust_prefix##_init_detached(cust_item_t *item){\
  61   item->cust_item_node.parent=NULL;\
  62 }\
  63 static inline gavl_node_t *\
  64 cust_prefix##_first_node(const cust_root_t *root)\
  65 {\
  66   return root->cust_root_field.first;\
  67 }\
  68 static inline gavl_node_t *\
  69 cust_prefix##_last_node(const cust_root_t *root)\
  70 {\
  71   return root->cust_root_field.last;\
  72 }\
  73 static inline cust_item_t *\
  74 cust_prefix##_first(const cust_root_t *root)\
  75 {\
  76   gavl_node_t *n=cust_prefix##_first_node(root);\
  77   return n?cust_prefix##_node2item(root,n):NULL;\
  78 }\
  79 static inline cust_item_t *\
  80 cust_prefix##_last(const cust_root_t *root)\
  81 {\
  82   gavl_node_t *n=cust_prefix##_last_node(root);\
  83   return n?cust_prefix##_node2item(root,n):NULL;\
  84 }\
  85 static inline cust_item_t *\
  86 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
  87 {\
  88   gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
  89   return n?cust_prefix##_node2item(root,n):NULL;\
  90 }\
  91 static inline cust_item_t *\
  92 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
  93 {\
  94   gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
  95   return n?cust_prefix##_node2item(root,n):NULL;\
  96 }\
  97 static inline int \
  98 cust_prefix##_is_empty(const cust_root_t *root)\
  99 {\
 100   return !root->cust_root_field.root;\
 101 }\
 102 /*** Iterators ***/\
 103 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
 104
 105 #define GAVL_FLES_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 106                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
 107         GAVL_FLES_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 108                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc)
 109
 110 /**
 111  * GAVL_FLES_INT_IMP - Implementation of new custom tree with fast first/last functions
 112  * @cust_prefix:        defines prefix for builded function names
 113  * @cust_root_t:        user defined structure type of root of the tree
 114  * @cust_item_t:        user defined structure type of items stored in the tree
 115  * @cust_key_t:         type of the key used for sorting of the items
 116  * @cust_root_field:    the field of the root structure pointing to the tree root node
 117  * @cust_item_node:     the field of item structure used for chaining of items
 118  * @cust_item_key:      the key field of item structure defining order of items
 119  * @cust_cmp_fnc:       the keys compare function
 120  *
 121  * This version of custom tree implementation allows multiple items with same
 122  * key value to be stored in tree.
 123  * There are two macros designed for building custom AVL trees. The macro
 124  * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
 125  * and is intended for use in header files.
 126  * The macro %GAVL_CUST_NODE_INT_REP_IMP builds implementations for non-inlined
 127  * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
 128  * for comparison of item keys in the search and insert functions. The types
 129  * of two input arguments of @cust_cmp_fnc functions must correspond
 130  * with @cust_key_t type. Return value should be positive for case when
 131  * the first pointed key value is greater then second, negative for reverse
 132  * case and zero for equal pointed values.
 133  */
 134 #define GAVL_FLES_INT_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 135                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
 136                 cust_ins_fl, cust_first_change, cust_last_change, cust_empty_state) \
 137 \
 138 void cust_prefix##_init_root_field(cust_root_t *root)\
 139 {\
 140   root->cust_root_field.root=NULL;\
 141   root->cust_root_field.first=NULL;\
 142   root->cust_root_field.last=NULL;\
 143   root->cust_root_field.count=0;\
 144 }\
 145 \
 146 int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep, int mode)\
 147 {\
 148   int cmp=1;\
 149   gavl_node_t *n, *p;\
 150   n=p=root->cust_root_field.root;\
 151   while(n){\
 152     cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 153     p=n;\
 154     if(cmp>0){\
 155       n=n->left;\
 156     }else if((cmp<0)||(mode&GAVL_FAFTER)){\
 157       n=n->right;\
 158     }else{\
 159       break;\
 160     }\
 161   }\
 162   if(!cmp && (mode&GAVL_FFIRST)){\
 163     while((n=p->left)){\
 164       cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 165       if(!cmp){\
 166         p=n;\
 167       }else{\
 168         while((n=n->right)){\
 169           cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 170           if(!cmp){\
 171             p=n;\
 172             break;\
 173           }\
 174         }\
 175         if(cmp) break;\
 176       }\
 177     }\
 178     cmp=0;\
 179   }\
 180   *nodep=p;\
 181   return cmp;\
 182 }\
 183 \
 184 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
 185 {\
 186   return cust_prefix##_search_node4(root, key, nodep, 0);\
 187 }\
 188 \
 189 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
 190 {\
 191   gavl_node_t *node;\
 192   if(cust_prefix##_search_node4(root, key, &node, 0))\
 193     return NULL;\
 194   return cust_prefix##_node2item(root,node);\
 195 }\
 196 \
 197 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
 198 {\
 199   gavl_node_t *n;\
 200   if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
 201     return NULL;\
 202   return cust_prefix##_node2item(root,n);\
 203 }\
 204 \
 205 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
 206 {\
 207   gavl_node_t *node;\
 208   if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
 209      if(node) node=gavl_next_node(node);\
 210   }\
 211   return node?cust_prefix##_node2item(root,node):NULL;\
 212 }\
 213 \
 214 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
 215 {\
 216   int cmp;\
 217   gavl_node_t *where, *n2add;\
 218   \
 219   cmp=cust_prefix##_search_node4(root, &item->cust_item_key, &where, cust_ins_fl);\
 220   if(!cmp && !(cust_ins_fl&GAVL_FAFTER)) return -1;\
 221   n2add=&item->cust_item_node;\
 222   if(!root->cust_root_field.root){\
 223     root->cust_root_field.first=root->cust_root_field.last=n2add;\
 224     cust_first_change; cust_last_change;\
 225   }else if((cmp>0)&&(where==root->cust_root_field.first)){\
 226     root->cust_root_field.first=n2add;\
 227     cust_first_change;\
 228   }else if((cmp<=0)&&(where==root->cust_root_field.last)){\
 229     root->cust_root_field.last=n2add;\
 230     cust_last_change;\
 231   }\
 232   root->cust_root_field.count++;\
 233   return gavl_insert_primitive_at(&root->cust_root_field.root, n2add, where, cmp);\
 234 }\
 235 \
 236 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
 237 {\
 238   gavl_node_t *p;\
 239   /*check if node is inserted into tree*/\
 240   for(p=node; p->parent; p=p->parent);\
 241   if(p!=root->cust_root_field.root)\
 242     return -1;\
 243   if(root->cust_root_field.first==node){\
 244     if(root->cust_root_field.last==node){\
 245       root->cust_root_field.first=root->cust_root_field.last=NULL;\
 246       cust_empty_state;\
 247     }else{\
 248       root->cust_root_field.first=gavl_next_node(node);\
 249       cust_first_change;\
 250     }\
 251   }else if(root->cust_root_field.last==node){\
 252     root->cust_root_field.last=gavl_prev_node(node);\
 253     cust_last_change;\
 254   }\
 255   root->cust_root_field.count--;\
 256   return gavl_delete_primitive(&root->cust_root_field.root, node);\
 257 }\
 258 \
 259 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 260 {\
 261   gavl_node_t *n;\
 262   if(!item) return -1;\
 263   n=&item->cust_item_node;\
 264   return cust_prefix##_delete_node(root, n);\
 265 }\
 266 \
 267 cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
 268 {\
 269   gavl_node_t *n, *p;\
 270   gavl_node_t **np=&root->cust_root_field.root;\
 271   if(!(n=root->cust_root_field.first))\
 272     return NULL;\
 273   if(n->parent) np=&n->parent->left;\
 274   if((*np=n->right)){\
 275     p=n->right;\
 276     p->parent=n->parent;\
 277     while(p->left) p=p->left;\
 278     root->cust_root_field.first=p;\
 279     cust_first_change;\
 280   }else{\
 281     if(!(root->cust_root_field.first=n->parent)){\
 282       root->cust_root_field.last=n->parent;\
 283       cust_empty_state;\
 284     }else{\
 285       cust_first_change;\
 286     }\
 287   }\
 288   for(p=n->parent;p;p=p->parent)\
 289     if(p->hdiff++<0) break;\
 290   n->parent=n->left=n->right=NULL;\
 291   root->cust_root_field.count--;\
 292   return cust_prefix##_node2item(root,n);\
 293 }
 294
 295
 296 #ifdef __cplusplus
 297 } /* extern "C"*/
 298 #endif
 299
 300 #endif /* _UL_GAVLFLESINT_H */