Follow up to "C simple hashcons data structure"

Question

This is a follow-up question to my previous question

I have modified the code according to the feedback I got from here and my Professor. However, my Professor is still not happy with the final code. More specifically he is not a fan searching once to see if the item exists in the table and searching for the second time to insert the item. I am wondering how can I solve this problem or rewrite the code to be more efficient.

hashcons.h

#ifndef HASHCONS_H
#define HASHCONS_H

#include <stddef.h>
#include <stdbool.h>

typedef int (*Hash_Cons_Hash)(void *);
typedef bool (*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 hashcons 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 "prime.h"
#include "hashcons.h"

#define HC_INITIAL_BASE_SIZE 61
#define MAX_DENSITY 0.5

/**
 * Initializes a table
 * @param hc table
 * @param capacity new capacity
 */
void hc_initialize(HASH_CONS_TABLE hc, const int capacity) {
    hc->capacity = capacity;
    hc->table = calloc(hc->capacity, sizeof(void *));
    hc->size = 0;
}

/**
 * Finds the candidate index intended to get inserted or searched in table
 * @param hc table
 * @param item the item looking to be added or removed
 * @param insert_mode true indicates insert false indicates search
 * @return
 */
static int hc_candidate_index(HASH_CONS_TABLE hc, void *item, bool insert_mode) {
    int attempt = 0;
    int hash = hc->hashf(item);
    int index = hash % hc->capacity;
    int step_size = 0;

    while (attempt++ < hc->capacity) {
        if (insert_mode && hc->table[index] == NULL) {
            return index;
        } else if (!insert_mode && hc->equalf(hc->table[index], item)) {
            return index;
        }

        if (attempt == 0) {
            step_size = hash % (hc->capacity - 2);
        }
        index = (index + step_size) % hc->capacity;
    }

    return -1;
}

/**
 * Insert an item into table
 * @param hc table
 * @param item the item intended to get inserted into the table
 */
static void hc_insert(HASH_CONS_TABLE hc, void *item) {
    int index = hc_candidate_index(hc, item, true);

    hc->table[index] = item;
    hc->size++;
}

/**
 * Search an item in table
 * @param hc table
 * @param item the item intended to get searched in the table
 * @return the item or null
 */
static void *hc_search(HASH_CONS_TABLE hc, void *item) {
    int index = hc_candidate_index(hc, item, false);

    return index == -1 ? NULL : hc->table[index];
}

static void hc_resize(HASH_CONS_TABLE hc, const int capacity) {
    void **old_table = hc->table;
    int old_capacity = hc->capacity;
    hc_initialize(hc, capacity);

    for (int i = 0; i < old_capacity; i++) {
        void *item = old_table[i];
        if (item != NULL) {
            hc_insert(hc, item);
        }
    }

    free(old_table);
}

/**
 * Insert an item into table if item is not already in table or just returns the existing item
 * @param item the item
 * @param temp_size item size
 * @param hc table
 * @return item just got inserted into the table or existing item
 */
void *hash_cons_get(void *item, size_t temp_size, HASH_CONS_TABLE hc) {
    void *result;

    if (hc->table == NULL) {
        hc_initialize(hc, HC_INITIAL_BASE_SIZE);
    }

    if (hc->size > hc->capacity * MAX_DENSITY) {
        const int new_capacity = next_twin_prime((hc->capacity << 1) + 1);
        hc_resize(hc, new_capacity);
    }

    if ((result = hc_search(hc, item)) != NULL) {
        return result;
    } else {
        result = malloc(temp_size);
        memcpy(result, item, temp_size);

        hc_insert(hc, result);

        return result;
    }
}

prime.h

#ifndef PRIME_H
#define PRIME_H

int next_twin_prime(int x);

#endif

prime.c

#include "prime.h"
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define INITIAL_TABLE_SIZE 9973

struct PrimesTable {
    int size;
    bool *table;
};

struct PrimesTable primesTable = {0, 0};

/**
 * Create a boolean array "prime[0..n]" and initialize
 * all entries it as true. A value in prime[i] will
 * finally be false if i is Not a prime, else true.
 */
void initialize_sieve_of_eratosthenes(int n) {
    if (primesTable.table == NULL) {
        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        memset(primesTable.table, true, primesTable.size);
    } else {
        int original_size = primesTable.size;
        bool *original_table = primesTable.table;

        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        memset(primesTable.table, true, primesTable.size);
        memcpy(primesTable.table, original_table, original_size * sizeof(bool));
        free(original_table);
    }

    for (int p = 2; p * p < n; p++) {
        // If primes[p] is not changed, then it is a prime
        if (primesTable.table[p] == true) {
            // Update all multiples of p
            for (int i = p * 2; i <= n; i += p) primesTable.table[i] = false;
        }
    }
}

/**
 * Return the next prime greater than parameter such that -2 is also a prime
 */
int next_twin_prime(int x) {
    if (primesTable.table == 0) {
        initialize_sieve_of_eratosthenes(INITIAL_TABLE_SIZE);
    }

    int i;
    for (i = x + 1; i < primesTable.size; i++) {
        if (primesTable.table[i] && primesTable.table[i - 2]) return i;
    }

    initialize_sieve_of_eratosthenes((primesTable.size << 1) + 1);

    return next_twin_prime(x);
}

Repository URL

Added by Reviewer

common.h

#ifndef COMMON_H
#define COMMON_H

#define TRUE 1
#define FALSE 0

#endif

test.h

#ifndef TEST_h
#define TEST_h

void test_integer_table();

#endif

test.c

#include "stdlib.h"
#include "stdio.h"
#include "stdbool.h"
#include "hashcons.h"


long hash_integer(void *p) {
    return *((int *) p);
}


bool equals_integer(void *p1, void *p2) {
    if (p1 == NULL || p2 == NULL) {
        return false;
    }

    int *i1 = (int *) p1;
    int *i2 = (int *) p2;
    return *i1 == *i2;
}

static struct hash_cons_table integer_table = {
        0, 0, 0,
        &hash_integer,
        &equals_integer
};


int *new_integer(int n) {
    return hash_cons_get(&n, sizeof(int), &integer_table);
}

void assertTrue(const char *message, bool b) {
    if (!b) {
        fprintf(stderr, "Assertion failed: %s\n", message);
        exit(1);
    }
}

void test_integer_table() {
    int *i3 = new_integer(3);
    assertTrue("initial i3", *i3 == 3);
    int *i8 = new_integer(8);
    assertTrue("initial i8", *i8 == 8);
    assertTrue("later i3", *i3 == 3);
    for (int i = 0; i < 100; ++i) {
        char buffer[256];
        sprintf(buffer, "integer for %d", i);
        assertTrue(buffer, *new_integer(i) == i);
    }
}

main.c

#include "common.h"
#include "hashcons.h"
#include <stdio.h>
#include <stdlib.h>
#include "test.h"

typedef struct dummy {
    int key;
} *DUMMY;

long hash(void *item) {
    return 13 * ((DUMMY) item)->key + 17;
}

int equal(void *item1, void *item2) {
    if (item1 == NULL || item2 == NULL) {
        return FALSE;
    }

    return ((DUMMY) item1)->key == ((DUMMY) item2)->key;
}

DUMMY create_dummy(int key) {
    DUMMY dummy = malloc(sizeof(dummy));
    dummy->key = key;
    return dummy;
}

static int test_adding_items(HASH_CONS_TABLE hc, int test_sample)
{
    printf("starting to add stuff\n");
    int failure_count = 0;
    for (int i = 0; i < test_sample; i++) {
        void *item = create_dummy(i);
        if (!hash_cons_get(item, sizeof(struct dummy), hc))
        {
            failure_count++;
        }
    }
    printf("finished adding stuff\n");

    return failure_count;
}

static int test_getting_times(HASH_CONS_TABLE hc, int test_sample)
{
    printf("starting to get stuff\n");
    int failure_count = 0;
    for (size_t i = 0; i < test_sample; i++) {
        void *item = create_dummy(i);

        if (hash_cons_get(item, sizeof(struct dummy), hc) == NULL)
        {
            failure_count++;
            printf("Item %d not found\n", i);
        }
    }
    printf("finished getting stuff\n");

    return failure_count;
}

int main() {
    HASH_CONS_TABLE hc = malloc(sizeof(struct hash_cons_table));
    hc->hashf = hash;
    hc->equalf = equal;
    hc->size = 0;
    int count = 300;

    printf("starting to add stuff\n");
    int i;
    for (i = 0; i < count; i++) {
        void *item = create_dummy(i);
        hash_cons_get(item, sizeof(struct dummy), hc);
    }
    printf("finished adding stuff\n");

    printf("starting to get stuff\n");
    for (i = 0; i < count; i++) {
        void *item = create_dummy(i);
        if (hash_cons_get(item, sizeof(struct dummy), hc) == NULL)
        {
            printf("Item %d not found\n", i);
        }
    }
    printf("finished getting stuff\n");

    printf("Done!");

    test_integer_table();

    test_adding_items(hc, 100);

    test_getting_times(hc, 100);

    return 0;
}

Answer 1

General Observations
The code has improved from the last version quite a bit. It now utilizes a more common algorithm for getting primes and this new algorithm should perform better. The code in hashcons.c is less complex and most or all of any possible bugs have been removed (thank you for removing the possible recursion).

I have taken the liberty of adding the files that were not included in both reviews from the repository. You can delete this if you like, but I am reviewing them.

Upate the repository readme file with the explanation of what a hashcons is that I had in my original review, as well as an explanation of what hashcons.c and prime.c do.

The most major area for improvement is memory allocation in C The rest of this review is organized by listing the items that can be improved in descending order from most major to most minor.

Test for Possible Memory Allocation Errors
I addressed this in the first review, however, I will address it again because it is very important.

In modern high level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. As the code is now, if this code was used in software to control an airplane during flight I would not get on that airplane, there is inherent Unknown Behavior (UB) in how malloc() and calloc() are used in the code, this is especially true if the code is working in a limited memory application such as embedded control systems. The failure of memory allocation in C on regular computers is less of an issue since there is a lot of memory, but in limited environments this is still important.

Here is the code I am talking about:

In main.c:

int main() {
    HASH_CONS_TABLE hc = malloc(sizeof(struct hash_cons_table));
    hc->hashf = hash;
    hc->equalf = equal;
    hc->size = 0;

DUMMY create_dummy(int key) {
    DUMMY dummy = malloc(sizeof(dummy));
    dummy->key = key;
    return dummy;
}

In hashcons.c

void hc_initialize(HASH_CONS_TABLE hc, const int capacity) {
    hc->capacity = capacity;
    hc->table = calloc(hc->capacity, sizeof(*hc->table));
    hc->size = 0;
}

In prime.c

void initialize_sieve_of_eratosthenes(int n) {
    if (primesTable.table == NULL) {
        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        memset(primesTable.table, true, primesTable.size);
    } else {
        int original_size = primesTable.size;
        bool *original_table = primesTable.table;

        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        memset(primesTable.table, true, primesTable.size);
        memcpy(primesTable.table, original_table, original_size * sizeof(bool));
        free(original_table);
    }

Each call of malloc() or calloc() should be followed by a test to see if the pointer is NULL to prevent accessing the address 0, this will prevent UB.

Examples:

int main() {
    HASH_CONS_TABLE hc = malloc(sizeof(struct hash_cons_table));
    if (hc == NULL)
    {
        fprintf(stderr, "Memory Allocation of HASH_CONS_TABLE hc error in main().\nExiting Program.");
        return(EXIT_FAILURE);
    }
    hc->hashf = hash;
    hc->equalf = equal;
    hc->size = 0;

DUMMY create_dummy(int key) {
    DUMMY dummy = malloc(sizeof(dummy));
    if (dummy == NULL)
    {
        fprintf(stderr, "Memory Allocation error in create_dummy().\nExiting Program.");
        exit(EXIT_FAILURE);
    }
    dummy->key = key;
    return dummy;
}

void initialize_sieve_of_eratosthenes(int n) {
    if (primesTable.table == NULL) {
        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        if (primesTable.table == NULL)
        {
            fprintf(stderr, "Memory Allocation of primesTable.table error in initialize_sieve_of_eratosthenes().\nExiting Program.");
            exit(EXIT_FAILURE);
        }
        memset(primesTable.table, true, primesTable.size);
    } else {
        int original_size = primesTable.size;
        bool *original_table = primesTable.table;

        primesTable.size = n;
        primesTable.table = malloc(n * sizeof(bool));
        if (primesTable.table == NULL)
        {
            fprintf(stderr, "Memory Allocation of primesTable.table error in initialize_sieve_of_eratosthenes().\nExiting Program.");
            exit(EXIT_FAILURE);
        }
        memset(primesTable.table, true, primesTable.size);
        memcpy(primesTable.table, original_table, original_size * sizeof(bool));
        free(original_table);
    }

Convention When Using Memory Allocation in C
When using malloc(), calloc() or realloc() in C a common convetion is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.

Example:

int main() {
    HASH_CONS_TABLE hc = malloc(sizeof(*hc));        // << What the pointer points to rather than sizeof struct.
    if (hc == NULL)
    {
        fprintf(stderr, "Memory Allocation of HASH_CONS_TABLE hc error in main().\nExiting Program.");
        return(EXIT_FAILURE);
    }
    hc->hashf = hash;
    hc->equalf = equal;
    hc->size = 0;

Improve Testing
Move all the testing functions into test.c, and provide interfaces for them, you might also want to consider moving the DUMMY test struct to test.c as well.

Make an overall test function in test.c and test.h that will test everything, have it call the current test functions.

Increase the test sample size to stress test the hashcons algorithm and the prime algorithm.

Take the overall start and end time of the functions to get an average value of the time insertion takes (you may not need this if you profile the code).

Profile the current code and the original code to see if there is an improvement in insertion and search times.

Missing Edit in main.c
While most of the program has been converted to use stdbool.h, main.c still includes common.h and uses FALSE rather than false in the function equal() which also returns int rather than bool.

Answer 2

Undefined behavior: Access outside array

Allocation is for n elements, yet code attempts to access 1 past primesTable.table[n-1]

... malloc(n * sizeof(bool));
...
for (int i = p * 2; i <= n; i += p) primesTable.table[i] = false;
//                     ^

Bug, wrong function type

hash() returns long yet .hashf points to a function returning int.

long hash(void *item) {
  return 13 * ((DUMMY) item)->key + 17;
}

typedef int (*Hash_Cons_Hash)(void *);
Hash_Cons_Hash hashf; 
hc->hashf = hash; 

Bug, signed integer overflow and negative indexes

13 * ((DUMMY) item)->key itself can signed integer overflow resulting in UB. Possible for hash() to return a negative value which cascades into UB in array indexing.

Performing an int * int + int and assigning that to long does not provide for a wider product when long wider than int.

long hash(void *item) {
  return 13 * ((DUMMY) item)->key + 17;  // problem code
}

hash % hc->capacity does not help as the result is signed: [-(hc->capacity-1) ... +(hc->capacity-1)].

int index = hash % hc->capacity;

I recommend to return an unsigned type like size_t from the hash function, then apply an unsigned % hc->capacity, such as

size_t hashu(const void *item) {
  return (size_t)8191 * ((DUMMY) item)->key + 17;
}

Bug int overflow

When int n is a prime near INT_MAX, p * p overflows. UB and potential infinite loop.

for (int p = 2; p * p < n; p++) {

Safe alternate

for (int p = 2; p < n/p; p++) {

Further, I expect <= is needed

for (int p = 2; p <= n/p; p++) {

On the edge of a bug: bool initialization

When sizeof(bool) > 1, like sizeof(int), memset(primesTable.table, true, primesTable.size); sets each bool object to 0x01010101. On reading table[i], that non-zero value is true, yet may look strange in debugging as 0x00000001 might be expected.

For me, I would reverse the table flags and initialize with memset(primesTable.table, false, primesTable.size); or better yet, use an unsigned char array and then initialize either way.

Simplify allocation

Allocate to the size of the referenced data, not the type. Easier to code right, review and maintain.

// primesTable.table = malloc(n * sizeof(bool));
primesTable.table = malloc(sizeof primesTable.table[0] * (n + 1u));
//            I also think OP needs a + 1 to prevent UB     ^^^^               

Do not hide pointers

There are times to hide, but not here.

//typedef struct dummy {
//  int key;
//} *DUMMY;
struct dummy {
  int key;
};
// or if you are trying to abstract the struct
typedef struct {
  int key;
} dummy;

include test

In general, list <> first. then "", except for the corresponding .h. This helps test that hashcons.h indeed can get called without prior includes.

In "hashcons.c"

#include "hashcons.h"
#include <stdlib.h>
#include <string.h>
#include "prime.h"
// #include "hashcons.h"  move to first

Naming

hashcons.h defines HASH_CONS_... and hash_cons_.... I recommend to use a _ in the filename or drop _ from the functions names.

bool size

bool may be the size of an int, or char, or ...

For space savings of a large bool array, consider unsigned char for the array which is defined as size 1. This might be a smidge slower, but IMO worth the potential space reduction.

// bool *table;
unsigned char *table;