Homework #5 – Chained hash table

chtbl.c

/*
 * chtbl.c
 */
#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "chtbl.h"

void chtbl_destroy(CHTbl *htbl) {

    int i;

    /* Destroy each bucket. */
    for (i = 0; i < htbl->buckets; i++) {
        list_destroy(&htbl->table[i]);
    }

    /* Free the storage allocated for the hash table. */
    free(htbl->table);

    /* No operations are allowed now, but clear the structure as a
     * precaution. */
    memset(htbl, 0, sizeof(CHTbl));
}

int chtbl_remove(CHTbl *htbl, void **data) {

    ListElmt *element, *prev;
    int bucket;

    /* Hash the key. */
    bucket = htbl->h(*data) % htbl->buckets;

    /* Search for the data in the bucket. */
    prev = NULL;

    for (element = list_head(&htbl->table[bucket]); element != NULL; element
            = list_next(element)) {

        if (htbl->match(*data, list_data(element))) {

            /* Remove the data from the bucket. */
            if (list_rem_next(&htbl->table[bucket], prev, data) == 0) {
                htbl->size--;
                return 0;
            }
            else {
                return -1;
            }
        }

        prev = element;
    }

    /* Return that the data was not found. */

    return -1;
}

int chtbl_lookup(const CHTbl *htbl, void **data) {

    ListElmt *element;
    int bucket;

    /* Hash the key. */
    bucket = htbl->h(*data) % htbl->buckets;

    /* Search for the data in the bucket. */
    for (element = list_head(&htbl->table[bucket]); element != NULL; element
            = list_next(element)) {

        if (htbl->match(*data, list_data(element))) {

            /* Pass back the data from the table. */
            *data = list_data(element);
            return 0;
        }
    }

    /* Return that the data was not found. */

    return -1;
}

chtbl.edit.c

#include <stdbool.h>
#include <string.h>
#include <alloca.h>
#include <assert.h>
#include <math.h>
#include "chtbl.h"

#define duplicate(SRC)                                                  \
        ({                                                              \
                memcpy(alloca(sizeof(*SRC)), SRC, sizeof(*SRC));        \
        })

#define restore(DEST, SRC) memcpy(DEST, SRC, sizeof(*(SRC)))

int chtbl_init( CHTbl* this,
		int buckets,
		int(*h)(const void *key),
		int(*match)(const void *key1, const void *key2),
		void(*destroy)(void*data),
		double maxLoadFactor,
		double resizeMultiplier                        )
{


	assert(resizeMultiplier > 0.0);

	this->table = malloc(buckets * sizeof(*this->table));

	if (this->table == NULL)
	{
		return -1;
	}
	else
	{
		this->h                = h;
		this->size             = 0;
		this->match            = match;
		this->destroy          = destroy;
		this->buckets          = buckets;
		this->maxLoadFactor    = maxLoadFactor;
		this->resizeMultiplier = resizeMultiplier;

		for (int i = 0; i < buckets; i++)
		{
			list_init(this->table + i, destroy);
		}

		return 0;
	}
}

bool list_empty(const List* this)
{
        return this->size == 0;
}

int chtbl_resize(CHTbl* this)
{
	const int  buckets = (this->buckets * this->resizeMultiplier) ?: 1;
	void*       memory = malloc(sizeof(List) * buckets);

	if (memory == NULL)
	{
		return -1;
	}
	else
	{
		// save previous state
		CHTbl* prev = duplicate(this);

		// update current state
		this->table   = memory;
		this->buckets = buckets;
		this->size    = 0;

		for (int i = 0; i < this->buckets; i++)
		{
			list_init(&this->table[i], this->destroy);
		}

		for (int i = 0; i < prev->buckets; ++i)
		{
			List* bucket = prev->table + i;

			while (list_empty(bucket) == false)
			{
				void* data;

				if (list_rem_next(bucket, NULL, &data) == 0 && bucket->destroy != NULL)
				{
					const int error = chtbl_insert(this, data);

					if (error)
					{
						restore(this, prev);
						return error;
					}
				}
			}
		}

		free(prev->table);
	}
	return 0;
}

double multiplication_method(const CHTbl* this, const void* data)
{
	/* h(k) = ⌠m(kA mod 1)⌡, where A ≈ (√5 - 1) ⁄ 2 = 0.618 */
	const double A = (sqrt(5) - 1) / 2;
	return floor(this->buckets * fmod(this->h(data) * A, 1));
}

int chtbl_insert(CHTbl* this, const void* data)
{
	int  bucket;
	int  retval;

	/* Do nothing if the data is already in the table. */
	if (chtbl_lookup(this, (void*) data) == 0)
	{
		return 1;
	}

	/* Hash the key using Multiplication method */
	bucket = multiplication_method(this, data);

	/* Insert the data into the bucket. */
	retval = list_ins_next(this->table + bucket, NULL, data);
	if (retval == 0)
	{
		this->size++;

                const double loadFactor = this->size / this->buckets;
                if (loadFactor > this->maxLoadFactor)
                {
                        retval = chtbl_resize(this);
                }
        }

	return retval;
}

