Program To Create a Lists and Hash Table in C Assignment Solutions

Instructions

Objective

Write a c assignment program to create a hash table and lists.

Requirements and Specifications

Source Code

/* */ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include // Include other standard modules if needed. #include "hash_table.h" // t_data regroups a key and an element. typedef struct { char key[MAX_CAR_CLE]; // The key void* item; // The element }t_data; // Code taken from: https://en.wikipedia.org/wiki/Fowler Noll Vo_hash_function #define FNV_OFFSET 14695981039346656037UL #define FNV_PRIME 1099511628211UL unsigned int hash_index(const char* key, int capability) { // Calculate a value from the key.and constants. u_int64_t hash = FNV_OFFSET; for (const char* p = key; *p; p++) { hash ^= (u_int64_t)(unsigned char)(*p); hash *= FNV_PRIME; } // The number generated is reset to 32 bits and serves as a key to the // pseudo-random generator. srand((unsigned int)hash); // Returns an index in avalid interval. return rand() % capability; } // Creates a table of the maximum capacity requested. // The table is empty (nb_elements == 0). t_hashtable* new_table(int capacite) { int i; t_hashtable* res = (t_hashtable*)malloc(sizeof(t_hashtable)); res->lists = (t_list**)calloc(capacite, sizeof(t_list*)); for (i = 0; i res->lists[i] = (t_list*)malloc(sizeof(t_list)); init_liste(res->lists[i]); } res->capacite = capacite; res->nb_elements = 0; return res; } // Basic boolean function that returns true // if the table is empty and false otherwise. bool table_est_vide(const t_hashtable* table) { return table->nb_elements == 0; } // Returns the data corresponding to the key. // The function sends an assertion message if the table is empty. void* obtenir_donnee_ds_table(const t_hashtable* table, char* cle) { assert(table->nb_elements); unsigned int hash = hash_index(cle, table->capacite); int i; for(i = 0; ilists[hash]); i++) { t_data* data = (t_data*)obtenir_element_ds_liste(table->lists[hash], i); if (strcmp(data->key, cle) == 0) { return data->item; } } return NULL; } // Acesseur of the number of items in the table. int obtenir_nb_ds_table(const t_hashtable* table) { return table->nb_elements; } // Key accessory that is in the position provided in the table in its order // of entry into the table. char* obtenir_cle_ds_table(const t_hashtable* table, int position) { assert(position < table->nb_elements); int elems_passed = 0; int curr_bucket = 0; int offset = -1; while (true) { if (elems_passed + obtenir_nb_ds_liste(table->lists[curr_bucket]) > position) { offset = position - elems_passed; break; } elems_passed += obtenir_nb_ds_liste(table->lists[curr_bucket]); curr_bucket++; } t_data* data = (t_data*)obtenir_element_ds_liste(table->lists[curr_bucket], offset); return data->key; } // Inserts the item into the table from the f0urnie key. // Returns if there is a collision by the return value. // To avoid a previous function call to find out, the procedure returns // if the value already exists via the parameter (*exists). // In this case, the key is not added. bool inserer_ds_table(t_hashtable* table, void* element, char* cle, bool* exists) { assert(table->nb_elements); unsigned int hash = hash_index(cle, table->capacite); int i; for(i = 0; ilists[hash]); i++) { t_data* data = (t_data*)obtenir_element_ds_liste(table->lists[hash], i); if (strcmp(data->key, cle) == 0) { data->item = element; *exists = true; return true; } } t_data* data = (t_data*)malloc(sizeof(t_data)); strcpy(data->key, cle); data->item = element; inserer_ds_liste(table->lists[hash], data, 0); *exists = false; return false; } // Deletes the element corresponding to the key in the table. // The table must not be empty. // The function returns false for a non-existent key or true if the deletion // is efffected. bool supprimerr_ds_table(t_hashtable* table, char* cle) { unsigned int hash = hash_index(cle, table->capacite); int i; for(i = 0; ilists[hash]); i++) { t_data* data = (t_data*)obtenir_element_ds_liste(table->lists[hash], i); if (strcmp(data->key, cle) == 0) { supprimer_ds_liste(table->lists[i], i); return true; } } return false; } // Frees up the space associated with the table created by new_table(). // The second * is used for the reference passage to put the // effective parameter to NULL. void liberer_table(t_hashtable** ptr_table) { int i; for (i = 0; i<(*ptr_table)->capacite; i++) { while(obtenir_nb_ds_liste((*ptr_table)->lists[i]) > 0) { supprimer_ds_liste((*ptr_table)->lists[i], 0); } free((*ptr_table)->lists[i]); } free((*ptr_table)->lists); free(*ptr_table); } // Used for debug. This is to display all table data in the order // that they are in the table (not necessarily the entry order in the table). void display_hachage(t_hashtable* table) { int i; for(i = 0; icapacite; i++) { int j; printf("%d: ", i); for(j = 0; jlists[i]); j++) { t_data* data = (t_data*)obtenir_element_ds_liste(table->lists[i], j); printf("->%s",data->key); } printf("\n"); } }