2 #include "lfds700_btree_addonly_unbalanced_internal.h"
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 )
21 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
23 struct lfds700_btree_au_element
24 *volatile compare = NULL,
25 *volatile baue_next = NULL,
26 *volatile baue_parent = NULL,
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 );
39 /* TRD : we follow a normal search for the insert node and which side to insert
41 the difference is that insertion may fail because someone else inserts
44 in this case, we resume searching for the insert node from the node
45 we were attempting to insert upon
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
52 baue->up = baue->left = baue->right = NULL;
54 LFDS700_MISC_BARRIER_LOAD;
56 baue_temp = baus->root;
58 LFDS700_MISC_BARRIER_LOAD;
62 // TRD : first we find where to insert
63 while( baue_temp != NULL )
65 compare_result = baus->key_compare_function( baue->key, baue_temp->key );
67 if( compare_result == 0 )
69 if( existing_baue != NULL )
70 *existing_baue = baue_temp;
72 switch( baus->existing_key )
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 );
79 case LFDS700_BTREE_AU_EXISTING_KEY_FAIL:
80 return( LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY );
85 if( compare_result < 0 )
86 baue_next = baue_temp->left;
88 if( compare_result > 0 )
89 baue_next = baue_temp->right;
91 baue_parent = baue_temp;
92 baue_temp = baue_next;
93 if( baue_temp != NULL )
94 LFDS700_MISC_BARRIER_LOAD;
97 /* TRD : second, we actually insert
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
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
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
111 or, similarly, other elements will have come in where we are,
112 and our insert will fail
115 if( baue_parent == 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 );
123 baue_temp = baus->root;
126 if( baue_parent != NULL )
128 if( compare_result <= 0 )
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 );
136 if( compare_result > 0 )
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 );
144 // TRD : if the insert fails, resume searching at the insert node
146 baue_temp = baue_parent;
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;
154 return( LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS );