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

   1 /***** defines *****/
   2 #define LFDS700_HASH_A_GET_KEY_FROM_ELEMENT( hash_a_element )             ( (hash_a_element).key )
   3 #define LFDS700_HASH_A_SET_KEY_IN_ELEMENT( hash_a_element, new_key )      ( (hash_a_element).key = (void *) (lfds700_pal_uint_t) (new_key) )
   4 #define LFDS700_HASH_A_GET_VALUE_FROM_ELEMENT( hash_a_element )           ( LFDS700_MISC_BARRIER_LOAD, (hash_a_element).value )
   5 #define LFDS700_HASH_A_SET_VALUE_IN_ELEMENT( hash_a_element, new_value )  { void *local_new_value = (void *) (lfds700_pal_uint_t) (new_value); LFDS700_PAL_ATOMIC_EXCHANGE( &(hash_a_element).value, &local_new_value ); }
   6 #define LFDS700_HASH_A_GET_USER_STATE_FROM_STATE( hash_a_state )          ( (hash_a_state).user_state )
   7
   8 #define LFDS700_HASH_A_32BIT_HASH_FUNCTION( data, data_length_in_bytes, hash )  {                                                           \
   9                                                                                   lfds700_pal_uint_t                                        \
  10                                                                                     loop;                                                   \
  11                                                                                                                                             \
  12                                                                                   for( loop = 0 ; loop < (data_length_in_bytes) ; loop++ )  \
  13                                                                                   {                                                         \
  14                                                                                     (hash) += *( (char unsigned *) (data) + loop );         \
  15                                                                                     (hash) += ((hash) << 10);                               \
  16                                                                                     (hash) ^= ((hash) >> 6);                                \
  17                                                                                   }                                                         \
  18                                                                                                                                             \
  19                                                                                   (hash) += ((hash) << 3);                                  \
  20                                                                                   (hash) ^= ((hash) >> 11);                                 \
  21                                                                                   (hash) += ((hash) << 15);                                 \
  22                                                                                 }
  23   /* TRD : this is the Jenkins one-at-a-time hash
  24            it produces a 32 bit hash
  25            http://en.wikipedia.org/wiki/Jenkins_hash_function
  26
  27            we ourselves do *not* initialize the value of *hash, so that
  28            our caller has the option to call us multiple times, each
  29            time with for example a different member of a struct, which is
  30            then hashed into the existing, built-up-so-far hash value, and
  31            so build up a quality hash
  32   */
  33
  34 /***** enums *****/
  35 enum lfds700_hash_a_existing_key
  36 {
  37   LFDS700_HASH_A_EXISTING_KEY_OVERWRITE,
  38   LFDS700_HASH_A_EXISTING_KEY_FAIL
  39 };
  40
  41 enum lfds700_hash_a_insert_result
  42 {
  43   LFDS700_HASH_A_PUT_RESULT_FAILURE_EXISTING_KEY,
  44   LFDS700_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE,
  45   LFDS700_HASH_A_PUT_RESULT_SUCCESS
  46 };
  47
  48 enum lfds700_hash_a_query
  49 {
  50   LFDS700_HASH_A_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  51   LFDS700_HASH_A_QUERY_SINGLETHREADED_VALIDATE
  52 };
  53
  54 /***** structs *****/
  55 struct lfds700_hash_a_element
  56 {
  57   struct lfds700_btree_au_element
  58     baue;
  59
  60   void
  61     *key;
  62
  63   void LFDS700_PAL_ALIGN(LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES)
  64     *volatile value;
  65 };
  66
  67 struct lfds700_hash_a_iterate
  68 {
  69   struct lfds700_btree_au_element
  70     *baue;
  71
  72   struct lfds700_btree_au_state
  73     *baus,
  74     *baus_end;
  75 };
  76
  77 struct lfds700_hash_a_state
  78 {
  79   enum lfds700_hash_a_existing_key
  80     existing_key;
  81
  82   int
  83     (*key_compare_function)( void const *new_key, void const *existing_key );
  84
  85   lfds700_pal_uint_t
  86     array_size;
  87
  88   struct lfds700_btree_au_state
  89     *baus_array;
  90
  91   void
  92     (*element_cleanup_callback)( struct lfds700_hash_a_state *has, struct lfds700_hash_a_element *hae ),
  93     (*key_hash_function)( void const *key, lfds700_pal_uint_t *hash ),
  94     *user_state;
  95 };
  96
  97 /***** public prototypes *****/
  98 void lfds700_hash_a_init_valid_on_current_logical_core( struct lfds700_hash_a_state *has,
  99                                                         struct lfds700_btree_au_state *baus_array,
 100                                                         lfds700_pal_uint_t array_size,
 101                                                         int (*key_compare_function)(void const *new_key, void const *existing_key),
 102                                                         void (*key_hash_function)(void const *key, lfds700_pal_uint_t *hash),
 103                                                         enum lfds700_hash_a_existing_key existing_key,
 104                                                         void *user_state );
 105   // TRD : used in conjunction with the #define LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE
 106
 107 void lfds700_hash_a_cleanup( struct lfds700_hash_a_state *has,
 108                              void (*element_cleanup_function)(struct lfds700_hash_a_state *has, struct lfds700_hash_a_element *hae) );
 109
 110 enum lfds700_hash_a_insert_result lfds700_hash_a_insert( struct lfds700_hash_a_state *has,
 111                                                          struct lfds700_hash_a_element *hae,
 112                                                          struct lfds700_hash_a_element **existing_hae,
 113                                                          struct lfds700_misc_prng_state *ps );
 114   // TRD : if existing_value is not NULL and the key exists, existing_value is set to the value of the existing key
 115
 116 int lfds700_hash_a_get_by_key( struct lfds700_hash_a_state *has,
 117                                void *key,
 118                                struct lfds700_hash_a_element **hae );
 119
 120 void lfds700_hash_a_iterate_init( struct lfds700_hash_a_state *has, struct lfds700_hash_a_iterate *hai );
 121 int lfds700_hash_a_iterate( struct lfds700_hash_a_iterate *hai, struct lfds700_hash_a_element **hae );
 122
 123 void lfds700_hash_a_query( struct lfds700_hash_a_state *has,
 124                            enum lfds700_hash_a_query query_type,
 125                            void *query_input,
 126                            void *query_output );
 127