pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/inc/liblfds710/lfds710_btree_addonly_unbalanced.h

   1 /***** defines *****/
   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 )
   7
   8 /***** enums *****/
   9 enum lfds710_btree_au_absolute_position
  10 {
  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
  14 };
  15
  16 enum lfds710_btree_au_existing_key
  17 {
  18   LFDS710_BTREE_AU_EXISTING_KEY_OVERWRITE,
  19   LFDS710_BTREE_AU_EXISTING_KEY_FAIL
  20 };
  21
  22 enum lfds710_btree_au_insert_result
  23 {
  24   LFDS710_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY,
  25   LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE,
  26   LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS
  27 };
  28
  29 enum lfds710_btree_au_query
  30 {
  31   LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  32   LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE
  33 };
  34
  35 enum lfds710_btree_au_relative_position
  36 {
  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
  44 };
  45
  46 /***** structs *****/
  47 struct lfds710_btree_au_element
  48 {
  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
  52   */
  53
  54   struct lfds710_btree_au_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
  55     *volatile left,
  56     *volatile right,
  57     *volatile up;
  58
  59   void LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
  60     *volatile value;
  61
  62   void
  63     *key;
  64 };
  65
  66 struct lfds710_btree_au_state
  67 {
  68   struct lfds710_btree_au_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
  69     *volatile root;
  70
  71   int
  72     (*key_compare_function)( void const *new_key, void const *existing_key );
  73
  74   enum lfds710_btree_au_existing_key
  75     existing_key;
  76
  77   void
  78     *user_state;
  79
  80   struct lfds710_misc_backoff_state
  81     insert_backoff;
  82 };
  83
  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,
  88                                                           void *user_state );
  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
  90
  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) );
  93
  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
  98
  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),
 101                                  void *key,
 102                                  struct lfds710_btree_au_element **baue );
 103
 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
 109
 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 );
 113
 114 int lfds710_btree_au_get_by_relative_position( struct lfds710_btree_au_element **baue,
 115                                                enum lfds710_btree_au_relative_position relative_position );
 116
 117 void lfds710_btree_au_query( struct lfds710_btree_au_state *baus,
 118                              enum lfds710_btree_au_query query_type,
 119                              void *query_input,
 120                              void *query_output );
 121