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_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue );
6 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue );
12 /****************************************************************************/
13 void libbenchmark_datastructure_btree_au_windows_critical_section_init( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus,
14 int (*key_compare_function)(void const *new_key, void const *existing_key),
15 enum libbenchmark_datastructure_btree_au_windows_critical_section_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_WINDOWS_CRITICAL_SECTION_CREATE( baus->lock );
30 LFDS710_MISC_BARRIER_STORE;
32 lfds710_misc_force_store();
41 /****************************************************************************/
42 void libbenchmark_datastructure_btree_au_windows_critical_section_cleanup( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus,
43 void (*element_cleanup_callback)(struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_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_windows_critical_section_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_windows_critical_section_get_by_absolute_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_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_windows_critical_section_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_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_windows_critical_section_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_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_windows_critical_section_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_RELATIVE_POSITION_RIGHT );
117 element_cleanup_callback( baus, temp );
120 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT:
121 libbenchmark_datastructure_btree_au_windows_critical_section_get_by_relative_position( baus, &baue, LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_RELATIVE_POSITION_LEFT );
127 LIBBENCHMARK_PAL_LOCK_WINDOWS_CRITICAL_SECTION_DESTROY( baus->lock );
136 /****************************************************************************/
137 enum libbenchmark_datastructure_btree_au_windows_critical_section_insert_result libbenchmark_datastructure_btree_au_windows_critical_section_insert( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus,
138 struct libbenchmark_datastructure_btree_au_windows_critical_section_element *baue,
139 struct libbenchmark_datastructure_btree_au_windows_critical_section_element **existing_baue )
144 struct libbenchmark_datastructure_btree_au_windows_critical_section_element
149 LFDS710_PAL_ASSERT( baus != NULL );
150 LFDS710_PAL_ASSERT( baue != NULL );
151 // TRD : existing_baue can be NULL
153 LIBBENCHMARK_PAL_LOCK_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_EXISTING_KEY_OVERWRITE:
171 LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_SET_VALUE_IN_ELEMENT( *baus, *baue_temp, baue->value );
172 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_INSERT_RESULT_SUCCESS_OVERWRITE;
175 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_EXISTING_KEY_FAIL:
176 return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_INSERT_RESULT_SUCCESS;
224 /****************************************************************************/
225 int libbenchmark_datastructure_btree_au_windows_critical_section_get_by_key( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus,
226 int (*key_compare_function)(void const *new_key, void const *existing_key),
228 struct libbenchmark_datastructure_btree_au_windows_critical_section_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_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_RELEASE( baus->lock );
269 /****************************************************************************/
270 int libbenchmark_datastructure_btree_au_windows_critical_section_get_by_absolute_position( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue, enum libbenchmark_datastructure_btree_au_windows_critical_section_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_WINDOWS_CRITICAL_SECTION_GET( baus->lock );
283 switch( absolute_position )
285 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_ABSOLUTE_POSITION_ROOT:
288 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_ABSOLUTE_POSITION_LARGEST_IN_TREE:
290 while( (*baue)->right != NULL )
291 *baue = (*baue)->right;
294 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
296 while( (*baue)->left != NULL )
297 *baue = (*baue)->left;
301 LIBBENCHMARK_PAL_LOCK_WINDOWS_CRITICAL_SECTION_RELEASE( baus->lock );
313 /****************************************************************************/
314 int libbenchmark_datastructure_btree_au_windows_critical_section_get_by_relative_position( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue, enum libbenchmark_datastructure_btree_au_windows_critical_section_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_WINDOWS_CRITICAL_SECTION_GET( baus->lock );
328 switch( relative_position )
330 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_RELATIVE_POSITION_UP:
334 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_RELATIVE_POSITION_LEFT:
335 *baue = (*baue)->left;
338 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_RELATIVE_POSITION_RIGHT:
339 *baue = (*baue)->right;
342 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_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_WINDOWS_CRITICAL_SECTION_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_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_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_windows_critical_section_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 )
464 /****************************************************************************/
465 #pragma warning( disable : 4100 )
467 static void libbenchmark_datastructure_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue )
469 enum libbenchmark_datastructure_btree_au_move
470 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
473 finished_flag = LOWERED;
475 struct libbenchmark_datastructure_btree_au_windows_critical_section_element
481 LFDS710_PAL_ASSERT( baus != NULL );
482 LFDS710_PAL_ASSERT( baue != NULL );
484 right = (*baue)->right;
488 up_left = (*baue)->up->left;
489 up_right = (*baue)->up->right;
493 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
495 if( right == NULL and up != NULL and up_left == *baue )
496 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
498 if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
499 action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE;
503 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
504 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
505 // TRD : remove compiler warning
508 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
511 while( (*baue)->left != NULL )
512 *baue = (*baue)->left;
515 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
519 case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
520 while( finished_flag == LOWERED )
524 up_right = (*baue)->up->right;
526 if( *baue != NULL and up != NULL and *baue == up_right )
529 finished_flag = RAISED;
539 #pragma warning( default : 4100 )
545 /****************************************************************************/
546 int libbenchmark_datastructure_btree_au_windows_critical_section_get_by_absolute_position_and_then_by_relative_position( struct libbenchmark_datastructure_btree_au_windows_critical_section_state *baus, struct libbenchmark_datastructure_btree_au_windows_critical_section_element **baue, enum libbenchmark_datastructure_btree_au_windows_critical_section_absolute_position absolute_position, enum libbenchmark_datastructure_btree_au_windows_critical_section_relative_position relative_position )
551 LFDS710_PAL_ASSERT( baus != NULL );
552 LFDS710_PAL_ASSERT( baue != NULL );
553 // TRD: absolute_position can be any value in its range
554 // TRD: relative_position can be any value in its range
557 rv = libbenchmark_datastructure_btree_au_windows_critical_section_get_by_absolute_position( baus, baue, absolute_position );
559 rv = libbenchmark_datastructure_btree_au_windows_critical_section_get_by_relative_position( baus, baue, relative_position );