ulan/host/libs4c/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(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   {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
  41 \
  42 static inline cust_key_t *\
  43 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
  44   { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
  45 \
  46 void cust_prefix##_init_root_field(cust_root_t *root);\
  47 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep);\
  48 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key);\
  49 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key);\
  50 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key);\
  51 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
  52 cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
  53 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
  54 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
  55 \
  56 static inline void \
  57 cust_prefix##_init_detached(cust_item_t *item){\
  58   item->cust_item_node.parent=NULL;\
  59 }\
  60 static inline gavl_node_t *\
  61 cust_prefix##_first_node(const cust_root_t *root)\
  62 {\
  63   return root->cust_root_field.first;\
  64 }\
  65 static inline gavl_node_t *\
  66 cust_prefix##_last_node(const cust_root_t *root)\
  67 {\
  68   return root->cust_root_field.last;\
  69 }\
  70 static inline cust_item_t *\
  71 cust_prefix##_first(const cust_root_t *root)\
  72 {\
  73   gavl_node_t *n=cust_prefix##_first_node(root);\
  74   return n?cust_prefix##_node2item(root,n):NULL;\
  75 }\
  76 static inline cust_item_t *\
  77 cust_prefix##_last(const cust_root_t *root)\
  78 {\
  79   gavl_node_t *n=cust_prefix##_last_node(root);\
  80   return n?cust_prefix##_node2item(root,n):NULL;\
  81 }\
  82 static inline cust_item_t *\
  83 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
  84 {\
  85   gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
  86   return n?cust_prefix##_node2item(root,n):NULL;\
  87 }\
  88 static inline cust_item_t *\
  89 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
  90 {\
  91   gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
  92   return n?cust_prefix##_node2item(root,n):NULL;\
  93 }\
  94 static inline int \
  95 cust_prefix##_is_empty(const cust_root_t *root)\
  96 {\
  97   return !root->cust_root_field.root;\
  98 }\
  99 /*** Iterators ***/\
 100 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
 101
 102
 103 /**
 104  * GAVL_FLES_INT_IMP - Implementation of new custom tree with fast first/last functions
 105  * @cust_prefix:        defines prefix for builded function names
 106  * @cust_root_t:        user defined structure type of root of the tree
 107  * @cust_item_t:        user defined structure type of items stored in the tree
 108  * @cust_key_t:         type of the key used for sorting of the items
 109  * @cust_root_field:    the field of the root structure pointing to the tree root node
 110  * @cust_item_node:     the field of item structure used for chaining of items
 111  * @cust_item_key:      the key field of item structure defining order of items
 112  * @cust_cmp_fnc:       the keys compare function
 113  *
 114  * This version of custom tree implementation allows multiple items with same
 115  * key value to be stored in tree.
 116  * There are two macros designed for building custom AVL trees. The macro
 117  * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
 118  * and is intended for use in header files.
 119  * The macro %GAVL_CUST_NODE_INT_REP_IMP builds implementations for non-inlined
 120  * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
 121  * for comparison of item keys in the search and insert functions. The types
 122  * of two input arguments of @cust_cmp_fnc functions must correspond
 123  * with @cust_key_t type. Return value should be positive for case when
 124  * the first pointed key value is greater then second, negative for reverse
 125  * case and zero for equal pointed values.
 126  */
 127 #define GAVL_FLES_INT_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
 128                 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
 129                 cust_ins_fl, cust_first_change, cust_last_change, cust_empty_state) \
 130 \
 131 void cust_prefix##_init_root_field(cust_root_t *root)\
 132 {\
 133   root->cust_root_field.root=NULL;\
 134   root->cust_root_field.first=NULL;\
 135   root->cust_root_field.last=NULL;\
 136   root->cust_root_field.count=0;\
 137 }\
 138 \
 139 int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep, int mode)\
 140 {\
 141   int cmp=1;\
 142   gavl_node_t *n, *p;\
 143   n=p=root->cust_root_field.root;\
 144   while(n){\
 145     cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 146     p=n;\
 147     if(cmp>0){\
 148       n=n->left;\
 149     }else if((cmp<0)||(mode&GAVL_FAFTER)){\
 150       n=n->right;\
 151     }else{\
 152       break;\
 153     }\
 154   }\
 155   if(!cmp && (mode&GAVL_FFIRST)){\
 156     while((n=p->left)){\
 157       cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 158       if(!cmp){\
 159         p=n;\
 160       }else{\
 161         while((n=n->right)){\
 162           cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
 163           if(!cmp){\
 164             p=n;\
 165             break;\
 166           }\
 167         }\
 168         if(cmp) break;\
 169       }\
 170     }\
 171     cmp=0;\
 172   }\
 173   *nodep=p;\
 174   return cmp;\
 175 }\
 176 \
 177 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep)\
 178 {\
 179   return cust_prefix##_search_node4(root, key, nodep, 0);\
 180 }\
 181 \
 182 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key)\
 183 {\
 184   gavl_node_t *node;\
 185   if(cust_prefix##_search_node4(root, key, &node, 0))\
 186     return NULL;\
 187   return cust_prefix##_node2item(root,node);\
 188 }\
 189 \
 190 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key)\
 191 {\
 192   gavl_node_t *n;\
 193   if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
 194     return NULL;\
 195   return cust_prefix##_node2item(root,n);\
 196 }\
 197 \
 198 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key)\
 199 {\
 200   gavl_node_t *node;\
 201   if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
 202      if(node) node=gavl_next_node(node);\
 203   }\
 204   return node?cust_prefix##_node2item(root,node):NULL;\
 205 }\
 206 \
 207 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
 208 {\
 209   int cmp;\
 210   gavl_node_t *where, *n2add;\
 211   \
 212   cmp=cust_prefix##_search_node4(root, &item->cust_item_key, &where, cust_ins_fl);\
 213   if(!cmp && !(cust_ins_fl&GAVL_FAFTER)) return -1;\
 214   n2add=&item->cust_item_node;\
 215   if(!root->cust_root_field.root){\
 216     root->cust_root_field.first=root->cust_root_field.last=n2add;\
 217     cust_first_change; cust_last_change;\
 218   }else if((cmp>0)&&(where==root->cust_root_field.first)){\
 219     root->cust_root_field.first=n2add;\
 220     cust_first_change;\
 221   }else if((cmp<=0)&&(where==root->cust_root_field.last)){\
 222     root->cust_root_field.last=n2add;\
 223     cust_last_change;\
 224   }\
 225   root->cust_root_field.count++;\
 226   return gavl_insert_primitive_at(&root->cust_root_field.root, n2add, where, cmp);\
 227 }\
 228 \
 229 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
 230 {\
 231   gavl_node_t *p;\
 232   /*check if node is inserted into tree*/\
 233   for(p=node; p->parent; p=p->parent);\
 234   if(p!=root->cust_root_field.root)\
 235     return -1;\
 236   if(root->cust_root_field.first==node){\
 237     if(root->cust_root_field.last==node){\
 238       root->cust_root_field.first=root->cust_root_field.last=NULL;\
 239       cust_empty_state;\
 240     }else{\
 241       root->cust_root_field.first=gavl_next_node(node);\
 242       cust_first_change;\
 243     }\
 244   }else if(root->cust_root_field.last==node){\
 245     root->cust_root_field.last=gavl_prev_node(node);\
 246     cust_last_change;\
 247   }\
 248   root->cust_root_field.count--;\
 249   return gavl_delete_primitive(&root->cust_root_field.root, node);\
 250 }\
 251 \
 252 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 253 {\
 254   gavl_node_t *n;\
 255   if(!item) return -1;\
 256   n=&item->cust_item_node;\
 257   return cust_prefix##_delete_node(root, n);\
 258 }\
 259 \
 260 cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
 261 {\
 262   gavl_node_t *n, *p;\
 263   gavl_node_t **np=&root->cust_root_field.root;\
 264   if(!(n=root->cust_root_field.first))\
 265     return NULL;\
 266   if(n->parent) np=&n->parent->left;\
 267   if((*np=n->right)){\
 268     p=n->right;\
 269     p->parent=n->parent;\
 270     while(p->left) p=p->left;\
 271     root->cust_root_field.first=p;\
 272     cust_first_change;\
 273   }else{\
 274     if(!(root->cust_root_field.first=n->parent)){\
 275       root->cust_root_field.last=n->parent;\
 276       cust_empty_state;\
 277     }else{\
 278       cust_first_change;\
 279     }\
 280   }\
 281   for(p=n->parent;p;p=p->parent)\
 282     if(p->hdiff++<0) break;\
 283   n->parent=n->left=n->right=NULL;\
 284   root->cust_root_field.count--;\
 285   return cust_prefix##_node2item(root,n);\
 286 }
 287
 288
 289 #ifdef __cplusplus
 290 } /* extern "C"*/
 291 #endif
 292
 293 #endif /* _UL_GAVLFLESINT_H */