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