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

   1 /***** includes *****/
   2 #include "lfds700_btree_addonly_unbalanced_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 enum lfds700_btree_au_insert_result lfds700_btree_au_insert( struct lfds700_btree_au_state *baus,
  10                                                              struct lfds700_btree_au_element *baue,
  11                                                              struct lfds700_btree_au_element **existing_baue,
  12                                                              struct lfds700_misc_prng_state *ps )
  13 {
  14   char unsigned
  15     result = 0;
  16
  17   int
  18     compare_result = 0;
  19
  20   lfds700_pal_uint_t
  21     backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
  22
  23   struct lfds700_btree_au_element
  24     *volatile compare = NULL,
  25     *volatile baue_next = NULL,
  26     *volatile baue_parent = NULL,
  27     *volatile baue_temp;
  28
  29   LFDS700_PAL_ASSERT( baus != NULL );
  30   LFDS700_PAL_ASSERT( baue != NULL );
  31   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &baue->left % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  32   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &baue->right % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  33   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &baue->up % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  34   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &baue->value % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  35   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &baue->key % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  36   // TRD : existing_baue can be NULL
  37   LFDS700_PAL_ASSERT( ps != NULL );
  38
  39   /* TRD : we follow a normal search for the insert node and which side to insert
  40
  41            the difference is that insertion may fail because someone else inserts
  42            there before we do
  43
  44            in this case, we resume searching for the insert node from the node
  45            we were attempting to insert upon
  46
  47            (if we attempted to insert the root node and this failed, i.e. we thought
  48             the tree was empty but then it wasn't, then we start searching from the
  49             new root)
  50   */
  51
  52   baue->up = baue->left = baue->right = NULL;
  53
  54   LFDS700_MISC_BARRIER_LOAD;
  55
  56   baue_temp = baus->root;
  57
  58   LFDS700_MISC_BARRIER_LOAD;
  59
  60   while( result == 0 )
  61   {
  62     // TRD : first we find where to insert
  63     while( baue_temp != NULL )
  64     {
  65       compare_result = baus->key_compare_function( baue->key, baue_temp->key );
  66
  67       if( compare_result == 0 )
  68       {
  69         if( existing_baue != NULL )
  70           *existing_baue = baue_temp;
  71
  72         switch( baus->existing_key )
  73         {
  74           case LFDS700_BTREE_AU_EXISTING_KEY_OVERWRITE:
  75             LFDS700_BTREE_AU_SET_VALUE_IN_ELEMENT( *baue_temp, baue->value );
  76             return( LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE );
  77           break;
  78
  79           case LFDS700_BTREE_AU_EXISTING_KEY_FAIL:
  80             return( LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY );
  81           break;
  82         }
  83       }
  84
  85       if( compare_result < 0 )
  86         baue_next = baue_temp->left;
  87
  88       if( compare_result > 0 )
  89         baue_next = baue_temp->right;
  90
  91       baue_parent = baue_temp;
  92       baue_temp = baue_next;
  93       if( baue_temp != NULL )
  94         LFDS700_MISC_BARRIER_LOAD;
  95     }
  96
  97     /* TRD : second, we actually insert
  98
  99              at this point baue_temp has come to NULL
 100              and baue_parent is the element to insert at
 101              and result of the last compare indicates
 102              the direction of insertion
 103
 104              it may be that another tree has already inserted an element with
 105              the same key as ourselves, or other elements which mean our position
 106              is now wrong
 107
 108              in this case, it is either inserted in the position we're trying
 109              to insert in now, in which case our insert will fail
 110
 111              or, similarly, other elements will have come in where we are,
 112              and our insert will fail
 113     */
 114
 115     if( baue_parent == NULL )
 116     {
 117       compare = NULL;
 118       baue->up = baus->root;
 119       LFDS700_MISC_BARRIER_STORE;
 120       LFDS700_PAL_ATOMIC_CAS_WITH_BACKOFF( &baus->root, &compare, baue, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
 121
 122       if( result == 0 )
 123         baue_temp = baus->root;
 124     }
 125
 126     if( baue_parent != NULL )
 127     {
 128       if( compare_result <= 0 )
 129       {
 130         compare = NULL;
 131         baue->up = baue_parent;
 132         LFDS700_MISC_BARRIER_STORE;
 133         LFDS700_PAL_ATOMIC_CAS_WITH_BACKOFF( &baue_parent->left, &compare, baue, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
 134       }
 135
 136       if( compare_result > 0 )
 137       {
 138         compare = NULL;
 139         baue->up = baue_parent;
 140         LFDS700_MISC_BARRIER_STORE;
 141         LFDS700_PAL_ATOMIC_CAS_WITH_BACKOFF( &baue_parent->right, &compare, baue, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
 142       }
 143
 144       // TRD : if the insert fails, resume searching at the insert node
 145       if( result == 0 )
 146         baue_temp = baue_parent;
 147     }
 148   }
 149
 150   // TRD : if we get to here, we added (not failed or overwrite on exist) a new element
 151   if( existing_baue != NULL )
 152     *existing_baue = NULL;
 153
 154   return( LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS );
 155 }
 156