Instructions
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");
}
}