1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_gavlflesint.h - custom trees with allowed repeat of keys
5 and fast access to the first and last item
7 (C) Copyright 2003-2004 by Pavel Pisa - Originator
9 The uLan utilities library can be used, copied and modified under
11 - GPL - GNU General Public License
12 - LGPL - GNU Lesser General Public License
13 - MPL - Mozilla Public License
14 - and other licenses added by project originators
15 Code can be modified and re-distributed under any combination
16 of the above listed licenses. If contributor does not agree with
17 some of the licenses, he/she can delete appropriate line.
18 Warning, if you delete all lines, you are not allowed to
19 distribute source code and/or binaries utilizing code.
21 See files COPYING and README for details.
23 *******************************************************************/
25 #ifndef _UL_GAVLFLESINT_H
26 #define _UL_GAVLFLESINT_H
34 /* Declaration of tree with first/last enhanced speed functions with internal node */
35 #define GAVL_FLES_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
36 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
38 static inline cust_item_t * \
39 cust_prefix##_node2item(const cust_root_t *root, const gavl_node_t *node) \
40 {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
42 static inline cust_key_t *\
43 cust_prefix##_node2key(const cust_root_t *root, gavl_node_t *node)\
44 { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
46 cust_scope void cust_prefix##_init_root_field(cust_root_t *root);\
47 cust_scope int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep);\
48 cust_scope cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key);\
49 cust_scope cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key);\
50 cust_scope cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key);\
51 cust_scope int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
52 cust_scope cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
53 cust_scope int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node);\
54 cust_scope int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
57 cust_prefix##_init_detached(cust_item_t *item){\
58 item->cust_item_node.parent=NULL;\
60 static inline gavl_node_t *\
61 cust_prefix##_first_node(const cust_root_t *root)\
63 return root->cust_root_field.first;\
65 static inline gavl_node_t *\
66 cust_prefix##_last_node(const cust_root_t *root)\
68 return root->cust_root_field.last;\
70 static inline cust_item_t *\
71 cust_prefix##_first(const cust_root_t *root)\
73 gavl_node_t *n=cust_prefix##_first_node(root);\
74 return n?cust_prefix##_node2item(root,n):NULL;\
76 static inline cust_item_t *\
77 cust_prefix##_last(const cust_root_t *root)\
79 gavl_node_t *n=cust_prefix##_last_node(root);\
80 return n?cust_prefix##_node2item(root,n):NULL;\
82 static inline cust_item_t *\
83 cust_prefix##_next(const cust_root_t *root, cust_item_t *item)\
85 gavl_node_t *n=gavl_next_node(&item->cust_item_node);\
86 return n?cust_prefix##_node2item(root,n):NULL;\
88 static inline cust_item_t *\
89 cust_prefix##_prev(const cust_root_t *root, cust_item_t *item)\
91 gavl_node_t *n=gavl_prev_node(&item->cust_item_node);\
92 return n?cust_prefix##_node2item(root,n):NULL;\
95 cust_prefix##_is_empty(const cust_root_t *root)\
97 return !root->cust_root_field.root;\
100 UL_ITBASE_SORT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t)
102 #define GAVL_FLES_INT_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
103 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
104 GAVL_FLES_INT_DEC_SCOPE(extern, cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
105 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc)
108 * GAVL_FLES_INT_IMP - Implementation of new custom tree with fast first/last functions
109 * @cust_prefix: defines prefix for builded function names
110 * @cust_root_t: user defined structure type of root of the tree
111 * @cust_item_t: user defined structure type of items stored in the tree
112 * @cust_key_t: type of the key used for sorting of the items
113 * @cust_root_field: the field of the root structure pointing to the tree root node
114 * @cust_item_node: the field of item structure used for chaining of items
115 * @cust_item_key: the key field of item structure defining order of items
116 * @cust_cmp_fnc: the keys compare function
118 * This version of custom tree implementation allows multiple items with same
119 * key value to be stored in tree.
120 * There are two macros designed for building custom AVL trees. The macro
121 * %GAVL_CUST_NODE_INT_DEC declares functions for custom tree manipulations
122 * and is intended for use in header files.
123 * The macro %GAVL_CUST_NODE_INT_REP_IMP builds implementations for non-inlined
124 * functions declared by %GAVL_CUST_NODE_INT_DEC. The @cust_cmp_fnc is used
125 * for comparison of item keys in the search and insert functions. The types
126 * of two input arguments of @cust_cmp_fnc functions must correspond
127 * with @cust_key_t type. Return value should be positive for case when
128 * the first pointed key value is greater then second, negative for reverse
129 * case and zero for equal pointed values.
131 #define GAVL_FLES_INT_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
132 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
133 cust_ins_fl, cust_first_change, cust_last_change, cust_empty_state) \
135 void cust_prefix##_init_root_field(cust_root_t *root)\
137 root->cust_root_field.root=NULL;\
138 root->cust_root_field.first=NULL;\
139 root->cust_root_field.last=NULL;\
140 root->cust_root_field.count=0;\
143 int cust_prefix##_search_node4(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep, int mode)\
147 n=p=root->cust_root_field.root;\
149 cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
153 }else if((cmp<0)||(mode&GAVL_FAFTER)){\
159 if(!cmp && (mode&GAVL_FFIRST)){\
161 cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
165 while((n=n->right)){\
166 cmp=cust_cmp_fnc(cust_prefix##_node2key(root,n),key);\
181 int cust_prefix##_search_node(const cust_root_t *root, cust_key_t const *key, gavl_node_t **nodep)\
183 return cust_prefix##_search_node4(root, key, nodep, 0);\
186 cust_item_t *cust_prefix##_find(const cust_root_t *root, cust_key_t const *key)\
189 if(cust_prefix##_search_node4(root, key, &node, 0))\
191 return cust_prefix##_node2item(root,node);\
194 cust_item_t *cust_prefix##_find_first(const cust_root_t *root, cust_key_t const *key)\
197 if(cust_prefix##_search_node4(root, key, &n, GAVL_FFIRST))\
199 return cust_prefix##_node2item(root,n);\
202 cust_item_t *cust_prefix##_find_after(const cust_root_t *root, cust_key_t const *key)\
205 if(cust_prefix##_search_node4(root, key, &node, GAVL_FAFTER)<=0){\
206 if(node) node=gavl_next_node(node);\
208 return node?cust_prefix##_node2item(root,node):NULL;\
211 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
214 gavl_node_t *where, *n2add;\
216 cmp=cust_prefix##_search_node4(root, &item->cust_item_key, &where, cust_ins_fl);\
217 if(!cmp && !(cust_ins_fl&GAVL_FAFTER)) return -1;\
218 n2add=&item->cust_item_node;\
219 if(!root->cust_root_field.root){\
220 root->cust_root_field.first=root->cust_root_field.last=n2add;\
221 cust_first_change; cust_last_change;\
222 }else if((cmp>0)&&(where==root->cust_root_field.first)){\
223 root->cust_root_field.first=n2add;\
225 }else if((cmp<=0)&&(where==root->cust_root_field.last)){\
226 root->cust_root_field.last=n2add;\
229 root->cust_root_field.count++;\
230 return gavl_insert_primitive_at(&root->cust_root_field.root, n2add, where, cmp);\
233 int cust_prefix##_delete_node(cust_root_t *root, gavl_node_t *node)\
236 /*check if node is inserted into tree*/\
237 for(p=node; p->parent; p=p->parent);\
238 if(p!=root->cust_root_field.root)\
240 if(root->cust_root_field.first==node){\
241 if(root->cust_root_field.last==node){\
242 root->cust_root_field.first=root->cust_root_field.last=NULL;\
245 root->cust_root_field.first=gavl_next_node(node);\
248 }else if(root->cust_root_field.last==node){\
249 root->cust_root_field.last=gavl_prev_node(node);\
252 root->cust_root_field.count--;\
253 return gavl_delete_primitive(&root->cust_root_field.root, node);\
256 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
259 if(!item) return -1;\
260 n=&item->cust_item_node;\
261 return cust_prefix##_delete_node(root, n);\
264 cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
267 gavl_node_t **np=&root->cust_root_field.root;\
268 if(!(n=root->cust_root_field.first))\
270 if(n->parent) np=&n->parent->left;\
273 p->parent=n->parent;\
274 while(p->left) p=p->left;\
275 root->cust_root_field.first=p;\
278 if(!(root->cust_root_field.first=n->parent)){\
279 root->cust_root_field.last=n->parent;\
285 for(p=n->parent;p;p=p->parent)\
286 if(p->hdiff++<0) break;\
287 n->parent=n->left=n->right=NULL;\
288 root->cust_root_field.count--;\
289 return cust_prefix##_node2item(root,n);\
297 #endif /* _UL_GAVLFLESINT_H */