1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_hptree.h - heap tree implementation
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 *******************************************************************/
31 typedef struct ul_hpt_node {
36 ul_hpt_node_t **heaparr;
39 } ul_hpt_root_field_t;
41 #define ul_hpt_first_i (1)
42 #define ul_hpt_parent_i(i) ((i)/2)
43 #define ul_hpt_left_i(i) ((i)*2)
44 #define ul_hpt_right_i(i) ((i)*2+1)
46 /* Declaration of heap tree */
47 #define UL_HPTREE_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
48 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
50 static inline cust_item_t * \
51 cust_prefix##_node2item(const cust_root_t *root, const ul_hpt_node_t *node) \
52 {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
54 static inline cust_key_t *\
55 cust_prefix##_node2key(const cust_root_t *root, ul_hpt_node_t *node)\
56 { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
58 int cust_prefix##_init_root_field(cust_root_t *root);\
61 cust_prefix##_init_detached(cust_item_t *item){;}\
63 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
64 cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
65 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
67 static inline cust_item_t *\
68 cust_prefix##_first(const cust_root_t *root)\
71 if(!root->cust_root_field.count)\
73 n=root->cust_root_field.heaparr[ul_hpt_first_i];\
74 return cust_prefix##_node2item(root,n);\
77 cust_prefix##_is_empty(const cust_root_t *root)\
79 return !root->cust_root_field.count;\
82 #define UL_HPTREE_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
83 cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
84 cust_ins_fl, cust_first_change, cust_empty_state) \
86 int cust_prefix##_init_root_field(cust_root_t *root)\
87 { return ul_hpt_init_root_hpt(&root->cust_root_field, 64);}\
90 cust_prefix##_cmp_hpt_i(cust_root_t *root, ul_hpt_node_t *p, ul_hpt_node_t *r)\
92 return cust_cmp_fnc(cust_prefix##_node2key(root,p),\
93 cust_prefix##_node2key(root,r));\
96 int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
99 ul_hpt_node_t *p, *r;\
100 i=root->cust_root_field.count+1;\
101 if(i>root->cust_root_field.capacity)\
102 if(ul_hpt_enlarge_hpt(&root->cust_root_field)<0)\
104 root->cust_root_field.count=i;\
105 p=&item->cust_item_node;\
106 while(i>ul_hpt_first_i){\
107 j=ul_hpt_parent_i(i);\
108 r=root->cust_root_field.heaparr[j];\
109 if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
112 root->cust_root_field.heaparr[i]=r;\
116 root->cust_root_field.heaparr[i]=p;\
117 if(i<=ul_hpt_first_i){\
123 cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
126 ul_hpt_node_t *n, *p, *r;\
127 if(!(i=root->cust_root_field.count))\
130 n=root->cust_root_field.heaparr[ul_hpt_first_i];\
131 if((root->cust_root_field.count=i-1)){\
132 p=root->cust_root_field.heaparr[i];\
134 while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
135 r=root->cust_root_field.heaparr[j];\
136 if(j!=root->cust_root_field.count)\
137 if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
138 {j++; r=root->cust_root_field.heaparr[j];}\
139 if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
142 root->cust_root_field.heaparr[i]=r;\
146 root->cust_root_field.heaparr[i]=p;\
151 return cust_prefix##_node2item(root,n);\
154 int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
157 ul_hpt_node_t *p, *r;\
158 p=&item->cust_item_node;\
160 if(i>root->cust_root_field.count) return -1;\
161 if(root->cust_root_field.heaparr[i]!=p) return -1;\
162 if(i==ul_hpt_first_i){\
163 cust_prefix##_cut_first(root);\
166 if(i==(j=root->cust_root_field.count--))\
168 p=root->cust_root_field.heaparr[j];\
169 j=ul_hpt_parent_i(i);\
170 r=root->cust_root_field.heaparr[j];\
171 if(cust_prefix##_cmp_hpt_i(root,p,r)<0){\
174 root->cust_root_field.heaparr[i]=r;\
176 j=ul_hpt_parent_i(i);\
177 r=root->cust_root_field.heaparr[j];\
178 if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
182 while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
183 r=root->cust_root_field.heaparr[j];\
184 if(j!=root->cust_root_field.count)\
185 if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
186 {j++; r=root->cust_root_field.heaparr[j];}\
187 if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
190 root->cust_root_field.heaparr[i]=r;\
195 root->cust_root_field.heaparr[i]=p;\
199 int ul_hpt_init_root_hpt(ul_hpt_root_field_t *hpt_root, int acapacity);
200 int ul_hpt_enlarge_hpt(ul_hpt_root_field_t *hpt_root);
206 #endif /* _UL_HPTREE_H */