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

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