Skip to main content
Fixed code formatting.
Source Link
pacmaninbw
  • 24.8k
  • 11
  • 46
  • 109

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;

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

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

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);
}
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);
}
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);
    }
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);
    }
Source Link
pacmaninbw
  • 24.8k
  • 11
  • 46
  • 109

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.