#ifndef HEADER_H_INCLUDED

#define HEADER_H_INCLUDED



#include <string.h>

#include <stdio.h>

#include <stdlib.h>

typedef struct hashentry__s

{

    char songtitle[256], interpreter[256];

} hashentry_t;

typedef struct hasharray__s

{

    hashentry_t *entries;

    long num_entries;

} hasharray_t;

typedef struct hashcontainer__s

{

    hasharray_t *harrays;

    long hashsize;

} hashcontainer_t;



long hash_key(char songtitle[], char interpreter[], long hash_max);

hashcontainer_t *create_hash(long hashsize);

void delete_hash(hashcontainer_t *hashcontainer);

void insert_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);

hashentry_t *search_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);

void delete_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);

void print_hash(hashcontainer_t *hashcontainer);

long count_entries(hashcontainer_t *hashcontainer);

long count_entries_with_songtitle(hashcontainer_t *hashcontainer, char songtitle[]);

void insert_entry_ext_exp(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max));

void insert_entry_ext(hashcontainer_t *hashcontainer, hashentry_t *hashentry, long(*hashkey_gen)(hashentry_t *entry, long hash_max));

long hashkey_gen1(hashentry_t *entry, long hash_max);

long hashkey_gen2(hashentry_t *entry, long hash_max);

void rehash1(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max);

void rehash2(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max);



#endif // HEADER_H_INCLUDED



#include "header.h"



long hash_key(char songtitle[], char interpreter[], long hash_max)

{

    unsigned long i, index = 0;

    for (i = 0; i < strlen(songtitle); ++i)

        index = 64 * index + (long)(songtitle[i]);

    for (i = 0; i < strlen(interpreter); ++i)

        index = 64 * index + (long)(interpreter[i]);

    return index % hash_max;

}





long hashkey_gen1(hashentry_t *entry, long hash_max)

{

    unsigned long i, index = 0;

    for (i = 0; i < strlen(entry->songtitle); ++i)

        index = 64 * index + (long)(entry->songtitle[i]);

    for (i = 0; i < strlen(entry->interpreter); ++i)

        index = 64 * index + (long)(entry->interpreter[i]);

    return index % hash_max;

}





hashcontainer_t *create_hash(long hashsize)

{

    unsigned long i;

    hashcontainer_t *new = 0;

    if (!(new = malloc(sizeof(hashcontainer_t))))

    {

        fprintf(stderr, "Memory allocation error in create_hash()");

        exit(-1);

    }

    if (!(new->harrays = calloc(hashsize, sizeof(hasharray_t))))

    {

        fprintf(stderr, "Memory allocation error in create_hash()");

        exit(-1);

    }

    new->hashsize = hashsize;

    for (i = 0; i < hashsize; i++)

    {

        new->harrays[i];

    }

    return new;

}





void delete_hash(hashcontainer_t *hashcontainer)

{

    unsigned long i;

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        if (hashcontainer->harrays[i].entries)

        {

            free(hashcontainer->harrays[i].entries);

            hashcontainer->harrays[i].entries = 0;

            hashcontainer->harrays[i].num_entries = 0;

        }

    }

    free(hashcontainer->harrays);

    hashcontainer->harrays = 0;

    hashcontainer->hashsize = 0;

}





void insert_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])

{

    unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);

    hashcontainer->harrays[index].num_entries++;

    hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));

    strcpy(hashcontainer->harrays[index].entries[hashcontainer->harrays[index].num_entries - 1].songtitle, songtitle);

    strcpy(hashcontainer->harrays[index].entries[hashcontainer->harrays[index].num_entries - 1].interpreter, interpreter);

}





hashentry_t *search_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])

{

    unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);

    unsigned long len = hashcontainer->harrays[index].num_entries, i;

    for (i = 0; i < len; i++)

    {

        if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))

            return (hashcontainer->harrays[index].entries)+i;

    }

    return 0;

}





void delete_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])

{

    unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);

    unsigned long len = hashcontainer->harrays[index].num_entries, i;

    for (i = 0; i < len; i++)

    {

        if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))

        {

            if (i == 0 && len == 1)

            {

                free(hashcontainer->harrays[index].entries);

                hashcontainer->harrays[index].entries = 0;

                hashcontainer->harrays[index].num_entries = 0;

            }

            else

            {

                if (i != len - 1)

                    memcpy(hashcontainer->harrays[index].entries + i, hashcontainer->harrays[index].entries + i + 1, (len - i - 1)* sizeof(hashentry_t));

                hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, --hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));

            }

        }

    }

}





void print_hash(hashcontainer_t *hashcontainer)

