Compiler Explorer

Source code

#define DECLARE_ITERATOR(identifier, type) CONTAINER_GENERATOR_ITERATOR(identifier, type)
#define DEFINE_ITERATOR(identifier, type) CONTAINER_GENERATOR_ITERATOR(identifier, type, with_defs)
#define EXPAND_ITERATOR(identifier) iterator_##identifier##_t
#define ITERATOR(identifier) EXPAND_ITERATOR(identifier)
#define ITERATOR_ACTIVE(iterator) ((iterator).container != nullptr)
#define ITERATOR_GET(iterator) (iterator).element.value
#define ITERATOR_NEXT(iterator) ((iterator).container == nullptr || (iterator).next == nullptr ? false : (iterator).next(&(iterator)))

#define CONTAINER_GENERATOR_ITERATOR(identifier, type, ...)				\
	typedef struct iterator_##identifier ITERATOR(identifier);			\
	typedef bool iterator_##identifier##_next_t(ITERATOR(identifier) *iterator);	\
											\
	__VA_OPT__(									\
		struct iterator_##identifier {						\
			void *container;						\
			union state {							\
				void *ptr;						\
				long value;						\
			} state;							\
			union identifier##_element {					\
				void *address;						\
				type value;						\
			} element;							\
			iterator_##identifier##_next_t *next;				\
		};									\
	)										\
											\
	struct iterator_##identifier

DEFINE_ITERATOR(void, void *);

#define DECLARE_PAIR(first_identifier, second_identifier, first_type, second_type) CONTAINER_GENERATOR_PAIR(first_identifier, second_identifier, first_type, second_type)
#define DEFINE_PAIR(first_identifier, second_identifier, first_type, second_type) CONTAINER_GENERATOR_PAIR(first_identifier, second_identifier, first_type, second_type, with_defs)
#define EXPAND_PAIR(first_identifier, second_identifier) pair_##first_identifier##_##second_identifier##_t
#define PAIR(first_identifier, second_identifier) EXPAND_PAIR(first_identifier, second_identifier)
#define PAIR_FIRST(pair) (pair).value.first
#define PAIR_SECOND(pair) (pair).value.second

#define CONTAINER_GENERATOR_PAIR(first_identifier, second_identifier, first_type, second_type, ...)		\
	typedef union pair_##first_identifier##_##second_identifier PAIR(first_identifier, second_identifier);	\
														\
	__VA_OPT__(												\
		union pair_##first_identifier##_##second_identifier {						\
			struct void_value_##first_identifier##_##second_identifier {				\
				void *first;									\
				void *second;									\
			} void_value;										\
			struct value_##first_identifier##_##second_identifier {					\
				first_type first;								\
				second_type second;								\
			} value;										\
		};												\
	)													\
														\
	union pair_##first_identifier##_##second_identifier

DEFINE_PAIR(void, void, void *, void *);

#include <stddef.h>
#include <stdint.h>

typedef uint64_t hash_64_t(const void *data, size_t size);

constexpr size_t HASH_NT = SIZE_MAX;
constexpr size_t HASH_OBJECT = 0;

extern hash_64_t *const HASH_DEFAULT;

extern hash_64_t fnv1a_64;
extern hash_64_t sip_64;

#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#ifndef C_ROUNDS
#define C_ROUNDS 2
#endif
#ifndef D_ROUNDS
#define D_ROUNDS 4
#endif

#define ROTATE(x, b) (((x) << (b)) | ((x) >> (UINT64_WIDTH - (b))))

#define SIP_ROUND(v0, v1, v2, v3) {	\
	v0 += v1;			\
	v2 += v3;			\
	v1 = ROTATE(v1, 13) ^ v0;	\
	v3 = ROTATE(v3, 16) ^ v2;	\
	v0 = ROTATE(v0, 32);		\
	v0 += v3;			\
	v2 += v1;			\
	v1 = ROTATE(v1, 17) ^ v2;	\
	v3 = ROTATE(v3, 21) ^ v0;	\
	v2 = ROTATE(v2, 32);		\
}

constexpr uint64_t FNV_64_BASIS = UINT64_C(14695981039346656037);
constexpr uint64_t FNV_64_PRIME = 1099511628211;
constexpr char KEY[/*16*/] = "Dark Forces RPG!";

static_assert(sizeof(KEY) == 17);

hash_64_t *const HASH_DEFAULT;

static uint64_t fnv1a_64_nts(const char *str);

hash_64_t *const HASH_DEFAULT = &sip_64;

hash_64_t fnv1a_64;
uint64_t fnv1a_64(const void *data, size_t size) {
	if (data == nullptr)
		return 0;
	else if (size == HASH_NT)
		return fnv1a_64_nts(data);
	else if (size == 0)
		return 0;
	uint64_t hash = FNV_64_BASIS;
	for (int i = 0; i < size; i++) {
		hash ^= ((unsigned char *)data)[i++];
		hash *= FNV_64_PRIME;
	}
	return hash;
}

static uint64_t fnv1a_64_nts(const char *str) {
	uint64_t hash = FNV_64_BASIS;
	int i = 0;
	while (str[i] != '\0') {
		hash ^= str[i++];
		hash *= FNV_64_PRIME;
	}
	return hash;
}

hash_64_t sip_64;
uint64_t sip_64(const void *data, size_t size) {
	if (data == nullptr)
		return 0;
	else if (size == HASH_NT)
		size = strlen(data);
	if (size == 0)
		return 0;
	uint64_t key_lower = ((uint64_t *)KEY)[0];
	uint64_t key_upper = ((uint64_t *)KEY)[1];
	uint64_t v0 = key_lower ^ 0x736f6d6570736575;
	uint64_t v1 = key_upper ^ 0x646f72616e646f6d;
	uint64_t v2 = key_lower ^ 0x6c7967656e657261;
	uint64_t v3 = key_upper ^ 0x7465646279746573;
	const unsigned char *pos = data;
	for (int i = 0; i < size / sizeof(uint64_t); i++) {
		uint64_t next_bytes = 0;
		for (int j = 0; j < sizeof(uint64_t); j++)
			next_bytes |= ((uint64_t)pos[j]) << (j * UINT8_WIDTH);
		v3 ^= next_bytes;
		for (int j = 0; j < C_ROUNDS; j++)
			SIP_ROUND(v0, v1, v2, v3);
		v0 ^= next_bytes;
		pos += sizeof(uint64_t);
	}
	uint64_t last_bytes = size << (SIZE_WIDTH - UINT8_WIDTH);
	for (int i = 0; i < size % sizeof(uint64_t); i++)
		last_bytes |= ((uint64_t)pos[i]) << (i * UINT8_WIDTH);
	v3 ^= last_bytes;
	for (int i = 0; i < C_ROUNDS; i++)
		SIP_ROUND(v0, v1, v2, v3);
	v0 ^= last_bytes;
	v2 ^= UINT8_MAX;
	for (int i = 0; i < D_ROUNDS; i++)
		SIP_ROUND(v0, v1, v2, v3);
	return v0 ^ v1 ^ v2 ^ v3;
}

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

#define DECLARE_LIST(identifier, type) CONTAINER_GENERATOR_LIST(identifier, type)
#define DEFINE_LIST(identifier, type) CONTAINER_GENERATOR_LIST(identifier, type, with_defs)
#define EXPAND_LIST(identifier) list_##identifier##_t
#define EXPAND_LIST_NEW(identifier) list_##identifier##_new()
#define LIST(identifier) EXPAND_LIST(identifier)
#define LIST_APPEND(list, element) ((list) == nullptr ? false : (list)->vtable->append(list, element))
#define LIST_DESTROY(list) ((list) == nullptr ? (void)0 : (list)->vtable->destroy(list))
#define LIST_GET_ITERATOR(list) ((list) == nullptr ? ((typeof(list->associated_types->iterator)){.container = nullptr}) : (list)->vtable->get_iterator(list))
#define LIST_NEW(identifier) EXPAND_LIST_NEW(identifier)
#define LIST_REMOVE(list, iterator) ((list) == nullptr ? false : (list)->vtable->remove(list, &iterator))

#define CONTAINER_GENERATOR_LIST(identifier, type, ...)									\
	typedef struct list_##identifier *LIST(identifier);								\
	struct list_##identifier##_vtable;										\
															\
	DECLARE_ITERATOR(identifier, type);										\
															\
	typedef bool list_##identifier##_append_t(LIST(identifier) list, type element);					\
	typedef void list_##identifier##_destroy_t(LIST(identifier) list);						\
	typedef ITERATOR(identifier) list_##identifier##_get_iterator_t(LIST(identifier) list);				\
	typedef bool list_##identifier##_remove_t(LIST(identifier) list, ITERATOR(identifier) *iterator);		\
															\
	__VA_OPT__(													\
		DEFINE_ITERATOR(identifier, type);									\
															\
		struct list_##identifier {										\
			const struct list_##identifier##_vtable *vtable;						\
			LIST(void) list;										\
			struct {											\
				ITERATOR(identifier) iterator;								\
			} *associated_types;										\
		};													\
															\
		struct list_##identifier##_vtable {									\
			list_##identifier##_append_t *append;								\
			list_##identifier##_destroy_t *destroy;								\
			list_##identifier##_get_iterator_t *get_iterator;						\
			list_##identifier##_remove_t *remove;								\
		};													\
															\
		static const struct list_##identifier##_vtable LIST_##identifier##_VTABLE;				\
	)														\
															\
	static iterator_##identifier##_next_t list_iterator_##identifier##_next;					\
	[[maybe_unused]] static inline list_##identifier##_append_t list_##identifier##_append;				\
	[[maybe_unused]] static inline list_##identifier##_destroy_t list_##identifier##_destroy;			\
	[[maybe_unused]] static inline list_##identifier##_get_iterator_t list_##identifier##_get_iterator;		\
	[[maybe_unused]] static inline LIST(identifier) list_##identifier##_new();					\
	[[maybe_unused]] static inline list_##identifier##_remove_t list_##identifier##_remove;				\
															\
	__VA_OPT__(													\
		static const struct list_##identifier##_vtable LIST_##identifier##_VTABLE = {				\
			.append = &list_##identifier##_append,								\
			.destroy = &list_##identifier##_destroy,							\
			.get_iterator = &list_##identifier##_get_iterator,						\
			.remove = &list_##identifier##_remove								\
		};													\
															\
		static iterator_##identifier##_next_t list_iterator_##identifier##_next;				\
		static bool list_iterator_##identifier##_next(ITERATOR(identifier) *iterator) {				\
			if (!list_iterator_void_next((ITERATOR(void) *)iterator))					\
				return false;										\
			else if (sizeof(type) <= sizeof(void *))							\
				memcpy(&iterator->element.value, &iterator->element.address, sizeof(type));		\
			else												\
				memcpy(&iterator->element.value, iterator->element.address, sizeof(type));		\
			return true;											\
		}													\
															\
		static inline list_##identifier##_append_t list_##identifier##_append;					\
		static inline bool list_##identifier##_append(LIST(identifier) list, type element) {			\
			void *copy;											\
			if (sizeof(type) <= sizeof(void *)) {								\
				memcpy(&copy, &element, sizeof(type));							\
				return list_void_append(list->list, copy);						\
			} else {											\
				copy = malloc(sizeof(type));								\
				if (copy == nullptr)									\
					return false;									\
				memcpy(copy, &element, sizeof(type));							\
				if (list_void_append(list->list, copy))							\
					return true;									\
				else {											\
					free(copy);									\
					return false;									\
				}											\
			}												\
		}													\
															\
		static inline list_##identifier##_destroy_t list_##identifier##_destroy;				\
		static inline void list_##identifier##_destroy(LIST(identifier) list) {					\
			if (sizeof(type) <= sizeof(void *))								\
				list_void_destroy(list->list);								\
			else												\
				list_void_destroy_free_elements(list->list);						\
		}													\
															\
		static inline list_##identifier##_get_iterator_t list_##identifier##_get_iterator;			\
		static inline ITERATOR(identifier) list_##identifier##_get_iterator(LIST(identifier) list) {		\
			ITERATOR(void) iterator = list_void_get_iterator(list->list);					\
			ITERATOR(identifier) ret = {									\
				.container = iterator.container,							\
				.next = &list_iterator_##identifier##_next,						\
				.state.ptr = iterator.state.ptr								\
			};												\
			if (sizeof(type) <= sizeof(void *))								\
				memcpy(&ret.element.value, &iterator.element.address, sizeof(type));			\
			else												\
				memcpy(&ret.element.value, iterator.element.address, sizeof(type));			\
			return ret;											\
		}													\
															\
		static inline LIST(identifier) list_##identifier##_new() {						\
			LIST(identifier) ret = malloc(sizeof(*ret));							\
			if (ret == nullptr)										\
				return nullptr;										\
			ret->list = list_void_new();									\
			if (ret->list == nullptr) {									\
				free(ret);										\
				return nullptr;										\
			}												\
			ret->vtable = &LIST_##identifier##_VTABLE;							\
			return ret;											\
		}													\
															\
		static inline list_##identifier##_remove_t list_##identifier##_remove;					\
		static inline bool list_##identifier##_remove(LIST(identifier) list, ITERATOR(identifier) *iterator) {	\
			if (sizeof(type) <= sizeof(void *))								\
				return list_void_remove(list->list, (ITERATOR(void) *)iterator);			\
			else												\
				return list_void_remove_and_free(list->list, (ITERATOR(void) *)iterator);		\
		}													\
	)														\
															\
	struct list_##identifier

typedef struct list_void *LIST(void);
struct list_void_vtable;

typedef bool list_void_append_t(LIST(void) list, void *element);
typedef void list_void_destroy_t(LIST(void) list);
typedef ITERATOR(void) list_void_get_iterator_t(LIST(void) list);
typedef bool list_void_remove_t(LIST(void) list, ITERATOR(void) *iterator);

struct list_void {
	const struct list_void_vtable *vtable;
	struct {
		ITERATOR(void) iterator;
	} *associated_types;
};

struct list_void_vtable {
	list_void_append_t *append;
	list_void_destroy_t *destroy;
	list_void_get_iterator_t *get_iterator;
	list_void_remove_t *remove;
};

extern iterator_void_next_t list_iterator_void_next;
extern list_void_append_t list_void_append;
extern list_void_destroy_t list_void_destroy;
extern list_void_destroy_t list_void_destroy_free_elements;
extern list_void_get_iterator_t list_void_get_iterator;
extern LIST(void) list_void_new();
extern list_void_remove_t list_void_remove;
extern list_void_remove_t list_void_remove_and_free;

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

#define DECLARE_MAP(key_identifier, value_identifier, key_type, value_type) CONTAINER_GENERATOR_MAP(key_identifier, value_identifier, key_type, value_type)
#define DEFINE_MAP(key_identifier, value_identifier, key_type, value_type) CONTAINER_GENERATOR_MAP(key_identifier, value_identifier, key_type, value_type, with_defs)
#define EXPAND_MAP(key_identifier, value_identifier) map_##key_identifier##_##value_identifier##_t
#define MAP(key_identifier, value_identifier) EXPAND_MAP(key_identifier, value_identifier)
#define MAP_DESTROY(map) ((map) == nullptr ? (void)0 : (map)->vtable->destroy(map))
#define MAP_GET(map, key) ((map) == nullptr ? (typeof((map)->vtable->get((map), (key)))){0} : (map)->vtable->get((map), (key)))
#define MAP_GET_ENTRY_ITERATOR(map) ((map) == nullptr ? ((typeof((map)->associated_types->entry_iterator)){.container = nullptr}) : (map)->vtable->get_entry_iterator(map))
#define MAP_GET_KEY_ITERATOR(map) ((map) == nullptr ? ((typeof((map)->associated_types->key_iterator)){.container = nullptr}) : (map)->vtable->get_key_iterator(map))
#define MAP_GET_VALUE_ITERATOR(map) ((map) == nullptr ? ((typeof((map)->associated_types->value_iterator)){.container = nullptr}) : (map)->vtable->get_value_iterator(map))
#define MAP_INSERT(map, key, element) ((map) == nullptr ? false : (map)->vtable->insert((map), (key), (element)))
#define MAP_NEW(key_identifier, value_identifier, key_length, ...) MAP_NEW_REAL##__VA_OPT__(_WITH_HASH_FN)(key_identifier, value_identifier, key_length __VA_OPT__(, __VA_ARGS__))
#define MAP_NEW_REAL(key_identifier, value_identifier, key_length) map_##key_identifier##_##value_identifier##_new(HASH_DEFAULT, key_length)
#define MAP_NEW_REAL_WITH_HASH_FN(key_identifier, value_identifier, hash_fn, key_length) map_##key_identifier##_##value_identifier##_new(hash_fn, key_length)
#define MAP_REMOVE(map, key) ((map) == nullptr ? (typeof((map)->vtable->remove((map), (key)))){0} : (map)->vtable->remove((map), (key)))
#define MAP_SIZE(map) ((map) == nullptr ? 0 : (map)->vtable->size(map))

