orte/include/ul_gavlcust.h

   1 #ifndef _UL_GAVLCUST_H
   2 #define _UL_GAVLCUST_H
   3
   4 #include "ul_gavl.h"
   5
   6 #ifdef __cplusplus
   7 extern "C" {
   8 #endif
   9
  10 /**
  11  * GAVL_CUST_NODE_INT_IMP - Implementation of new custom tree with internal node
  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  * There are two macros designed for building custom AVL trees. The macro
  22  * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
  23  * and is intended for use in header files.
  24  * The macro %GAVL_CUST_NODE_INT_IMP builds implementations for non-inlined
  25  * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
  26  * for comparison of item keys in the search and insert functions. The types
  27  * of two input arguments of @cust_cmp_fnc functions must correspond
  28  * with @cust_key_t type. Return value should be positive for case when
  29  * the first pointed key value is greater then second, negative for reverse
  30  * case and zero for equal pointed values.
  31  */
  32 #define GAVL_CUST_NODE_INT_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  33                 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
  34 \
  35 void cust_prefix##_init_root_field(cust_root_t *root)\
  36 {\
  37   root->cust_root_node=NULL;\
  38 }\
  39 \
  40 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t *key, gavl_node_t **nodep)\
  41 {\
  42   int cmp=1;\
  43   gavl_node_t *n, *p;\
  44   n=p=root->cust_root_node;\
  45   while(n){\
  46     cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  47     p=n;\
  48     if(cmp>0){\
  49       n=n->left;\
  50     }else if(cmp<0){\
  51       n=n->right;\
  52     }else{\
  53       *nodep=n;\
  54       return 0;\
  55     }\
  56   }\
  57   *nodep=p;\
  58   return cmp;\
  59 }\
  60 \
  61 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t *key)\
  62 {\
  63   gavl_node_t *node;\
  64   if(cust_prefix##_search_node(root, key, &node))\
  65     return NULL;\
  66   return cust_prefix##_node2item(root,node);\
  67 }\
  68 \
  69 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t *key)\
  70 {\
  71   return cust_prefix##_find(root, key);\
  72 }\
  73 \
  74 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t *key)\
  75 {\
  76   gavl_node_t *node;\
  77   if(cust_prefix##_search_node(root, key, &node)<=0){\
  78      if(node) node=gavl_next_node(node);\
  79   }\
  80   return node?cust_prefix##_node2item(root,node):NULL;\
  81 }\
  82 \
  83 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
  84 {\
  85   int cmp;\
  86   gavl_node_t *where, *n2add;\
  87   \
  88   cmp=cust_prefix##_search_node(root, &item->cust_item_key, &where);\
  89   if(!cmp) return -1;\
  90   n2add=&item->cust_item_node;\
  91   return gavl_insert_primitive_at(&root->cust_root_node, n2add, where, cmp);\
  92 }\
  93 \
  94 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
  95 {\
  96   return gavl_delete_primitive(&root->cust_root_node, node);\
  97 }\
  98 \
  99 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 100 {\
 101   int ret;\
 102   gavl_node_t *n, *p;\
 103   if(!item) return -1;\
 104   /*if(cust_prefix##_search_node(root, &item->cust_item_key, &n))*/\
 105   n=&item->cust_item_node;\
 106   /*check if node is inserted into tree*/\
 107   for(p=n; p->parent; p=p->parent);\
 108   if(p!=root->cust_root_node)\
 109     return -1;\
 110   ret=gavl_delete_primitive(&root->cust_root_node, n);\
 111   return 1;\
 112 }\
 113 \
 114 gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
 115 {\
 116   gavl_node_t *n=root->cust_root_node;\
 117   if(!n) return NULL;\
 118   while(n->left)\
 119     n=n->left;\
 120   return n;\
 121 }\
 122 \
 123 gavl_node_t *cust_prefix##_last_node(const cust_root_t *root)\
 124 {\
 125   gavl_node_t *n=root->cust_root_node;\
 126   if(!n) return NULL;\
 127   while(n->right)\
 128     n=n->right;\
 129   return n;\
 130 }
 131
 132
 133 #ifdef __cplusplus
 134 } /* extern "C"*/
 135 #endif
 136
 137 #endif /* _UL_GAVLCUST_H */