#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;
}