2 #include "libbenchmark_datastructure_btree_au_internal.h"
4 /***** private prototypes *****/
5 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue );
6 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue );
12 /****************************************************************************/
13 void libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_init( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus,
14 int (*key_compare_function)(void const *new_key, void const *existing_key),
15 enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_existing_key existing_key,
18 LFDS710_PAL_ASSERT( baus != NULL );
19 LFDS710_PAL_ASSERT( key_compare_function != NULL );
20 // TRD : existing_key can be any value in its range
21 // TRD : user_state can be NULL
24 baus->key_compare_function = key_compare_function;
25 baus->existing_key = existing_key;
26 baus->user_state = user_state;
28 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_CREATE( baus->lock );
30 LFDS710_MISC_BARRIER_STORE;
32 lfds710_misc_force_store();
41 /****************************************************************************/
42 void libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_cleanup( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus,
43 void (*element_cleanup_callback)(struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element *baue) )
45 enum libbenchmark_datastructure_btree_au_delete_action
46 delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF; // TRD : to remove compiler warning
48 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element
52 LFDS710_PAL_ASSERT( baus != NULL );
53 // TRD : element_delete_function can be NULL
55 if( element_cleanup_callback != NULL )
57 libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_absolute_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_ABSOLUTE_POSITION_ROOT );
61 if( baue->left == NULL and baue->right == NULL )
62 delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF;
64 if( baue->left != NULL and baue->right == NULL )
65 delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD;
67 if( baue->left == NULL and baue->right != NULL )
68 delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD;
70 if( baue->left != NULL and baue->right != NULL )
71 delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT;
73 switch( delete_action )
75 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF:
76 // TRD : if we have a parent (we could be root) set his point to us to NULL
77 if( baue->up != NULL )
79 if( baue->up->left == baue )
80 baue->up->left = NULL;
81 if( baue->up->right == baue )
82 baue->up->right = NULL;
86 libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_UP );
87 element_cleanup_callback( baus, temp );
90 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD:
91 baue->left->up = baue->up;
92 if( baue->up != NULL )
94 if( baue->up->left == baue )
95 baue->up->left = baue->left;
96 if( baue->up->right == baue )
97 baue->up->right = baue->left;
101 libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_LEFT );
102 element_cleanup_callback( baus, temp );
105 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD:
106 baue->right->up = baue->up;
107 if( baue->up != NULL )
109 if( baue->up->left == baue )
110 baue->up->left = baue->right;
111 if( baue->up->right == baue )
112 baue->up->right = baue->right;
116 libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_RIGHT );
117 element_cleanup_callback( baus, temp );
120 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT:
121 libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_LEFT );
127 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_DESTROY( baus->lock );
136 /****************************************************************************/
137 enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_insert_result libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_insert( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus,
138 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element *baue,
139 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **existing_baue )
144 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element
149 LFDS710_PAL_ASSERT( baus != NULL );
150 LFDS710_PAL_ASSERT( baue != NULL );
151 // TRD : existing_baue can be NULL
153 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_GET( baus->lock );
155 baue->up = baue->left = baue->right = NULL;
157 baue_temp = baus->root;
159 while( baue_temp != NULL )
161 compare_result = baus->key_compare_function( baue->key, baue_temp->key );
163 if( compare_result == 0 )
165 if( existing_baue != NULL )
166 *existing_baue = baue_temp;
168 switch( baus->existing_key )
170 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_EXISTING_KEY_OVERWRITE:
171 LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_SET_VALUE_IN_ELEMENT( *baus, *baue_temp, baue->value );
172 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_INSERT_RESULT_SUCCESS_OVERWRITE;
175 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_EXISTING_KEY_FAIL:
176 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_INSERT_RESULT_FAILURE_EXISTING_KEY;
181 if( compare_result < 0 )
182 baue_next = baue_temp->left;
184 if( compare_result > 0 )
185 baue_next = baue_temp->right;
187 baue_parent = baue_temp;
188 baue_temp = baue_next;
191 if( baue_parent == NULL )
193 baue->up = baus->root;
196 if( baue_parent != NULL )
198 if( compare_result <= 0 )
200 baue->up = baue_parent;
201 baue_parent->left = baue;
204 if( compare_result > 0 )
206 baue->up = baue_parent;
207 baue_parent->right = baue;
211 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_RELEASE( baus->lock );
213 // TRD : if we get to here, we added (not failed or overwrite on exist) a new element
214 if( existing_baue != NULL )
215 *existing_baue = NULL;
217 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_INSERT_RESULT_SUCCESS;
224 /****************************************************************************/
225 int libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_key( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus,
226 int (*key_compare_function)(void const *new_key, void const *existing_key),
228 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue )
234 LFDS710_PAL_ASSERT( baus != NULL );
235 // TRD : key_compare_function can be NULL
236 // TRD : key can be NULL
237 LFDS710_PAL_ASSERT( baue != NULL );
239 if( key_compare_function == NULL )
240 key_compare_function = baus->key_compare_function;
242 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_GET( baus->lock );
246 while( *baue != NULL and compare_result != 0 )
248 compare_result = key_compare_function( key, (*baue)->key );
250 if( compare_result < 0 )
251 *baue = (*baue)->left;
253 if( compare_result > 0 )
254 *baue = (*baue)->right;
257 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_RELEASE( baus->lock );
269 /****************************************************************************/
270 int libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_absolute_position( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue, enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_absolute_position absolute_position )
275 LFDS710_PAL_ASSERT( baus != NULL );
276 LFDS710_PAL_ASSERT( baue != NULL );
277 // TRD : absolute_position can be any value in its range
279 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_GET( baus->lock );
283 switch( absolute_position )
285 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_ABSOLUTE_POSITION_ROOT:
288 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_ABSOLUTE_POSITION_LARGEST_IN_TREE:
290 while( (*baue)->right != NULL )
291 *baue = (*baue)->right;
294 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
296 while( (*baue)->left != NULL )
297 *baue = (*baue)->left;
301 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_RELEASE( baus->lock );
313 /****************************************************************************/
314 int libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue, enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_relative_position relative_position )
319 LFDS710_PAL_ASSERT( baus != NULL );
320 LFDS710_PAL_ASSERT( baue != NULL );
321 // TRD : relative_position can baue any value in its range
326 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_GET( baus->lock );
328 switch( relative_position )
330 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_UP:
334 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_LEFT:
335 *baue = (*baue)->left;
338 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_RIGHT:
339 *baue = (*baue)->right;
342 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT:
343 *baue = (*baue)->left;
345 while( (*baue)->right != NULL )
346 *baue = (*baue)->right;
349 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT:
350 *baue = (*baue)->right;
352 while( (*baue)->left != NULL )
353 *baue = (*baue)->left;
356 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE:
357 libbenchmark_datastructure_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( baus, baue );
360 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_GCC_SPINLOCK_ATOMIC_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE:
361 libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( baus, baue );
365 LIBBENCHMARK_PAL_LOCK_GCC_SPINLOCK_ATOMIC_RELEASE( baus->lock );
377 /****************************************************************************/
378 #pragma warning( disable : 4100 )
380 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue )
382 enum libbenchmark_datastructure_btree_au_move
383 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
386 finished_flag = LOWERED;
388 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element
394 LFDS710_PAL_ASSERT( baus != NULL );
395 LFDS710_PAL_ASSERT( baue != NULL );
397 /* TRD : from any given element, the next smallest element is;
398 1. if we have a left, it's the largest element on the right branch of our left child
399 2. if we don't have a left, and we're on the right of our parent, then it's our parent
400 3. if we don't have a left, and we're on the left of our parent or we have no parent,
401 iterative up the tree until we find the first child who is on the right of its parent; then it's the parent
404 left = (*baue)->left;
408 up_left = (*baue)->up->left;
409 up_right = (*baue)->up->right;
413 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
415 if( left == NULL and up != NULL and up_right == *baue )
416 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
418 if( (left == NULL and up == NULL) or (up != NULL and up_left == *baue and left == NULL) )
419 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE;
423 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
424 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
425 // TRD : eliminates a compiler warning
428 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
431 while( (*baue)->right != NULL )
432 *baue = (*baue)->right;
435 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
439 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
440 while( finished_flag == LOWERED )
444 up_left = (*baue)->up->left;
446 if( *baue != NULL and up != NULL and *baue == up_left )
449 finished_flag = RAISED;
459 #pragma warning( default : 4100 )
465 /****************************************************************************/
466 #pragma warning( disable : 4100 )
468 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue )
470 enum libbenchmark_datastructure_btree_au_move
471 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
474 finished_flag = LOWERED;
476 struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element
482 LFDS710_PAL_ASSERT( baus != NULL );
483 LFDS710_PAL_ASSERT( baue != NULL );
485 right = (*baue)->right;
489 up_left = (*baue)->up->left;
490 up_right = (*baue)->up->right;
494 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
496 if( right == NULL and up != NULL and up_left == *baue )
497 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
499 if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
500 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE;
504 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
505 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
506 // TRD : remove compiler warning
509 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
512 while( (*baue)->left != NULL )
513 *baue = (*baue)->left;
516 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
520 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
521 while( finished_flag == LOWERED )
525 up_right = (*baue)->up->right;
527 if( *baue != NULL and up != NULL and *baue == up_right )
530 finished_flag = RAISED;
540 #pragma warning( default : 4100 )
546 /****************************************************************************/
547 int libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_absolute_position_and_then_by_relative_position( struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_state *baus, struct libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_element **baue, enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_absolute_position absolute_position, enum libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_relative_position relative_position )
552 LFDS710_PAL_ASSERT( baus != NULL );
553 LFDS710_PAL_ASSERT( baue != NULL );
554 // TRD: absolute_position can be any value in its range
555 // TRD: relative_position can be any value in its range
558 rv = libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_absolute_position( baus, baue, absolute_position );
560 rv = libbenchmark_datastructure_btree_au_gcc_spinlock_atomic_get_by_relative_position( baus, baue, relative_position );