#define CONTAINER_GENERATOR_MAP(key_identifier, value_identifier, key_type, value_type, ...)													\
	typedef struct map_##key_identifier##_##value_identifier *MAP(key_identifier, value_identifier);											\
	struct map_##key_identifier##_##value_identifier##_vtable;																\
																								\
	DECLARE_PAIR(key_identifier, value_identifier, key_type, value_type);															\
	DECLARE_ITERATOR(PAIR(key_identifier, value_identifier), PAIR(key_identifier, value_identifier));											\
	DECLARE_ITERATOR(key_identifier, key_type);																		\
	DECLARE_ITERATOR(value_identifier, value_type);																		\
																								\
	typedef void map_##key_identifier##_##value_identifier##_destroy_t(MAP(key_identifier, value_identifier) map);										\
	typedef ITERATOR(PAIR(key_identifier, value_identifier)) map_##key_identifier##_##value_identifier##_get_entry_iterator_t(MAP(key_identifier, value_identifier) map);			\
	typedef ITERATOR(key_identifier) map_##key_identifier##_##value_identifier##_get_key_iterator_t(MAP(key_identifier, value_identifier) map);						\
	typedef ITERATOR(value_identifier) map_##key_identifier##_##value_identifier##_get_value_iterator_t(MAP(key_identifier, value_identifier) map);						\
	typedef value_type map_##key_identifier##_##value_identifier##_get_t(MAP(key_identifier, value_identifier) map, key_type key);								\
	typedef bool map_##key_identifier##_##value_identifier##_insert_t(MAP(key_identifier, value_identifier) map, key_type key, value_type element);						\
	typedef value_type map_##key_identifier##_##value_identifier##_remove_t(MAP(key_identifier, value_identifier) map, key_type key);							\
	typedef int map_##key_identifier##_##value_identifier##_size_t(MAP(key_identifier, value_identifier) map);										\
																								\
	__VA_OPT__(																						\
		DEFINE_PAIR(key_identifier, value_identifier, key_type, value_type);														\
																								\
		DEFINE_ITERATOR(PAIR(key_identifier, value_identifier), PAIR(key_identifier, value_identifier));										\
		DEFINE_ITERATOR(key_identifier, key_type);																	\
		DEFINE_ITERATOR(value_identifier, value_type);																	\
																								\
		struct map_##key_identifier##_##value_identifier {																\
			const struct map_##key_identifier##_##value_identifier##_vtable *vtable;												\
			MAP(void, void) map;																			\
			struct {																				\
				ITERATOR(PAIR(key_identifier, value_identifier)) entry_iterator;												\
				ITERATOR(key_identifier) key_iterator;																\
				ITERATOR(value_identifier) value_iterator;															\
			} *associated_types;																			\
		};																						\
																								\
		struct map_##key_identifier##_##value_identifier##_vtable {															\
			map_##key_identifier##_##value_identifier##_destroy_t *destroy;														\
			map_##key_identifier##_##value_identifier##_get_t *get;															\
			map_##key_identifier##_##value_identifier##_get_entry_iterator_t *get_entry_iterator;											\
			map_##key_identifier##_##value_identifier##_get_key_iterator_t *get_key_iterator;											\
			map_##key_identifier##_##value_identifier##_get_value_iterator_t *get_value_iterator;											\
			map_##key_identifier##_##value_identifier##_insert_t *insert;														\
			map_##key_identifier##_##value_identifier##_remove_t *remove;														\
			map_##key_identifier##_##value_identifier##_size_t *size;														\
		};																						\
																								\
		static const struct map_##key_identifier##_##value_identifier##_vtable MAP_##key_identifier##_##value_identifier##_VTABLE;							\
	)																							\
																								\
	static iterator_pair_##key_identifier##_##value_identifier##_t_next_t map_entry_iterator_pair_##key_identifier##_##value_identifier##_t_next;						\
	static iterator_##key_identifier##_next_t map_key_iterator_##key_identifier##_##value_identifier##_next;										\
	static iterator_##value_identifier##_next_t map_value_iterator_##key_identifier##_##value_identifier##_next;										\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_destroy_t map_##key_identifier##_##value_identifier##_destroy;						\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_get_t map_##key_identifier##_##value_identifier##_get;							\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_get_entry_iterator_t map_##key_identifier##_##value_identifier##_get_entry_iterator;				\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_get_key_iterator_t map_##key_identifier##_##value_identifier##_get_key_iterator;				\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_get_value_iterator_t map_##key_identifier##_##value_identifier##_get_value_iterator;				\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_insert_t map_##key_identifier##_##value_identifier##_insert;							\
	[[maybe_unused]] static inline MAP(key_identifier, value_identifier) map_##key_identifier##_##value_identifier##_new(hash_64_t *const hash_fn, size_t key_length);			\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_remove_t map_##key_identifier##_##value_identifier##_remove;							\
	[[maybe_unused]] static inline map_##key_identifier##_##value_identifier##_size_t map_##key_identifier##_##value_identifier##_size;							\
																								\
	__VA_OPT__(																						\
		static const struct map_##key_identifier##_##value_identifier##_vtable MAP_##key_identifier##_##value_identifier##_VTABLE = {							\
			.destroy = &map_##key_identifier##_##value_identifier##_destroy,													\
			.get = &map_##key_identifier##_##value_identifier##_get,														\
			.get_entry_iterator = &map_##key_identifier##_##value_identifier##_get_entry_iterator,											\
			.get_key_iterator = &map_##key_identifier##_##value_identifier##_get_key_iterator,											\
			.get_value_iterator = &map_##key_identifier##_##value_identifier##_get_value_iterator,											\
			.insert = &map_##key_identifier##_##value_identifier##_insert,														\
			.remove = &map_##key_identifier##_##value_identifier##_remove,														\
			.size = &map_##key_identifier##_##value_identifier##_size														\
		};																						\
																								\
		static iterator_pair_##key_identifier##_##value_identifier##_t_next_t map_entry_iterator_pair_##key_identifier##_##value_identifier##_t_next;					\
		static bool map_entry_iterator_pair_##key_identifier##_##value_identifier##_t_next(ITERATOR(PAIR(key_identifier, value_identifier)) *iterator) {				\
			MAP(void, void) map = (MAP(void, void))iterator->container;														\
			if (!map_entry_iterator_pair_void_void_t_next((ITERATOR(PAIR(void, void)) *)iterator))											\
				return false;																			\
			void *second_address = iterator->element.value.void_value.second;													\
			if (map->hash_object)																			\
				memcpy(&iterator->element.value.value.first, iterator->element.value.void_value.first, sizeof(key_type));							\
			if (sizeof(value_type) <= sizeof(void *))																\
				memcpy(&iterator->element.value.value.second, &second_address, sizeof(value_type));										\
			else																					\
				memcpy(&iterator->element.value.value.second, second_address, sizeof(value_type));										\
			return true;																				\
		}																						\
																								\
		static iterator_##key_identifier##_next_t map_key_iterator_##key_identifier##_##value_identifier##_next;									\
		static bool map_key_iterator_##key_identifier##_##value_identifier##_next(ITERATOR(key_identifier) *iterator) {									\
			MAP(void, void) map = (MAP(void, void))iterator->container;														\
			if (!map_key_iterator_void_next((ITERATOR(void) *)iterator))														\
				return false;																			\
			else if (map->hash_object)																		\
				memcpy(&iterator->element.value, iterator->element.address, sizeof(key_type));											\
			return true;																				\
		}																						\
																								\
		static iterator_##value_identifier##_next_t map_value_iterator_##key_identifier##_##value_identifier##_next;									\
		static bool map_value_iterator_##key_identifier##_##value_identifier##_next(ITERATOR(value_identifier) *iterator) {								\
			if (!map_value_iterator_void_next((ITERATOR(void) *)iterator))														\
				return false;																			\
			else if (sizeof(value_type) <= sizeof(void *))																\
				memcpy(&iterator->element.value, &iterator->element.address, sizeof(value_type));										\
			else																					\
				memcpy(&iterator->element.value, iterator->element.address, sizeof(value_type));										\
			return true;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_destroy_t map_##key_identifier##_##value_identifier##_destroy;							\
		static inline void map_##key_identifier##_##value_identifier##_destroy(MAP(key_identifier, value_identifier) map) {								\
			if (sizeof(value_type) <= sizeof(void *))																\
				map_void_void_destroy(map->map);																\
			else																					\
				map_void_void_destroy_and_free(map->map);															\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_get_t map_##key_identifier##_##value_identifier##_get;								\
		static inline value_type map_##key_identifier##_##value_identifier##_get(MAP(key_identifier, value_identifier) map, key_type key) {						\
			void *void_key;																				\
			if (map->map->hash_object)																		\
				void_key = &key;																		\
			else {																					\
				assert(sizeof(key) == sizeof(void_key));															\
				memcpy(&void_key, &key, sizeof(void_key));															\
			}																					\
			void *void_value = map_void_void_get(map->map, void_key);														\
			value_type value;																			\
			if (sizeof(value_type) <= sizeof(void *))																\
				memcpy(&value, &void_value, sizeof(value_type));														\
			else																					\
				memcpy(&value, void_value, sizeof(value_type));															\
			return value;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_get_entry_iterator_t map_##key_identifier##_##value_identifier##_get_entry_iterator;					\
		static inline ITERATOR(PAIR(key_identifier, value_identifier)) map_##key_identifier##_##value_identifier##_get_entry_iterator(MAP(key_identifier, value_identifier) map) {	\
			ITERATOR(PAIR(void, void)) iterator = map_void_void_get_entry_iterator(map->map);											\
			ITERATOR(PAIR(key_identifier, value_identifier)) ret = {														\
				.container = iterator.container,																\
				.next = &map_entry_iterator_pair_##key_identifier##_##value_identifier##_t_next,										\
				.state = iterator.state																		\
			};																					\
			if (map->map->hash_object)																		\
				memcpy(&ret.element.value.value.first, iterator.element.value.value.first, sizeof(key_type));									\
			else																					\
				memcpy(&ret.element.value.value.first, &iterator.element.value.value.first, sizeof(key_type));									\
			if (sizeof(value_type) <= sizeof (void *))																\
				memcpy(&ret.element.value.value.second, &iterator.element.value.value.second, sizeof(value_type));								\
			else																					\
				memcpy(&ret.element.value.value.second, iterator.element.value.value.second, sizeof(value_type));								\
			return ret;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_get_key_iterator_t map_##key_identifier##_##value_identifier##_get_key_iterator;					\
		static inline ITERATOR(key_identifier) map_##key_identifier##_##value_identifier##_get_key_iterator(MAP(key_identifier, value_identifier) map) {				\
			ITERATOR(void) iterator = map_void_void_get_key_iterator(map->map);													\
			ITERATOR(key_identifier) ret = {																	\
				.container = iterator.container,																\
				.next = &map_key_iterator_##key_identifier##_##value_identifier##_next,												\
				.state = iterator.state																		\
			};																					\
			if (map->map->hash_object)																		\
				memcpy(&ret.element.value, iterator.element.address, sizeof(key_type));												\
			else																					\
				memcpy(&ret.element.value, &iterator.element.value, sizeof(key_type));												\
			return ret;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_get_value_iterator_t map_##key_identifier##_##value_identifier##_get_value_iterator;					\
		static inline ITERATOR(value_identifier) map_##key_identifier##_##value_identifier##_get_value_iterator(MAP(key_identifier, value_identifier) map) {				\
			ITERATOR(void) iterator = map_void_void_get_value_iterator(map->map);													\
			ITERATOR(value_identifier) ret = {																	\
				.container = iterator.container,																\
				.next = &map_value_iterator_##key_identifier##_##value_identifier##_next,											\
				.state = iterator.state																		\
			};																					\
			if (sizeof(value_type) <= sizeof (void *))																\
				memcpy(&ret.element.value, &iterator.element.address, sizeof(value_type));											\
			else																					\
				memcpy(&ret.element.value, iterator.element.address, sizeof(value_type));											\
			return ret;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_insert_t map_##key_identifier##_##value_identifier##_insert;								\
		static inline bool map_##key_identifier##_##value_identifier##_insert(MAP(key_identifier, value_identifier) map, key_type key, value_type element) {				\
			void *void_key;																				\
			if (map->map->hash_object)																		\
				void_key = &key;																		\
			else if (sizeof(key) != sizeof(void_key))																\
				return false;																			\
			else																					\
				memcpy(&void_key, &key, sizeof(void_key));															\
			void *copy;																				\
			if (sizeof(value_type) <= sizeof(void *)) {																\
				memcpy(&copy, &element, sizeof(value_type));															\
				return map_void_void_insert(map->map, void_key, copy);														\
			} else {																				\
				copy = malloc(sizeof(value_type));																\
				if (copy == nullptr)																		\
					return false;																		\
				memcpy(copy, &element, sizeof(value_type));															\
				if (map_void_void_insert_after_free(map->map, void_key, copy))													\
					return true;																		\
				else {																				\
					free(copy);																		\
					return false;																		\
				}																				\
			}																					\
		}																						\
																								\
		static inline MAP(key_identifier, value_identifier) map_##key_identifier##_##value_identifier##_new(hash_64_t *const hash_fn, size_t key_length) {				\
			if (sizeof(key_type) > sizeof(void *) && key_length != HASH_OBJECT)													\
				return nullptr;																			\
			MAP(key_identifier, value_identifier) ret = malloc(sizeof(*ret));													\
			if (ret == nullptr)																			\
				return nullptr;																			\
			bool hash_object = key_length == HASH_OBJECT;																\
			if (hash_object)																			\
				key_length = sizeof(key_type);																	\
			ret->map = map_void_void_new(hash_fn, key_length);															\
			if (ret->map == nullptr) {																		\
				free(ret);																			\
				return nullptr;																			\
			}																					\
			ret->map->hash_object = hash_object;																	\
			ret->vtable = &MAP_##key_identifier##_##value_identifier##_VTABLE;													\
			return ret;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_remove_t map_##key_identifier##_##value_identifier##_remove;								\
		static inline value_type map_##key_identifier##_##value_identifier##_remove(MAP(key_identifier, value_identifier) map, key_type key) {						\
			void *void_key;																				\
			if (map->map->hash_object)																		\
				void_key = &key;																		\
			else {																					\
				assert(sizeof(key) == sizeof(void_key));															\
				memcpy(&void_key, &key, sizeof(void_key));															\
			}																					\
			void *void_value = map_void_void_remove(map->map, void_key);														\
			value_type value;																			\
			if (sizeof(value_type) <= sizeof(void *))																\
				memcpy(&value, &void_value, sizeof(value_type));														\
			else {																					\
				memcpy(&value, void_value, sizeof(value_type));															\
				free(void_value);																		\
			}																					\
			return value;																				\
		}																						\
																								\
		static inline map_##key_identifier##_##value_identifier##_size_t map_##key_identifier##_##value_identifier##_size;								\
		static inline int map_##key_identifier##_##value_identifier##_size(MAP(key_identifier, value_identifier) map) {									\
			return map_void_void_size(map->map);																	\
		}																						\
	)																							\
																								\
	struct map_##key_identifier##_##value_identifier