chtbl.h

/*
 * chtbl.h
 */
#ifndef CHTBL_H
#define CHTBL_H

#include <stdlib.h>

#include "list.h"

/* Define a structure for chained hash tables. */
typedef struct CHTbl_
{
        int buckets;

        int (*h)(const void *key);
        int (*match)(const void *key1, const void *key2);
        void (*destroy)(void *data);

        int size;
        List *table;
        double maxLoadFactor;
        double resizeMultiplier;

} CHTbl;

/* Public Interface */
int chtbl_init(CHTbl* this,
               int buckets,
               int(*h)(const void *key),
               int(*match)(const void *key1, const void *key2),
               void(*destroy)(void*data),
               double maxLoadFactor,
               double resizeMultiplier);

void chtbl_destroy(CHTbl *htbl);

int chtbl_insert(CHTbl *htbl, const void *data);

int chtbl_remove(CHTbl *htbl, void **data);

int chtbl_lookup(const CHTbl *htbl, void **data);

#define chtbl_size(htbl) ((htbl)->size)

#endif

hw5.c

#include <stddef.h>
#include <string.h>
#include <assert.h>
#include "chtbl.h"

static int h(const void *key)
{
	return (ptrdiff_t) key;
}

static int match(const void* key1, const void* key2)
{
	return strcmp(key1, key2) == 0;
}

static void destroy()
{
	return;
}

#define sizeof_array(PTR) (sizeof(PTR) / sizeof(*(PTR)))

int main(void)
{
	static const char*      data[] = {"0", "1", "2", "3", "4"};

	static const int          init = sizeof_array(data);
	static const double     factor = 0.5;
	static const double multiplier = 2;

	CHTbl table;

	chtbl_init(&table, init, h, match, destroy, factor, multiplier);

        assert(table.buckets == init);

	for (int i = 0; i < init; ++i)
	{
		assert(chtbl_insert(&table, data + i) == 0);
	}

        assert(table.buckets == init * multiplier);

	chtbl_destroy(&table);

	return 0;
}

list.c

/*
 * list.c
 */
#include <stdlib.h>
#include <string.h>

#include "list.h"

void list_init(List *list, void (*destroy)(void *data)) {
    /* Initialize the list */
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}

void list_destroy(List *list)
{
    void *data;

    /* Remove each element */
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy !=
                NULL) {
            /* Call a user-defined function to free dynamically allocated
               data. */
            list->destroy(data);
        }
    }

    /* No operations are allowed now, but clear the structure as a
       precaution. */
    memset(list, 0, sizeof(List));
}

int list_ins_next(List *list, ListElmt *element, const void *data)
{
    ListElmt *new_element;

    /* Allocate storage for the element. */
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
        return -1;

    /* Insert the element into the list. */
    new_element->data = (void *)data;
    if (element == NULL) {
        /* Handle insertion at the head of the list. */
        if (list_size(list) == 0)
            list->tail = new_element;
        new_element->next = list->head;
        list->head = new_element;
    }
    else {
        /* Handle insertion somewhere other than at the head. */
        if (element->next == NULL)
            list->tail = new_element;
        new_element->next = element->next;
        element->next = new_element;
    }

    /*  Adjust the size of the list to account for the inserted element. */
    list->size++;

    return 0;
}

int list_rem_next(List *list, ListElmt *element, void **data)
{
    ListElmt *old_element;

    /* Do not allow removal from an empty list. */
    if (list_size(list) == 0)
        return -1;

    /* Remove the element from the list. */
    if (element == NULL) {
        /* Handle removal from the head of the list. */
        *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;

        if (list_size(list) == 1)
            list->tail = NULL;
    }
    else {
        /* Handle removal from somewhere other than the head. */
        if (element->next == NULL)
            return -1;

        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;

        if (element->next == NULL)
            list->tail = element;
    }

    /* Free the storage allocated by the abstract data type. */
    free(old_element);

    /* Adjust the size of the list to account for the removed element. */
    list->size--;

    return 0;
}

list.h

/*
 * list.h
 */
#ifndef LIST_H
#define LIST_H

#include <stdlib.h>

/*
 * Singly-linked list element
 */
typedef struct ListElmt_
{
    void               *data;
    struct ListElmt_   *next;
} ListElmt;

/*
 * Singly-linked list
 */
typedef struct List_
{
    int                size;

    int                (*match)(const void *key1, const void *key2);
    void               (*destroy)(void *data);

    ListElmt           *head;
    ListElmt           *tail;
} List;

/*
 * Public interface
 */
void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif