359 lines
12 KiB
C
359 lines
12 KiB
C
|
#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
|