DEFINE_ITERATOR(PAIR(void, void), PAIR(void, void));

typedef struct map_void_void *MAP(void, void);
struct map_void_void_vtable;

typedef void map_void_void_destroy_t(MAP(void, void) map);
typedef void *map_void_void_get_t(MAP(void, void) map, void *key);
typedef ITERATOR(PAIR(void, void)) map_void_void_get_entry_iterator_t(MAP(void, void) map);
typedef ITERATOR(void) map_void_void_get_key_iterator_t(MAP(void, void) map);
typedef ITERATOR(void) map_void_void_get_value_iterator_t(MAP(void, void) map);
typedef bool map_void_void_insert_t(MAP(void, void) map, void *key, void *element);
typedef void *map_void_void_remove_t(MAP(void, void) map, void *key);
typedef int map_void_void_size_t(MAP(void, void) map);

struct map_void_void {
	const struct map_void_void_vtable *vtable;
	struct {
		ITERATOR(PAIR(void, void)) entry_iterator;
		ITERATOR(void) key_iterator;
		ITERATOR(void) value_iterator;
	} *associated_types;
	bool hash_object;
};

struct map_void_void_vtable {
	map_void_void_destroy_t *destroy;
	map_void_void_get_t *get;
	map_void_void_get_entry_iterator_t *get_entry_iterator;
	map_void_void_get_key_iterator_t *get_key_iterator;
	map_void_void_get_value_iterator_t *get_value_iterator;
	map_void_void_insert_t *insert;
	map_void_void_remove_t *remove;
	map_void_void_size_t *size;
};

extern iterator_pair_void_void_t_next_t map_entry_iterator_pair_void_void_t_next;
extern iterator_void_next_t map_key_iterator_void_next;
extern iterator_void_next_t map_value_iterator_void_next;
extern map_void_void_destroy_t map_void_void_destroy;
extern map_void_void_destroy_t map_void_void_destroy_and_free;
extern map_void_void_get_t map_void_void_get;
extern map_void_void_get_entry_iterator_t map_void_void_get_entry_iterator;
extern map_void_void_get_key_iterator_t map_void_void_get_key_iterator;
extern map_void_void_get_value_iterator_t map_void_void_get_value_iterator;
extern map_void_void_insert_t map_void_void_insert;
extern map_void_void_insert_t map_void_void_insert_after_free;
extern MAP(void, void) map_void_void_new(hash_64_t *const hash_fn, size_t key_length);
extern map_void_void_remove_t map_void_void_remove;
extern map_void_void_size_t map_void_void_size;

#include <stdlib.h>

typedef struct list_void_internal list_t;
typedef struct node node_t;

struct list_void_internal {
	struct list_void list;
	node_t *head;
	node_t *tail;
};

struct node {
	void *element;
	node_t *next;
	node_t *prev;
};

static const struct list_void_vtable LIST_VOID_VTABLE;

static const struct list_void_vtable LIST_VOID_VTABLE = {
	.append = &list_void_append,
	.destroy = &list_void_destroy,
	.get_iterator = &list_void_get_iterator,
	.remove = &list_void_remove
};

iterator_void_next_t list_iterator_void_next;
bool list_iterator_void_next(ITERATOR(void) *iterator) {
	if (iterator == nullptr || iterator->container == nullptr)
		return false;
	if (iterator->state.ptr == nullptr)
		iterator->state.ptr = ((list_t *)iterator->container)->head;
	else
		iterator->state.ptr = ((node_t *)iterator->state.ptr)->next;
	if (iterator->state.ptr == nullptr) {
		iterator->container = nullptr;
		return false;
	}
	iterator->element.address = ((node_t *)iterator->state.ptr)->element;
	return true;
}

list_void_append_t list_void_append;
bool list_void_append(LIST(void) list, void *element) {
	if (list == nullptr)
		return false;
	node_t *node = malloc(sizeof(*node));
	if (node == nullptr)
		return false;
	list_t *internal = (list_t *)list;
	if (internal->head == nullptr)
		internal->head = node;
	else
		internal->tail->next = node;
	node->element = element;
	node->next = nullptr;
	node->prev = internal->tail;
	internal->tail = node;
	return true;
}

list_void_destroy_t list_void_destroy;
void list_void_destroy(LIST(void) list) {
	if (list == nullptr)
		return;
	for (node_t *node = ((list_t *)list)->head, *next_node; node != nullptr; node = next_node) {
		next_node = node->next;
		free(node);
	}
	free(list);
}

list_void_destroy_t list_void_destroy_free_elements;
void list_void_destroy_free_elements(LIST(void) list) {
	if (list == nullptr)
		return;
	for (node_t *node = ((list_t *)list)->head, *next_node; node != nullptr; node = next_node) {
		next_node = node->next;
		free(node->element);
		free(node);
	}
	free(list);
}

list_void_get_iterator_t list_void_get_iterator;
ITERATOR(void) list_void_get_iterator(LIST(void) list) {
	if (list == nullptr || ((list_t *)list)->head == nullptr) {
		return (ITERATOR(void)) {
			.container = nullptr
		};
	} else {
		return (ITERATOR(void)) {
			.container = list,
			.element.address = ((list_t *)list)->head->element,
			.next = &list_iterator_void_next,
			.state.ptr = ((list_t *)list)->head
		};
	}
}

LIST(void) list_void_new() {
	list_t *list = malloc(sizeof(*list));
	if (list == nullptr)
		return nullptr;
	list->head = nullptr;
	list->tail = nullptr;
	list->list.vtable = &LIST_VOID_VTABLE;
	return &list->list;
}

list_void_remove_t list_void_remove;
bool list_void_remove(LIST(void) list, ITERATOR(void) *iterator) {
	if (list == nullptr || iterator == nullptr || iterator->container == nullptr || iterator->state.ptr == nullptr)
		return false;
	node_t *removed = iterator->state.ptr;
	list_t *internal = (list_t *)list;
	node_t *next = removed->next;
	node_t *prev = removed->prev;
	if (next == nullptr)
		internal->tail = prev;
	else
		next->prev = prev;
	if (prev == nullptr)
		internal->head = next;
	else
		prev->next = next;
	iterator->state.ptr = removed->prev;
	free(removed);
	return true;
}

list_void_remove_t list_void_remove_and_free;
bool list_void_remove_and_free(LIST(void) list, ITERATOR(void) *iterator) {
	if (iterator == nullptr || iterator->container != list)
		return false;
	void *element = ((node_t *)iterator->state.ptr)->element;
	if (!list_void_remove(list, iterator))
		return false;
	free(element);
	return true;
}

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

typedef struct entry entry_t;
typedef struct entry_location entry_location_t;
typedef struct map_void_void_internal map_t;
typedef struct page page_t;

struct entry {
	void *key;
	void *element;
	uint64_t hash;
	unsigned char probe_distance;
};

struct entry_location {
	int page;
	int slot;
};

struct map_void_void_internal {
	struct map_void_void map;
	hash_64_t *hash_fn;
	size_t key_length;
	page_t *pages;
	int num_expansions;
	enum {
		MAP_GROW,
		MAP_INIT,
		MAP_SHRINK
	} last_resize;
};

struct page {
	bool dirty;
	int num_entries;
	entry_t *entries;
};

//TODO: should probably pull this from the system, though 4k is unlikely to ever end up not being the right size
constexpr int PAGE_SIZE = 4096;

constexpr int ENTRIES_PER_PAGE = PAGE_SIZE / sizeof(entry_t);

static_assert(ENTRIES_PER_PAGE < (typeof((entry_t){}.probe_distance))UINT64_MAX);

constexpr int MAX_ENTRIES_PER_PAGE = ENTRIES_PER_PAGE / 2;
constexpr int MIN_ENTRIES_PER_PAGE = ENTRIES_PER_PAGE / 4;

static const struct map_void_void_vtable MAP_VOID_VOID_VTABLE;

static entry_location_t find_entry(map_t *map, void *key);
static bool map_grow(map_t *map);
static void map_migrate_dirty(map_t *map, page_t *dirty_page);
static void map_shrink(map_t *map);
static bool map_void_void_insert_real(MAP(void, void) map, void *key, void *element, bool free_previous_element);
static void map_void_void_insert_slot(map_t *map, void *key, uint64_t hash, void *element, bool free_previous_element);

static const struct map_void_void_vtable MAP_VOID_VOID_VTABLE = {
	.destroy = &map_void_void_destroy,
	.get = &map_void_void_get,
	.get_entry_iterator = &map_void_void_get_entry_iterator,
	.get_key_iterator = &map_void_void_get_key_iterator,
	.get_value_iterator = &map_void_void_get_value_iterator,
	.insert = &map_void_void_insert,
	.remove = &map_void_void_remove,
	.size = &map_void_void_size
};

static entry_location_t find_entry(map_t *map, void *key) {
	uint64_t hash = map->hash_fn(key, map->key_length);
	int page = map->num_expansions == 0 ? 0 : hash >> UINT64_WIDTH - map->num_expansions;
	if (map->last_resize == MAP_GROW && map->pages[page & ~1].dirty)
		map_migrate_dirty(map, &map->pages[page & ~1]);
	else if (map->last_resize == MAP_SHRINK && map->pages[page + (1 << map->num_expansions)].dirty)
		map_migrate_dirty(map, &map->pages[page + (1 << map->num_expansions)]);
	int slot = (hash & UINT64_MAX >> map->num_expansions) % ENTRIES_PER_PAGE;
	int i = slot;
	do {
		if (map->pages[page].entries[i].key == nullptr)
			return (entry_location_t){.page = -1};
		else if (map->pages[page].entries[i].hash == hash)
			return (entry_location_t){.page = page, .slot = i};
		i = (i + 1) % ENTRIES_PER_PAGE;
	} while (i != slot);
	return (entry_location_t){.page = -1};
}

iterator_pair_void_void_t_next_t map_entry_iterator_pair_void_void_t_next;
bool map_entry_iterator_pair_void_void_t_next(ITERATOR(PAIR(void, void)) *iterator) {
	if (iterator == nullptr || iterator->container == nullptr)
		return false;
	map_t *map = iterator->container;
	for (int entry = iterator->state.value + 1; entry < (1 << map->num_expansions) * ENTRIES_PER_PAGE; entry++) {
		int page = entry / ENTRIES_PER_PAGE;
		if (map->pages[page].dirty)
			map_migrate_dirty(map, &map->pages[page]);
		if (map->pages[page].entries[entry % ENTRIES_PER_PAGE].key != nullptr) {
			iterator->state.value = entry;
			iterator->element.value.value.first = map->pages[page].entries[entry % ENTRIES_PER_PAGE].key;
			iterator->element.value.value.second = map->pages[page].entries[entry % ENTRIES_PER_PAGE].element;
			return true;
		}
	}
	iterator->container = nullptr;
	return false;
}

static bool map_grow(map_t *map) {
	//TODO: can potentially shortcut some migration work if last_resize == MAP_SHRINK
	for (int i = 0; i < 1 << map->num_expansions; i++)
		if (map->pages[i].dirty)
			map_migrate_dirty(map, &map->pages[i]);
	entry_t *entries;
	if (map->last_resize == MAP_SHRINK)
		entries = map->pages[1 << map->num_expansions].entries;
	else {
		page_t *pages = realloc(map->pages, sizeof(map->pages[0]) * (1 << map->num_expansions + 1));
		if (pages == nullptr)
			return false;
		map->pages = pages;
		entries = aligned_alloc(PAGE_SIZE, (1 << map->num_expansions) * PAGE_SIZE);
		if (entries == nullptr)
			return false;
	}
	for (int i = (1 << map->num_expansions) - 1; i >= 0; i--) {
		map->pages[i * 2] = map->pages[i];
		map->pages[i * 2].dirty = true;
		map->pages[i * 2 + 1].dirty = false;
		map->pages[i * 2 + 1].num_entries = 0;
		map->pages[i * 2 + 1].entries = (entry_t *)(((unsigned char *)entries) + i * PAGE_SIZE);
		for (int j = 0; j < ENTRIES_PER_PAGE; j++)
			map->pages[i * 2 + 1].entries[j].key = nullptr;
	}
	map->num_expansions++;
	map->last_resize = MAP_GROW;
	return true;
}

iterator_void_next_t map_key_iterator_void_next;
bool map_key_iterator_void_next(ITERATOR(void) *iterator) {
	if (iterator == nullptr || iterator->container == nullptr)
		return false;
	map_t *map = iterator->container;
	for (int entry = iterator->state.value + 1; entry < (1 << map->num_expansions) * ENTRIES_PER_PAGE; entry++) {
		int page = entry / ENTRIES_PER_PAGE;
		if (map->pages[page].dirty)
			map_migrate_dirty(map, &map->pages[page]);
		if (map->pages[page].entries[entry % ENTRIES_PER_PAGE].key != nullptr) {
			iterator->state.value = entry;
			iterator->element.value = map->pages[page].entries[entry % ENTRIES_PER_PAGE].key;
			return true;
		}
	}
	iterator->container = nullptr;
	return false;
}

static void map_migrate_dirty(map_t *map, page_t *dirty_page) {
	entry_t copy[ENTRIES_PER_PAGE];
	memcpy(copy, dirty_page->entries, sizeof(entry_t) * ENTRIES_PER_PAGE);
	for (int i = 0; i < ENTRIES_PER_PAGE; i++)
		dirty_page->entries[i].key = nullptr;
	dirty_page->num_entries = 0;
	dirty_page->dirty = false;
	for (int i = 0; i < ENTRIES_PER_PAGE; i++)
		if (copy[i].key != nullptr)
			map_void_void_insert_slot(map, copy[i].key, copy[i].hash, copy[i].element, false);
}

static void map_shrink(map_t *map) {
	//TODO: can potentially shortcut some migration work if last_resize == MAP_GROW
	for (int i = 0; i < 1 << map->num_expansions + (map->last_resize == MAP_SHRINK); i++)
		if (map->pages[i].dirty)
			map_migrate_dirty(map, &map->pages[i]);
	if (map->last_resize == MAP_SHRINK) {
		entry_t *entries = map->pages[1 << map->num_expansions].entries;
		page_t *pages = realloc(map->pages, sizeof(map->pages[0]) * (1 << map->num_expansions));
		if (pages == nullptr)
			return;
		free(entries);
		map->pages = pages;
	}
	if (map->num_expansions >= 2) {
		page_t page_copies[1 << map->num_expansions - 2];
		for (int i = 0; i < 1 << map->num_expansions - 2; i++) {
			map->pages[i * 2] = map->pages[i * 4];
			page_copies[i] = map->pages[i * 2 + 1];
			map->pages[i * 2 + 1] = map->pages[i * 4 + 2];
		}
		for (int i = 0; i < (1 << map->num_expansions - 2) - 1; i++)
			map->pages[(1 << map->num_expansions) - i - 2] = map->pages[(1 << map->num_expansions) - i * 2 - 3];
		memcpy(&map->pages[1 << map->num_expansions - 1], page_copies, sizeof(page_copies));
	}
	for (int i = 1 << map->num_expansions - 1; i < 1 << map->num_expansions; i++)
		map->pages[i].dirty = true;
	map->num_expansions--;
	map->last_resize = MAP_SHRINK;
}

iterator_void_next_t map_value_iterator_void_next;
bool map_value_iterator_void_next(ITERATOR(void) *iterator) {
	if (iterator == nullptr || iterator->container == nullptr)
		return false;
	map_t *map = iterator->container;
	for (int entry = iterator->state.value + 1; entry < (1 << map->num_expansions) * ENTRIES_PER_PAGE; entry++) {
		int page = entry / ENTRIES_PER_PAGE;
		if (map->pages[page].dirty)
			map_migrate_dirty(map, &map->pages[page]);
		if (map->pages[page].entries[entry % ENTRIES_PER_PAGE].key != nullptr) {
			iterator->state.value = entry;
			iterator->element.value = map->pages[page].entries[entry % ENTRIES_PER_PAGE].element;
			return true;
		}
	}
	iterator->container = nullptr;
	return false;
}

map_void_void_destroy_t map_void_void_destroy;
void map_void_void_destroy(MAP(void, void) map) {
	if (map == nullptr)
		return;
	map_t *internal = (map_t *)map;
	for (int i = 0; i < 1 << internal->num_expansions; i++)
		for (int j = 0; j < ENTRIES_PER_PAGE; j++)
			free(internal->pages[i].entries[j].key);
	free(internal->pages[0].entries);
	for (int i = 0; i < internal->num_expansions; i++)
		free(internal->pages[1 << i].entries);
	free(internal->pages);
	free(internal);
}

map_void_void_destroy_t map_void_void_destroy_and_free;
void map_void_void_destroy_and_free(MAP(void, void) map) {
	if (map == nullptr)
		return;
	map_t *internal = (map_t *)map;
	for (int i = 0; i < 1 << internal->num_expansions; i++) {
		for (int j = 0; j < ENTRIES_PER_PAGE; j++) {
			if (internal->pages[i].entries[j].key != nullptr) {
				free(internal->pages[i].entries[j].key);
				free(internal->pages[i].entries[j].element);
			}
		}
	}
	free(internal->pages[0].entries);
	for (int i = 0; i < internal->num_expansions; i++)
		free(internal->pages[1 << i].entries);
	free(internal->pages);
	free(internal);
}

map_void_void_get_t map_void_void_get;
void *map_void_void_get(MAP(void, void) map, void *key) {
	if (map == nullptr || key == nullptr)
		return nullptr;
	map_t *internal = (map_t *)map;
	entry_location_t entry = find_entry(internal, key);
	if (entry.page == -1)
		return nullptr;
	else
		return internal->pages[entry.page].entries[entry.slot].element;
}

