5
\$\begingroup\$

I wrote code that implements perfect hash table, according to its description in the book "Introduction to Algorithms by Thomas H Cormen", but the code does not pass time tests in contest. I would really appreciate any help in making this code run faster (code must be in clear C).

Regarding the main function, we enter the number of elements in the set Then the elements themselves. Then requests, we respond to requests with “YES”|“NO” We finish reading requests when we encounter '.'

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <string.h>

#define BUFFER_SIZE 1024 // Size of buffer for input
#define P_VALUE 4294967311

struct Node {
    int key;
    int value;
};

// Define the structure for the hash table
struct SecondLevelHashTable {
    size_t size;
    size_t numElements;
    struct Node** table;
    size_t a;
    size_t b;
};

// Define the structure for the hash table
struct FirstLevelHashTable {
    size_t size;
    size_t numElements;
    struct SecondLevelHashTable** table;
    size_t a;
    size_t b;
};

// Define the hash function
size_t universalHash(int key, size_t a, size_t b, size_t m);

// Function to check if a number is prime
bool isPrime(int n);

// Function to find the minimum prime number greater than m
int findNextPrime(int m);

// Function to generate random values for a and b
void generateRandomValues(size_t *a, size_t *b);

// Function to initialize node
struct Node* initializeNode(int key, int value);

// Function to create a second-level hash table
struct SecondLevelHashTable* createSecondLevelHashTable(size_t size);

// Function to create a first-level hash table
struct FirstLevelHashTable* createFirstLevelHashTable(size_t size);

// Function to create an array of counts based on hash function results
size_t* countElementsByHash(int* keys, struct FirstLevelHashTable *firstLevelHashTable, size_t numKeys);

// Function to initialize second-level hash tables based on counts
void initializeSecondLevelHashTables(struct FirstLevelHashTable* firstLevelHashTable, size_t* counts);

// Function to initialize hash for second-level hash tables
void initializeHashForSecondHashTables(struct SecondLevelHashTable* secondLevelHashTable, struct FirstLevelHashTable* firstLevelHashTable, int* keys, size_t numKeys, size_t index);

// Function to check if an element exists in the hash table
bool locate(int x, struct FirstLevelHashTable* firstLevelHashTable);

void freeFirstLevelHashTable(struct FirstLevelHashTable* firstLevelHashTable);

void freeSecondLevelHashTable(struct SecondLevelHashTable* secondLevelHashTable);

// Define the hash function
size_t universalHash(int key, size_t a, size_t b, size_t m) {
    return ((a * key + b) % P_VALUE) % m;
}

// Function to generate random values for a and b
void generateRandomValues(size_t *a, size_t *b) {
    // Generate random values for a and b
    *a = (rand() % (P_VALUE - 1)) + 1; // Ensure a falls within the range [1, p - 1]
    *b = rand() % P_VALUE;             // Ensure b falls within the range [0, p - 1]
}


// Function to initialize node
struct Node* initializeNode(int key, int value) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        // Handle memory allocation failure
        perror("Memory allocation failed");
        return NULL;
    }

    // Assign key and value to the node
    newNode->key = key;
    newNode->value = value;

    return newNode;
}

struct SecondLevelHashTable* createSecondLevelHashTable(size_t size) {
    // Allocate memory for the hash table structure
    struct SecondLevelHashTable* secondLevelHashTable = (struct SecondLevelHashTable*)malloc(sizeof(struct SecondLevelHashTable));
    if (secondLevelHashTable == NULL) {
        freeSecondLevelHashTable(secondLevelHashTable);
        perror("Memory allocation failed");
        return NULL;
    }

    // Allocate memory for the array of pointers to doubly linked lists
    secondLevelHashTable->table = (struct Node**)malloc(size * sizeof(struct Node*));
    if (secondLevelHashTable->table == NULL) {
        freeSecondLevelHashTable(secondLevelHashTable);
        perror("Memory allocation failed");
        return NULL;
    }

    // Initialize each pointer in the array to NULL
    for (int i = 0; i < size; i++) {
        secondLevelHashTable->table[i] = NULL;
    }
    // Set the size and number of elements
    secondLevelHashTable->size = size;
    secondLevelHashTable->numElements = 0;

    return secondLevelHashTable;
}


struct FirstLevelHashTable* createFirstLevelHashTable(size_t size) {
    // Allocate memory for the hash table structure
    struct FirstLevelHashTable* firstLevelHashTable = (struct FirstLevelHashTable*)malloc(sizeof(struct FirstLevelHashTable));
    if (firstLevelHashTable == NULL) {
        freeFirstLevelHashTable(firstLevelHashTable);
        perror("Memory allocation failed");
        return NULL;
    }

    // Allocate memory for the array of pointers to second-level hash tables
    firstLevelHashTable->table = (struct SecondLevelHashTable**)malloc(size * sizeof(struct SecondLevelHashTable*));
    if (firstLevelHashTable->table == NULL) {
        freeFirstLevelHashTable(firstLevelHashTable);
        perror("Memory allocation failed");
        return NULL;
    }
    /**
    // Initialize each pointer in the array to NULL
    for (int i = 0; i < size; i++) {
        firstLevelHashTable->table[i] = createSecondLevelHashTable(1LL<<14);
    }
    **/
    firstLevelHashTable->size = size;
    firstLevelHashTable->numElements = 0;
    firstLevelHashTable->a = 0;
    firstLevelHashTable->b = 0;
    generateRandomValues(&firstLevelHashTable->a, &firstLevelHashTable->b);

    return firstLevelHashTable;
}



// Function to create an array of counts based on hash function results
size_t* countElementsByHash(int* keys, struct FirstLevelHashTable *firstLevelHashTable, size_t numKeys) {
    // Allocate memory for the array of counts
    size_t* counts = (size_t*)calloc(firstLevelHashTable->size, sizeof(size_t));
    if (counts == NULL) {
        perror("Memory allocation failed");
        return NULL;
    }
    // Iterate over each key
    for (size_t i = 0; i < numKeys; i++) {
        // Calculate the hash value for the current key
        size_t hashValue = universalHash(keys[i], firstLevelHashTable->a, firstLevelHashTable->b, firstLevelHashTable->size);
        // Increment the count at the corresponding index
        counts[hashValue]++;
    }

    return counts;
}


void initializeSecondLevelHashTables(struct FirstLevelHashTable* firstLevelHashTable, size_t* counts) {
    if (firstLevelHashTable == NULL || counts == NULL) {
        return;
    }

    // Iterate over each index in the first-level hash table
    for (size_t i = 0; i < firstLevelHashTable->size; ++i) {
        size_t size = counts[i] * counts[i] + 1; // Get the size from the counts array

        // Allocate memory for the second-level hash table
        struct SecondLevelHashTable* secondLevelHashTable = createSecondLevelHashTable(size);
        if (secondLevelHashTable == NULL) {
            freeSecondLevelHashTable(secondLevelHashTable);
            return;
        }

        // Assign the second-level hash table to the first-level hash table
        firstLevelHashTable->table[i] = secondLevelHashTable;
    }
}


void initializeHashForSecondHashTables(struct SecondLevelHashTable* secondLevelHashTable, struct FirstLevelHashTable* firstLevelHashTable, int* keys, size_t numKeys, size_t index) {
    if (secondLevelHashTable == NULL || keys == NULL) {
        return;
    }
    secondLevelHashTable->a = 0;
    secondLevelHashTable->b = 0;
    bool isCorrect = true;
    do {
        generateRandomValues(&secondLevelHashTable->a, &secondLevelHashTable->b);
        // Iterate over each key
        for (size_t i = 0; i < numKeys; i++) {
            // Calculate the hash value for the current key
            size_t firstHashValue = universalHash(keys[i], firstLevelHashTable->a,
                                               firstLevelHashTable->b,
                                               firstLevelHashTable->size);
            // Increment the count at the corresponding index
            if (firstHashValue == index) {
                size_t secondHashValue = universalHash(keys[i], secondLevelHashTable->a,
                                                    secondLevelHashTable->b,
                                                    secondLevelHashTable->size);
                //printf("%lld\n", secondLevelHashTable->size);
                if (secondLevelHashTable->table[secondHashValue] == NULL) {
                    secondLevelHashTable->table[secondHashValue] = initializeNode(keys[i], 1);
                } else {
                    isCorrect = false;
                    break;
                }
            }
        }
    } while (isCorrect != true);
}


