orte/include/ul_gavlrepcust.h

   1 #ifndef _UL_GAVLREPCUST_H
   2 #define _UL_GAVLREPCUST_H
   3
   4 #include "ul_gavl.h"
   5
   6 #ifdef __cplusplus
   7 extern "C" {
   8 #endif
   9
  10 /**
  11  * GAVL_CUST_NODE_INT_REP_IMP - Implementation of new custom tree with internal node allowed item repeat
  12  * @cust_prefix:        defines prefix for builded function names
  13  * @cust_root_t:        user defined structure type of root of the tree
  14  * @cust_item_t:        user defined structure type of items stored in the tree
  15  * @cust_key_t:         type of the key used for sorting of the items
  16  * @cust_root_node:     the field of the root structure pointing to the tree root node
  17  * @cust_item_node:     the field of item structure used for chaining of items
  18  * @cust_item_key:      the key field of item structure defining order of items
  19  * @cust_cmp_fnc:       the keys compare function
  20  *
  21  * This version of custom tree implementation allows multiple items with same
  22  * key value to be stored in tree.
  23  * There are two macros designed for building custom AVL trees. The macro
  24  * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
  25  * and is intended for use in header files.
  26  * The macro %GAVL_CUST_NODE_INT_REP_IMP builds implementations for non-inlined
  27  * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
  28  * for comparison of item keys in the search and insert functions. The types
  29  * of two input arguments of @cust_cmp_fnc functions must correspond
  30  * with @cust_key_t type. Return value should be positive for case when
  31  * the first pointed key value is greater then second, negative for reverse
  32  * case and zero for equal pointed values.
  33  */
  34 #define GAVL_CUST_NODE_INT_REP_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  35                 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
  36 \
  37 void cust_prefix##_init_root_field(cust_root_t *root)\
  38 {\
  39   root->cust_root_node=NULL;\
  40 }\
  41 \
  42 int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep, int mode)\
  43 {\
  44   int cmp=1;\
  45   gavl_node_t *n, *p;\
  46   n=p=root->cust_root_node;\
  47   while(n){\
  48     cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  49     p=n;\
  50     if(cmp>0){\
  51       n=n->left;\
  52     }else if((cmp<0)||(mode&GAVL_FAFTER)){\
  53       n=n->right;\
  54     }else{\
  55       break;\
  56     }\
  57   }\
  58   if(!cmp && (mode&GAVL_FFIRST)){\
  59     while((n=p->left)){\
  60       cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  61       if(!cmp){\
  62         p=n;\
  63       }else{\
  64         while((n=n->right)){\
  65           cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  66           if(!cmp){\
  67             p=n;\
  68             break;\
  69           }\
  70         }\
  71         if(cmp) break;\
  72       }\
  73     }\
  74     cmp=0;\
  75   }\
  76   *nodep=p;\
  77   return cmp;\
  78 }\
  79 \
  80 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep)\
  81 {\
  82   return cust_prefix##_search_node4(root, key, nodep, 0);\
  83 }\
  84 \
  85 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key)\
  86 {\
  87   gavl_node_t *node;\
  88   if(cust_prefix##_search_node4(root, key, &node, 0))\
  89     return NULL;\
  90   return cust_prefix##_node2item(root,node);\
  91 }\
  92 \
  93 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key)\
  94 {\
  95   gavl_node_t *n;\
  96   if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
  97     return NULL;\
  98   return cust_prefix##_node2item(root,n);\
  99 }\
 100 \
 101 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key)\
 102 {\
 103   gavl_node_t *node;\
 104   if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
 105      if(node) node=gavl_next_node(node);\
 106   }\
 107   return node?cust_prefix##_node2item(root,node):NULL;\
 108 }\
 109 \
 110 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
 111 {\
 112   int cmp;\
 113   gavl_node_t *where, *n2add;\
 114   \
 115   cmp=cust_prefix##_search_node4(root, &item->cust_item_key, &where, GAVL_FAFTER);\
 116   n2add=&item->cust_item_node;\
 117   return gavl_insert_primitive_at(&root->cust_root_node, n2add, where, cmp);\
 118 }\
 119 \
 120 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
 121 {\
 122   return gavl_delete_primitive(&root->cust_root_node, node);\
 123 }\
 124 \
 125 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 126 {\
 127   int ret;\
 128   gavl_node_t *n, *p;\
 129   if(!item) return -1;\
 130   n=&item->cust_item_node;\
 131   /*check if node is inserted into tree*/\
 132   for(p=n; p->parent; p=p->parent);\
 133   if(p!=root->cust_root_node)\
 134     return -1;\
 135   ret=gavl_delete_primitive(&root->cust_root_node, n);\
 136   return 1;\
 137 }\
 138 \
 139 gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
 140 {\
 141   gavl_node_t *n=root->cust_root_node;\
 142   if(!n) return NULL;\
 143   while(n->left)\
 144     n=n->left;\
 145   return n;\
 146 }\
 147 \
 148 gavl_node_t *cust_prefix##_last_node(const cust_root_t *root)\
 149 {\
 150   gavl_node_t *n=root->cust_root_node;\
 151   if(!n) return NULL;\
 152   while(n->right)\
 153     n=n->right;\
 154   return n;\
 155 }
 156
 157
 158 #ifdef __cplusplus
 159 } /* extern "C"*/
 160 #endif
 161
 162 #endif /* _UL_GAVLREPCUST_H */