map_void_void_get_entry_iterator_t map_void_void_get_entry_iterator;
ITERATOR(PAIR(void, void)) map_void_void_get_entry_iterator(MAP(void, void) map) {
	if (map == nullptr) {
		return (ITERATOR(PAIR(void, void))) {
			.container = nullptr
		};
	} else {
		map_t *internal = (map_t *)map;
		if (internal->pages[0].dirty)
			map_migrate_dirty(internal, &internal->pages[0]);
		ITERATOR(PAIR(void, void)) iterator = {
			.container = map,
			.next = &map_entry_iterator_pair_void_void_t_next,
			.state.value = 0
		};
		if (internal->pages[0].entries[0].key == nullptr)
			iterator.next(&iterator);
		else {
			iterator.element.value.value.first = internal->pages[0].entries[0].key;
			iterator.element.value.value.second = internal->pages[0].entries[0].element;
		}
		return iterator;
	}
}

map_void_void_get_key_iterator_t map_void_void_get_key_iterator;
ITERATOR(void) map_void_void_get_key_iterator(MAP(void, void) map) {
	if (map == nullptr) {
		return (ITERATOR(void)) {
			.container = nullptr
		};
	} else {
		map_t *internal = (map_t *)map;
		if (internal->pages[0].dirty)
			map_migrate_dirty(internal, &internal->pages[0]);
		ITERATOR(void) iterator = {
			.container = map,
			.next = &map_key_iterator_void_next,
			.state.value = 0
		};
		if (internal->pages[0].entries[0].key == nullptr)
			iterator.next(&iterator);
		else
			iterator.element.value = internal->pages[0].entries[0].key;
		return iterator;
	}
}

map_void_void_get_value_iterator_t map_void_void_get_value_iterator;
ITERATOR(void) map_void_void_get_value_iterator(MAP(void, void) map) {
	if (map == nullptr) {
		return (ITERATOR(void)) {
			.container = nullptr
		};
	} else {
		map_t *internal = (map_t *)map;
		if (internal->pages[0].dirty)
			map_migrate_dirty(internal, &internal->pages[0]);
		ITERATOR(void) iterator = {
			.container = map,
			.next = &map_value_iterator_void_next,
			.state.value = 0
		};
		if (internal->pages[0].entries[0].key == nullptr)
			iterator.next(&iterator);
		else
			iterator.element.value = internal->pages[0].entries[0].element;
		return iterator;
	}
}

map_void_void_insert_t map_void_void_insert;
bool map_void_void_insert(MAP(void, void) map, void *key, void *element) {
	return map_void_void_insert_real(map, key, element, false);
}

map_void_void_insert_t map_void_void_insert_after_free;
bool map_void_void_insert_after_free(MAP(void, void) map, void *key, void *element) {
	return map_void_void_insert_real(map, key, element, true);
}

static bool map_void_void_insert_real(MAP(void, void) map, void *key, void *element, bool free_previous_element) {
	if (map == nullptr || key == nullptr)
		return false;
	map_t *internal = (map_t *)map;
	void *key_copy;
	if (internal->key_length == HASH_NT)
		key_copy = strdup(key);
	else
		key_copy = malloc(internal->key_length);
	if (key_copy == nullptr)
		return false;
	else if (internal->key_length != HASH_NT)
		memcpy(key_copy, key, internal->key_length);
	uint64_t hash = internal->hash_fn(key, internal->key_length);
	int page = internal->num_expansions == 0 ? 0 : hash >> UINT64_WIDTH - internal->num_expansions;
	if (internal->pages[page].num_entries + 1 > MAX_ENTRIES_PER_PAGE) {
		//TODO: should this be allowed to still insert if more space exists but the grow failed?
		if (!map_grow(internal)) {
			free(key_copy);
			return false;
		}
		page = internal->num_expansions == 0 ? 0 : hash >> UINT64_WIDTH - internal->num_expansions;
	}
	if (internal->pages[page & ~1].dirty)
		map_migrate_dirty(internal, &internal->pages[page & ~1]);
	if (internal->pages[page].num_entries == ENTRIES_PER_PAGE)
		return false;
	map_void_void_insert_slot(internal, key_copy, hash, element, free_previous_element);
	return true;
}

static void map_void_void_insert_slot(map_t *map, void *key, uint64_t hash, void *element, bool free_previous_element) {
	int page = map->num_expansions == 0 ? 0 : hash >> UINT64_WIDTH - map->num_expansions;
	int slot = (hash & UINT64_MAX >> map->num_expansions) % ENTRIES_PER_PAGE;
	int i = slot;
	do {
		if (map->pages[page].entries[i].key == nullptr) {
			map->pages[page].entries[i].key = key;
			map->pages[page].entries[i].element = element;
			map->pages[page].entries[i].hash = hash;
			map->pages[page].entries[i].probe_distance = (i + ENTRIES_PER_PAGE - slot) % ENTRIES_PER_PAGE;
			map->pages[page].num_entries++;
			return;
		} else if (map->pages[page].entries[i].hash == hash) {
			free(map->pages[page].entries[i].key);
			map->pages[page].entries[i].key = key;
			if (free_previous_element)
				free(map->pages[page].entries[i].element);
			map->pages[page].entries[i].element = element;
			return;
		} else if (map->pages[page].entries[i].probe_distance < (i + ENTRIES_PER_PAGE - slot) % ENTRIES_PER_PAGE) {
			entry_t swapped = map->pages[page].entries[i];
			map->pages[page].entries[i].key = key;
			map->pages[page].entries[i].element = element;
			map->pages[page].entries[i].hash = hash;
			map->pages[page].entries[i].probe_distance = (i + ENTRIES_PER_PAGE - slot) % ENTRIES_PER_PAGE;
			key = swapped.key;
			element = swapped.element;
			hash = swapped.hash;
			slot = (i + ENTRIES_PER_PAGE - swapped.probe_distance) % ENTRIES_PER_PAGE;
		}
		i = (i + 1) % ENTRIES_PER_PAGE;
	} while (i != slot);
}

//TODO: should HASH_OBJECT be allowed through here and still give valid results?
MAP(void, void) map_void_void_new(hash_64_t *const hash_fn, size_t key_length) {
	if (hash_fn == nullptr || key_length != HASH_NT && key_length == 0)
		return nullptr;
	map_t *map = malloc(sizeof(*map));
	if (map == nullptr)
		return nullptr;
	map->pages = malloc(sizeof(map->pages[0]));
	if (map->pages == nullptr)
		goto free_map;
	entry_t *entries = aligned_alloc(PAGE_SIZE, PAGE_SIZE);
	if (entries == nullptr)
		goto free_pages;
	for (int i = 0; i < ENTRIES_PER_PAGE; i++)
		entries[i].key = nullptr;
	map->pages[0].entries = entries;
	map->pages[0].num_entries = 0;
	map->pages[0].dirty = false;
	map->num_expansions = 0;
	map->last_resize = MAP_INIT;
	map->hash_fn = hash_fn;
	map->key_length = key_length;
	map->map.vtable = &MAP_VOID_VOID_VTABLE;
	return &map->map;
free_pages:
	free(map->pages);
free_map:
	free(map);
	return nullptr;
}

map_void_void_remove_t map_void_void_remove;
void *map_void_void_remove(MAP(void, void) map, void *key) {
	if (map == nullptr || key == nullptr)
		return nullptr;
	map_t *internal = (map_t *)map;
	entry_location_t entry = find_entry(internal, key);
	if (entry.page == -1)
		return nullptr;
	void *value = internal->pages[entry.page].entries[entry.slot].element;
	free(internal->pages[entry.page].entries[entry.slot].key);
	internal->pages[entry.page].num_entries--;
	//TODO: is it actually possible to continue past the removed slot's probe distance location?
	for (int i = entry.slot, next_slot = (i + 1) % ENTRIES_PER_PAGE; next_slot != entry.slot; i = next_slot, next_slot = (next_slot + 1) % ENTRIES_PER_PAGE) {
		if (internal->pages[entry.page].entries[next_slot].key == nullptr || internal->pages[entry.page].entries[next_slot].probe_distance == 0) {
			internal->pages[entry.page].entries[i].key = nullptr;
			if (internal->pages[entry.page].num_entries < MIN_ENTRIES_PER_PAGE && internal->num_expansions > 0) {
				for (int i = 0; i < 1 << internal->num_expansions; i += 2)
					if (internal->pages[i].num_entries + internal->pages[i + 1].num_entries > MAX_ENTRIES_PER_PAGE)
						return value;
				map_shrink(internal);
			}
			return value;
		}
		internal->pages[entry.page].entries[i] = internal->pages[entry.page].entries[next_slot];
		internal->pages[entry.page].entries[i].probe_distance--;
	}
	internal->pages[entry.page].entries[(entry.slot + ENTRIES_PER_PAGE - 1) % ENTRIES_PER_PAGE].key = nullptr;
	return value;
}

