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_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue );
6 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue );
12 /****************************************************************************/
13 void libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_init( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus,
14 int (*key_compare_function)(void const *new_key, void const *existing_key),
15 enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_PTHREAD_SPINLOCK_PROCESS_SHARED_CREATE( baus->lock );
30 LFDS710_MISC_BARRIER_STORE;
32 lfds710_misc_force_store();
41 /****************************************************************************/
42 void libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_cleanup( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus,
43 void (*element_cleanup_callback)(struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_pthread_spinlock_process_shared_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_pthread_spinlock_process_shared_get_by_absolute_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_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_pthread_spinlock_process_shared_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_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_pthread_spinlock_process_shared_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_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_pthread_spinlock_process_shared_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_RIGHT );
117 element_cleanup_callback( baus, temp );
120 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT:
121 libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_LEFT );
127 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_DESTROY( baus->lock );
136 /****************************************************************************/
137 enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_insert_result libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_insert( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus,
138 struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element *baue,
139 struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **existing_baue )
144 struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
149 LFDS710_PAL_ASSERT( baus != NULL );
150 LFDS710_PAL_ASSERT( baue != NULL );
151 // TRD : existing_baue can be NULL
153 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_EXISTING_KEY_OVERWRITE:
171 LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_SET_VALUE_IN_ELEMENT( *baus, *baue_temp, baue->value );
172 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_INSERT_RESULT_SUCCESS_OVERWRITE;
175 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_EXISTING_KEY_FAIL:
176 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_INSERT_RESULT_SUCCESS;
224 /****************************************************************************/
225 int libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_key( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus,
226 int (*key_compare_function)(void const *new_key, void const *existing_key),
228 struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
269 /****************************************************************************/
270 int libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_absolute_position( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue, enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
283 switch( absolute_position )
285 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_ROOT:
288 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_LARGEST_IN_TREE:
290 while( (*baue)->right != NULL )
291 *baue = (*baue)->right;
294 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
296 while( (*baue)->left != NULL )
297 *baue = (*baue)->left;
301 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
313 /****************************************************************************/
314 int libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_relative_position( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue, enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
328 switch( relative_position )
330 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_UP:
334 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_LEFT:
335 *baue = (*baue)->left;
338 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_RIGHT:
339 *baue = (*baue)->right;
342 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_PTHREAD_SPINLOCK_PROCESS_SHARED_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_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_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_pthread_spinlock_process_shared_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 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
406 left = (*baue)->left;
410 up_left = (*baue)->up->left;
411 up_right = (*baue)->up->right;
415 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
417 if( left == NULL and up != NULL and up_right == *baue )
418 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
420 if( (left == NULL and up == NULL) or (up != NULL and up_left == *baue and left == NULL) )
421 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE;
425 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
426 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
427 // TRD : eliminates a compiler warning
430 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
433 while( (*baue)->right != NULL )
434 *baue = (*baue)->right;
437 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
441 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
442 while( finished_flag == LOWERED )
446 up_left = (*baue)->up->left;
448 if( *baue != NULL and up != NULL and *baue == up_left )
451 finished_flag = RAISED;
458 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
463 #pragma warning( default : 4100 )
469 /****************************************************************************/
470 #pragma warning( disable : 4100 )
472 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue )
474 enum libbenchmark_datastructure_btree_au_move
475 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
478 finished_flag = LOWERED;
480 struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
486 LFDS710_PAL_ASSERT( baus != NULL );
487 LFDS710_PAL_ASSERT( baue != NULL );
489 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
491 right = (*baue)->right;
495 up_left = (*baue)->up->left;
496 up_right = (*baue)->up->right;
500 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
502 if( right == NULL and up != NULL and up_left == *baue )
503 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
505 if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
506 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE;
510 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
511 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
512 // TRD : remove compiler warning
515 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
518 while( (*baue)->left != NULL )
519 *baue = (*baue)->left;
522 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
526 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
527 while( finished_flag == LOWERED )
531 up_right = (*baue)->up->right;
533 if( *baue != NULL and up != NULL and *baue == up_right )
536 finished_flag = RAISED;
543 LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
548 #pragma warning( default : 4100 )
554 /****************************************************************************/
555 int libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_absolute_position_and_then_by_relative_position( struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_state *baus, struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue, enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_absolute_position absolute_position, enum libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_relative_position relative_position )
560 LFDS710_PAL_ASSERT( baus != NULL );
561 LFDS710_PAL_ASSERT( baue != NULL );
562 // TRD: absolute_position can be any value in its range
563 // TRD: relative_position can be any value in its range
566 rv = libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_absolute_position( baus, baue, absolute_position );
568 rv = libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_relative_position( baus, baue, relative_position );