pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libbenchmark/src/libbenchmark_datastructures_btree_au/libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared.c

   1 /***** includes *****/
   2 #include "libbenchmark_datastructure_btree_au_internal.h"
   3
   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 );
   7
   8
   9
  10
  11
  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,
  16                                                                                void *user_state )
  17 {
  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
  22
  23   baus->root = NULL;
  24   baus->key_compare_function = key_compare_function;
  25   baus->existing_key = existing_key;
  26   baus->user_state = user_state;
  27
  28   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_CREATE( baus->lock );
  29
  30   LFDS710_MISC_BARRIER_STORE;
  31
  32   lfds710_misc_force_store();
  33
  34   return;
  35 }
  36
  37
  38
  39
  40
  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) )
  44 {
  45   enum libbenchmark_datastructure_btree_au_delete_action
  46     delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF; // TRD : to remove compiler warning
  47
  48   struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
  49     *baue,
  50     *temp;
  51
  52   LFDS710_PAL_ASSERT( baus != NULL );
  53   // TRD : element_delete_function can be NULL
  54
  55   if( element_cleanup_callback != NULL )
  56   {
  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 );
  58
  59     while( baue != NULL )
  60     {
  61       if( baue->left == NULL and baue->right == NULL )
  62         delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF;
  63
  64       if( baue->left != NULL and baue->right == NULL )
  65         delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD;
  66
  67       if( baue->left == NULL and baue->right != NULL )
  68         delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD;
  69
  70       if( baue->left != NULL and baue->right != NULL )
  71         delete_action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_MOVE_LEFT;
  72
  73       switch( delete_action )
  74       {
  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 )
  78           {
  79             if( baue->up->left == baue )
  80               baue->up->left = NULL;
  81             if( baue->up->right == baue )
  82               baue->up->right = NULL;
  83           }
  84
  85           temp = baue;
  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 );
  88         break;
  89
  90         case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD:
  91           baue->left->up = baue->up;
  92           if( baue->up != NULL )
  93           {
  94             if( baue->up->left == baue )
  95               baue->up->left = baue->left;
  96             if( baue->up->right == baue )
  97               baue->up->right = baue->left;
  98           }
  99
 100           temp = baue;
 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 );
 103         break;
 104
 105         case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD:
 106           baue->right->up = baue->up;
 107           if( baue->up != NULL )
 108           {
 109             if( baue->up->left == baue )
 110               baue->up->left = baue->right;
 111             if( baue->up->right == baue )
 112               baue->up->right = baue->right;
 113           }
 114
 115           temp = baue;
 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 );
 118         break;
 119
 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 );
 122         break;
 123       }
 124     }
 125   }
 126
 127   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_DESTROY( baus->lock );
 128
 129   return;
 130 }
 131
 132
 133
 134
 135
 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 )
 140 {
 141   int
 142     compare_result = 0;
 143
 144   struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
 145     *baue_next = NULL,
 146     *baue_parent = NULL,
 147     *baue_temp;
 148
 149   LFDS710_PAL_ASSERT( baus != NULL );
 150   LFDS710_PAL_ASSERT( baue != NULL );
 151   // TRD : existing_baue can be NULL
 152
 153   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 154
 155   baue->up = baue->left = baue->right = NULL;
 156
 157   baue_temp = baus->root;
 158
 159   while( baue_temp != NULL )
 160   {
 161     compare_result = baus->key_compare_function( baue->key, baue_temp->key );
 162
 163     if( compare_result == 0 )
 164     {
 165       if( existing_baue != NULL )
 166         *existing_baue = baue_temp;
 167
 168       switch( baus->existing_key )
 169       {
 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;
 173         break;
 174
 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;
 177         break;
 178       }
 179     }
 180
 181     if( compare_result < 0 )
 182       baue_next = baue_temp->left;
 183
 184     if( compare_result > 0 )
 185       baue_next = baue_temp->right;
 186
 187     baue_parent = baue_temp;
 188     baue_temp = baue_next;
 189   }
 190
 191   if( baue_parent == NULL )
 192   {
 193     baue->up = baus->root;
 194     baus->root = baue;  }
 195
 196   if( baue_parent != NULL )
 197   {
 198     if( compare_result <= 0 )
 199     {
 200       baue->up = baue_parent;
 201       baue_parent->left = baue;
 202     }
 203
 204     if( compare_result > 0 )
 205     {
 206       baue->up = baue_parent;
 207       baue_parent->right = baue;
 208     }
 209   }
 210
 211   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 212
 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;
 216
 217   return LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_INSERT_RESULT_SUCCESS;
 218 }
 219
 220
 221
 222
 223
 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),
 227                                                     void *key,
 228                                                     struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element **baue )
 229 {
 230   int
 231     compare_result = !0,
 232     rv = 1;
 233
 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 );
 238
 239   if( key_compare_function == NULL )
 240     key_compare_function = baus->key_compare_function;
 241
 242   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 243
 244   *baue = baus->root;
 245
 246   while( *baue != NULL and compare_result != 0 )
 247   {
 248     compare_result = key_compare_function( key, (*baue)->key );
 249
 250     if( compare_result < 0 )
 251       *baue = (*baue)->left;
 252
 253     if( compare_result > 0 )
 254       *baue = (*baue)->right;
 255   }
 256
 257   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 258
 259   if( *baue == NULL )
 260     rv = 0;
 261
 262   return rv;
 263 }
 264
 265
 266
 267
 268
 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 )
 271 {
 272   int
 273     rv = 1;
 274
 275   LFDS710_PAL_ASSERT( baus != NULL );
 276   LFDS710_PAL_ASSERT( baue != NULL );
 277   // TRD : absolute_position can be any value in its range
 278
 279   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 280
 281   *baue = baus->root;
 282
 283   switch( absolute_position )
 284   {
 285     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_ROOT:
 286     break;
 287
 288     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_LARGEST_IN_TREE:
 289       if( *baue != NULL )
 290         while( (*baue)->right != NULL )
 291           *baue = (*baue)->right;
 292     break;
 293
 294     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
 295       if( *baue != NULL )
 296         while( (*baue)->left != NULL )
 297           *baue = (*baue)->left;
 298     break;
 299   }
 300
 301   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 302
 303   if( *baue == NULL )
 304     rv = 0;
 305
 306   return rv;
 307 }
 308
 309
 310
 311
 312
 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 )
 315 {
 316   int
 317     rv = 1;
 318
 319   LFDS710_PAL_ASSERT( baus != NULL );
 320   LFDS710_PAL_ASSERT( baue != NULL );
 321   // TRD : relative_position can baue any value in its range
 322
 323   if( *baue == NULL )
 324     return 0;
 325
 326   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 327
 328   switch( relative_position )
 329   {
 330     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_UP:
 331       *baue = (*baue)->up;
 332     break;
 333
 334     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_LEFT:
 335       *baue = (*baue)->left;
 336     break;
 337
 338     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_RIGHT:
 339       *baue = (*baue)->right;
 340     break;
 341
 342     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT:
 343       *baue = (*baue)->left;
 344       if( *baue != NULL )
 345         while( (*baue)->right != NULL )
 346           *baue = (*baue)->right;
 347     break;
 348
 349     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_PTHREAD_SPINLOCK_PROCESS_SHARED_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT:
 350       *baue = (*baue)->right;
 351       if( *baue != NULL )
 352         while( (*baue)->left != NULL )
 353           *baue = (*baue)->left;
 354     break;
 355
 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 );
 358     break;
 359
 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 );
 362     break;
 363   }
 364
 365   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 366
 367   if( *baue == NULL )
 368     rv = 0;
 369
 370   return rv;
 371 }
 372
 373
 374
 375
 376
 377 /****************************************************************************/
 378 #pragma warning( disable : 4100 )
 379
 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 )
 381 {
 382   enum libbenchmark_datastructure_btree_au_move
 383     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
 384
 385   enum flag
 386     finished_flag = LOWERED;
 387
 388   struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
 389     *left = NULL,
 390     *up = NULL,
 391     *up_left = NULL,
 392     *up_right = NULL;
 393
 394   LFDS710_PAL_ASSERT( baus != NULL );
 395   LFDS710_PAL_ASSERT( baue != NULL );
 396
 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
 402   */
 403
 404   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 405
 406   left = (*baue)->left;
 407   up = (*baue)->up;
 408   if( up != NULL )
 409   {
 410     up_left = (*baue)->up->left;
 411     up_right = (*baue)->up->right;
 412   }
 413
 414   if( left != NULL )
 415     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
 416
 417   if( left == NULL and up != NULL and up_right == *baue )
 418     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
 419
 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;
 422
 423   switch( action )
 424   {
 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
 428     break;
 429
 430     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
 431       *baue = left;
 432       if( *baue != NULL )
 433         while( (*baue)->right != NULL )
 434           *baue = (*baue)->right;
 435     break;
 436
 437     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
 438       *baue = up;
 439     break;
 440
 441     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
 442       while( finished_flag == LOWERED )
 443       {
 444         up = (*baue)->up;
 445         if( up != NULL )
 446           up_left = (*baue)->up->left;
 447
 448         if( *baue != NULL and up != NULL and *baue == up_left )
 449           *baue = up;
 450         else
 451           finished_flag = RAISED;
 452       }
 453
 454       *baue = up;
 455     break;
 456   }
 457
 458   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 459
 460   return;
 461 }
 462
 463 #pragma warning( default : 4100 )
 464
 465
 466
 467
 468
 469 /****************************************************************************/
 470 #pragma warning( disable : 4100 )
 471
 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 )
 473 {
 474   enum libbenchmark_datastructure_btree_au_move
 475     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID;
 476
 477   enum flag
 478     finished_flag = LOWERED;
 479
 480   struct libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_element
 481     *right = NULL,
 482     *up = NULL,
 483     *up_left = NULL,
 484     *up_right = NULL;
 485
 486   LFDS710_PAL_ASSERT( baus != NULL );
 487   LFDS710_PAL_ASSERT( baue != NULL );
 488
 489   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_GET( baus->lock );
 490
 491   right = (*baue)->right;
 492   up = (*baue)->up;
 493   if( up != NULL )
 494   {
 495     up_left = (*baue)->up->left;
 496     up_right = (*baue)->up->right;
 497   }
 498
 499   if( right != NULL )
 500     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
 501
 502   if( right == NULL and up != NULL and up_left == *baue )
 503     action = LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT;
 504
 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;
 507
 508   switch( action )
 509   {
 510     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_INVALID:
 511     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
 512       // TRD : remove compiler warning
 513     break;
 514
 515     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
 516       *baue = right;
 517       if( *baue != NULL )
 518         while( (*baue)->left != NULL )
 519           *baue = (*baue)->left;
 520     break;
 521
 522     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_GET_PARENT:
 523       *baue = up;
 524     break;
 525
 526     case LIBBENCHMARK_DATASTRUCTURE_BTREE_AU_MOVE_MOVE_UP_TREE:
 527       while( finished_flag == LOWERED )
 528       {
 529         up = (*baue)->up;
 530         if( up != NULL )
 531           up_right = (*baue)->up->right;
 532
 533         if( *baue != NULL and up != NULL and *baue == up_right )
 534           *baue = up;
 535         else
 536           finished_flag = RAISED;
 537       }
 538
 539       *baue = up;
 540     break;
 541   }
 542
 543   LIBBENCHMARK_PAL_LOCK_PTHREAD_SPINLOCK_PROCESS_SHARED_RELEASE( baus->lock );
 544
 545   return;
 546 }
 547
 548 #pragma warning( default : 4100 )
 549
 550
 551
 552
 553
 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 )
 556 {
 557   int
 558     rv;
 559
 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
 564
 565   if( *baue == NULL )
 566     rv = libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_absolute_position( baus, baue, absolute_position );
 567   else
 568     rv = libbenchmark_datastructure_btree_au_pthread_spinlock_process_shared_get_by_relative_position( baus, baue, relative_position );
 569
 570   return rv;
 571 }
 572