#StackBounty: #c C simpe hashcons data structure

Bounty: 100

I wrote this hashcons data structure in C and it works correctly. It uses larger twin primes as the capacity and double hashing (open addressing). Page 614 of "Data Structures and Other Objects Using C++ (4th Edition)" describes the approach.

I am wondering if I can get some feedback on whether I followed the standards and conventions.

hashcons.h

#ifndef HASHCONS_H
#define HASHCONS_H

#include <stddef.h>

typedef long (*HASH_CONS_HASH)(void *);

typedef int (*HASH_CONS_EQUAL)(void *, void *);

typedef struct hash_cons_table {
    int size;
    int capacity;
    void **table;
    HASH_CONS_HASH hashf;
    HASH_CONS_EQUAL equalf;
} *HASH_CONS_TABLE;

/**
 * Get item if there is one otherwise create one
 * @param temp_item it is a temporary or perhaps stack allocated creation of item
 * @param temp_size how many bytes it is
 * @param table
 */
void *hash_cons_get(void *temp_item, size_t temp_size, HASH_CONS_TABLE table);

#endif

hashcons.c

#include <stdlib.h>
#include <string.h>
#include "common.h"
#include "prime.h"
#include "hashcons.h"

#define HC_INITIAL_BASE_SIZE 61

// if it's bigger, we need to rehash
// if size > capacity * MAX_DENSITY then rehash
#define MAX_DENSITY 0.5

void hc_insert(HASH_CONS_TABLE hc, void *item);

void hc_initialize(HASH_CONS_TABLE hc, const int base_size) {
    hc->capacity = base_size;
//    hc->table = malloc(hc->capacity * sizeof(void *));
    hc->table = calloc(hc->capacity, sizeof(void *));
    hc->size = 0;
    int i;
    for (i = 0; i < hc->capacity; i++) {
        hc->table[i] = NULL;
    }
}


/**
 * Resizes the table by creating a temporary hash table for values to go off of.
 */
static void hc_resize(HASH_CONS_TABLE hc, const int capacity) {

    HASH_CONS_TABLE temp_hc = malloc(sizeof(struct hash_cons_table));
    hc_initialize(temp_hc, capacity);
    temp_hc->equalf = hc->equalf;
    temp_hc->hashf = hc->hashf;

    for (int i = 0; i < hc->capacity; i++) {
        void *item = hc->table[i];
        if (item != NULL) {
            hc_insert(temp_hc, item);
        }
    }

    hc->table = temp_hc->table;
    hc->capacity = capacity;
    free(temp_hc);
}

/**
 * Increases the table size based on the "base size" by a factor of 2 + 1
 */
static void hc_resize_up(HASH_CONS_TABLE hc) {
    const int new_capacity = next_twin_prime((hc->capacity << 1) + 1);

    hc_resize(hc, new_capacity);
}

static int hc_get_index(const int index1, const int index2, const int attempt, const int capacity) {
    return (index1 + attempt * index2) % capacity;
}

static int hash1(HASH_CONS_TABLE hc, void *item) {
    return labs(hc->hashf(item)) % hc->capacity;
}

static int hash2(HASH_CONS_TABLE hc, void *item) {
    return labs(hc->hashf(item)) % (hc->capacity - 2);
}

/**
 * Inserts a key/value pair into the hash table.
 */
void hc_insert(HASH_CONS_TABLE hc, void *item) {
    if (hc->size > hc->capacity * MAX_DENSITY) {
        hc_resize_up(hc);
    }

    int h1 = hash1(hc, item);
    int h2 = hash2(hc, item);

    // if collision occurs
    if (hc->table[h1] != NULL) {
        int attempt = 1;
        while (TRUE) {
            // get new index
            int index = hc_get_index(h1, h2, attempt, hc->capacity);

            // if no collision occurs, store
            if (hc->table[index] == NULL) {
                hc->table[index] = item;
                break;
            }
            attempt++;
        }
    }
        // if no collision occurs
    else {
        hc->table[h1] = item;
    }

    hc->size++;
}

/**
 * Searches through the hash table for the value of the corresponding key. If nothing is found, NULL
 * is returned.
 */
void *hc_search(HASH_CONS_TABLE hc, void *item) {
    int h1 = hash1(hc, item);
    int h2 = hash2(hc, item);

    int attempt = 0;
    while (attempt < hc->capacity) {
        int index = hc_get_index(h1, h2, attempt, hc->capacity);

        // Failed to find
        if (hc->table[index] == NULL) {
            break;
        } else if (hc->equalf(hc->table[index], item)) {
            return hc->table[index];
        }

        attempt++;
    }

    return NULL;
}

void *hash_cons_get(void *item, size_t temp_size, HASH_CONS_TABLE hc) {
    // Initialize data-structure
    if (hc->table == NULL) {
        hc_initialize(hc, HC_INITIAL_BASE_SIZE);
    }

    void *search_result = hc_search(hc, item);

    if (search_result == NULL) {
        // memcopy item before insert
        void *copied_item = malloc(temp_size);
        memcpy(copied_item, item, temp_size);

        hc_insert(hc, copied_item);

        return item;
    } else {
        return search_result;
    }
}

prime.h

#ifndef PRIME_H
#define PRIME_H

int next_prime(int x);
int next_twin_prime(int x);

#endif

prime.c

#include "common.h"
#include <math.h>

/*
 * Returns whether x is prime or not.
 * 1 if prime
 * 0 if not prime
 * -1 if undefined.
 */
int is_prime(const int x)
{
    if (x < 2)
    {
        return -1;
    }
    if (x < 4)
    {
        return 1;
    }
    if ((x % 2) == 0)
    {
        return 0;
    }

    for (int i = 3; i <= floor(sqrt((double)x)); i += 2)
    {
        if ((x % i) == 0)
        {
            return 0;
        }
    }
    return 1;
}

/**
 * Returns next possible prime
 */
int next_prime(int x)
{
    while (is_prime(x) != 1)
    {
        x++;
    }

    return x;
}

/**
 * Return the next prime greater than parameter such that -2 is also a prime
 */
int next_twin_prime(int x)
{
    int attempts = 0;
    while (TRUE)
    {
        int prime = next_prime(x);
        if (is_prime(prime - 2))
        {
            return prime;
        }

        attempts++;
        x = prime + 1;
    }
}

I could not attach the complete code here but this is the repository link


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.