Hello,
I am attempting to code a dynamic hash table. The number of buckets is doubled when one of the buckets contains 20 or more items. If I ignore this (and thus run the program as a statically sized hash table) the program runs and completes as expected with zero memory leaks.
However, if I attempt to resize the table, crazy things happen. I'm not attempting an in-place resize but instead creating a second hash table then iterating through every bucket in the first hash table, recalculating the new position, and placing the items into the new hash table. Afterwards I free the old hash table.
Due to the fact that the statically sized hash table works, I have narrowed down the error to the only new function, expand(...). The code for which is below.
This is my first post on this forum and the program is part of an exercise for University (of which I'm about two weeks ahead and thus haven't been receiving assistance from tutors). If further code/context is required I will be able to produce the code.
Code:
..............
typedef struct bucketItem {
struct bucketItem *next;
MEntry *entry;
} entry;
typedef struct bucket {
int entries;
struct bucketItem *head;
struct bucketItem *tail;
} bucket;
struct mlist {
unsigned long size;
struct bucket **buckets;
};
..............
static MList *expand(MList **ml, MEntry *me) { MList *oldTable, *newTable;
unsigned long i, oldPosition, newPosition;
bucket *oldBucket, *newBucket;
entry *oldEntry, *newEntry;
oldTable = *ml;
/* Create a new hash table */
if( (newTable=(MList *)malloc(sizeof(MList))) == NULL) {
fprintf(stderr, "%s\n", "Unable to allocate memory for mailing list.");
return NULL;
}
/* Make the new hash table twice the size of the old one */
newTable->size = oldTable->size * 2;
if( (newTable->buckets=malloc(sizeof(bucket)*(newTable->size))) == NULL) {
fprintf(stderr, "%s\n", "Unable to allocate memory for mailing list.");
return NULL;
}
/* Initialise the new buckets */
for(i=0; i<(newTable->size); i++) {
if((newTable->buckets[i]=malloc(sizeof(bucket))) == NULL) {
fprintf(stderr, "%s\n", "Unable to allocate memory for entry.");
return NULL;
}
newTable->buckets[i]->entries = 0;
newTable->buckets[i]->head = NULL;
newTable->buckets[i]->tail = NULL;
}
/* Move every entry in the old hash table over to new position in new hash table */
for(oldPosition = 0; oldPosition < (oldTable->size); oldPosition++) {
oldBucket = oldTable->buckets[oldPosition];
oldEntry = oldBucket->head;
while(oldEntry != NULL) {
if((newEntry=(entry *)malloc(sizeof(entry))) == NULL) {
fprintf(stderr, "%s\n", "Unable to allocate memory for new entry");
return NULL;
}
newEntry->entry = oldEntry->entry;
newEntry->next = NULL;
oldEntry->entry = NULL;
oldEntry = oldEntry->next;
newPosition = me_hash(newEntry->entry, newTable->size);
newBucket = newTable->buckets[newPosition];
if(newBucket->head == NULL) {
newBucket->head = newEntry;
} else {
newBucket->tail->next = newEntry;
}
newBucket->tail = newEntry;
newBucket->entries += 1;
}
}
/* Now add new entry into the new hash table */
if((newEntry=(entry *)malloc(sizeof(entry))) == NULL) {
fprintf(stderr, "%s\n", "Unable to allocate memory for new entry");
return NULL;
}
newEntry->entry = me;
newEntry->next = NULL;
newPosition = me_hash(me, newTable->size);
newBucket = newTable->buckets[newPosition];
if(newBucket->head == NULL) {
newBucket->head = newEntry;
} else {
newBucket->tail->next = newEntry;
}
newBucket->tail = newEntry;
newBucket->entries += 1;
ml_destroy(oldTable);
return newTable;
}
..............