2 #define LFDS710_BTREE_AU_GET_KEY_FROM_ELEMENT( btree_au_element ) ( (btree_au_element).key )
3 #define LFDS710_BTREE_AU_SET_KEY_IN_ELEMENT( btree_au_element, new_key ) ( (btree_au_element).key = (void *) (lfds710_pal_uint_t) (new_key) )
4 #define LFDS710_BTREE_AU_GET_VALUE_FROM_ELEMENT( btree_au_element ) ( LFDS710_MISC_BARRIER_LOAD, (btree_au_element).value )
5 #define LFDS710_BTREE_AU_SET_VALUE_IN_ELEMENT( btree_au_element, new_value ) { LFDS710_PAL_ATOMIC_SET( &(btree_au_element).value, new_value ); }
6 #define LFDS710_BTREE_AU_GET_USER_STATE_FROM_STATE( btree_au_state ) ( (btree_au_state).user_state )
9 enum lfds710_btree_au_absolute_position
11 LFDS710_BTREE_AU_ABSOLUTE_POSITION_ROOT,
12 LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE,
13 LFDS710_BTREE_AU_ABSOLUTE_POSITION_LARGEST_IN_TREE
16 enum lfds710_btree_au_existing_key
18 LFDS710_BTREE_AU_EXISTING_KEY_OVERWRITE,
19 LFDS710_BTREE_AU_EXISTING_KEY_FAIL
22 enum lfds710_btree_au_insert_result
24 LFDS710_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY,
25 LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE,
26 LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS
29 enum lfds710_btree_au_query
31 LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
32 LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE
35 enum lfds710_btree_au_relative_position
37 LFDS710_BTREE_AU_RELATIVE_POSITION_UP,
38 LFDS710_BTREE_AU_RELATIVE_POSITION_LEFT,
39 LFDS710_BTREE_AU_RELATIVE_POSITION_RIGHT,
40 LFDS710_BTREE_AU_RELATIVE_POSITION_SMALLEST_ELEMENT_BELOW_CURRENT_ELEMENT,
41 LFDS710_BTREE_AU_RELATIVE_POSITION_LARGEST_ELEMENT_BELOW_CURRENT_ELEMENT,
42 LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_SMALLER_ELEMENT_IN_ENTIRE_TREE,
43 LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE
47 struct lfds710_btree_au_element
49 /* TRD : we are add-only, so these elements are only written once
50 as such, the write is wholly negligible
51 we are only concerned with getting as many structs in one cache line as we can
54 struct lfds710_btree_au_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
59 void LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
66 struct lfds710_btree_au_state
68 struct lfds710_btree_au_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
72 (*key_compare_function)( void const *new_key, void const *existing_key );
74 enum lfds710_btree_au_existing_key
80 struct lfds710_misc_backoff_state
84 /***** public prototypes *****/
85 void lfds710_btree_au_init_valid_on_current_logical_core( struct lfds710_btree_au_state *baus,
86 int (*key_compare_function)(void const *new_key, void const *existing_key),
87 enum lfds710_btree_au_existing_key existing_key,
89 // TRD : used in conjunction with the #define LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE
91 void lfds710_btree_au_cleanup( struct lfds710_btree_au_state *baus,
92 void (*element_cleanup_callback)(struct lfds710_btree_au_state *baus, struct lfds710_btree_au_element *baue) );
94 enum lfds710_btree_au_insert_result lfds710_btree_au_insert( struct lfds710_btree_au_state *baus,
95 struct lfds710_btree_au_element *baue,
96 struct lfds710_btree_au_element **existing_baue );
97 // TRD : if a link collides with an existing key and existing_baue is non-NULL, existing_baue is set to the existing element
99 int lfds710_btree_au_get_by_key( struct lfds710_btree_au_state *baus,
100 int (*key_compare_function)(void const *new_key, void const *existing_key),
102 struct lfds710_btree_au_element **baue );
104 int lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position( struct lfds710_btree_au_state *baus,
105 struct lfds710_btree_au_element **baue,
106 enum lfds710_btree_au_absolute_position absolute_position,
107 enum lfds710_btree_au_relative_position relative_position );
108 // TRD : if *baue is NULL, we get the element at position, otherwise we move from *baue according to direction
110 int lfds710_btree_au_get_by_absolute_position( struct lfds710_btree_au_state *baus,
111 struct lfds710_btree_au_element **baue,
112 enum lfds710_btree_au_absolute_position absolute_position );
114 int lfds710_btree_au_get_by_relative_position( struct lfds710_btree_au_element **baue,
115 enum lfds710_btree_au_relative_position relative_position );
117 void lfds710_btree_au_query( struct lfds710_btree_au_state *baus,
118 enum lfds710_btree_au_query query_type,
120 void *query_output );