ulut/ul_gavlrepcust.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_gavlrepcust.h  - custom trees with allowed repeat of keys
   5
   6   (C) Copyright 2003-2004 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  10     - GPL - GNU General Public License
  11     - LGPL - GNU Lesser General Public License
  12     - MPL - Mozilla Public License
  13     - and other licenses added by project originators
  14   Code can be modified and re-distributed under any combination
  15   of the above listed licenses. If contributor does not agree with
  16   some of the licenses, he/she can delete appropriate line.
  17   Warning, if you delete all lines, you are not allowed to
  18   distribute source code and/or binaries utilizing code.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #ifndef _UL_GAVLREPCUST_H
  25 #define _UL_GAVLREPCUST_H
  26
  27 #include "ul_gavl.h"
  28
  29 #ifdef __cplusplus
  30 extern "C" {
  31 #endif
  32
  33 /**
  34  * GAVL_CUST_NODE_INT_REP_IMP - Implementation of new custom tree with internal node allowed item repeat
  35  * @cust_prefix:        defines prefix for builded function names
  36  * @cust_root_t:        user defined structure type of root of the tree
  37  * @cust_item_t:        user defined structure type of items stored in the tree
  38  * @cust_key_t:         type of the key used for sorting of the items
  39  * @cust_root_node:     the field of the root structure pointing to the tree root node
  40  * @cust_item_node:     the field of item structure used for chaining of items
  41  * @cust_item_key:      the key field of item structure defining order of items
  42  * @cust_cmp_fnc:       the keys compare function
  43  *
  44  * This version of custom tree implementation allows multiple items with same
  45  * key value to be stored in tree.
  46  * There are two macros designed for building custom AVL trees. The macro
  47  * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
  48  * and is intended for use in header files.
  49  * The macro %GAVL_CUST_NODE_INT_REP_IMP builds implementations for non-inlined
  50  * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
  51  * for comparison of item keys in the search and insert functions. The types
  52  * of two input arguments of @cust_cmp_fnc functions must correspond
  53  * with @cust_key_t type. Return value should be positive for case when
  54  * the first pointed key value is greater then second, negative for reverse
  55  * case and zero for equal pointed values.
  56  */
  57 #define GAVL_CUST_NODE_INT_REP_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
  58                 cust_root_node, cust_item_node, cust_item_key, cust_cmp_fnc) \
  59 \
  60 void cust_prefix##_init_root_field(cust_root_t *root)\
  61 {\
  62   root->cust_root_node=NULL;\
  63 }\
  64 \
  65 int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep, int mode)\
  66 {\
  67   int cmp=1;\
  68   gavl_node_t *n, *p;\
  69   n=p=root->cust_root_node;\
  70   while(n){\
  71     cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  72     p=n;\
  73     if(cmp>0){\
  74       n=n->left;\
  75     }else if((cmp<0)||(mode&GAVL_FAFTER)){\
  76       n=n->right;\
  77     }else{\
  78       break;\
  79     }\
  80   }\
  81   if(!cmp && (mode&GAVL_FFIRST)){\
  82     while((n=p->left)){\
  83       cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  84       if(!cmp){\
  85         p=n;\
  86       }else{\
  87         while((n=n->right)){\
  88           cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
  89           if(!cmp){\
  90             p=n;\
  91             break;\
  92           }\
  93         }\
  94         if(cmp) break;\
  95       }\
  96     }\
  97     cmp=0;\
  98   }\
  99   *nodep=p;\
 100   return cmp;\
 101 }\
 102 \
 103 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
 104 {\
 105   return cust_prefix##_search_node4(root, key, nodep, 0);\
 106 }\
 107 \
 108 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
 109 {\
 110   gavl_node_t *node;\
 111   if(cust_prefix##_search_node4(root, key, &node, 0))\
 112     return NULL;\
 113   return cust_prefix##_node2item(root,node);\
 114 }\
 115 \
 116 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
 117 {\
 118   gavl_node_t *n;\
 119   if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
 120     return NULL;\
 121   return cust_prefix##_node2item(root,n);\
 122 }\
 123 \
 124 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
 125 {\
 126   gavl_node_t *node;\
 127   if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
 128      if(node) node=gavl_next_node(node);\
 129   }\
 130   return node?cust_prefix##_node2item(root,node):NULL;\
 131 }\
 132 \
 133 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
 134 {\
 135   int cmp;\
 136   gavl_node_t *where, *n2add;\
 137   \
 138   cmp=cust_prefix##_search_node4(root, &item->cust_item_key, &where, GAVL_FAFTER);\
 139   n2add=&item->cust_item_node;\
 140   return gavl_insert_primitive_at(&root->cust_root_node, n2add, where, cmp);\
 141 }\
 142 \
 143 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
 144 {\
 145   return gavl_delete_primitive(&root->cust_root_node, node);\
 146 }\
 147 \
 148 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
 149 {\
 150   gavl_node_t *n, *p;\
 151   if(!item) return -1;\
 152   n=&item->cust_item_node;\
 153   /*check if node is inserted into tree*/\
 154   for(p=n; p->parent; p=p->parent);\
 155   if(p!=root->cust_root_node)\
 156     return -1;\
 157   return gavl_delete_primitive(&root->cust_root_node, n);\
 158 }\
 159 \
 160 gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
 161 {\
 162   gavl_node_t *n=root->cust_root_node;\
 163   if(!n) return NULL;\
 164   while(n->left)\
 165     n=n->left;\
 166   return n;\
 167 }\
 168 \
 169 gavl_node_t *cust_prefix##_last_node(const cust_root_t *root)\
 170 {\
 171   gavl_node_t *n=root->cust_root_node;\
 172   if(!n) return NULL;\
 173   while(n->right)\
 174     n=n->right;\
 175   return n;\
 176 }
 177
 178
 179 #ifdef __cplusplus
 180 } /* extern "C"*/
 181 #endif
 182
 183 #endif /* _UL_GAVLREPCUST_H */