ulut/ul_gavlcust.h

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