A simple, generic, dynamic hashset implementation with linear probing in C.

hashset.h

#ifndef SET_H
#define SET_H

#include <stdint.h>  // uint8_t, uint32_t
#include <stdlib.h>  // size_t, calloc, free
#include <stdbool.h> // bool
#include <assert.h>  // assert
#include <stdio.h>   // printf

#define TOKENPASTE(X, Y)  X ## Y
#define INDENT(DEPTH)     printf("%*c", DEPTH * 2, ' ')

#define SET_ELEM(SET)     TOKENPASTE(SET, Elem)
#define SET_CONS(SET)     TOKENPASTE(SET, Cons)
#define SET_CONTAINS(SET) TOKENPASTE(SET, Contains)
#define SET_EXPAND(SET)   TOKENPASTE(SET, Expand)
#define SET_INSERT(SET)   TOKENPASTE(SET, Insert)
#define SET_EQUALS(SET)   TOKENPASTE(SET, Equals)
#define SET_DEBUG(SET)    TOKENPASTE(SET, Debug)
#define SET_DES(SET)      TOKENPASTE(SET, Des)

#define SET_ELEM_UNUSED   0
#define SET_ELEM_OCCUPIED 1

#define SET_GEN_DECL(SET, KEY)                                                                                         \
                                                                                                                       \
    struct SET_ELEM(SET) {                                                                                             \
        uint8_t type;                                                                                                  \
        KEY key;                                                                                                       \
    };                                                                                                                 \
                                                                                                                       \
    struct SET {                                                                                                       \
        struct SET_ELEM(SET) *elems;                                                                                   \
        size_t capacity;                                                                                               \
        size_t len;                                                                                                    \
    };                                                                                                                 \
                                                                                                                       \
    struct SET *SET_CONS(SET)(struct SET *set, size_t capacity);                                                       \
                                                                                                                       \
    bool SET_CONTAINS(SET)(const struct SET *set, KEY key);                                                            \
                                                                                                                       \
    void SET_EXPAND(SET)(struct SET *set);                                                                             \
                                                                                                                       \
    void SET_INSERT(SET)(struct SET *set, KEY key);                                                                    \
                                                                                                                       \
    bool SET_EQUALS(SET)(const struct SET *a, const struct SET *b);                                                    \
                                                                                                                       \
    void SET_DEBUG(SET)(const struct SET *set, uint32_t depth);                                                        \
                                                                                                                       \
    struct SET *SET_DES(SET)(struct SET *set);

