1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gavlcust.h - custom GAVL trees for unique keys
6 (C) Copyright 2003-2004 by Pavel Pisa - Originator
8 The uLan utilities library can be used, copied and modified under
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.
20 See files COPYING and README for details.
22 *******************************************************************/
24 #ifndef _UL_GAVLCUST_H
25 #define _UL_GAVLCUST_H
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
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.
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) \
58 void cust_prefix##_init_root_field(cust_root_t *root)\
60 root->cust_root_node=NULL;\
63 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
67 n=p=root->cust_root_node;\
69 cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
84 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
87 if(cust_prefix##_search_node(root, key, &node))\
89 return cust_prefix##_node2item(root,node);\
92 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
94 return cust_prefix##_find(root, key);\
97 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
100 if(cust_prefix##_search_node(root, key, &node)<=0){\
101 if(node) node=gavl_next_node(node);\
103 return node?cust_prefix##_node2item(root,node):NULL;\
106 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
109 gavl_node_t *where, *n2add;\
111 cmp=cust_prefix##_search_node(root, &item->cust_item_key, &where);\
113 n2add=&item->cust_item_node;\
114 return gavl_insert_primitive_at(&root->cust_root_node, n2add, where, cmp);\
117 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
119 return gavl_delete_primitive(&root->cust_root_node, node);\
122 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
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)\
133 ret=gavl_delete_primitive(&root->cust_root_node, n);\
137 gavl_node_t *cust_prefix##_first_node(const cust_root_t *root)\
139 gavl_node_t *n=root->cust_root_node;\
146 gavl_node_t *cust_prefix##_last_node(const cust_root_t *root)\
148 gavl_node_t *n=root->cust_root_node;\
160 #endif /* _UL_GAVLCUST_H */