pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_btree_addonly_unbalanced/lfds700_btree_addonly_unbalanced_get.c

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