bool locate(int x, struct FirstLevelHashTable* firstLevelHashTable) {
    // Calculate the hash value for the input key
    size_t firstHashValue = universalHash(x, firstLevelHashTable->a, firstLevelHashTable->b, firstLevelHashTable->size);

    // Get the corresponding second-level hash table
    struct SecondLevelHashTable* secondLevelHashTable = firstLevelHashTable->table[firstHashValue];
    if (secondLevelHashTable == NULL) {
        return false; // No elements at this index
    }
    // Calculate the hash value for the input key in the second-level hash table
    size_t secondHashValue = universalHash(x, secondLevelHashTable->a, secondLevelHashTable->b, secondLevelHashTable->size);
    // Check if the key exists in the second-level hash table
    if (secondLevelHashTable->table[secondHashValue] != NULL && secondLevelHashTable->table[secondHashValue]->key == x) {
        return true; // Key exists
    }

    return false; // Key does not exist
}

void freeFirstLevelHashTable(struct FirstLevelHashTable* firstLevelHashTable) {
    if (firstLevelHashTable == NULL) {
        return;
    }
    for (size_t i = 0; i < firstLevelHashTable->size; ++i) {
        struct SecondLevelHashTable* secondLevelHashTable = firstLevelHashTable->table[i];
        freeSecondLevelHashTable(secondLevelHashTable);
    }
    free(firstLevelHashTable->table);
    free(firstLevelHashTable);
}

void freeSecondLevelHashTable(struct SecondLevelHashTable* secondLevelHashTable) {
    if (secondLevelHashTable == NULL) {
        return;
    }
    for (size_t i = 0; i < secondLevelHashTable->size; i++) {
        free(secondLevelHashTable->table[i]);
    }
    free(secondLevelHashTable->table);
    free(secondLevelHashTable);
}


