pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_btree_addonly_unbalanced/lfds710_btree_addonly_unbalanced_get.c

   1 /***** includes *****/
   2 #include "lfds710_btree_addonly_unbalanced_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds710_btree_au_element **baue );
   6 static void lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds710_btree_au_element **baue );
   7
   8
   9
  10
  11
  12 /****************************************************************************/
  13 int lfds710_btree_au_get_by_key( struct lfds710_btree_au_state *baus,
  14                                  int (*key_compare_function)(void const *new_key, void const *existing_key),
  15                                  void *key,
  16                                  struct lfds710_btree_au_element **baue )
  17 {
  18   int
  19     compare_result = !0,
  20     rv = 1;
  21
  22   LFDS710_PAL_ASSERT( baus != NULL );
  23   // TRD : key_compare_function can be NULL
  24   // TRD : key can be NULL
  25   LFDS710_PAL_ASSERT( baue != NULL );
  26
  27   if( key_compare_function == NULL )
  28     key_compare_function = baus->key_compare_function;
  29
  30   LFDS710_MISC_BARRIER_LOAD;
  31
  32   *baue = baus->root;
  33
  34   LFDS710_MISC_BARRIER_LOAD;
  35
  36   while( *baue != NULL and compare_result != 0 )
  37   {
  38     compare_result = key_compare_function( key, (*baue)->key );
  39
  40     if( compare_result < 0 )
  41     {
  42       *baue = (*baue)->left;
  43       LFDS710_MISC_BARRIER_LOAD;
  44     }
  45
  46     if( compare_result > 0 )
  47     {
  48       *baue = (*baue)->right;
  49       LFDS710_MISC_BARRIER_LOAD;
  50     }
  51   }
  52
  53   if( *baue == NULL )
  54     rv = 0;
  55
  56   return rv;
  57 }
  58
  59
  60
  61
  62
  63 /****************************************************************************/
  64 int lfds710_btree_au_get_by_absolute_position( struct lfds710_btree_au_state *baus,
  65                                                struct lfds710_btree_au_element **baue,
  66                                                enum lfds710_btree_au_absolute_position absolute_position )
  67 {
  68   int
  69     rv = 1;
  70
  71   LFDS710_PAL_ASSERT( baus != NULL );
  72   LFDS710_PAL_ASSERT( baue != NULL );
  73   // TRD : absolute_position can be any value in its range
  74
  75   LFDS710_MISC_BARRIER_LOAD;
  76
  77   *baue = baus->root;
  78
  79   LFDS710_MISC_BARRIER_LOAD;
  80
  81   switch( absolute_position )
  82   {
  83     case LFDS710_BTREE_AU_ABSOLUTE_POSITION_ROOT:
  84     break;
  85
  86     case LFDS710_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE:
  87       if( *baue != NULL )
  88         while( (*baue)->right != NULL )
  89         {
  90           *baue = (*baue)->right;
  91           LFDS710_MISC_BARRIER_LOAD;
  92         }
  93     break;
  94
  95     case LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE:
  96       if( *baue != NULL )
  97         while( (*baue)->left != NULL )
  98         {
  99           *baue = (*baue)->left;
 100           LFDS710_MISC_BARRIER_LOAD;
 101         }
 102     break;
 103   }
 104
 105   if( *baue == NULL )
 106     rv = 0;
 107
 108   return rv;
 109 }
 110
 111
 112
 113
 114
 115 /****************************************************************************/
 116 int lfds710_btree_au_get_by_relative_position( struct lfds710_btree_au_element **baue,
 117                                                enum lfds710_btree_au_relative_position relative_position )
 118 {
 119   int
 120     rv = 1;
 121
 122   LFDS710_PAL_ASSERT( baue != NULL );
 123   // TRD : relative_position can baue any value in its range
 124
 125   if( *baue == NULL )
 126     return 0;
 127
 128   LFDS710_MISC_BARRIER_LOAD;
 129
 130   switch( relative_position )
 131   {
 132     case LFDS710_BTREE_AU_RELATIVE_POSITION_UP:
 133       *baue = (*baue)->up;
 134       // TRD : no load barrier - up already existed, so is known to be safely propagated
 135     break;
 136
 137     case LFDS710_BTREE_AU_RELATIVE_POSITION_LEFT:
 138       *baue = (*baue)->left;
 139       LFDS710_MISC_BARRIER_LOAD;
 140     break;
 141
 142     case LFDS710_BTREE_AU_RELATIVE_POSITION_RIGHT:
 143       *baue = (*baue)->right;
 144       LFDS710_MISC_BARRIER_LOAD;
 145     break;
 146
 147     case LFDS710_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT:
 148       *baue = (*baue)->left;
 149       if( *baue != NULL )
 150       {
 151         LFDS710_MISC_BARRIER_LOAD;
 152         while( (*baue)->right != NULL )
 153         {
 154           *baue = (*baue)->right;
 155           LFDS710_MISC_BARRIER_LOAD;
 156         }
 157       }
 158     break;
 159
 160     case LFDS710_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT:
 161       *baue = (*baue)->right;
 162       if( *baue != NULL )
 163       {
 164         LFDS710_MISC_BARRIER_LOAD;
 165         while( (*baue)->left != NULL )
 166         {
 167           *baue = (*baue)->left;
 168           LFDS710_MISC_BARRIER_LOAD;
 169         }
 170       }
 171     break;
 172
 173     case LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE:
 174       lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( baue );
 175     break;
 176
 177     case LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE:
 178       lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( baue );
 179     break;
 180   }
 181
 182   if( *baue == NULL )
 183     rv = 0;
 184
 185   return rv;
 186 }
 187
 188
 189
 190
 191
 192 /****************************************************************************/
 193 static void lfds710_btree_au_internal_inorder_walk_from_largest_get_next_smallest_element( struct lfds710_btree_au_element **baue )
 194 {
 195   enum lfds710_btree_au_move
 196     action = LFDS710_BTREE_AU_MOVE_INVALID;
 197
 198   enum lfds710_misc_flag
 199     finished_flag = LFDS710_MISC_FLAG_LOWERED,
 200     load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
 201
 202   struct lfds710_btree_au_element
 203     *left = NULL,
 204     *right = NULL,
 205     *up = NULL,
 206     *up_left = NULL,
 207     *up_right = NULL;
 208
 209   LFDS710_PAL_ASSERT( baue != NULL );
 210
 211   /* TRD : from any given element, the next smallest element is;
 212            1. if we have a left, it's the largest element on the right branch of our left child
 213            2. if we don't have a left, and we're on the right of our parent, then it's our parent
 214            3. if we don't have a left, and we're on the left of our parent or we have no parent,
 215               iterative up the tree until we find the first child who is on the right of its parent; then it's the parent
 216   */
 217
 218   /* TRD : we need to ensure the variables we use to decide our action are self-consistent
 219            to do this, we make local copies of them all
 220            then, if they are all not NULL, we can know they cannot change and we can continue
 221            if however any of them are NULL, they could have changed while we were reading
 222            and so our variables could be non-self-consistent
 223            to check for this, we issue another processor read barrier
 224            and then compare our local variables with the values in the tree
 225            if they all match, then we know our variable set is self-consistent
 226            (even though it may now be wrong - but we will discover this when we try the atomic operation)
 227   */
 228
 229   LFDS710_MISC_BARRIER_LOAD;
 230
 231   while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
 232   {
 233     left = (*baue)->left;
 234     right = (*baue)->right;
 235     up = (*baue)->up;
 236     if( up != NULL )
 237     {
 238       up_left = (*baue)->up->left;
 239       up_right = (*baue)->up->right;
 240     }
 241
 242     // TRD : optimization - if all already not NULL, given we're add-only, they won't change
 243     if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
 244       break;
 245
 246     LFDS710_MISC_BARRIER_LOAD;
 247
 248     if( left == (*baue)->left and right == (*baue)->right and (up == NULL or (up != NULL and up == (*baue)->up and up_left == (*baue)->up->left and up_right == (*baue)->up->right)) )
 249       load_finished_flag = LFDS710_MISC_FLAG_RAISED;
 250   }
 251
 252   if( left != NULL )
 253     action = LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD;
 254
 255   if( left == NULL and up != NULL and up_right == *baue )
 256     action = LFDS710_BTREE_AU_MOVE_GET_PARENT;
 257
 258   if( (left == NULL and up == NULL) or (up != NULL and up_left == *baue and left == NULL) )
 259     action = LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE;
 260
 261   switch( action )
 262   {
 263     case LFDS710_BTREE_AU_MOVE_INVALID:
 264     case LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
 265       // TRD : eliminates a compiler warning
 266     break;
 267
 268     case LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
 269       *baue = left;
 270       if( *baue != NULL )
 271       {
 272         LFDS710_MISC_BARRIER_LOAD;
 273         while( (*baue)->right != NULL )
 274         {
 275           *baue = (*baue)->right;
 276           LFDS710_MISC_BARRIER_LOAD;
 277         }
 278       }
 279     break;
 280
 281     case LFDS710_BTREE_AU_MOVE_GET_PARENT:
 282       *baue = up;
 283     break;
 284
 285     case LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE:
 286       while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
 287       {
 288         load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
 289
 290         while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
 291         {
 292           up = (*baue)->up;
 293           if( up != NULL )
 294             up_left = (*baue)->up->left;
 295
 296           // TRD : optimization - if all already not NULL, given we're add-only, they won't change
 297           if( up == NULL or (up != NULL and up_left != NULL) )
 298             break;
 299
 300           LFDS710_MISC_BARRIER_LOAD;
 301
 302           if( up == (*baue)->up and up_left == (*baue)->up->left )
 303             load_finished_flag = LFDS710_MISC_FLAG_RAISED;
 304         }
 305
 306         if( *baue != NULL and up != NULL and *baue == up_left )
 307           *baue = up;
 308         else
 309           finished_flag = LFDS710_MISC_FLAG_RAISED;
 310       }
 311
 312       *baue = up;
 313
 314       /*
 315
 316       while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->left )
 317         *baue = (*baue)->up;
 318
 319       *baue = (*baue)->up;
 320
 321       */
 322     break;
 323   }
 324
 325   return;
 326 }
 327
 328
 329
 330
 331
 332 /****************************************************************************/
 333 static void lfds710_btree_au_internal_inorder_walk_from_smallest_get_next_largest_element( struct lfds710_btree_au_element **baue )
 334 {
 335   enum lfds710_btree_au_move
 336     action = LFDS710_BTREE_AU_MOVE_INVALID;
 337
 338   enum lfds710_misc_flag
 339     finished_flag = LFDS710_MISC_FLAG_LOWERED,
 340     load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
 341
 342   struct lfds710_btree_au_element
 343     *left = NULL,
 344     *right = NULL,
 345     *up = NULL,
 346     *up_left = NULL,
 347     *up_right = NULL;
 348
 349   LFDS710_PAL_ASSERT( baue != NULL );
 350
 351   /* TRD : from any given element, the next largest element is;
 352            1. if we have a right, it's the smallest element on the left branch of our right child
 353            2. if we don't have a right, and we're on the left of our parent, then it's our parent
 354            3. if we don't have a right, and we're on the right of our parent or we have no parent,
 355               iterate up the tree until we find the first child who is on the left of its parent; then it's the parent
 356   */
 357
 358   LFDS710_MISC_BARRIER_LOAD;
 359
 360   while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
 361   {
 362     left = (*baue)->left;
 363     right = (*baue)->right;
 364     up = (*baue)->up;
 365     if( up != NULL )
 366     {
 367       up_left = (*baue)->up->left;
 368       up_right = (*baue)->up->right;
 369     }
 370
 371     // TRD : optimization - if all already not NULL, given we're add-only, they won't change
 372     if( left != NULL and right != NULL and (up == NULL or (up != NULL and up_left != NULL and up_right != NULL)) )
 373       break;
 374
 375     LFDS710_MISC_BARRIER_LOAD;
 376
 377     if( left == (*baue)->left and right == (*baue)->right and (up == NULL or (up != NULL and up == (*baue)->up and up_left == (*baue)->up->left and up_right == (*baue)->up->right)) )
 378       load_finished_flag = LFDS710_MISC_FLAG_RAISED;
 379   }
 380
 381   if( right != NULL )
 382     action = LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD;
 383
 384   if( right == NULL and up != NULL and up_left == *baue )
 385     action = LFDS710_BTREE_AU_MOVE_GET_PARENT;
 386
 387   if( (right == NULL and up == NULL) or (up != NULL and up_right == *baue and right == NULL) )
 388     action = LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE;
 389
 390   switch( action )
 391   {
 392     case LFDS710_BTREE_AU_MOVE_INVALID:
 393     case LFDS710_BTREE_AU_MOVE_LARGEST_FROM_LEFT_CHILD:
 394       // TRD : remove compiler warning
 395     break;
 396
 397     case LFDS710_BTREE_AU_MOVE_SMALLEST_FROM_RIGHT_CHILD:
 398       *baue = right;
 399       if( *baue != NULL )
 400       {
 401         LFDS710_MISC_BARRIER_LOAD;
 402         while( (*baue)->left != NULL )
 403         {
 404           *baue = (*baue)->left;
 405           LFDS710_MISC_BARRIER_LOAD;
 406         }
 407       }
 408     break;
 409
 410     case LFDS710_BTREE_AU_MOVE_GET_PARENT:
 411       *baue = up;
 412     break;
 413
 414     case LFDS710_BTREE_AU_MOVE_MOVE_UP_TREE:
 415       while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
 416       {
 417         load_finished_flag = LFDS710_MISC_FLAG_LOWERED;
 418
 419         while( load_finished_flag == LFDS710_MISC_FLAG_LOWERED )
 420         {
 421           up = (*baue)->up;
 422           if( up != NULL )
 423             up_right = (*baue)->up->right;
 424
 425           // TRD : optimization - if all already not NULL, given we're add-only, they won't change
 426           if( up == NULL or (up != NULL and up_right != NULL) )
 427             break;
 428
 429           LFDS710_MISC_BARRIER_LOAD;
 430
 431           if( up == (*baue)->up and up_right == (*baue)->up->right )
 432             load_finished_flag = LFDS710_MISC_FLAG_RAISED;
 433         }
 434
 435         if( *baue != NULL and up != NULL and *baue == up_right )
 436           *baue = up;
 437         else
 438           finished_flag = LFDS710_MISC_FLAG_RAISED;
 439       }
 440
 441       *baue = up;
 442
 443       /*
 444
 445       while( *baue != NULL and (*baue)->up != NULL and *baue == (*baue)->up->right )
 446         *baue = (*baue)->up;
 447
 448       *baue = (*baue)->up;
 449
 450       */
 451     break;
 452   }
 453
 454   return;
 455 }
 456
 457
 458
 459
 460
 461 /****************************************************************************/
 462 int lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds710_btree_au_state *baus,
 463                                                                              struct lfds710_btree_au_element **baue,
 464                                                                              enum lfds710_btree_au_absolute_position absolute_position,
 465                                                                              enum lfds710_btree_au_relative_position relative_position )
 466 {
 467   int
 468     rv;
 469
 470   LFDS710_PAL_ASSERT( baus != NULL );
 471   LFDS710_PAL_ASSERT( baue != NULL );
 472   // TRD: absolute_position can be any value in its range
 473   // TRD: relative_position can be any value in its range
 474
 475   if( *baue == NULL )
 476     rv = lfds710_btree_au_get_by_absolute_position( baus, baue, absolute_position );
 477   else
 478     rv = lfds710_btree_au_get_by_relative_position( baue, relative_position );
 479
 480   return rv;
 481 }
 482