pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/inc/liblfds700/lfds700_btree_addonly_unbalanced.h

   1 /***** defines *****/
   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 )
   7
   8 /***** enums *****/
   9 enum lfds700_btree_au_absolute_position
  10 {
  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
  14 };
  15
  16 enum lfds700_btree_au_existing_key
  17 {
  18   LFDS700_BTREE_AU_EXISTING_KEY_OVERWRITE,
  19   LFDS700_BTREE_AU_EXISTING_KEY_FAIL
  20 };
  21
  22 enum lfds700_btree_au_insert_result
  23 {
  24   LFDS700_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY,
  25   LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE,
  26   LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS
  27 };
  28
  29 enum lfds700_btree_au_relative_position
  30 {
  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
  38 };
  39
  40 enum lfds700_btree_au_query
  41 {
  42   LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  43   LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE
  44 };
  45
  46 /***** structs *****/
  47 struct lfds700_btree_au_element
  48 {
  49   struct lfds700_btree_au_element LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  50     *volatile left,
  51     *volatile right,
  52     *volatile up;
  53
  54   void LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  55     *volatile value;
  56
  57   void LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  58     *key;
  59 };
  60
  61 struct lfds700_btree_au_state
  62 {
  63   struct lfds700_btree_au_element LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  64     *volatile root;
  65
  66   int LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  67     (*key_compare_function)( void const *new_key, void const *existing_key );
  68
  69   enum lfds700_btree_au_existing_key
  70     existing_key;
  71
  72   void
  73     *user_state;
  74 };
  75
  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,
  80                                                           void *user_state );
  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
  82
  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) );
  85
  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
  91
  92 int lfds700_btree_au_get_by_key( struct lfds700_btree_au_state *baus,
  93                                  void *key,
  94                                  struct lfds700_btree_au_element **baue );
  95
  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
 101
 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 );
 105
 106 int lfds700_btree_au_get_by_relative_position( struct lfds700_btree_au_element **baue,
 107                                                enum lfds700_btree_au_relative_position relative_position );
 108
 109 void lfds700_btree_au_query( struct lfds700_btree_au_state *baus,
 110                              enum lfds700_btree_au_query query_type,
 111                              void *query_input,
 112                              void *query_output );
 113