int main() {
    // Seed the random number generator
    srand(time(NULL));

    size_t num_elements, i;
    int query;
    char buffer[BUFFER_SIZE];

    // Reading the number of elements in the set
    if (!fgets(buffer, sizeof(buffer), stdin) || sscanf(buffer, "%zu", &num_elements) != 1 || num_elements <= 0) {
        fprintf(stderr, "Error: invalid input for the number of elements.\n");
        return EXIT_FAILURE;
    }

    int* elements = (int*)malloc(num_elements * sizeof(int*));
    if (!elements) {
        fprintf(stderr, "Error: memory allocation failed.\n");
        return EXIT_FAILURE;
    }

    // Reading the elements of the set
    if (!fgets(buffer, sizeof(buffer), stdin)) {
        fprintf(stderr, "Error: invalid input for elements.\n");
        free(elements);
        return EXIT_FAILURE;
    }

    char *token = strtok(buffer, " \t\n");
    for (i = 0; i < num_elements; i++) {
        if (!token) {
            fprintf(stderr, "Error: insufficient elements in the input.\n");
            free(elements);
            return EXIT_FAILURE;
        }
        elements[i] = (int)(uintptr_t)strtoull(token, NULL, 10);
        token = strtok(NULL, " \t\n");
    }

    struct FirstLevelHashTable* firstLevelHashTable = createFirstLevelHashTable(1LL << 3);
    if (!firstLevelHashTable) {
        fprintf(stderr, "Error: failed to create first-level hash table.\n");
        free(elements);
        return EXIT_FAILURE;
    }
    size_t* counts = countElementsByHash(elements, firstLevelHashTable, num_elements);
    if (!counts) {
        fprintf(stderr, "Error: failed to count elements by hash.\n");
        free(firstLevelHashTable);
        free(elements);
        return EXIT_FAILURE;
    }
    initializeSecondLevelHashTables(firstLevelHashTable, counts);
    for (size_t j = 0; j < firstLevelHashTable->size; j++) {
        struct SecondLevelHashTable *secondLevelHashTable = firstLevelHashTable->table[j];
        if (!secondLevelHashTable) {
            fprintf(stderr, "Error: failed to initialize second-level hash table.\n");
            free(counts);
            free(firstLevelHashTable);
            free(elements);
            return EXIT_FAILURE;
        }
        initializeHashForSecondHashTables(secondLevelHashTable, firstLevelHashTable,elements,num_elements,j);
    }
    while (1) {
        if (!fgets(buffer, sizeof(buffer), stdin)) {
            fprintf(stderr, "Error reading input.\n");
            freeFirstLevelHashTable(firstLevelHashTable);
            free(elements);
            free(counts);
            return EXIT_FAILURE;
        }

        // Check if the input is '.'
        if (buffer[0] == '.') {
            break;  // End of input
        }

        // Convert input to a long long integer
        if (sscanf(buffer, "%lld", &query) != 1) {
            fprintf(stderr, "Error: incorrect input format.\n");
            freeFirstLevelHashTable(firstLevelHashTable);
            free(elements);
            free(counts);
            return EXIT_FAILURE;
        }

        if (locate(query, firstLevelHashTable)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    freeFirstLevelHashTable(firstLevelHashTable);
    free(elements);
    free(counts);
    return EXIT_SUCCESS;
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Enable more compiler warnings:

ht.c: In function ‘universalHash’:
ht.c:73:16: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
   73 |     return ((a * key + b) % P_VALUE) % m;
      |                ^
ht.c: In function ‘generateRandomValues’:
ht.c:79:10: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘long int’ may change the sign of the result [-Wsign-conversion]
   79 |     *a = (rand() % (P_VALUE - 1)) + 1; // Ensure a falls within the range [1, p - 1]
      |          ^
ht.c:80:10: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘long int’ may change the sign of the result [-Wsign-conversion]
   80 |     *b = rand() % P_VALUE;             // Ensure b falls within the range [0, p - 1]
      |          ^~~~
ht.c: In function ‘createSecondLevelHashTable’:
ht.c:119:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘size_t’ {aka ‘long unsigned int’} [-Wsign-compare]
  119 |     for (int i = 0; i < size; i++) {
      |                       ^
ht.c: In function ‘main’:
ht.c:283:11: warning: conversion from ‘time_t’ {aka ‘long int’} to ‘unsigned int’ may change value [-Wconversion]
  283 |     srand(time(NULL));
      |           ^~~~~~~~~~
ht.c:359:32: warning: format ‘%lld’ expects argument of type ‘long long int *’, but argument 3 has type ‘int *’ [-Wformat=]
  359 |         if (sscanf(buffer, "%lld", &query) != 1) {
      |                             ~~~^   ~~~~~~
      |                                |   |
      |                                |   int *
      |                                long long int *
      |                             %d
ht.c: In function ‘freeFirstLevelHashTable’:
ht.c:261:47: warning: use of uninitialized value ‘*firstLevelHashTable.size’ [CWE-457] [-Wanalyzer-use-of-uninitialized-value]
  261 |     for (size_t i = 0; i < firstLevelHashTable->size; ++i) {
      |                            ~~~~~~~~~~~~~~~~~~~^~~~~~
  ‘main’: events 1-8
    |
    |  281 | int main() {
    |      |     ^~~~
    |      |     |
    |      |     (1) entry to ‘main’
    |......
    |  290 |     if (!fgets(buffer, sizeof(buffer), stdin) || sscanf(buffer, "%zu", &num_elements) != 1 || num_elements <= 0) {
    |      |        ~
    |      |        |
    |      |        (2) following ‘false’ branch...
    |......
    |  295 |     int* elements = (int*)malloc(num_elements * sizeof(int*));
    |      |                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                           |
    |      |                           (3) ...to here
    |  296 |     if (!elements) {
    |      |        ~
    |      |        |
    |      |        (4) following ‘false’ branch (when ‘elements’ is non-NULL)...
    |......
    |  302 |     if (!fgets(buffer, sizeof(buffer), stdin)) {
    |      |        ~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |        | |
    |      |        | (5) ...to here
    |      |        (6) following ‘false’ branch...
    |......
    |  308 |     char *token = strtok(buffer, " \t\n");
    |      |                   ~~~~~~~~~~~~~~~~~~~~~~~
    |      |                   |
    |      |                   (7) ...to here
    |......
    |  319 |     struct FirstLevelHashTable* firstLevelHashTable = createFirstLevelHashTable(1LL << 3);
    |      |                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                                                       |
    |      |                                                       (8) calling ‘createFirstLevelHashTable’ from ‘main’
    |
    +--> ‘createFirstLevelHashTable’: events 9-15
           |
           |  130 | struct FirstLevelHashTable* createFirstLevelHashTable(size_t size) {
           |      |                             ^~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                             |
           |      |                             (9) entry to ‘createFirstLevelHashTable’
           |  131 |     // Allocate memory for the hash table structure
           |  132 |     struct FirstLevelHashTable* firstLevelHashTable = (struct FirstLevelHashTable*)malloc(sizeof(struct FirstLevelHashTable));
           |      |                                                                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                                                                    |
           |      |                                                                                    (10) region created on heap here
           |  133 |     if (firstLevelHashTable == NULL) {
           |      |        ~                     
           |      |        |
           |      |        (11) following ‘false’ branch (when ‘firstLevelHashTable’ is non-NULL)...
           |......
           |  140 |     firstLevelHashTable->table = (struct SecondLevelHashTable**)malloc(size * sizeof(struct SecondLevelHashTable*));
           |      |                                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |                                                                 |
           |      |                                                                 (12) ...to here
           |  141 |     if (firstLevelHashTable->table == NULL) {
           |      |        ~                     
           |      |        |
           |      |        (13) following ‘true’ branch...
           |  142 |         freeFirstLevelHashTable(firstLevelHashTable);
           |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           |      |         |
           |      |         (14) ...to here
           |      |         (15) calling ‘freeFirstLevelHashTable’ from ‘createFirstLevelHashTable’
           |
           +--> ‘freeFirstLevelHashTable’: events 16-19
                  |
                  |  257 | void freeFirstLevelHashTable(struct FirstLevelHashTable* firstLevelHashTable) {

Output truncated, because it had 61823 characters. It reports a lot of sign conversions, incorrect format specifiers (undefined behavior), and use of uninitialized variables (undefined behavior).

Elide redundant and ambiguous comments:

// Define the structure for the hash table
struct SecondLevelHashTable {
    size_t size;
    size_t numElements;
    struct Node** table;
    size_t a;
    size_t b;
};

// Define the structure for the hash table
struct FirstLevelHashTable {
    size_t size;
    size_t numElements;
    struct SecondLevelHashTable** table;
    size_t a;
    size_t b;
};

// Define the hash function
size_t universalHash(int key, size_t a, size_t b, size_t m);

Why do you need to comment that you are declaring a struct? Simply remove them all. FirstLevelHashTable and SecondLevelHashTable as names make no sense to me. I'd have expected a single HashTable, or HTable, or hashTable, or hash_table.

// Function to check if a number is prime
bool isPrime(int n);

Yes, the name isPrime was clear enough. Kindly elide this comment too.

// Function to find the minimum prime number greater than m
int findNextPrime(int m);

// Function to generate random values for a and b
void generateRandomValues(size_t *a, size_t *b);

// Function to initialize node
struct Node* initializeNode(int key, int value);

// Function to create a second-level hash table
struct SecondLevelHashTable* createSecondLevelHashTable(size_t size);

// Function to create a first-level hash table
struct FirstLevelHashTable* createFirstLevelHashTable(size_t size);

None of the comments actually serves as documentation. initializeNode() is clear enough as a name, // function to initialize node adds nothing to it.

Consider adding:

  • What the functions return on success and failure.
  • For integers, what's the valid range that is allowed? Does isPrime() accept negative integers too? int n suggests so to me. If it was size_t or uintmax_t, I, and perhaps others too, wouldn't be asking this question.
  • For pointers, what happens when a null pointer is passed in? Does the library abort, or return a null pointer back, or something else?
  • What the functions that allocate memory do on failure. Do they return a null-pointer? Do they call exit() or abort()?

Define a type-alias for the structures to type less:

If we define an alias for struct SecondLevelHashTable, we wouldn't need to type struct everywhere:

typedef struct SecondLevelHashTable {
    size_t size;
    size_t numElements;
    struct Node** table;
    size_t a;
    size_t b;
} SecondLevelHashTable;

Though, I am still unsure what SecondLevel stands for.

Move all the function declarations to a header file and their definitions to a corresponding source file:

As of now, this hash table can only be used in this translation unit.

When you make this change, add the static keyword to all the functions that are internal to the hash table and shouldn't be part of the public API, and declare the structures as opaque types.

Use meaningful identifiers:

size_t a;
size_t b;

In FirstLevelHashStructure and SecondLevelHashStructure, what do a and b mean? Are they perchance supposed to hold the key and value?

You've used single-character identifiers in a lot of places. For instance:

size_t universalHash(int key, size_t a, size_t b, size_t m);

What do a, b, and m mean here? I'd suggest alternatives, but I do not understand what they mean.

Single-letter variables are expected and okay in loops where they are used as an index, like i, j, k, et cetera, but frowned upon in a public API where the identifers should be as meaningful as possible.

Do not cast the result of malloc() and family:

Since the C89 standard, or about 35 years, malloc() and family have returned a generic void * that is implicitly converted to and from any other pointer type and does not require a cast. Casting is redundant and only serves to clutter the code.

This is different in C++, where there is no implicit conversion from a void *, and a cast is necessary. Though in C++, you'd be using something like reinterpret_cast.

So, this:

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        // Handle memory allocation failure
        perror("Memory allocation failed");
        return NULL;
    }

becomes:

/* Allocate to the referenced object, and not the type.
 * This makes the code easier to maintain; if you change
 * the type, you wouldn't have to update the call to 
 * malloc() too. Though, it would probably be a bug if 
 * you changed the type but forgot to update the malloc call. */
struct Node *newNode = malloc(sizeof *newNode);
    if (newNode == NULL) {
        perror("Memory allocation failed");
        return NULL;
    }

Also note that malloc() is not required by the C standard to set errno, and if errno was set by a previous call to some function, but not set by malloc() on failure, you'd be printing misleading diagnostic information (assuming the previous function didn't set it to the same value you'd expect it to have on a memory allocation failure, in which case the diagnostic would not be misleading).

Moreover, no one expects library code to print arbitrary error messages, especially not when the documentation (which doesn't exist) includes no such warning.

If you're using at least C99, you can simply the function to:

#if 0
struct Node* initializeNode(int key, int value) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        // Handle memory allocation failure
        perror("Memory allocation failed");
        return NULL;
    }

    // Assign key and value to the node
    newNode->key = key;
    newNode->value = value;

    return newNode;
}
#else
struct Node *initializeNode(int key, int value) {
    struct Node *const newNode = malloc(sizeof *newNode);
    
    if (newNode != NULL) {
        *newNode = (struct Node) {
                       .key = key,
                       .value = value,
    }
    
    return newNode;
}
#endif

In createSecondLevelHashTable, you can again use a compound-literal to simply initialization:

// Initialize each pointer in the array to NULL
    for (int i = 0; i < size; i++) {
        secondLevelHashTable->table[i] = NULL;
    }
    // Set the size and number of elements
    secondLevelHashTable->size = size;
    secondLevelHashTable->numElements = 0;

with:

   *secondLevelHashTable = (struct SecondLevelHashTable) {
                               .table = { NULL },
                               .size = size,
                           };

Also note that ptr* a is C++ style. The recommended style to use for C is ptr *a.

The parsing code in main function is erroneous:

This is how I ran your program:

./ht
5
hello bya cdskcas c\0 caskcsa\n
hello
byte
.
cac
.
c
clcaskcna
bya
.
.
192



clear
d
c
1038492032

^C

According to the question, it was supposed to respond with "YES|NO", but I didn't get any response. According to the code "." was supposed to stop taking input, but that failed too. The program also did not respect end-of-file (CTRL-D) here, and I had to terminate it abnormally with a SIGINT.

It looks like the input only expected integers, then why did it not complain when I entered invalid characters?

It didn't because you used strtoull() incorrectly and ignored its return value. See: Correct usage of strtol.

The program runs cleanly under valgrind. Good job on that. My advice would be to get rid of the warnings and focus on robustness before worrying about optimizations. What good is a fast program that runs correctly only half of the time? Or a library that a client doesn't even know what to expect from because of lack of documentation or arbitrary and unsolicited diagnostic information?

\$\endgroup\$
1
  • \$\begingroup\$ I think it’s defensible for a coding style to say that all functions have some documentation, even when the name is self-explanatory. (Great function names!) It avoids situations where a name is less self-explanatory to the user of the API than it was to the author. \$\endgroup\$
    – Davislor
    Apr 19 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.