2 #define LFDS700_BTREE_AU_GET_KEY_FROM_ELEMENT( btree_au_element ) ( (btree_au_element).key )
3 #define LFDS700_BTREE_AU_SET_KEY_IN_ELEMENT( btree_au_element, new_key ) ( (btree_au_element).key = (void *) (lfds700_pal_uint_t) (new_key) )
4 #define LFDS700_BTREE_AU_GET_VALUE_FROM_ELEMENT( btree_au_element ) ( LFDS700_MISC_BARRIER_LOAD, (btree_au_element).value )
5 #define LFDS700_BTREE_AU_SET_VALUE_IN_ELEMENT( btree_au_element, new_value ) { void *local_new_value = (void *) (lfds700_pal_uint_t) (new_value); LFDS700_PAL_ATOMIC_EXCHANGE( &(btree_au_element).value, &local_new_value ); }
6 #define LFDS700_BTREE_AU_GET_USER_STATE_FROM_STATE( btree_au_state ) ( (btree_au_state).user_state )
9 enum lfds700_btree_au_absolute_position
11 LFDS700_BTREE_AU_ABSOLUTE_POSITION_ROOT,
12 LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE,
13 LFDS700_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE
16 enum lfds700_btree_au_existing_key
18 LFDS700_BTREE_AU_EXISTING_KEY_OVERWRITE,
19 LFDS700_BTREE_AU_EXISTING_KEY_FAIL
22 enum lfds700_btree_au_insert_result
24 LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY,
25 LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE,
26 LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS
29 enum lfds700_btree_au_relative_position
31 LFDS700_BTREE_AU_RELATIVE_POSITION_UP,
32 LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT,
33 LFDS700_BTREE_AU_RELATIVE_POSITION_RIGHT,
34 LFDS700_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT,
35 LFDS700_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT,
36 LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE,
37 LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE
40 enum lfds700_btree_au_query
42 LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
43 LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE
47 struct lfds700_btree_au_element
49 struct lfds700_btree_au_element LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
54 void LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
57 void LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
61 struct lfds700_btree_au_state
63 struct lfds700_btree_au_element LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
66 int LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
67 (*key_compare_function)( void const *new_key, void const *existing_key );
69 enum lfds700_btree_au_existing_key
76 /***** public prototypes *****/
77 void lfds700_btree_au_init_valid_on_current_logical_core( struct lfds700_btree_au_state *baus,
78 int (*key_compare_function)(void const *new_key, void const *existing_key),
79 enum lfds700_btree_au_existing_key existing_key,
81 // TRD : used in conjunction with the #define LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE
83 void lfds700_btree_au_cleanup( struct lfds700_btree_au_state *baus,
84 void (*element_cleanup_callback)(struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element *baue) );
86 enum lfds700_btree_au_insert_result lfds700_btree_au_insert( struct lfds700_btree_au_state *baus,
87 struct lfds700_btree_au_element *baue,
88 struct lfds700_btree_au_element **existing_baue,
89 struct lfds700_misc_prng_state *ps );
90 // TRD : if a link collides with an existing key and existing_baue is non-NULL, existing_baue is set to the existing element
92 int lfds700_btree_au_get_by_key( struct lfds700_btree_au_state *baus,
94 struct lfds700_btree_au_element **baue );
96 int lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds700_btree_au_state *baus,
97 struct lfds700_btree_au_element **baue,
98 enum lfds700_btree_au_absolute_position absolute_position,
99 enum lfds700_btree_au_relative_position relative_position );
100 // TRD : if *baue is NULL, we get the element at position, otherwise we move from *baue according to direction
102 int lfds700_btree_au_get_by_absolute_position( struct lfds700_btree_au_state *baus,
103 struct lfds700_btree_au_element **baue,
104 enum lfds700_btree_au_absolute_position absolute_position );
106 int lfds700_btree_au_get_by_relative_position( struct lfds700_btree_au_element **baue,
107 enum lfds700_btree_au_relative_position relative_position );
109 void lfds700_btree_au_query( struct lfds700_btree_au_state *baus,
110 enum lfds700_btree_au_query query_type,
112 void *query_output );