orte/include/ul_gavlflesint.h

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