#define SET_GEN_DEF(SET, KEY, KEY_HASH, KEY_EQUALS, KEY_DEBUG, KEY_DES)                                                \
                                                                                                                       \
    struct SET *SET_CONS(SET)(struct SET *set, size_t capacity) {                                                      \
        set->elems = (struct SET_ELEM(SET) *)calloc(capacity, sizeof(struct SET_ELEM(SET)));                           \
        set->capacity = capacity;                                                                                      \
        set->len = 0;                                                                                                  \
        return set;                                                                                                    \
    }                                                                                                                  \
                                                                                                                       \
    bool SET_CONTAINS(SET)(const struct SET *set, KEY key) {                                                           \
        size_t hash, i;                                                                                                \
        hash = (KEY_HASH(key) % set->capacity) - 1;                                                                    \
        for (i = 0; i < set->capacity; i++) {                                                                          \
            hash = (hash + 1) % set->capacity;                                                                         \
            if (set->elems[hash].type == SET_ELEM_OCCUPIED && KEY_EQUALS(set->elems[hash].key, key)) {                 \
                return true;                                                                                           \
            } else if (set->elems[hash].type == SET_ELEM_UNUSED) {                                                     \
                return false;                                                                                          \
            }                                                                                                          \
        }                                                                                                              \
        return false;                                                                                                  \
    }                                                                                                                  \
                                                                                                                       \
    void SET_EXPAND(SET)(struct SET *set) {                                                                            \
        struct SET_ELEM(SET) *elems;                                                                                   \
        size_t i, j, hash;                                                                                             \
        elems = (struct SET_ELEM(SET) *)calloc(set->capacity * 2, sizeof(struct SET_ELEM(SET)));                       \
        for (i = 0; i < set->capacity; i++) {                                                                          \
            if (set->elems[i].type == SET_ELEM_OCCUPIED) {                                                             \
                hash = (KEY_HASH(set->elems[i].key) % (set->capacity * 2)) - 1;                                        \
                for (j = 0; j < set->capacity * 2; j++) {                                                              \
                    hash = (hash + 1) % (set->capacity * 2);                                                           \
                    if (elems[hash].type == SET_ELEM_UNUSED) {                                                         \
                        elems[hash].type = SET_ELEM_OCCUPIED;                                                          \
                        elems[hash].key = set->elems[i].key;                                                           \
                        break;                                                                                         \
                    }                                                                                                  \
                }                                                                                                      \
                assert((j < set->capacity * 2) && "key not inserted");                                                 \
            }                                                                                                          \
        }                                                                                                              \
        free(set->elems);                                                                                              \
        set->elems = elems;                                                                                            \
        set->capacity *= 2;                                                                                            \
    }                                                                                                                  \
                                                                                                                       \
    void SET_INSERT(SET)(struct SET *set, KEY key) {                                                                   \
        size_t hash, i;                                                                                                \
        hash = (KEY_HASH(key) % set->capacity) - 1;                                                                    \
        for (i = 0; i < set->capacity; i++) {                                                                          \
            hash = (hash + 1) % set->capacity;                                                                         \
            if (set->elems[hash].type == SET_ELEM_OCCUPIED && KEY_EQUALS(set->elems[hash].key, key)) {                 \
                assert(false && "key exists");                                                                         \
            } else if (set->elems[hash].type == SET_ELEM_UNUSED) {                                                     \
                set->elems[hash].type = SET_ELEM_OCCUPIED;                                                             \
                set->elems[hash].key = key;                                                                            \
                set->len++;                                                                                            \
                break;                                                                                                 \
            }                                                                                                          \
        }                                                                                                              \
        assert((i < set->capacity) && "key not inserted");                                                             \
        if (3 * set->len > 2 * set->capacity) {                                                                        \
            SET_EXPAND(SET)(set);                                                                                      \
        }                                                                                                              \
    }                                                                                                                  \
                                                                                                                       \
    bool SET_EQUALS(SET)(const struct SET *a, const struct SET *b) {                                                   \
        size_t i;                                                                                                      \
        if (a->len != b->len) {                                                                                        \
            return false;                                                                                              \
        }                                                                                                              \
        for (i = 0; i < a->capacity; a++) {                                                                            \
            if (a->elems[i].type == SET_ELEM_OCCUPIED) {                                                               \
                if (!SET_CONTAINS(SET)(b, a->elems[i].key)) {                                                          \
                    return false;                                                                                      \
                }                                                                                                      \
            }                                                                                                          \
        }                                                                                                              \
        return true;                                                                                                   \
    }                                                                                                                  \
                                                                                                                       \
    void SET_DEBUG(SET)(const struct SET *set, uint32_t depth) {                                                       \
        size_t i;                                                                                                      \
        printf(#SET " {\n");                                                                                           \
        for (i = 0; i < set->capacity; i++) {                                                                          \
            if (set->elems[i].type == SET_ELEM_OCCUPIED) {                                                             \
                INDENT(depth); printf("  "); KEY_DEBUG(set->elems[i].key, depth + 1); printf(",\n");                   \
            }                                                                                                          \
        }                                                                                                              \
        INDENT(depth); printf("}");                                                                                    \
    }                                                                                                                  \
                                                                                                                       \
    struct SET *SET_DES(SET)(struct SET *set) {                                                                        \
        size_t i;                                                                                                      \
        for (i = 0; i < set->capacity; i++) {                                                                          \
            if (set->elems[i].type == SET_ELEM_OCCUPIED) {                                                             \
                KEY_DES(set->elems[i].key);                                                                            \
            }                                                                                                          \
        }                                                                                                              \
        free(set->elems);                                                                                              \
        set->capacity = 0;                                                                                             \
        set->len = 0;                                                                                                  \
        return set;                                                                                                    \
    }

#endif