frsh_aquosa/mngr/hash.c

   1
   2
   3 /***********************************************************/
   4 /* H A S H   T A B L E   U T I L I T Y   F U N C T I O N S */
   5 /***********************************************************/
   6
   7 /*
   8  * initialize the table
   9  *
  10  * sets all pointers of the array table of the hash table to NULL
  11  * and init the mutex (if a multithreaded service thread has
  12  * been configured)
  13  *
  14  * possible return values:
  15  *  true (all ok)
  16  *  false (something wrong with the mutex)
  17  */
  18 static bool contract_hash_init()
  19 {
  20         int i;
  21
  22 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
  23         if (fosa_mutex_init(&contract_hash_table.mutex, 0) != 0)
  24                 return false;
  25 #endif
  26         for (i = 0; i < HASH_N_ELEMENTS; i++)
  27                 contract_hash_table.table[i] = NULL;
  28
  29         return true;
  30 }
  31
  32 /*
  33  * hash function
  34  *
  35  * obtains the hash (int) value associated to the (string) key provided
  36  * simply accessing each character as an integer value and summing them all
  37  *
  38  * always returns the hash value (no room for errors!)
  39  */
  40 static unsigned int contract_hash_hash(const char *key_str)
  41 {
  42         int i, step = CHAR_PER_INT;
  43         unsigned int hash = 0;
  44         unsigned int key_val = 0;
  45         char *key_val_ptr = (char*) &key_val;
  46
  47         for (i = 0; i < strlen(key_str); i += step) {
  48                 strncpy(key_val_ptr, (key_str + i), step);
  49                 hash += key_val;
  50         }
  51
  52         return hash % HASH_N_ELEMENTS;
  53 }
  54
  55 /*
  56  * search an element
  57  *
  58  * calculates the hash value, accesses the hash table element and
  59  * follows the linked list if needed
  60  * data_ptr can be used to access/modify the element data field
  61  *
  62  * possible return values:
  63  *  HASH_LABEL_FOUND
  64  *  HASH_ERR_LABEL_NOT_FOUND
  65  */
  66 static int contract_hash_find(const char *key, contract_hash_data_t **data_ptr)
  67 {
  68         contract_hash_entry_t *curr_entry;
  69         unsigned int hash_value;
  70         int result;
  71
  72         /* hash value of the the key */
  73         hash_value = contract_hash_hash(key);
  74 #ifdef frsh_enable_service_th_multithread
  75         /* lock the table */
  76         fosa_mutex_lock(&contract_hash_table.mutex);
  77 #endif
  78         /* start traversing the linked list (if needed) */
  79         curr_entry = contract_hash_table.table[hash_value];
  80         while (curr_entry != NULL) {
  81                 if (strncmp(key, curr_entry->contract_label, HASH_KEY_LENGTH) == 0) {
  82                         /* key found! */
  83                         *data_ptr = &(curr_entry->contract_data);
  84                         result =  HASH_LABEL_FOUND;
  85                         break;
  86                 }
  87                 /* not found yet, let's try the next element */
  88                 curr_entry = curr_entry->next;
  89         }
  90 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
  91         /* unlock the table */
  92         fosa_mutex_unlock(&contract_hash_table.mutex);
  93 #endif
  94
  95         return result;
  96 }
  97
  98 /*
  99  * add an element
 100  *
 101  * calculates the hash function and adds the new element at the end
 102  * of the linked list of the hash table entry, unless one with the same
 103  * key value already exists
 104  * data_ptr can be used to access/modify the element data field
 105  *
 106  * possible return values:
 107  *  HASH_NO_ERROR
 108  *  HASH_ERR_LABEL_FOUND
 109  */
 110 static int contract_hash_add(const char *key, contract_hash_data_t **data_ptr)
 111 {
 112         contract_hash_entry_t *new_entry, **curr_entry;
 113         unsigned int hash_value;
 114         int result;
 115
 116         /* hash value of the key */
 117         hash_value = contract_hash_hash(key);
 118 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
 119         /* lock the table */
 120         fosa_mutex_lock(&contract_hash_table.mutex);
 121 #endif
 122         /* traverse the linked list till the end
 123          * (stop if the key already exists) */
 124         curr_entry = &contract_hash_table.table[hash_value];
 125         result = HASH_NO_ERROR;
 126         while (*curr_entry != NULL) {
 127                 if (strncmp(key, (*curr_entry)->contract_label, HASH_KEY_LENGTH) == 0) {
 128                         result = HASH_ERR_LABEL_FOUND;
 129                         break;
 130                 }
 131                 curr_entry = &(*curr_entry)->next;
 132         }
 133         if (result == HASH_NO_ERROR) {
 134                 /* create the new element */
 135                 new_entry = (contract_hash_entry_t*) malloc(sizeof(contract_hash_entry_t));
 136                 strncpy(new_entry->contract_label, key, HASH_KEY_LENGTH);
 137                 /* add it (we're already at the end of the linked list) */
 138                 *data_ptr = &(new_entry->contract_data);
 139                 *curr_entry = new_entry;
 140                 new_entry->next = NULL;
 141         }
 142 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
 143         /* unlock the table */
 144         fosa_mutex_unlock(&contract_hash_table.mutex);
 145 #endif
 146
 147         return result;
 148 }
 149
 150 /*
 151  * remove an element
 152  *
 153  * calculates the hash function, searches the element in the linked
 154  * list and remove it
 155  *
 156  * possible return values:
 157  *  HASH_NO_ERROR
 158  *  HASH_ERR_LABEL_NOT_FOUND
 159  */
 160 static int contract_hash_del(const char *key)
 161 {
 162         contract_hash_entry_t *curr_entry, *curr_entry_prev;
 163         unsigned int hash_value;
 164         int result;
 165
 166         /* hash value of the key */
 167         hash_value = contract_hash_hash(key);
 168 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
 169         /* lock the table */
 170         fosa_mutex_lock(&contract_hash_table.mutex);
 171 #endif
 172         /* traverse the list searching for the key */
 173         curr_entry_prev = NULL;
 174         curr_entry = contract_hash_table.table[hash_value];
 175         result = HASH_ERR_LABEL_NOT_FOUND;
 176         while (curr_entry != NULL) {
 177                 if (strncmp(key, curr_entry->contract_label, HASH_KEY_LENGTH) == 0) {
 178                         /* update the list and remove the element */
 179                         if (curr_entry_prev == NULL)
 180                                 contract_hash_table.table[hash_value] = curr_entry->next;
 181                         else
 182                                 curr_entry_prev->next = curr_entry->next;
 183                         free((void*) curr_entry);
 184                         result = HASH_NO_ERROR;
 185                         break;
 186                 }
 187                 curr_entry_prev = curr_entry;
 188                 curr_entry = curr_entry->next;
 189         }
 190 #ifdef FRSH_CONFIG_ENABLE_SERVICE_TH_MULTITHREAD
 191         /* unlock the table */
 192         fosa_mutex_unlock(&contract_hash_table.mutex);
 193 #endif
 194
 195         return result;
 196 }