Collision resolution — double hashing

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define SIZE 11
int table[SIZE], occupied[SIZE];

The table has 11 slots. Global occupied flags start at zero, so key 0 is a valid stored key rather than an empty-slot sentinel.

int insert(int key) {
    int base = key % SIZE;

base = key % SIZE gives an index from 0 through 10 for the nonnegative input keys. The helper returns 2 for duplicate, 1 for insertion and 0 when no probed slot is available.

    int step = 1 + key % (SIZE - 1);

step lies from 1 through 10. Because SIZE is the prime 11, every such step is relatively prime to the size, so this probe sequence can reach every slot.

    for (int i = 0; i < SIZE; ++i) {
        int index = (base + i * step) % SIZE;

(base + i*step) % SIZE uses the key-specific second-hash stride rather than a constant step of one. Bounding the loop by SIZE guarantees termination.

        if (occupied[index] && table[index] == key) return 2;
        if (!occupied[index]) { occupied[index] = 1; table[index] = key; return 1; }

If the occupied slot already stores key, return 2. If it is empty, set occupied, store key and return 1. No deletion operation is provided, so there are no tombstones to handle.

    }
    return 0;
}

After all attempts, return 0. The full-cycle probe rule here has examined every slot.

void display(void) {
    printf("Table:");
    for (int i = 0; i < SIZE; ++i) {
        if (occupied[i]) printf(" %d:%d",i,table[i]); else printf(" %d:_",i);
    }
    putchar('\n');
}

Print index:key for occupied entries and index:_ for empty ones, then a newline. The separate occupancy array makes zero keys display correctly.

/* n (0..100), then n nonnegative keys. Display after every insertion attempt. */
int main(void) {
    int n, key; if (!readInt(&n) || n < 0 || n > 100) return invalid();
    if (!n) display();

Accept n from 0 to 100. For n = 0, display the empty table even though the insertion loop will have no iterations.

    for (int i = 0; i < n; ++i) {
        if (!readInt(&key) || key < 0) return invalid();
        int result = insert(key);

Validate the key before computing its remainder. Save the helper’s status so the next branch can distinguish a duplicate from probe failure.

        if (result == 2) puts("Duplicate ignored.");
        else if (!result) puts("Insertion failed: probe sequence has no free slot.");
        else puts("Inserted.");
        display();
    }

Print Duplicate ignored, the probe-failure message, or Inserted according to the result. Always show the table after this attempt, even if the key was not added.

    return 0;
}

Return success after processing n valid key tokens. An insertion failure is reported as an operation result rather than a malformed-input failure.