{

    unsigned long i, j;

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        fprintf(stdout, "Hash index %ld\n", i);

        for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)

        {

            fprintf(stdout, "%s\t%s\n", hashcontainer->harrays[i].entries[j].songtitle, hashcontainer->harrays[i].entries[j].interpreter);

        }

        fprintf(stdout, "\n");

    }

}





long count_entries(hashcontainer_t *hashcontainer)

{

    unsigned long i, j, count = 0;

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)

        {

                count++;

        }

    }

    return count;

}





long count_entries_with_songtitle(hashcontainer_t *hashcontainer, char songtitle[])

{

    unsigned long i, j, count = 0;

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)

        {

            if (strcmp(hashcontainer->harrays[i].entries[j].songtitle, songtitle) == 0)

                count++;

        }

    }

    return count;

}





void insert_entry_ext_exp(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max))

{

    hashentry_t *new = malloc(sizeof(hashentry_t));

    strcpy(new->songtitle, songtitle);

    strcpy(new->interpreter, interpreter);

    unsigned long index = hashkey_gen(new, hashcontainer->hashsize);



    hashcontainer->harrays[index].num_entries++;

    hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));

    memcpy(hashcontainer->harrays[index].entries + hashcontainer->harrays[index].num_entries - 1, new, sizeof(hashentry_t));

}





void insert_entry_ext(hashcontainer_t *hashcontainer, hashentry_t *new, long(*hashkey_gen)(hashentry_t *entry, long hash_max))

{

    unsigned long index = hashkey_gen(new, hashcontainer->hashsize);



    hashcontainer->harrays[index].num_entries++;

    hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));

    memcpy(hashcontainer->harrays[index].entries + hashcontainer->harrays[index].num_entries - 1, new, sizeof(hashentry_t));

}





hashentry_t *search_entry_ext(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max))

{

    hashentry_t *new = malloc(sizeof(hashentry_t));

    strcpy(new->songtitle, songtitle);

    strcpy(new->interpreter, interpreter);

    unsigned long index = hashkey_gen(new, hashcontainer->hashsize);



    unsigned long i;

    for (i = 0; i < hashcontainer->harrays[index].num_entries; i++)

    {

        if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))

            return (hashcontainer->harrays[index].entries)+i;

    }

    return 0;

}





void rehash1(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max)

{

    hashcontainer_t *new = create_hash(hash_max);

    unsigned long i, j;

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)

        {

            insert_entry_ext(new, hashcontainer->harrays[i].entries + j, hashkey_gen);

        }

    }

    delete_hash(hashcontainer);

    hashcontainer->harrays = new->harrays;

    hashcontainer->hashsize = new->hashsize;

}





void rehash2(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max)

{

    unsigned long i, j, count = 0, len = count_entries(hashcontainer);

    hashentry_t temp[len];

    for (i = 0; i < hashcontainer->hashsize; i++)

    {

        for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)

        {

            strcpy(temp[count].songtitle, hashcontainer->harrays[i].entries[j].songtitle);

            strcpy(temp[count].interpreter, hashcontainer->harrays[i].entries[j].interpreter);

            count++;

        }

    }

    delete_hash(hashcontainer);

    hashcontainer_t *new = create_hash(hash_max);

    for (i = 0; i < len; i++)

    {

        insert_entry_ext(new, &temp[i], hashkey_gen);

    }

    hashcontainer->harrays = new->harrays;

    hashcontainer->hashsize = new->hashsize;

    free(new);

}



#include "source.c"





int main()

{

    hashcontainer_t *container = create_hash(3);



    insert_entry_ext_exp(container, "Title1", "Inter1", hashkey_gen1);

    insert_entry_ext_exp(container, "Title2", "Inter2", hashkey_gen1);

    insert_entry_ext_exp(container, "Title2", "Inter2", hashkey_gen1);

    insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);

    insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);

    insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);

    insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);

    insert_entry_ext_exp(container, "Title4", "Inter4", hashkey_gen1);

    insert_entry_ext_exp(container, "Title7", "Inter7", hashkey_gen1);

    insert_entry_ext_exp(container, "Title7", "Inter7", hashkey_gen1);

    delete_entry(container, "Title7", "Inter7");



    print_hash(container);

    fprintf(stdout, "\nRehashing...\n\n");

    rehash1(container, hashkey_gen1, 11);

    print_hash(container);



    hashentry_t *temp = search_entry_ext(container, "Title7", "Inter7", hashkey_gen1);

    if (temp)

        fprintf(stdout, "%s\t%s\n", temp->songtitle, temp->interpreter);

    else

        fprintf(stdout, "Not found.\n");



    fprintf(stdout, "%ld entries found.", count_entries(container));



    delete_hash(container);

    free(container);

    return 0;

}