perfect_str_hash_compile_time.c

template<typename T>
constexpr bool isprimeloop(T p, T d)
{
        return (d == p) ? true :
                (p % d == 0) ? false : isprimeloop(p, d+1);
}
template<typename T>
constexpr bool isprime(T p)
{
        return (p <= 2) ? true :
                isprimeloop(p, 2);
}

template<typename T>
constexpr T next_prime(T p)
{
        return isprime(p) ? p : next_prime(p+1);
}


int
hash_str(const char *str, const int prime_number, const int size_cap)
{
        int cursor = 0;
        do {
                cursor = ((cursor + *str) * prime_number) % size_cap;
        } while(*(++str) != 0);
        return cursor;
}

constexpr int
hash_str_cursor_ct(const char *str, const int prime_number, const int size_cap, const int cursor)
{
        return (*str == '\0') ? cursor :
                hash_str_cursor_ct(str+1, prime_number, size_cap,
                            ((cursor + *str) * prime_number) % size_cap);
}

constexpr int
hash_str_ct(const char *str, const int prime_number, const int size_cap)
{
        return hash_str_cursor_ct(str, prime_number, size_cap, 0);
}

constexpr bool
collision_detect(const T *arr, const size_t left, T detector)
{
        return (left == 0) ? false :
                (detector == *arr) ? true :
                collision_detect(arr+1, left-1, detector);
}

constexpr int
perfect_hash(const char **str, const int size_cap)
{
        int hash_table[size_cap] = {0};
        bool found = false;
        int hash_val = 1003;
        do {
                for (int i = 0; i < size_cap; i++) {
                        hash_table[i] = hash_str_ct(str[i], hash_val, size_cap);
                        if (collision_detect(hash_table, i+1, hash_table[i])) {
                                hash_val = next_prime(hash_val);
                                break;
                        }
                }
                found = true;
        } while (found);
        return hash_val;
}