libutil

// util/map.c, version 0.1.2
// Map utility source file from libutil
// Copyright (C) 2021, Jakob Wakeling
// MIT Licence

/*
	This file uses the currently non-standard 'typeof' operator. Its use is
	considered acceptable because it is supported by both GCC and Clang, and
	POSIX extensions are used here anyway. Additionally, it is expected that the
	'typeof' operator will become standard in C23.
*/

#include "alloc.h"
#include "map.h"
#include "util.h"

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

#define LOAD_FACTOR 0.90

UINT map_initial_capacity = 64;

static void map_resize(map *m);
static u64  hash(const char *s, UINT l);

/* Initialise a map. */
map map_init(void (*free)(void *)) {
	return (map){ NULL, 0, 0, free };
}

/* Uninitialise a map. */
void map_free(map *m) {
	for (UINT i = 0; i < m->ac; i += 1) {
		if (m->a[i].h == 0) { continue; } free(m->a[i].k);
		if (m->free != NULL) { m->free(m->a[i].v); }
	}
	
	free(m->a); *m = (map){ NULL, 0, 0, NULL };
}

#define SWAP(a, b) { register typeof (a) t = a; a = b; b = t; }
#define DIB(i) ((i + m->ac - (m->a[i].h % m->ac)) % m->ac)

/* Insert a key-value pair into a map. The key is duplicated. */
void map_insert(map *m, char *k, void *v) {
	if (m->ac == 0 || m->al >= ((f64)m->ac * LOAD_FACTOR)) { map_resize(m); }
	UINT h = hash(k, strlen(k)), i = h % m->ac; k = strdup(k);
	
	for (UINT dist = 0;; i = (i + 1) % m->ac, dist += 1) {
		if (m->a[i].h == 0) {
			/* If an empty bucket is found, insert here */
			m->a[i] = (typeof (*m->a)){ h, k, v };
			m->al += 1; return;
		}
		
		/* Calculate tsid, the DIB of the item at the current index */
		UINT tsid = (i + m->ac - (m->a[i].h % m->ac)) % m->ac;
		
		if (dist > tsid) {
			SWAP(m->a[i].h, h);
			SWAP(m->a[i].k, k);
			SWAP(m->a[i].v, v);
			
			dist = tsid;
		}
	}
}

/* Lookup the value associated with a key from a map. */
void *map_lookup(map *m, char *k) {
	UINT h = hash(k, strlen(k)), i = h % m->ac;
	
	for (UINT dist = 0;; i = (i + 1) % m->ac, dist += 1) {
		if (m->a[i].h == 0) { return NULL; }
		
		if (dist > DIB(i)) { return NULL; }
		if ((m->a[i].h == h) && (strcmp(m->a[i].k, k) == 0)) {
			return m->a[i].v;
		}
	}
}

/* Remove a key-value pair from a map. */
void *map_remove(map *m, char *k) {
	UINT h = hash(k, strlen(k)), i = h % m->ac;
	
	for (UINT dist = 0;; i = (i + 1) % m->ac, dist += 1) {
		if (m->a[i].h == 0) { return NULL; }
		
		if (dist > DIB(i)) { return NULL; }
		if ((m->a[i].h == h) && (strcmp(m->a[i].k, k) == 0)) {
			/* If the element to be removed is found, then deallocate it */
			if (m->free != NULL) { m->free(m->a[i].v); } free(m->a[i].k);
			m->a[i] = (typeof (*m->a)){ 0, NULL, NULL }; m->al -= 1;
			
			/*  */
			for (UINT j = (i + 1) % m->ac;; i = j, j = (j + 1) % m->ac) {
				if (m->a[j].h == 0 || DIB(j) == 0) { break; }
				
				SWAP(m->a[i].h, m->a[j].h);
				SWAP(m->a[i].k, m->a[j].k);
				SWAP(m->a[i].v, m->a[j].v);
			}
			
			/*
				TODO I am unsure if I want to have this procedure return the
				removed value or simply an acknowledgement of its removal
			*/
			return (void *)true;
		}
	}
}

/* Print a basic representation of a map to stdout. */
void map_print(map *m) {
	for (UINT i = 0; i < m->ac; i += 1) if (m->a[i].h != 0) {
		printf("%s -> %s\n", m->a[i].k, (char *)m->a[i].v);
	}
}

/* Print a debug representation of a map to stdout. */
void map_debug(map *m) {
	for (UINT i = 0; i < m->ac; i += 1) {
		if (m->a[i].h == 0) { printf("[%zu] %lu\n", i, m->a[i].h); }
		else printf(
			"[%zu] %lu, %s -> %s, DIB: %zu\n",
			i, m->a[i].h, m->a[i].k, (char *)m->a[i].v, DIB(i)
		);
	}
}

/* Double the number of buckets in a map. */
static void map_resize(map *m) {
	/* If the map is empty, simply allocate it without rehashing */
	if (m->ac == 0) {
		m->ac = map_initial_capacity;
		m->a = xcalloc(m->ac, sizeof (*m->a)); return;
	}
	
	/* Otherwise rehash every element into a new resized map */
	map old = *m; m->ac *= 2; m->a = xcalloc(m->ac, sizeof (*m->a)); m->al = 0;
	
	for (UINT i = 0; i < old.ac; i += 1) {
		if (old.a[i].h == 0) { continue; }
		
		map_insert(m, old.a[i].k, old.a[i].v);
		free(old.a[i].k);
	}
	
	free(old.a);
}

/* Compute the hash of some data. Will not return 0. */
static u64 hash(const char *dat, UINT len) {
	register u64 fnv = 0xCBF29CE484222325;
	for (; len; len -= 1, dat += 1) { fnv ^= *dat; fnv *= 0x00000100000001B3; }
	fnv |= fnv == 0; return fnv;
}