tree.h

Go to the documentation of this file.
00001 /* Adapted from... */
00002 /*
00003  * ANSI C Library for maintainance of AVL Balanced Trees
00004  *
00005  * ref.:
00006  *  G. M. Adelson-Velskij & E. M. Landis
00007  *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
00008  *
00009  * see also:
00010  *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
00011  *
00012  * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
00013  * Released under GNU General Public License (GPL) version 2
00014  * 
00015  */
00016 #ifndef CTL_TREE_H
00017 #define CTL_TREE_H
00018 
00071 typedef int (*tree_compare)(const void *left, const void *right );
00072 
00073 /* Give each kind of offset ctlt_ a name/value to operate with #if/#elif/#else directives for template code a little easier to follow */
00074 #define ctlt_offset_name(offset)                ppConcat(ctlt_offset_name_,offset)
00075 #define     ctlt_offset_name_ctlt_zero                  zero
00076 #define     ctlt_offset_name_ctlt_after                 after
00077 #define     ctlt_offset_name_ctlt_relative(off)         rel
00078 #define     ctlt_offset_name_ctlt_member(type,member)   ppConcat3(type,_,member) /* this is an #elif directive fall-through sort of thing */
00079 
00080 /* Dereference node type by member type */
00081 #define ctlt_node_type(offset,multiple)                 ppConcat(ctlt_node_type_,offset)(offset,multiple)
00082 #define     ctlt_node_type_ctlt_zero(offset,multiple)           ctl_tree_(offset,multiple, node )
00083 #define     ctlt_node_type_ctlt_after(offset,multiple)          ctl_tree_(offset,multiple, node )
00084 #define     ctlt_node_type_ctlt_relative(off)                   ctlt_node_type_ctlt_relative_x
00085 #define         ctlt_node_type_ctlt_relative_x(offset,multiple) ctl_tree_(offset,multiple, node )
00086 #define     ctlt_node_type_ctlt_member(type,mbr)                type ppEat
00087 
00088 /* Get data-to-node dereference data offset by template */
00089 #define ctlt_getoffset(offset,multiple)             ppConcat(ctlt_getoffset_,offset)
00090 #define     ctlt_getoffset_ctlt_zero                    0
00091 #define     ctlt_getoffset_ctlt_after                   (-sizeof(ctlt_node_type(offset,multiple)))
00092 #define     ctlt_getoffset_ctlt_relative(off)           (off)
00093 #define     ctlt_getoffset_ctlt_member(type,member)     offsetof(type,member)
00094 
00095 /* Dereference data type by member type */
00096 #define ctlt_offset_type(off_t)                     ppConcat(ctlt_offset_type_,off_t)
00097 #define     ctlt_offset_type_ctlt_zero                  void
00098 #define     ctlt_offset_type_ctlt_after                 void
00099 #define     ctlt_offset_type_ctlt_relative(off)         void
00100 #define     ctlt_offset_type_ctlt_member(type,member)   type
00101 
00102 /* Dereference member by member type (ctlt_member is only valid for ctlt_member) */
00103 #define ctlt_offset_member(off_t)               ppConcat(ctlt_offset_member_,off_t)
00104 #define     ctlt_offset_member_ctlt_zero                /*#error ctlt_member is only valid for ctlt_member*/
00105 #define     ctlt_offset_member_ctlt_after               /*#error ctlt_member is only valid for ctlt_member*/
00106 #define     ctlt_offset_member_ctlt_relative(off)       /*#error ctlt_member is only valid for ctlt_member*/
00107 #define     ctlt_offset_member_ctlt_member(type,member) member
00108 
00109 /* Selection of code/data/tokens based on 'member' template */
00110 #define ctlt_offset_for_zero(off_t,dothis)              ppConcat(ctlt_for_zero_,off_t)(dothis)
00111 #define     ctlt_for_zero_ctlt_zero(dothis)                 dothis
00112 #define     ctlt_for_zero_ctlt_after(dothis)
00113 #define     ctlt_for_zero_ctlt_relative(off)                ppEat
00114 #define     ctlt_for_zero_ctlt_member(type,member)          ppEat
00115 #define ctlt_offset_for_after(off_t,dothis)             ppConcat(ctlt_for_after_,off_t)(dothis)
00116 #define     ctlt_for_after_ctlt_after(dothis)               dothis
00117 #define     ctlt_for_after_ctlt_zero(dothis)            
00118 #define     ctlt_for_after_ctlt_relative(off)               ppEat
00119 #define     ctlt_for_after_ctlt_member(type,member)         ppEat
00120 #define ctlt_offset_for_relative(off_t,dothis)          ppConcat(ctlt_for_relative_,off_t)(dothis)
00121 #define     ctlt_for_relative_ctlt_relative(off)            ctlt_for_relative_ctlt_relative_x
00122 #define         ctlt_for_relative_ctlt_relative_x(dothis)   dothis
00123 #define     ctlt_for_relative_ctlt_zero(dothis)         
00124 #define     ctlt_for_relative_ctlt_after(dothis)            
00125 #define     ctlt_for_relative_ctlt_member(type,member)      ppEat
00126 #define ctlt_offset_for_member(off_t,dothis)            ppConcat(ctlt_for_member_,off_t)(dothis)
00127 #define     ctlt_for_member_ctlt_member(type,member)        ctlt_for_member_member_x
00128 #define         ctlt_for_member_ctlt_member_x(dothis)           dothis
00129 #define     ctlt_for_member_ctlt_zero(dothis)           
00130 #define     ctlt_for_member_ctlt_after(dothis)          
00131 #define     ctlt_for_member_ctlt_relative(off)              ppEat
00132 
00133 /* Give each kind of multiple ctlt_ a value  */
00134 #define ctlt_multi_value(multi)             ppConcat(multi_value_,multi)
00135 #define     multi_value_ctlt_multiple           1
00136 #define     multi_value_ctlt_unique             0
00137 
00138 /* Doxygen chokes on !(ctlt_multi_value(multi)), so use an alternative */
00139 #define ctlt_multi_not_value(multi)         ppConcat(multi_not_value_,multi)
00140 #define     multi_not_value_ctlt_multiple       0
00141 #define     multi_not_value_ctlt_unique         1
00142 
00143 /* Give each kind of offset ctlt_ a name/value to operate with #if/#elif/#else directives for template code a little easier to follow */
00144 #define ctlt_multi_name(multi)              offset_name_##multi
00145 #define     offset_name_ctlt_multiple           multi
00146 #define     offset_name_ctlt_unique             unique
00147 
00148 /* Selection of code/data/tokens based on 'multiple' template */
00149 #define ctlt_multiple_for_multiple(multiple,dothis) ppConcat(ctlt_for_multiple_,member)(dothis)
00150 #define     ctlt_for_multiple_multiple(dothis)          dothis
00151 #define     ctlt_for_multiple_unique(dothis)            
00152 #define ctlt_multiple_for_unique(multiple,dothis)   ppConcat(ctlt_for_unique_,member)(dothis)
00153 #define     ctlt_for_unique_multiple(dothis)            
00154 #define     ctlt_for_unique_unique(dothis)              dothis
00155 
00162 #define ctl_tree(offset,multiple)           ppConcat4(ctl_tree_,ctlt_offset_name(offset),_,ctlt_multi_name(multiple))
00163 
00171 #define ctl_tree_(offset,multiple, label )  ppConcat3(ctl_tree(offset,multiple),_,label)
00172 
00173 #define ctldecl_ctl_tree(offset,multiple) \
00174 /*\
00175  * \ingroup Containers
00176  * \brief One element of an AVL tree \
00177  */\
00178 typedef struct ctlt_node_type(offset,multiple)\
00179 {\
00180     struct ctlt_node_type(offset,multiple)*     left;       /* Lower value node */\
00181     struct ctlt_node_type(offset,multiple)*     right;      /* Higher value node */\
00182     int8                                        balance;    /* Housekeeping value for balancing tree */\
00183     /* Wasted space... maybe just copy tree offset to nodes? */\
00184 } ctlt_node_type(offset,multiple);\
00185 /*\
00186  * An avl tree \
00187  */\
00188 typedef struct ctl_tree(offset,multiple) \
00189 {\
00190     ctlt_node_type(offset,multiple)*                root;       /* Root node for tree */\
00191     tree_compare                                    compare;    /* Comparator */\
00192     size_t                                          size;       /* Count of things in the tree */\
00193     ctlt_node_type(offset,multiple)*                found;      /* A place to put insert/search status */\
00194     ctlt_offset_for_relative(offset, size_t         data_offset;/* Offset to node data, per node */)    \
00195 } ctl_tree(offset,multiple);\
00196 ctlt_offset_type(offset)* ctl_tree_(offset,multiple, insert)( ctl_tree(offset,multiple)* tree, ctlt_offset_type(offset)* data );\
00197 ctlt_offset_type(offset)* ctl_tree_(offset,multiple, remove)( ctl_tree(offset,multiple)* tree, ctlt_offset_type(offset)* data );\
00198 ctlt_offset_type(offset)* ctl_tree_(offset,multiple, unlink)( ctl_tree(offset,multiple)* tree, ctlt_offset_type(offset)* data );\
00199 void ctl_tree_(offset,multiple, reset)( ctl_tree(offset,multiple)* tree );\
00200 size_t ctl_tree_(offset,multiple, tally)( const ctl_tree(offset,multiple)* tree );\
00201 size_t ctl_tree_(offset,multiple, depth)( const ctl_tree(offset,multiple)* tree );\
00202 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, front)( const ctl_tree(offset,multiple)* tree );\
00203 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, back)( const ctl_tree(offset,multiple)* tree );\
00204 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, find)( const ctl_tree(offset,multiple)* tree, const ctlt_offset_type(offset)* data );\
00205 ctlt_offset_type(offset)* ctl_tree_(offset,multiple, pop_front)( ctl_tree(offset,multiple)* tree );\
00206 ctlt_offset_type(offset)* ctl_tree_(offset,multiple, pop_back)( ctl_tree(offset,multiple)* tree );\
00207 ppForUnit( void ctl_tree_(offset,multiple, pretty_print)( const ctl_tree(offset,multiple) *tree, ctl_tree_printf print, ctlt_node_type(offset,multiple)* hilight ); )\
00208 /*\
00209  * A binary tree stack for iterating node members.\
00210  * Basically, this takes the place of having 'parent' members in every node\
00211  * and inexpensively allows stl iterator-like operations.\
00212  * Not reversible once it's begun.\
00213  */\
00214 typedef struct ctl_tree_(offset,multiple, iterator )\
00215 {\
00216     const ctl_tree(offset,multiple)*            tree;       /* Tree for reference */\
00217     const ctlt_node_type(offset,multiple)*      node;       /* The last node that begin.../next/rbegin.../prev returned */\
00218     const ctlt_node_type(offset,multiple)**     sp;         /* Stack pointer for operations */\
00219     const ctlt_node_type(offset,multiple)*      stack[64];  /* LIFO Maximum stack depth (a 64-deep binary tree could contain quadrillion of members) */\
00220     bool                                        bReverse;   /* Set if this was iterating backwards */\
00221 } ctl_tree_(offset,multiple, iterator );\
00222 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_begin)( ctl_tree_(offset,multiple, iterator )* stack, const ctl_tree(offset,multiple)* tree );\
00223 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_begin_from)( ctl_tree_(offset,multiple, iterator )* stack, const ctl_tree(offset,multiple)* tree, const ctlt_offset_type(offset)* data );\
00224 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_next)( ctl_tree_(offset,multiple, iterator )* stack );\
00225 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_rbegin)( ctl_tree_(offset,multiple, iterator )* stack, const ctl_tree(offset,multiple) *tree );\
00226 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_rbegin_from)( ctl_tree_(offset,multiple, iterator )* stack, const ctl_tree(offset,multiple)* tree, const ctlt_offset_type(offset)* data );\
00227 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, iterator_prev)( ctl_tree_(offset,multiple, iterator )* stack );\
00228 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, unlink_curr)( ctl_tree_(offset,multiple, iterator )* stack );\
00229 const ctlt_offset_type(offset)* ctl_tree_(offset,multiple, unlink_curr_resume)( ctl_tree_(offset,multiple, iterator )* stack );\
00230 
00231 
00240 #define ctl_tree_node_to_data(offset,multiple, tree,node)                   ppConcat(ctl_tree_node_data_,offset)(offset,multiple, tree, node )
00241 #define     ctl_tree_node_data_ctlt_zero(offset,multiple, tree,node)            (node)
00242 #define     ctl_tree_node_data_ctlt_after(offset,multiple, tree,node)           ((node)+1)
00243 #define     ctl_tree_node_data_ctlt_relative(offset)                            ctl_tree_node_data_ctlt_relativex
00244 #define         ctl_tree_node_data_ctlt_relativex(offset,multiple, tree,node)       ((uint8*)(node)-(tree)->data_offset)
00245 #define     ctl_tree_node_data_member(type,mbr)                                 ((type *) ctl_tree_node_data_memberx
00246 #define         ctl_tree_node_data_memberx(offset,multiple, tree,node)              (node))
00247 
00257 #define ctl_tree_data_to_node(offset,multiple, tree, data)                  ppConcat(ctl_tree_data_node_,offset)(offset,multiple, tree, data )
00258 #define     ctl_tree_data_node_ctlt_zero(offset,multiple, tree,data)            ((ctlt_node_type(offset,multiple)*)(data))
00259 #define     ctl_tree_data_node_ctlt_after(offset,multiple, tree,data)           ((ctlt_node_type(offset,multiple)*)(data)-1)
00260 #define     ctl_tree_data_node_ctlt_relative(off)                               ctl_tree_data_node_ctlt_relativex
00261 #define         ctl_tree_data_node_ctlt_relativex(offset,multiple, tree,data)       ((ctlt_node_type(offset,multiple)*)((uint8*)(data)+(tree)->data_offset))
00262 #define     ctl_tree_data_node_ctlt_member(type,mbr)                            ((type *) ctl_tree_data_node_ctlt_memberx
00263 #define         ctl_tree_data_node_ctlt_memberx(offset,multiple, tree,data)     (data))
00264 
00272 #define ctl_tree_node_init(offset,multiple, node)               { (node)->left = (node)->right = NULL; (node)->balance = 0; }
00273 
00283 #define ctl_tree_auto(offset,multiple, comparator, label )      \
00284     ctl_tree(offset,multiple) label = \
00285         { NULL, (tree_compare)(comparator), 0, NULL, ctlt_offset_for_relative(offset, ctlt_getoffset(offset,multiple)) }
00286 
00295 #define ctl_tree_init(offset,multiple, comparator, tree )       { (tree)->found = (tree)->root = NULL; (tree)->compare = (tree_compare)(comparator); (tree)->size = 0; ctlt_offset_for_relative(offset, (tree)->data_offset = ctlt_getoffset(offset,multiple);) }
00296 
00305 #define ctl_tree_size(offset,multiple,  tree )      ((tree)->size)
00306 
00307 
00308 #ifdef CTL_UNIT
00309 
00317 typedef size_t (*ctl_tree_printf)(const void* data, char *buff, size_t buffSize);
00318 #endif
00319 /*
00320  * Generate relative trees
00321 **/
00322 ctldecl_ctl_tree(ctlt_relative(0),ctlt_unique)
00323 ctldecl_ctl_tree(ctlt_relative(0),ctlt_multiple)
00324 ctldecl_ctl_tree(ctlt_after,ctlt_unique)
00325 ctldecl_ctl_tree(ctlt_after,ctlt_multiple)
00326 
00327 #endif /* CTL_TREE_H */