2 #include "lfds710_btree_addonly_unbalanced_internal.h"
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 )
20 backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
22 struct lfds710_btree_au_element
24 *volatile baue_next = NULL,
25 *volatile baue_parent = NULL,
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
36 /* TRD : we follow a normal search for the insert node and which side to insert
38 the difference is that insertion may fail because someone else inserts
41 in this case, we resume searching for the insert node from the node
42 we were attempting to insert upon
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
49 baue->up = baue->left = baue->right = NULL;
51 LFDS710_MISC_BARRIER_LOAD;
53 baue_temp = baus->root;
55 LFDS710_MISC_BARRIER_LOAD;
59 // TRD : first we find where to insert
60 while( baue_temp != NULL )
62 compare_result = baus->key_compare_function( baue->key, baue_temp->key );
64 if( compare_result == 0 )
66 if( existing_baue != NULL )
67 *existing_baue = baue_temp;
69 switch( baus->existing_key )
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;
76 case LFDS710_BTREE_AU_EXISTING_KEY_FAIL:
77 return LFDS710_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY;
82 if( compare_result < 0 )
83 baue_next = baue_temp->left;
85 if( compare_result > 0 )
86 baue_next = baue_temp->right;
88 baue_parent = baue_temp;
89 baue_temp = baue_next;
90 if( baue_temp != NULL )
91 LFDS710_MISC_BARRIER_LOAD;
94 /* TRD : second, we actually insert
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
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
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
108 or, similarly, other elements will have come in where we are,
109 and our insert will fail
112 if( baue_parent == 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 );
120 baue_temp = baus->root;
123 if( baue_parent != NULL )
125 if( compare_result <= 0 )
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 );
133 if( compare_result > 0 )
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 );
141 // TRD : if the insert fails, then resume searching at the insert node
143 baue_temp = baue_parent;
147 LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( baus->insert_backoff, backoff_iteration );
150 LFDS710_BACKOFF_AUTOTUNE( baus->insert_backoff, backoff_iteration );
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;
156 return LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS;