2 #include "lfds710_btree_addonly_unbalanced_internal.h"
4 /***** private prototypes *****/
5 static void lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds710_btree_au_element **baue );
6 static void lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds710_btree_au_element **baue );
12 /****************************************************************************/
13 int lfds710_btree_au_get_by_key( struct lfds710_btree_au_state *baus,
14 int (*key_compare_function)(void const *new_key, void const *existing_key),
16 struct lfds710_btree_au_element **baue )
22 LFDS710_PAL_ASSERT( baus != NULL );
23 // TRD : key_compare_function can be NULL
24 // TRD : key can be NULL
25 LFDS710_PAL_ASSERT( baue != NULL );
27 if( key_compare_function == NULL )
28 key_compare_function = baus->key_compare_function;
30 LFDS710_MISC_BARRIER_LOAD;
34 LFDS710_MISC_BARRIER_LOAD;
36 while( *baue != NULL and compare_result != 0 )
38 compare_result = key_compare_function( key, (*baue)->key );
40 if( compare_result < 0 )
42 *baue = (*baue)->left;
43 LFDS710_MISC_BARRIER_LOAD;
46 if( compare_result > 0 )
48 *baue = (*baue)->right;
49 LFDS710_MISC_BARRIER_LOAD;
63 /****************************************************************************/
64 int lfds710_btree_au_get_by_absolute_position( struct lfds710_btree_au_state *baus,
65 struct lfds710_btree_au_element **baue,
66 enum lfds710_btree_au_absolute_position absolute_position )
71 LFDS710_PAL_ASSERT( baus != NULL );
72 LFDS710_PAL_ASSERT( baue != NULL );
73 // TRD : absolute_position can be any value in its range
75 LFDS710_MISC_BARRIER_LOAD;
79 LFDS710_MISC_BARRIER_LOAD;
81 switch( absolute_position )
83 case LFDS710_BTREE_AU_ABSOLUTE_POSITION_ROOT:
86 case LFDS710_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE:
88 while( (*baue)->right != NULL )
90 *baue = (*baue)->right;
91 LFDS710_MISC_BARRIER_LOAD;
95 case LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
97 while( (*baue)->left != NULL )
99 *baue = (*baue)->left;
100 LFDS710_MISC_BARRIER_LOAD;
115 /****************************************************************************/
116 int lfds710_btree_au_get_by_relative_position( struct lfds710_btree_au_element **baue,
117 enum lfds710_btree_au_relative_position relative_position )
122 LFDS710_PAL_ASSERT( baue != NULL );
123 // TRD : relative_position can baue any value in its range
128 LFDS710_MISC_BARRIER_LOAD;
130 switch( relative_position )
132 case LFDS710_BTREE_AU_RELATIVE_POSITION_UP:
134 // TRD : no load barrier - up already existed, so is known to be safely propagated
137 case LFDS710_BTREE_AU_RELATIVE_POSITION_LEFT:
138 *baue = (*baue)->left;
139 LFDS710_MISC_BARRIER_LOAD;
142 case LFDS710_BTREE_AU_RELATIVE_POSITION_RIGHT:
143 *baue = (*baue)->right;
144 LFDS710_MISC_BARRIER_LOAD;
147 case LFDS710_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT:
148 *baue = (*baue)->left;
151 LFDS710_MISC_BARRIER_LOAD;
152 while( (*baue)->right != NULL )
154 *baue = (*baue)->right;
155 LFDS710_MISC_BARRIER_LOAD;
160 case LFDS710_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT:
161 *baue = (*baue)->right;
164 LFDS710_MISC_BARRIER_LOAD;
165 while( (*baue)->left != NULL )
167 *baue = (*baue)->left;
168 LFDS710_MISC_BARRIER_LOAD;
173 case LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE:
174 lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( baue );
177 case LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE:
178 lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( baue );
192 /****************************************************************************/
193 static void lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds710_btree_au_element **baue )
195 enum lfds710_btree_au_move
196 action = LFDS710_BTREE_AU_MOVE_INVALID;
198 enum lfds710_misc_flag
199 finished_flag = LFDS710_MISC_FLAG_LOWERED,
200 load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
202 struct lfds710_btree_au_element
209 LFDS710_PAL_ASSERT( baue != NULL );
211 /* TRD : from any given element, the next smallest element is;
212 1. if we have a left, it's the largest element on the right branch of our left child
213 2. if we don't have a left, and we're on the right of our parent, then it's our parent
214 3. if we don't have a left, and we're on the left of our parent or we have no parent,
215 iterative up the tree until we find the first child who is on the right of its parent; then it's the parent
218 /* TRD : we need to ensure the variables we use to decide our action are self-consistent
219 to do this, we make local copies of them all
220 then, if they are all not NULL, we can know they cannot change and we can continue
221 if however any of them are NULL, they could have changed while we were reading
222 and so our variables could be non-self-consistent
223 to check for this, we issue another processor read barrier
224 and then compare our local variables with the values in the tree
225 if they all match, then we know our variable set is self-consistent
226 (even though it may now be wrong - but we will discover this when we try the atomic operation)
229 LFDS710_MISC_BARRIER_LOAD;
231 while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
233 left = (*baue)->left;
234 right = (*baue)->right;
238 up_left = (*baue)->up->left;
239 up_right = (*baue)->up->right;
242 // TRD : optimization - if all already not NULL, given we're add-only, they won't change
243 if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
246 LFDS710_MISC_BARRIER_LOAD;
248 if( left == (*baue)->left and right == (*baue)->right and (up == NULL or (up != NULL and up == (*baue)->up and up_left == (*baue)->up->left and up_right == (*baue)->up->right)) )
249 load_finished_flag = LFDS710_MISC_FLAG_RAISED;
253 action = LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
255 if( left == NULL and up != NULL and up_right == *baue )
256 action = LFDS710_BTREE_AU_MOVE_GET_PARENT;
258 if( (left == NULL and up == NULL) or (up != NULL and up_left == *baue and left == NULL) )
259 action = LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE;
263 case LFDS710_BTREE_AU_MOVE_INVALID:
264 case LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
265 // TRD : eliminates a compiler warning
268 case LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
272 LFDS710_MISC_BARRIER_LOAD;
273 while( (*baue)->right != NULL )
275 *baue = (*baue)->right;
276 LFDS710_MISC_BARRIER_LOAD;
281 case LFDS710_BTREE_AU_MOVE_GET_PARENT:
285 case LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE:
286 while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
288 load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
290 while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
294 up_left = (*baue)->up->left;
296 // TRD : optimization - if all already not NULL, given we're add-only, they won't change
297 if( up == NULL or (up != NULL and up_left != NULL) )
300 LFDS710_MISC_BARRIER_LOAD;
302 if( up == (*baue)->up and up_left == (*baue)->up->left )
303 load_finished_flag = LFDS710_MISC_FLAG_RAISED;
306 if( *baue != NULL and up != NULL and *baue == up_left )
309 finished_flag = LFDS710_MISC_FLAG_RAISED;
316 while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->left )
332 /****************************************************************************/
333 static void lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds710_btree_au_element **baue )
335 enum lfds710_btree_au_move
336 action = LFDS710_BTREE_AU_MOVE_INVALID;
338 enum lfds710_misc_flag
339 finished_flag = LFDS710_MISC_FLAG_LOWERED,
340 load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
342 struct lfds710_btree_au_element
349 LFDS710_PAL_ASSERT( baue != NULL );
351 /* TRD : from any given element, the next largest element is;
352 1. if we have a right, it's the smallest element on the left branch of our right child
353 2. if we don't have a right, and we're on the left of our parent, then it's our parent
354 3. if we don't have a right, and we're on the right of our parent or we have no parent,
355 iterate up the tree until we find the first child who is on the left of its parent; then it's the parent
358 LFDS710_MISC_BARRIER_LOAD;
360 while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
362 left = (*baue)->left;
363 right = (*baue)->right;
367 up_left = (*baue)->up->left;
368 up_right = (*baue)->up->right;
371 // TRD : optimization - if all already not NULL, given we're add-only, they won't change
372 if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
375 LFDS710_MISC_BARRIER_LOAD;
377 if( left == (*baue)->left and right == (*baue)->right and (up == NULL or (up != NULL and up == (*baue)->up and up_left == (*baue)->up->left and up_right == (*baue)->up->right)) )
378 load_finished_flag = LFDS710_MISC_FLAG_RAISED;
382 action = LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
384 if( right == NULL and up != NULL and up_left == *baue )
385 action = LFDS710_BTREE_AU_MOVE_GET_PARENT;
387 if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
388 action = LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE;
392 case LFDS710_BTREE_AU_MOVE_INVALID:
393 case LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
394 // TRD : remove compiler warning
397 case LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
401 LFDS710_MISC_BARRIER_LOAD;
402 while( (*baue)->left != NULL )
404 *baue = (*baue)->left;
405 LFDS710_MISC_BARRIER_LOAD;
410 case LFDS710_BTREE_AU_MOVE_GET_PARENT:
414 case LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE:
415 while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
417 load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
419 while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
423 up_right = (*baue)->up->right;
425 // TRD : optimization - if all already not NULL, given we're add-only, they won't change
426 if( up == NULL or (up != NULL and up_right != NULL) )
429 LFDS710_MISC_BARRIER_LOAD;
431 if( up == (*baue)->up and up_right == (*baue)->up->right )
432 load_finished_flag = LFDS710_MISC_FLAG_RAISED;
435 if( *baue != NULL and up != NULL and *baue == up_right )
438 finished_flag = LFDS710_MISC_FLAG_RAISED;
445 while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->right )
461 /****************************************************************************/
462 int lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds710_btree_au_state *baus,
463 struct lfds710_btree_au_element **baue,
464 enum lfds710_btree_au_absolute_position absolute_position,
465 enum lfds710_btree_au_relative_position relative_position )
470 LFDS710_PAL_ASSERT( baus != NULL );
471 LFDS710_PAL_ASSERT( baue != NULL );
472 // TRD: absolute_position can be any value in its range
473 // TRD: relative_position can be any value in its range
476 rv = lfds710_btree_au_get_by_absolute_position( baus, baue, absolute_position );
478 rv = lfds710_btree_au_get_by_relative_position( baue, relative_position );