Int→int hash table (open addressing)

Challenge

Build a fixed-capacity int-to-int hash table that resolves collisions with linear probing.

The grader supplies this struct:

typedef struct {
    int *keys; int *vals; unsigned char *used;
    size_t cap, len;
} htab_t;

Task

Implement these functions (no main — the grader calls them):

• int ht_init(htab_t *h, size_t cap) — allocate the three arrays and zero used; return 0, or -1 on allocation failure.
• void ht_free(htab_t *h) — free storage and reset fields.
• int ht_set(htab_t *h, int key, int val) — insert or update; return 0, or -1 if the table is full and key is new.
• int ht_get(const htab_t *h, int key, int *out) — look up key; write the value to *out and return 0 if found, else -1.

Input

A sequence of set/get operations after ht_init. Keys and values are int. Setting an existing key updates its value. Assume no key equals INT_MIN.

Output

Status codes as above; ht_get writes the found value through out. Updating an existing key keeps len unchanged.

Example

init cap=32
set(1,10), set(2,20)   ->   0, 0
get(1)                 ->   out=10, returns 0
get(42)                ->   -1 (missing)
set(1,99)              ->   0 (update)
get(1)                 ->   out=99

Edge cases

• Missing key returns -1.
• Re-setting an existing key overwrites the value without increasing len.
• A new key in a full table returns -1.

Rules

• Use the hash ((unsigned)key * 2654435761u) % cap and linear probing; allocate with malloc/calloc.

Input format

An htab_t pointer plus per-call args (capacity at init, or key/val for set, or key/out for get).

Output format

Status codes: 0 on success, -1 on missing key / full table / alloc failure; found value via out.

Constraints

Hash is ((unsigned)key * 2654435761u) % cap with linear probing; no key equals INT_MIN.

Starter code

#include <stdlib.h>
#include <string.h>
#include <stddef.h>

int  ht_init(htab_t *h, size_t cap){ /* TODO */ return -1; }
void ht_free(htab_t *h){ /* TODO */ }
int  ht_set(htab_t *h, int key, int val){ /* TODO */ return -1; }
int  ht_get(const htab_t *h, int key, int *out){ /* TODO */ return -1; }