2 #include "lfds700_btree_addonly_unbalanced_internal.h"
8 /****************************************************************************/
9 void lfds700_btree_au_cleanup( struct lfds700_btree_au_state *baus,
10 void (*element_cleanup_callback)(struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element *baue) )
12 enum lfds700_btree_au_delete_action
13 delete_action = LFDS700_BTREE_AU_DELETE_SELF; // TRD : to remove compiler warning
15 struct lfds700_btree_au_element
18 struct lfds700_btree_au_element
21 LFDS700_PAL_ASSERT( baus != NULL );
22 // TRD : element_delete_function can be NULL
24 /* TRD : we're not lock-free now, so delete at will
25 but be iterative, so can be used in kernels (where there's little stack)
26 and be performant, since the user may be
27 creating/destroying many of these trees
28 also remember the user may be deallocating user data
29 so we cannot visit an element twice
31 we start at the root and iterate till we go to NULL
32 if the element has zero children, we delete it and move up to its parent
33 if the element has one child, we delete it, move its child into its place, and continue from its child
34 if the element has two children, we move left
36 the purpose of this is to minimize walking around the tree
37 to prevent visiting an element twice
38 while also minimizing code complexity
41 if( element_cleanup_callback == NULL )
44 LFDS700_MISC_BARRIER_LOAD;
46 lfds700_btree_au_get_by_absolute_position( baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_ROOT );
50 if( baue->left == NULL and baue->right == NULL )
51 delete_action = LFDS700_BTREE_AU_DELETE_SELF;
53 if( baue->left != NULL and baue->right == NULL )
54 delete_action = LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD;
56 if( baue->left == NULL and baue->right != NULL )
57 delete_action = LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD;
59 if( baue->left != NULL and baue->right != NULL )
60 delete_action = LFDS700_BTREE_AU_DELETE_MOVE_LEFT;
62 switch( delete_action )
64 case LFDS700_BTREE_AU_DELETE_SELF:
65 // TRD : if we have a parent (we could be root) set his point to us to NULL
66 if( baue->up != NULL )
68 if( baue->up->left == baue )
69 baue->up->left = NULL;
70 if( baue->up->right == baue )
71 baue->up->right = NULL;
75 lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_UP );
76 element_cleanup_callback( baus, temp );
79 case LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD:
80 baue->left->up = baue->up;
81 if( baue->up != NULL )
83 if( baue->up->left == baue )
84 baue->up->left = baue->left;
85 if( baue->up->right == baue )
86 baue->up->right = baue->left;
90 lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT );
91 element_cleanup_callback( baus, temp );
94 case LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD:
95 baue->right->up = baue->up;
96 if( baue->up != NULL )
98 if( baue->up->left == baue )
99 baue->up->left = baue->right;
100 if( baue->up->right == baue )
101 baue->up->right = baue->right;
105 lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_RIGHT );
106 element_cleanup_callback( baus, temp );
109 case LFDS700_BTREE_AU_DELETE_MOVE_LEFT:
110 lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT );