#ifndef __UTIL_H_
#define __UTIL_H_

#include <stdio.h>
#include <stddef.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>

typedef enum {
    LEVEL_DEBUG,
    LEVEL_INFO,
    LEVEL_WARN,
    LEVEL_ERROR,
    LEVEL_FATAL,
} loglevel_t;

void volog(loglevel_t level, const char *file, int line, const char *fmt, va_list ap);
void olog(loglevel_t level, const char *file, int line, const char *fmt, ...);
void die(const char *fmt, ...);
void *xmalloc(size_t size);
void *xcalloc(size_t nmemb, size_t size);
void *xrealloc(void *ptr, size_t size);
void xfree(void *ptr);
size_t sanitize2ascii(char *out, const char *inp, size_t outsize);
char *sanitize2ascii_dyn(const char *inp, size_t maxlen);

// wikipedia sample function. read comment in util.c
uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed);

bool hset_charp_cmp(char **lhs, char **rhs);
size_t hset_charp_hash(char **str);

#define min(A, B) \
   ({ __typeof__ (A) _a = (A); \
       __typeof__ (B) _b = (B); \
     _a < _b ? _a : _b; })

#define max(A, B) \
   ({ __typeof__ (A) _a = (A); \
       __typeof__ (B) _b = (B); \
     _a > _b ? _a : _b; })

#define DYNARR_INIT_CAP 16
#define DEQUE_INIT_CAP 16
#define HSET_INIT_CAP 256

#define debug(...) olog(LEVEL_DEBUG, __FILE__, __LINE__, __VA_ARGS__)
#define info(...) olog(LEVEL_INFO,__FILE__, __LINE__, __VA_ARGS__)
#define warn( ...) olog(LEVEL_WARN, __FILE__, __LINE__, __VA_ARGS__)
#define error(...) olog(LEVEL_ERROR, __FILE__, __LINE__, __VA_ARGS__)
#define fatal(...) olog(LEVEL_FATAL, __FILE__, __LINE__, __VA_ARGS__)

#define array_size(ARR) (sizeof(ARR) / sizeof(typeof(*ARR)))

#define dynarr_def(T, NAME) typedef DYNARR(T) NAME; typedef T NAME ## _innertype

#define DYNARR(T) struct { \
        T* data; \
        size_t len, cap; \
    }

#define dynarr_initi(ARR_T) (ARR_T){ .data = xmalloc(sizeof(ARR_T ## _innertype) * DYNARR_INIT_CAP), .len = 0, .cap = DYNARR_INIT_CAP }
#define dynarr_init(ARR_T, ARR) (ARR) = dynarr_initi(ARR_T)
#define dynarr_destroy(ARR) do { \
        if ((ARR).data == NULL) \
            break; \
        xfree((ARR).data); \
        (ARR).data = NULL; \
    } while(0)

#define dynarr_push(ARR, ELEM) do { \
        if ((ARR).len >= (ARR).cap) { \
            (ARR).cap *= 2; \
            (ARR).data = xrealloc((ARR).data, (ARR).cap * sizeof(typeof(ELEM))); \
        } \
        (ARR).data[(ARR).len] = (ELEM); \
        (ARR).len += 1; \
    } while(0)

#define dynarr_get(ARR, INDEX) ({ \
        size_t index = (INDEX); \
        if (index >= (ARR).len)\
            die("dyn array out of bounds access"); \
        &(ARR).data[index]; })

#define dynarr_pop(ARR) ({ \
        if ((ARR).len < 1) \
            die("dyn array empty array pop"); \
        (ARR).data[--(ARR).len]; })

#define dynarr_insert(ARR, INDEX, ELEM) do { \
        size_t index = (INDEX); \
        if (index > (ARR).len) \
            die("dyn array out of bounds insert"); \
        if ((ARR).len >= (ARR).cap) { \
            (ARR).cap *= 2; \
            (ARR).data = xrealloc((ARR).data, (ARR).cap * sizeof(ELEM)); \
        } \
        memmove((ARR).data + index + 1, (ARR).data + index, ((ARR).len - index) * sizeof(ELEM)); \
        (ARR).data[index] = (ELEM); \
        (ARR).len += 1; \
    } while (0)

#define dynarr_remove(ARR, INDEX) do { \
        size_t index = INDEX;\
        if ((index) >= (ARR).len) \
            die("dyn array out of bounds remove"); \
        memmove((ARR).data + index, (ARR).data + index + 1, ((ARR).len - index - 1) * sizeof(*(ARR).data)); \
        (ARR).len -= 1; \
    } while (0)

#define dynarr_extend_fixed(DYN_ARR, FIXED_ARR, NMEMB) do { \
        size_t nmemb = NMEMB; \
        size_t new_cap = (DYN_ARR).cap; \
        while ((DYN_ARR).len + nmemb > new_cap) \
            new_cap *= 2; \
        if (new_cap > (DYN_ARR).cap) { \
            (DYN_ARR).cap = new_cap; \
            (DYN_ARR).data = xrealloc((DYN_ARR).data, (DYN_ARR).cap * sizeof(*(DYN_ARR).data)); \
        } \
        memcpy((DYN_ARR).data + (DYN_ARR).len, FIXED_ARR, nmemb * sizeof(*(DYN_ARR).data)); \
        (DYN_ARR).len += nmemb; \
    } while(0)

#define dynarr_extend_dyn(LHS, RHS) do { \
        size_t new_cap = (LHS).cap; \
        while ((LHS).len + (RHS).len > new_cap) \
            new_cap *= 2; \
        if (new_cap > (LHS).cap) { \
            (LHS).cap = new_cap; \
            (LHS).data = xrealloc((LHS).data, (LHS).cap * sizeof(*(LHS).data)); \
        } \
        memcpy((LHS).data + (LHS).len, (RHS).data, (RHS).len * sizeof(*(LHS).data)); \
        (LHS).len += (RHS).len; \
    } while(0)

dynarr_def(size_t, size_dynarr_t);
dynarr_def(int, int_dynarr_t);
dynarr_def(long, long_dynarr_t);
dynarr_def(long long, long_long_dynarr_t);
dynarr_def(char *, charp_dynarr_t);
dynarr_def(char, char_dynarr_t);
dynarr_def(void *, vp_dynarr_t);

#define DEQUE(T) struct { \
        T* base;\
        size_t cap, front, back, len; \
    } \

#define deque_def(T, NAME) typedef DEQUE(T) NAME; typedef T NAME ## _innertype

//#define deque_init(DEQ_T) { .base = xmalloc(DEQUE_INIT_CAP * sizeof(DEQ_T ## _innertype)), .cap = DEQUE_INIT_CAP, .front = 0, .back = 0, .len = 0 }

#define deque_init(DEQ_T, DEQ) do { (DEQ).base = xmalloc(DEQUE_INIT_CAP * sizeof(DEQ_T ## _innertype)), (DEQ).cap = DEQUE_INIT_CAP, (DEQ).front = 0, (DEQ).back = 0, (DEQ).len = 0; } while (0)

#define deque_destroy(DEQ) do { \
        if ((DEQ).base == NULL)\
            break; \
        xfree((DEQ).base); \
        (DEQ).base = NULL; \
    } while (0)

#define deque_grow(DEQ, NEW_CAP) do { \
        if ((DEQ).cap >= NEW_CAP) \
            continue; \
        size_t new_cap = NEW_CAP, size = sizeof(typeof(*(DEQ).base)); \
        typeof((DEQ).base) new_base = xmalloc(new_cap * size); \
        if ((DEQ).len > 0 && (DEQ).front >= (DEQ).back) { \
            size_t end_len = (DEQ).cap - (DEQ).front; \
            memcpy(new_base, (DEQ).base + (DEQ).front, end_len * size);\
            memcpy(new_base + end_len, (DEQ).base, (DEQ).back * size); \
        } \
        else { \
            memcpy(new_base, (DEQ).base + (DEQ).front, (DEQ).len * size); \
        } \
        xfree((DEQ).base); \
        (DEQ).base = new_base, (DEQ).cap = new_cap, (DEQ).front = 0, (DEQ).back = (DEQ).len; \
    } while (0)

#define deque_push_back(DEQ, ELEM) do { \
        if ((DEQ).len > 0 && (DEQ).back == (DEQ).front) \
            deque_grow(DEQ, (DEQ).cap * 2); \
        (DEQ).base[(DEQ).back] = (ELEM); \
        (DEQ).back = ((DEQ).back + 1) % (DEQ).cap; \
        (DEQ).len += 1; \
    } while (0)

#define deque_pop_back(DEQ) ({ \
        if ((DEQ).len == 0) \
            die("deque empty pop back"); \
        (DEQ).back = (DEQ).back == 0 ? (DEQ).cap - 1 : (DEQ).back - 1; \
        (DEQ).len -= 1;\
        (DEQ).base[(DEQ).back]; \
    })

#define deque_push_front(DEQ, ELEM) do { \
        if ((DEQ).len > 0 && (DEQ).back == (DEQ).front) \
            deque_grow(DEQ, (DEQ).cap * 2); \
        (DEQ).front = (DEQ).front == 0 ? (DEQ).cap - 1 : (DEQ).front - 1; \
        (DEQ).len += 1; \
        (DEQ).base[(DEQ).front] = (ELEM); \
    } while (0)

#define deque_pop_front(DEQ) ({ \
        if ((DEQ).len == 0) \
            die("deque empty pop front"); \
        size_t old_front = (DEQ).front; \
        (DEQ).front = ((DEQ).front + 1) % (DEQ).cap; \
        (DEQ).len -= 1;\
        (DEQ).base[old_front]; \
    })

#define deque_get(DEQ, INDEX) ({ \
        size_t index = (INDEX); \
        if (index >= (DEQ).len) \
            die("deque out of bounds access"); \
        &(DEQ).base[((DEQ).front + index) % (DEQ).cap]; \
    })

#define deque_clone(DST, SRC) ({ \
        memcpy(&(DST), &(SRC), sizeof(DST)); \
        (DST).base = xmalloc((SRC).len * sizeof(typeof(*(DST).base))); \
        memcpy((DST).base, (SRC).base, (SRC).len * sizeof(typeof(*(DST).base))); \
    })

deque_def(int, int_deque_t);
deque_def(size_t, size_deque_t);
deque_def(long, long_deque_t);
deque_def(long long, longlong_deque_t);
deque_def(char, char_deque_t);
deque_def(char *, charp_deque_t);
deque_def(void *, voidp_deque_t);

size_t parityhash(const void *data, size_t ndata);

#define HSET_BUCKET(T, NAME) struct NAME ## _struct { \
        struct NAME ## _struct *next; \
        T data; \
    } 

#define HSET(T, BUCKET_T) struct { \
        BUCKET_T** buckets; \
        size_t nbuckets, len; \
        size_t (*algo)(T*); \
        bool (*cmp)(T*, T*); \
    }

#define hset_def(T, NAME) typedef HSET_BUCKET(T, NAME ## _bucket) NAME ## _bucket; \
    typedef HSET(T, NAME ## _bucket) NAME; \
    typedef T NAME ## _innertype

#define hset_initi(HSET_T, ALGO, CMP) (HSET_T) { \
        .buckets = xcalloc(HSET_INIT_CAP, sizeof(HSET_T ## _bucket *)), \
        .nbuckets = HSET_INIT_CAP, .len = 0, .algo = (ALGO), .cmp = (CMP), \
    }

#define hset_init(HSET_T, HSET, ALGO, CMP) (HSET) = hset_initi(HSET_T, ALGO, CMP)

#define hset_destroy(HSET) do { \
        if ((HSET).buckets == NULL) \
            break; \
        for (size_t i = 0; i < (HSET).nbuckets; i++) { \
            if ((HSET).buckets[i] == NULL) \
                continue; \
            typeof(*(HSET).buckets) cur = (HSET).buckets[i], next;\
            for (; cur != NULL; cur = next) { \
                next = cur->next; \
                xfree(cur); \
            } \
        } \
        xfree((HSET).buckets); \
        (HSET).buckets = NULL; \
    } while (0)

// c has reminded me of how good i had it with rust
#define hset_iter(HSET, STATE) ({ \
        typeof(&(HSET).buckets[0]->data) ret;\
        do { \
            if ((STATE) == NULL) {\
                (STATE) = xmalloc(2 * sizeof(void*)); \
                ((void**) (STATE))[0] = (HSET).buckets; \
                ((void**) (STATE))[1] = NULL; \
            } \
            typeof(&(HSET).buckets) entryptr = &((typeof(&(HSET).buckets)) (STATE))[0];\
            typeof((HSET).buckets) bucketptr = &((typeof((HSET).buckets)) (STATE))[1];\
            if (*bucketptr != NULL && (*bucketptr)->next != NULL) { \
                *bucketptr = (*bucketptr)->next; \
                ret = &(*bucketptr)->data; \
                break; \
            } \
            *bucketptr = NULL; \
            for (; *entryptr < (HSET).buckets + (HSET).nbuckets; (*entryptr)++) \
                if (**entryptr != NULL) \
                    break; \
            if (*entryptr < (HSET).buckets + (HSET).nbuckets) { \
                *bucketptr = **entryptr; \
                (*entryptr)++; \
                ret = &(*bucketptr)->data; \
            } else { \
                xfree((STATE)); \
                (STATE) = NULL; \
                ret = NULL; \
            } \
        } while (0); \
        ret; \
    })

#define hset_add(HSET, ELEM) ({ \
        size_t ind = (HSET).algo(&(ELEM)) % (HSET).nbuckets; \
        bool ret = false; \
        if ((HSET).buckets[ind] == NULL) {\
            (HSET).buckets[ind] = xmalloc(sizeof(typeof(**(HSET).buckets))); \
            (HSET).buckets[ind]->data = ELEM; \
            (HSET).buckets[ind]->next = NULL; \
        } \
        else { \
            typeof(*(HSET).buckets) cur, prev; \
            for (cur = (HSET).buckets[ind]; !ret && cur != NULL; prev = cur, cur = cur->next) { \
                if ((HSET).cmp == NULL) { \
                    if(cur->data == (ELEM)) \
                        ret = true; \
                } \
                else if ((*(HSET).cmp)(&cur->data, &(ELEM))) { \
                    ret = true; \
                } \
            } \
            if (!ret) { \
                prev->next = xmalloc(sizeof(typeof(**(HSET).buckets))); \
                prev->next->data = ELEM; \
                prev->next->next = NULL; \
            } \
        } \
        ret; \
    })

#define hset_find(HSET, ELEM) ({ \
        size_t ind = (HSET).algo(&(ELEM)) % (HSET).nbuckets; \
        bool ret = false; \
        typeof(*(HSET).buckets) cur; \
        for (cur = (HSET).buckets[ind]; !ret && cur != NULL; cur = cur->next) { \
            if ((HSET).cmp == NULL) { \
                if(cur->data == (ELEM)) \
                    ret = true; \
            } \
            else if ((*(HSET).cmp)(&cur->data, &(ELEM))) { \
                ret = true; \
            } \
        } \
        ret; \
    })

hset_def(int, int_hset_t);
hset_def(char *, charp_hset_t);

typedef unsigned char byte;

#endif