/* C11. integer set: linear probing with tombstones. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#define CAP 7

typedef enum { EMPTY, OCCUPIED, DELETED } State;
typedef struct { int key; State state; } Slot;
typedef struct { Slot slot[CAP]; } Table;
/* Nonnegative modulo, including negative keys; no negation of INT_MIN. */
static size_t hash(int key)
{
    int remainder = key % CAP;
    return (size_t)(remainder < 0 ? remainder + CAP : remainder);
}
static size_t locate(const Table *t, int key)
{
    size_t start = hash(key);
    for (size_t step = 0; step < CAP; ++step) {
        size_t i = (start + step) % CAP;
        if (t->slot[i].state == EMPTY) return CAP;
        if (t->slot[i].state == OCCUPIED && t->slot[i].key == key) return i;
    }
    return CAP;
}
static bool insert(Table *t, int key)
{
    size_t start = hash(key), available = CAP;
    for (size_t step = 0; step < CAP; ++step) {
        size_t i = (start + step) % CAP;
        if (t->slot[i].state == OCCUPIED) {
            if (t->slot[i].key == key) return true; /* set: no duplicates */
        } else {
            if (available == CAP) available = i;
            if (t->slot[i].state == EMPTY) break;
        }
    }
    if (available == CAP) return false;
    t->slot[available] = (Slot){key, OCCUPIED}; return true;
}
static bool erase(Table *t, int key)
{
    size_t i = locate(t, key);
    if (i == CAP) return false;
    t->slot[i].state = DELETED; /* Do not break a later key's probe chain. */
    return true;
}
int main(void)
{
    Table t = {{{0, EMPTY}}};
    assert(locate(&t, 10) == CAP && !erase(&t, 10));
    assert(insert(&t, 10) && insert(&t, 17) && insert(&t, 24));
    assert(locate(&t, 10) == 3 && locate(&t, 17) == 4 && locate(&t, 24) == 5);
    assert(erase(&t, 17)); assert(locate(&t, 24) == 5);
    assert(insert(&t, 31)); assert(locate(&t, 31) == 4);
    assert(insert(&t, 24)); /* Duplicate after a previously deleted position. */
    assert(insert(&t, -1)); assert(locate(&t, -1) != CAP);
    assert(insert(&t, 0) && insert(&t, 1) && insert(&t, 2));
    assert(!insert(&t, 99)); assert(locate(&t, 99) == CAP);
    assert(insert(&t, 10)); /* Existing key succeeds even in a full table. */
    assert(erase(&t, 0) && insert(&t, 99));
    printf("Collision chain: 10 at %zu, 31 at %zu, 24 at %zu\n",
           locate(&t, 10), locate(&t, 31), locate(&t, 24));
    Table negatives = {{{0, EMPTY}}};
    assert(insert(&negatives, INT_MIN) && insert(&negatives, INT_MAX));
    assert(locate(&negatives, INT_MIN) != CAP && locate(&negatives, INT_MAX) != CAP);
    Table tombstones = {{{0, EMPTY}}};
    for (int i = 0; i < CAP; ++i) assert(insert(&tombstones, i));
    for (int i = 0; i < CAP; ++i) assert(erase(&tombstones, i));
    assert(locate(&tombstones, 99) == CAP);
    assert(insert(&tombstones, 99) && locate(&tombstones, 99) != CAP);
    puts("hashing tests passed");
    return 0;
}