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_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **baue );
6 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **baue );
12 /****************************************************************************/
13 void libbenchmark_datastructure_btree_au_msvc_spinlock_init( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus,
14 int (*key_compare_function)(void const *new_key, void const *existing_key),
15 enum libbenchmark_datastructure_btree_au_msvc_spinlock_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_MSVC_SPINLOCK_CREATE( baus->lock );
30 LFDS710_MISC_BARRIER_STORE;
32 lfds710_misc_force_store();
41 /****************************************************************************/
42 void libbenchmark_datastructure_btree_au_msvc_spinlock_cleanup( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus,
43 void (*element_cleanup_callback)(struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_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_msvc_spinlock_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_msvc_spinlock_get_by_absolute_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_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_msvc_spinlock_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_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_msvc_spinlock_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_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_msvc_spinlock_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_RELATIVE_POSITION_RIGHT );
117 element_cleanup_callback( baus, temp );
120 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT:
121 libbenchmark_datastructure_btree_au_msvc_spinlock_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_RELATIVE_POSITION_LEFT );
127 LIBBENCHMARK_PAL_LOCK_MSVC_SPINLOCK_DESTROY( baus->lock );
136 /****************************************************************************/
137 enum libbenchmark_datastructure_btree_au_msvc_spinlock_insert_result libbenchmark_datastructure_btree_au_msvc_spinlock_insert( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus,
138 struct libbenchmark_datastructure_btree_au_msvc_spinlock_element *baue,
139 struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **existing_baue )
144 struct libbenchmark_datastructure_btree_au_msvc_spinlock_element
149 LFDS710_PAL_ASSERT( baus != NULL );
150 LFDS710_PAL_ASSERT( baue != NULL );
151 // TRD : existing_baue can be NULL
153 LIBBENCHMARK_PAL_LOCK_MSVC_SPINLOCK_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_MSVC_SPINLOCK_EXISTING_KEY_OVERWRITE:
171 LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_SET_VALUE_IN_ELEMENT( *baus, *baue_temp, baue->value );
172 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_INSERT_RESULT_SUCCESS_OVERWRITE;
175 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_EXISTING_KEY_FAIL:
176 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_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_MSVC_SPINLOCK_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_MSVC_SPINLOCK_INSERT_RESULT_SUCCESS;
224 /****************************************************************************/
225 int libbenchmark_datastructure_btree_au_msvc_spinlock_get_by_key( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus,
226 int (*key_compare_function)(void const *new_key, void const *existing_key),
228 struct libbenchmark_datastructure_btree_au_msvc_spinlock_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_MSVC_SPINLOCK_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_MSVC_SPINLOCK_RELEASE( baus->lock );
269 /****************************************************************************/
270 int libbenchmark_datastructure_btree_au_msvc_spinlock_get_by_absolute_position( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **baue, enum libbenchmark_datastructure_btree_au_msvc_spinlock_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_MSVC_SPINLOCK_GET( baus->lock );
283 switch( absolute_position )
285 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_ABSOLUTE_POSITION_ROOT:
288 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_ABSOLUTE_POSITION_LARGEST_IN_TREE:
290 while( (*baue)->right != NULL )
291 *baue = (*baue)->right;
294 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
296 while( (*baue)->left != NULL )
297 *baue = (*baue)->left;
301 LIBBENCHMARK_PAL_LOCK_MSVC_SPINLOCK_RELEASE( baus->lock );
313 /****************************************************************************/
314 int libbenchmark_datastructure_btree_au_msvc_spinlock_get_by_relative_position( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **baue, enum libbenchmark_datastructure_btree_au_msvc_spinlock_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_MSVC_SPINLOCK_GET( baus->lock );
328 switch( relative_position )
330 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_RELATIVE_POSITION_UP:
334 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_RELATIVE_POSITION_LEFT:
335 *baue = (*baue)->left;
338 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_RELATIVE_POSITION_RIGHT:
339 *baue = (*baue)->right;
342 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MSVC_SPINLOCK_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_MSVC_SPINLOCK_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_MSVC_SPINLOCK_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_MSVC_SPINLOCK_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_MSVC_SPINLOCK_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_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_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_msvc_spinlock_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_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_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_msvc_spinlock_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_msvc_spinlock_get_by_absolute_position_and_then_by_relative_position( struct libbenchmark_datastructure_btree_au_msvc_spinlock_state *baus, struct libbenchmark_datastructure_btree_au_msvc_spinlock_element **baue, enum libbenchmark_datastructure_btree_au_msvc_spinlock_absolute_position absolute_position, enum libbenchmark_datastructure_btree_au_msvc_spinlock_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_msvc_spinlock_get_by_absolute_position( baus, baue, absolute_position );
560 rv = libbenchmark_datastructure_btree_au_msvc_spinlock_get_by_relative_position( baus, baue, relative_position );