2 #include "lfds700_btree_addonly_unbalanced_internal.h"
4 /***** private prototypes *****/
5 static void lfds700_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds700_btree_au_element **baue );
6 static void lfds700_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds700_btree_au_element **baue );
12 /****************************************************************************/
13 int lfds700_btree_au_get_by_key( struct lfds700_btree_au_state *baus,
15 struct lfds700_btree_au_element **baue )
21 LFDS700_PAL_ASSERT( baus != NULL );
22 // TRD : key can be NULL
23 LFDS700_PAL_ASSERT( baue != NULL );
25 LFDS700_MISC_BARRIER_LOAD;
29 LFDS700_MISC_BARRIER_LOAD;
31 while( *baue != NULL and compare_result != 0 )
33 compare_result = baus->key_compare_function( key, (*baue)->key );
35 if( compare_result < 0 )
37 *baue = (*baue)->left;
38 LFDS700_MISC_BARRIER_LOAD;
41 if( compare_result > 0 )
43 *baue = (*baue)->right;
44 LFDS700_MISC_BARRIER_LOAD;
58 /****************************************************************************/
59 int lfds700_btree_au_get_by_absolute_position( struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element **baue, enum lfds700_btree_au_absolute_position absolute_position )
64 LFDS700_PAL_ASSERT( baus != NULL );
65 LFDS700_PAL_ASSERT( baue != NULL );
66 // TRD : absolute_position can be any value in its range
68 LFDS700_MISC_BARRIER_LOAD;
72 LFDS700_MISC_BARRIER_LOAD;
74 switch( absolute_position )
76 case LFDS700_BTREE_AU_ABSOLUTE_POSITION_ROOT:
79 case LFDS700_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE:
81 while( (*baue)->right != NULL )
83 *baue = (*baue)->right;
84 LFDS700_MISC_BARRIER_LOAD;
88 case LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
90 while( (*baue)->left != NULL )
92 *baue = (*baue)->left;
93 LFDS700_MISC_BARRIER_LOAD;
108 /****************************************************************************/
109 int lfds700_btree_au_get_by_relative_position( struct lfds700_btree_au_element **baue, enum lfds700_btree_au_relative_position relative_position )
114 LFDS700_PAL_ASSERT( baue != NULL );
115 // TRD : relative_position can baue any value in its range
120 LFDS700_MISC_BARRIER_LOAD;
122 switch( relative_position )
124 case LFDS700_BTREE_AU_RELATIVE_POSITION_UP:
126 // TRD : no load barrier - up already existed, so is known to be safely propagated
129 case LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT:
130 *baue = (*baue)->left;
131 LFDS700_MISC_BARRIER_LOAD;
134 case LFDS700_BTREE_AU_RELATIVE_POSITION_RIGHT:
135 *baue = (*baue)->right;
136 LFDS700_MISC_BARRIER_LOAD;
139 case LFDS700_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT:
140 *baue = (*baue)->left;
143 LFDS700_MISC_BARRIER_LOAD;
144 while( (*baue)->right != NULL )
146 *baue = (*baue)->right;
147 LFDS700_MISC_BARRIER_LOAD;
152 case LFDS700_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT:
153 *baue = (*baue)->right;
156 LFDS700_MISC_BARRIER_LOAD;
157 while( (*baue)->left != NULL )
159 *baue = (*baue)->left;
160 LFDS700_MISC_BARRIER_LOAD;
165 case LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE:
166 lfds700_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( baue );
169 case LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE:
170 lfds700_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( baue );
184 /****************************************************************************/
185 static void lfds700_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds700_btree_au_element **baue )
187 enum lfds700_btree_au_move
188 action = LFDS700_BTREE_AU_MOVE_INVALID;
190 enum lfds700_misc_flag
191 finished_flag = LFDS700_MISC_FLAG_LOWERED,
192 load_finished_flag = LFDS700_MISC_FLAG_LOWERED;
194 struct lfds700_btree_au_element
201 LFDS700_PAL_ASSERT( baue != NULL );
203 /* TRD : from any given element, the next smallest element is;
204 1. if we have a left, it's the largest element on the right branch of our left child
205 2. if we don't have a left, and we're on the right of our parent, then it's our parent
206 3. if we don't have a left, and we're on the left of our parent or we have no parent,
207 iterative up the tree until we find the first child who is on the right of its parent; then it's the parent
210 /* TRD : we need to ensure the variables we use to decide our action are self-consistent
211 to do this, we make local copies of them all
212 then, if they are all not NULL, we can know they cannot change and we can continue
213 if however any of them are NULL, they could have changed while we were reading
214 and so our variables could be non-self-consistent
215 to check for this, we issue another processor read barrier
216 and then compare our local variables with the values in the tree
217 if they all match, then we know our variable set is self-consistent
218 (even though it may now be wrong - but we will discover this when we try the atomic operation)
221 LFDS700_MISC_BARRIER_LOAD;
223 while( load_finished_flag == LFDS700_MISC_FLAG_LOWERED )
225 left = (*baue)->left;
226 right = (*baue)->right;
230 up_left = (*baue)->up->left;
231 up_right = (*baue)->up->right;
234 if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
237 LFDS700_MISC_BARRIER_LOAD;
239 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)) )
240 load_finished_flag = LFDS700_MISC_FLAG_RAISED;
244 action = LFDS700_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
246 if( left == NULL and up != NULL and up_right == *baue )
247 action = LFDS700_BTREE_AU_MOVE_GET_PARENT;
249 if( (left == NULL and up == NULL) or (up != NULL and up_left == *baue and left == NULL) )
250 action = LFDS700_BTREE_AU_MOVE_MOVE_UP_TREE;
254 case LFDS700_BTREE_AU_MOVE_INVALID:
255 case LFDS700_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
256 // TRD : eliminates a compiler warning
259 case LFDS700_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
263 LFDS700_MISC_BARRIER_LOAD;
264 while( (*baue)->right != NULL )
266 *baue = (*baue)->right;
267 LFDS700_MISC_BARRIER_LOAD;
272 case LFDS700_BTREE_AU_MOVE_GET_PARENT:
276 case LFDS700_BTREE_AU_MOVE_MOVE_UP_TREE:
277 while( finished_flag == LFDS700_MISC_FLAG_LOWERED )
279 load_finished_flag = LFDS700_MISC_FLAG_LOWERED;
281 while( load_finished_flag == LFDS700_MISC_FLAG_LOWERED )
285 up_left = (*baue)->up->left;
287 if( up == NULL or (up != NULL and up_left != NULL) )
290 LFDS700_MISC_BARRIER_LOAD;
292 if( up == (*baue)->up and up_left == (*baue)->up->left )
293 load_finished_flag = LFDS700_MISC_FLAG_RAISED;
296 if( *baue != NULL and up != NULL and *baue == up_left )
299 finished_flag = LFDS700_MISC_FLAG_RAISED;
306 while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->left )
322 /****************************************************************************/
323 static void lfds700_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds700_btree_au_element **baue )
325 enum lfds700_btree_au_move
326 action = LFDS700_BTREE_AU_MOVE_INVALID;
328 enum lfds700_misc_flag
329 finished_flag = LFDS700_MISC_FLAG_LOWERED,
330 load_finished_flag = LFDS700_MISC_FLAG_LOWERED;
332 struct lfds700_btree_au_element
339 LFDS700_PAL_ASSERT( baue != NULL );
341 /* TRD : from any given element, the next largest element is;
342 1. if we have a right, it's the smallest element on the left branch of our right child
343 2. if we don't have a right, and we're on the left of our parent, then it's our parent
344 3. if we don't have a right, and we're on the right of our parent or we have no parent,
345 iterate up the tree until we find the first child who is on the left of its parent; then it's the parent
348 LFDS700_MISC_BARRIER_LOAD;
350 while( load_finished_flag == LFDS700_MISC_FLAG_LOWERED )
352 left = (*baue)->left;
353 right = (*baue)->right;
357 up_left = (*baue)->up->left;
358 up_right = (*baue)->up->right;
361 if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
364 LFDS700_MISC_BARRIER_LOAD;
366 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)) )
367 load_finished_flag = LFDS700_MISC_FLAG_RAISED;
371 action = LFDS700_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
373 if( right == NULL and up != NULL and up_left == *baue )
374 action = LFDS700_BTREE_AU_MOVE_GET_PARENT;
376 if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
377 action = LFDS700_BTREE_AU_MOVE_MOVE_UP_TREE;
381 case LFDS700_BTREE_AU_MOVE_INVALID:
382 case LFDS700_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
383 // TRD : remove compiler warning
386 case LFDS700_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
390 LFDS700_MISC_BARRIER_LOAD;
391 while( (*baue)->left != NULL )
393 *baue = (*baue)->left;
394 LFDS700_MISC_BARRIER_LOAD;
399 case LFDS700_BTREE_AU_MOVE_GET_PARENT:
403 case LFDS700_BTREE_AU_MOVE_MOVE_UP_TREE:
404 while( finished_flag == LFDS700_MISC_FLAG_LOWERED )
406 load_finished_flag = LFDS700_MISC_FLAG_LOWERED;
408 while( load_finished_flag == LFDS700_MISC_FLAG_LOWERED )
412 up_right = (*baue)->up->right;
414 if( up == NULL or (up != NULL and up_right != NULL) )
417 LFDS700_MISC_BARRIER_LOAD;
419 if( up == (*baue)->up and up_right == (*baue)->up->right )
420 load_finished_flag = LFDS700_MISC_FLAG_RAISED;
423 if( *baue != NULL and up != NULL and *baue == up_right )
426 finished_flag = LFDS700_MISC_FLAG_RAISED;
433 while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->right )
449 /****************************************************************************/
450 int lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element **baue, enum lfds700_btree_au_absolute_position absolute_position, enum lfds700_btree_au_relative_position relative_position )
455 LFDS700_PAL_ASSERT( baus != NULL );
456 LFDS700_PAL_ASSERT( baue != NULL );
457 // TRD: absolute_position can be any value in its range
458 // TRD: relative_position can be any value in its range
461 rv = lfds700_btree_au_get_by_absolute_position( baus, baue, absolute_position );
463 rv = lfds700_btree_au_get_by_relative_position( baue, relative_position );