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

   1 /***** defines *****/
   2 #define LFDS710_HASH_A_GET_KEY_FROM_ELEMENT( hash_a_element )             ( (hash_a_element).key )
   3 #define LFDS710_HASH_A_SET_KEY_IN_ELEMENT( hash_a_element, new_key )      ( (hash_a_element).key = (void *) (lfds710_pal_uint_t) (new_key) )
   4 #define LFDS710_HASH_A_GET_VALUE_FROM_ELEMENT( hash_a_element )           ( LFDS710_MISC_BARRIER_LOAD, (hash_a_element).value )
   5 #define LFDS710_HASH_A_SET_VALUE_IN_ELEMENT( hash_a_element, new_value )  { LFDS710_PAL_ATOMIC_SET( &(hash_a_element).value, new_value ); }
   6 #define LFDS710_HASH_A_GET_USER_STATE_FROM_STATE( hash_a_state )          ( (hash_a_state).user_state )
   7
   8 // TRD : a quality hash function, provided for user convenience - note hash must be initialized to 0 before the first call by the user
   9
  10 #if( LFDS710_PAL_ALIGN_SINGLE_POINTER == 4 )
  11   // TRD : void *data, lfds710_pal_uint_t data_length_in_bytes, lfds710_pal_uint_t hash
  12   #define LFDS710_HASH_A_HASH_FUNCTION( data, data_length_in_bytes, hash )  {                                                           \
  13                                                                               lfds710_pal_uint_t                                        \
  14                                                                                 loop;                                                   \
  15                                                                                                                                         \
  16                                                                               for( loop = 0 ; loop < (data_length_in_bytes) ; loop++ )  \
  17                                                                               {                                                         \
  18                                                                                 (hash) += *( (char unsigned *) (data) + loop );         \
  19                                                                                 (hash) = ((hash) ^ ((hash) >> 16)) * 0x85ebca6bUL;      \
  20                                                                                 (hash) = ((hash) ^ ((hash) >> 13)) * 0xc2b2ae35UL;      \
  21                                                                                 (hash) = (hash ^ (hash >> 16));                         \
  22                                                                               }                                                         \
  23                                                                             }
  24 #endif
  25
  26 #if( LFDS710_PAL_ALIGN_SINGLE_POINTER == 8 )
  27   // TRD : void *data, lfds710_pal_uint_t data_length_in_bytes, lfds710_pal_uint_t hash
  28   #define LFDS710_HASH_A_HASH_FUNCTION( data, data_length_in_bytes, hash )  {                                                                \
  29                                                                               lfds710_pal_uint_t                                             \
  30                                                                                 loop;                                                        \
  31                                                                                                                                              \
  32                                                                               for( loop = 0 ; loop < (data_length_in_bytes) ; loop++ )       \
  33                                                                               {                                                              \
  34                                                                                 (hash) += *( (char unsigned *) (data) + loop );              \
  35                                                                                 (hash) = ((hash) ^ ((hash) >> 30)) * 0xBF58476D1CE4E5B9ULL;  \
  36                                                                                 (hash) = ((hash) ^ ((hash) >> 27)) * 0x94D049BB133111EBULL;  \
  37                                                                                 (hash) = (hash ^ (hash >> 31));                              \
  38                                                                               }                                                              \
  39                                                                             }
  40 #endif
  41
  42 /***** enums *****/
  43 enum lfds710_hash_a_existing_key
  44 {
  45   LFDS710_HASH_A_EXISTING_KEY_OVERWRITE,
  46   LFDS710_HASH_A_EXISTING_KEY_FAIL
  47 };
  48
  49 enum lfds710_hash_a_insert_result
  50 {
  51   LFDS710_HASH_A_PUT_RESULT_FAILURE_EXISTING_KEY,
  52   LFDS710_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE,
  53   LFDS710_HASH_A_PUT_RESULT_SUCCESS
  54 };
  55
  56 enum lfds710_hash_a_query
  57 {
  58   LFDS710_HASH_A_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  59   LFDS710_HASH_A_QUERY_SINGLETHREADED_VALIDATE
  60 };
  61
  62 /***** structs *****/
  63 struct lfds710_hash_a_element
  64 {
  65   struct lfds710_btree_au_element
  66     baue;
  67
  68   void
  69     *key;
  70
  71   void LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
  72     *volatile value;
  73 };
  74
  75 struct lfds710_hash_a_iterate
  76 {
  77   struct lfds710_btree_au_element
  78     *baue;
  79
  80   struct lfds710_btree_au_state
  81     *baus,
  82     *baus_end;
  83 };
  84
  85 struct lfds710_hash_a_state
  86 {
  87   enum lfds710_hash_a_existing_key
  88     existing_key;
  89
  90   int
  91     (*key_compare_function)( void const *new_key, void const *existing_key );
  92
  93   lfds710_pal_uint_t
  94     array_size;
  95
  96   struct lfds710_btree_au_state
  97     *baus_array;
  98
  99   void
 100     (*element_cleanup_callback)( struct lfds710_hash_a_state *has, struct lfds710_hash_a_element *hae ),
 101     (*key_hash_function)( void const *key, lfds710_pal_uint_t *hash ),
 102     *user_state;
 103 };
 104
 105 /***** public prototypes *****/
 106 void lfds710_hash_a_init_valid_on_current_logical_core( struct lfds710_hash_a_state *has,
 107                                                         struct lfds710_btree_au_state *baus_array,
 108                                                         lfds710_pal_uint_t array_size,
 109                                                         int (*key_compare_function)(void const *new_key, void const *existing_key),
 110                                                         void (*key_hash_function)(void const *key, lfds710_pal_uint_t *hash),
 111                                                         enum lfds710_hash_a_existing_key existing_key,
 112                                                         void *user_state );
 113   // TRD : used in conjunction with the #define LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE
 114
 115 void lfds710_hash_a_cleanup( struct lfds710_hash_a_state *has,
 116                              void (*element_cleanup_function)(struct lfds710_hash_a_state *has, struct lfds710_hash_a_element *hae) );
 117
 118 enum lfds710_hash_a_insert_result lfds710_hash_a_insert( struct lfds710_hash_a_state *has,
 119                                                          struct lfds710_hash_a_element *hae,
 120                                                          struct lfds710_hash_a_element **existing_hae );
 121   // TRD : if existing_value is not NULL and the key exists, existing_hae is set to the hash element of the existing key
 122
 123 int lfds710_hash_a_get_by_key( struct lfds710_hash_a_state *has,
 124                                int (*key_compare_function)(void const *new_key, void const *existing_key),
 125                                void (*key_hash_function)(void const *key, lfds710_pal_uint_t *hash),
 126                                void *key,
 127                                struct lfds710_hash_a_element **hae );
 128
 129 void lfds710_hash_a_iterate_init( struct lfds710_hash_a_state *has, struct lfds710_hash_a_iterate *hai );
 130 int lfds710_hash_a_iterate( struct lfds710_hash_a_iterate *hai, struct lfds710_hash_a_element **hae );
 131
 132 void lfds710_hash_a_query( struct lfds710_hash_a_state *has,
 133                            enum lfds710_hash_a_query query_type,
 134                            void *query_input,
 135                            void *query_output );
 136