generic hashmap

meta_map.h

#ifndef DETAIL_META_HEADER_MAP
#define DETAIL_META_HEADER_MAP

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

#define meta_map_header(MAP) \
	(*(union meta_map_header*)(MAP))
typedef union meta_map_header {
	union meta_map_header* next[16];
	void* value;
} meta_map_header;
static_assert(!(SIZE_WIDTH % stdc_trailing_zeros(sizeof(((meta_map_header*)0)->next) / sizeof(int*))));

#define meta_map(TYPE) \
	((typeof(TYPE)*)meta_map())
static inline void* (meta_map)() {
	meta_map_header* map = malloc(sizeof(meta_map_header));
	for (size_t i = 0; i < (sizeof(map->next) / sizeof(int*)); ++i) {
		map->next[i] = nullptr;
	}
	return map;
}

#define meta_map_free(MAP) \
	((MAP) = (meta_map_free((void*)(MAP), 0), nullptr))
static inline void (meta_map_free)(meta_map_header* map, size_t i) {
	static constexpr size_t chunk_size = sizeof(map->next) / sizeof(int*);
	if (!map) {
		return;
	}
	if (i < SIZE_WIDTH) {
		for (size_t j = 0; j < chunk_size; ++j) {
			(meta_map_free)(map->next[j], i + stdc_trailing_zeros(chunk_size));
		}
	} else {
		free(map->value);
	}
	free(map);
}

#define meta_map_at(MAP, ...) \
	(*(typeof(MAP))meta_map_at((void*)(MAP), (__VA_ARGS__), sizeof(*(MAP))))
static inline void* (meta_map_at)(meta_map_header* map, size_t index, size_t size) {
	static constexpr size_t chunk_size = sizeof(map->next) / sizeof(int*);
	for (size_t i = 0; i < SIZE_WIDTH; i += stdc_trailing_zeros(chunk_size)) {
		size_t j = (index >> i) & ~-chunk_size;
		if (!map->next[j]) {
			map->next[j] = (meta_map)();
		}
		map = map->next[j];
	}
	if (!map->value) {
		map->value = malloc(size);
	}
	return map->value;
}

#define meta_map_has(MAP, ...) \
	meta_map_has((void*)(MAP), (__VA_ARGS__))
static inline bool (meta_map_has)(meta_map_header* map, size_t index) {
	static constexpr size_t chunk_size = sizeof(map->next) / sizeof(int*);
	for (size_t i = 0; i < SIZE_WIDTH; i += stdc_trailing_zeros(chunk_size)) {
		if (!map) {
			return false;
		}
		map = map->next[(index >> i) & ~-chunk_size];
	}
	return map && map->value;
}

#define meta_map_erase(MAP, ...) \
	((void)meta_map_erase((void*)(MAP), (__VA_ARGS__), 0))
static inline bool (meta_map_erase)(meta_map_header* map, size_t index, size_t i) {
	static constexpr size_t chunk_size = sizeof(map->next) / sizeof(int*);
	if (map) {
		if (i < SIZE_WIDTH) {
			meta_map_header** next = &map->next[(index >> i) & ~-chunk_size];
			if ((meta_map_erase)(*next, index, i + stdc_trailing_zeros(chunk_size))) {
				return true;
			}
			free(*next);
			*next = nullptr;
			for (size_t j = 0; j < chunk_size; ++j) {
				if (map->next[j]) {
					return true;
				}
			}
		} else {
			free(map->value);
			map->value = nullptr;
		}
	}
	return false;
}

#define meta_map_size(MAP) \
	meta_map_size((void*)(MAP), 0)
static inline size_t (meta_map_size)(meta_map_header* map, size_t i) {
	static constexpr size_t chunk_size = sizeof(map->next) / sizeof(int*);
	if (!map) {
		return 0;
	}
	if (i < SIZE_WIDTH) {
		size_t count = 0;
		for (size_t j = 0; j < chunk_size; ++j) {
			count += (meta_map_size)(map->next[j], i + stdc_trailing_zeros(chunk_size));
		}
		return count;
	}
	return !!map->value;
}

#endif