map_void_void_size_t map_void_void_size;
int map_void_void_size(MAP(void, void) map) {
	if (map == nullptr)
		return 0;
	map_t *internal = (map_t *)map;
	int size = 0;
	for (int page = 0; page < 1 << internal->num_expansions; page++)
		size += internal->pages[page].num_entries;
	return size;
}

#include <stdio.h>

struct foo {
	char bar[16];
};

DEFINE_LIST(int, int);
DEFINE_LIST(intptr, int *);
DEFINE_LIST(foo, struct foo);
DEFINE_LIST(string, char *);
DEFINE_LIST(LIST(string), LIST(string));
DEFINE_LIST(LIST(LIST(string)), LIST(LIST(string)));
DEFINE_MAP(short, long, short, long);
DEFINE_MAP(string, string, char *, char *);
DEFINE_MAP(int, string, int, char *);
DEFINE_MAP(int, foo, int, struct foo);
DEFINE_MAP(string, LIST(string), char *, LIST(string));

int main() {
	LIST(foo) foolist = LIST_NEW(foo);
	struct foo foo = {"123456789ABCDEF"};
	LIST_APPEND(foolist, foo);
	LIST_APPEND(foolist, foo);
	for (ITERATOR(foo) iterator = LIST_GET_ITERATOR(foolist); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%s\n", ITERATOR_GET(iterator).bar);
	LIST_DESTROY(foolist);
	printf("\n");
	LIST(int) intlist = LIST_NEW(int);
	LIST_APPEND(intlist, 4);
	LIST_APPEND(intlist, 9);
	LIST_APPEND(intlist, 2);
	LIST_APPEND(intlist, 7);
	for (ITERATOR(int) iterator = LIST_GET_ITERATOR(intlist); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator)) {
		printf("%d\n", ITERATOR_GET(iterator));
		if (ITERATOR_GET(iterator) >= 5)
			LIST_REMOVE(intlist, iterator);
	}
	printf("\n");
	for (ITERATOR(int) iterator = LIST_GET_ITERATOR(intlist); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%d\n", ITERATOR_GET(iterator));
	printf("\n");
	LIST(string) stringlist = LIST_NEW(string);
	LIST_APPEND(stringlist, "foo");
	LIST_APPEND(stringlist, "bar");
	LIST_APPEND(stringlist, "fur");
	LIST_APPEND(stringlist, "bur");
	for (ITERATOR(string) iterator = LIST_GET_ITERATOR(stringlist); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%s\n", ITERATOR_GET(iterator));
	printf("\n");
	LIST(intptr) intptrlist = LIST_NEW(intptr);
	int intvalues[4] = {4, 9, 2, 7};
	LIST_APPEND(intptrlist, &intvalues[0]);
	LIST_APPEND(intptrlist, &intvalues[1]);
	LIST_APPEND(intptrlist, &intvalues[2]);
	LIST_APPEND(intptrlist, &intvalues[3]);
	for (ITERATOR(intptr) iterator = LIST_GET_ITERATOR(intptrlist); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%d\n", *ITERATOR_GET(iterator));
	printf("\n");
	LIST(LIST(string)) lists = LIST_NEW(LIST(string));
	for (int i = 0; i < 10; i++)
		LIST_APPEND(lists, LIST_NEW(string));
	LIST(LIST(LIST(string))) bigger_list = LIST_NEW(LIST(LIST(string)));
	LIST_APPEND(bigger_list, lists);
    MAP(short, long) shortmap = MAP_NEW(short, long, HASH_OBJECT);
    MAP_INSERT(shortmap, 2, 11);
    MAP_INSERT(shortmap, 7, 14);
    MAP_INSERT(shortmap, -3, 29);
    for (ITERATOR(long) iterator = MAP_GET_VALUE_ITERATOR(shortmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
        printf("%ld\n", ITERATOR_GET(iterator));
    printf("\n");
    for (ITERATOR(short) iterator = MAP_GET_KEY_ITERATOR(shortmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
        printf("%d\n", ITERATOR_GET(iterator));
    printf("\n");
    for (ITERATOR(PAIR(short, long)) iterator = MAP_GET_ENTRY_ITERATOR(shortmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator)) {
        PAIR(short, long) pair = ITERATOR_GET(iterator);
        printf("%d -> %ld\n", PAIR_FIRST(pair), PAIR_SECOND(pair));
    }
    printf("\n");
	MAP(string, string) stringmap = MAP_NEW(string, string, HASH_NT);
	MAP_INSERT(stringmap, "foo", "bar");
	MAP_INSERT(stringmap, "fur", "bur");
	MAP_INSERT(stringmap, "will", "remove");
	for (ITERATOR(string) iterator = MAP_GET_VALUE_ITERATOR(stringmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%s\n", ITERATOR_GET(iterator));
	printf("\n");
	for (ITERATOR(string) iterator = MAP_GET_KEY_ITERATOR(stringmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%s\n", ITERATOR_GET(iterator));
	printf("\n");
	for (ITERATOR(PAIR(string, string)) iterator = MAP_GET_ENTRY_ITERATOR(stringmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator)) {
		PAIR(string, string) pair = ITERATOR_GET(iterator);
		printf("%s -> %s\n", PAIR_FIRST(pair), PAIR_SECOND(pair));
	}
	printf("\n");
	MAP_REMOVE(stringmap, "will");
	for (ITERATOR(PAIR(string, string)) iterator = MAP_GET_ENTRY_ITERATOR(stringmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator)) {
		PAIR(string, string) pair = ITERATOR_GET(iterator);
		printf("%s -> %s\n", PAIR_FIRST(pair), PAIR_SECOND(pair));
	}
	printf("\n");
	MAP(int, string) intmap = MAP_NEW(int, string, HASH_OBJECT);
	MAP_INSERT(intmap, 4, "foo bar");
	MAP_INSERT(intmap, 8, "fur bur");
	for (ITERATOR(string) iterator = MAP_GET_VALUE_ITERATOR(intmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%s\n", ITERATOR_GET(iterator));
	printf("\n");
	for (ITERATOR(int) iterator = MAP_GET_KEY_ITERATOR(intmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator))
		printf("%d\n", ITERATOR_GET(iterator));
	printf("\n");
	for (ITERATOR(PAIR(int, string)) iterator = MAP_GET_ENTRY_ITERATOR(intmap); ITERATOR_ACTIVE(iterator); ITERATOR_NEXT(iterator)) {
		PAIR(int, string) pair = ITERATOR_GET(iterator);
		printf("%d -> %s\n", PAIR_FIRST(pair), PAIR_SECOND(pair));
	}
	printf("\n");
	printf("MAP_GET(intmap, 4) = %s\n", MAP_GET(intmap, 4));
	MAP(int, foo) foomap = MAP_NEW(int, foo, HASH_OBJECT);
	MAP_INSERT(foomap, 9, foo);
	MAP_INSERT(foomap, 9, foo);
	printf("MAP_GET(foomap, 9).bar = %s\n", MAP_GET(foomap, 9).bar);
	MAP_DESTROY(foomap);
	printf("\n");
	LIST(string) more_strings = LIST_NEW(string);
	LIST_APPEND(more_strings, "meow");
	LIST_APPEND(more_strings, "woof");
	MAP(string, LIST(string)) map_of_lists = MAP_NEW(string, LIST(string), HASH_NT);
	MAP_INSERT(map_of_lists, "mylist", stringlist);
	MAP_INSERT(map_of_lists, "animals", more_strings);
	for (ITERATOR(LIST(string)) map_iter = MAP_GET_VALUE_ITERATOR(map_of_lists); ITERATOR_ACTIVE(map_iter); ITERATOR_NEXT(map_iter))
		for (ITERATOR(string) list_iter = LIST_GET_ITERATOR(ITERATOR_GET(map_iter)); ITERATOR_ACTIVE(list_iter); ITERATOR_NEXT(list_iter))
			printf("%s\n", ITERATOR_GET(list_iter));
	return 0;
}