Voir la source de 2015:04:07:HashTables

[[category:EPITA:TP:20142015]]
=Introduction=

Today, we are going to see how to implement simple hashtables.
You will resolve collisions with linked lists.

=Subject maintainer=

Feel free to contact me if you find an error or if something is unclear.

* veyry_p (Pierre-Alexandre VEYRY) [mailto:veyry_p@epita.fr veyry_p@epita.fr]


=Submission=

You will submit a repository containing at least a AUTHORS file, a Makefile at the root of the directory, and your source code.
The main function must be in a file called main.c separated from the rest so that we can replace it with our own main.

We remind you that to be valid, your AUTHORS must match this :
    sh$ cat -e AUTHORS
    * login_x$

Architecture : 
* <tt>login_x-tp-hash</tt>
** <tt>AUTHORS</tt>
** <tt>Makefile</tt>
** <tt>README</tt> (facultatif)
** <tt>src</tt>
*** <tt>main.c</tt>
*** Your source code

=Reminder=

In a hashtable, you have pairs of key,value. To store them, you will apply a hash function on the key
to determine the position in the vector. If two keys have the same position, this is a conflict. 
You will link them in a linked list if the keys are different. However, remind that a key must be unique
in the entire hashtable.

=Structure Definitions=
You will use this <tt>hashtable.h</tt> :
<source lang="C">
#ifndef HASHTABLE_H
# define HASHTABLE_H

# include <stddef.h>

struct place
{
  char *key;
  char *val;
  struct place *next;
};

struct hashtable
{
  size_t size;
  struct place **table;
};

#endif /* !HASHTABLE_H */
</source>

In the following exercises, you will implement functions and add their prototypes inside the hashtable.h header file.

=Init the hashtable=

You will implement the following function. It creates a new empty hashtable.
<source lang="C">
struct hashtable *init_hashtable(size_t s);
</source>


=Hash function=

To implement a hashtable, you need to calculate the position of your element in the vector.
To do so, we will use a very common and simple hash function. 
The position of the vector will be calculated using this formula :
    pos = (strlen(key) + sum(ascii_val(key[i]))) mod hashtable.size
The main advantage of hashtable is performance. So you will use only one loop
to implement this function. We will check the optimisation. The usage of strlen from the standard library is forbidden.

You can also use another hash function if you want but everything must work. This one is efficient and simple.

=Insertion=

You will have to implement the following function to add a value inside your hashtable :
<source lang="C">
int insert_hash(struct hashtable *table, const char *key, char *value);
</source>
If everything works, you will return 1.
If you have a position conflict, add the new value at the beginning of the list.
If the key already exists, you will not insert the element and return 0.
If any other problem occurs, you will return 0.


=Removing an element=

You will implement the following function :
<source lang="C">
int rm_hash(struct hashtable *table, const char *key);
</source>
You will return 1 if it succeeded and 0 if you didn't find the key or if anything went wrong.


=Getting a value=

You will implement the following function :
<source lang="C">
char *get_hash(struct hashtable *table, const char *key);
</source>
You will return NULL if you don't find the key. Otherwise, you will return the value.


=Free=

If you free your memory, then you've understand everything. 
You will implement this function that removes everything in the hashtable and frees everything.
We will check with valgrind.
<source lang="C">
void free_hash(struct hashtable *table);
</source>


=BONUS : Print the table=

You will implement a function to print the table.
<source lang="C">
void print_table(struct hashtable* table);
</source>
It will print all the keys and values.

You will separate the keys from their values with a space, a colon, and a space : <tt>" : "</tt>

The different places (slots) will be separated with a newline : <tt>'\n'</tt>

Don't print anything for empty places.

And when there are several values on the same line, you will separate them with this : <tt>" -> "

Example : 
    sh$ ./a.out
    KEY1 : value1
    KEY2 : value2 -> KEX3 : value3
    KEY4 : value4