map.c

/* Crit-bit tree based map which supports lookups based on unique
 * prefixes as well as ordered iteration.
 *
 * Based on public domain code from Rusty Russel, Adam Langley
 * and D. J. Bernstein.
 *
 * Further information about the data structure can be found at:
 *  http://cr.yp.to/critbit.html
 *  http://github.com/agl/critbit
 *  http://ccodearchive.net/info/strmap.html
 */
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <inttypes.h>
#include "map.h"

typedef struct Node Node;

struct Map {     /* struct holding either an item with value v and key u.s or an internal node */
	union {
		Node *n;
		const char *s;
	} u;
	void *v; /* value stored in the map, if non NULL u.s holds the corresponding key */
};

struct Node {
	Map child[2];    /* These point to strings or nodes. */
	size_t byte_num; /* The byte number where first bit differs. */
	uint8_t bit_num; /* The bit where these children differ. */
};

/* Closest key to this in a non-empty map. */
static Map *closest(Map *n, const char *key)
{
	size_t len = strlen(key);
	const uint8_t *bytes = (const uint8_t *)key;

	/* Anything with NULL value is an internal node. */
	while (!n->v) {
		uint8_t direction = 0;

		if (n->u.n->byte_num < len) {
			uint8_t c = bytes[n->u.n->byte_num];
			direction = (c >> n->u.n->bit_num) & 1;
		}
		n = &n->u.n->child[direction];
	}
	return n;
}

void *map_get(const Map *map, const char *key)
{
	/* Not empty map? */
	if (map->u.n) {
		Map *n = closest((Map *)map, key);
		if (strcmp(key, n->u.s) == 0)
			return n->v;
	}
	return NULL;
}

void *map_closest(const Map *map, const char *prefix)
{
	errno = 0;
	void *v = map_get(map, prefix);
	if (v)
		return v;
	const Map *m = map_prefix(map, prefix);
	if (map_empty(m))
		errno = ENOENT;
	return m->v;
}

bool map_contains(const Map *map, const char *prefix)
{
	return !map_empty(map_prefix(map, prefix));
}

static bool leaf(const char *key, void *value, void *data)
{
	int *nodes = data;
	return (*nodes)++ < 1;
}

bool map_leaf(const Map *map, const char *prefix)
{
	int nodes = 0;
	map_iterate(map_prefix(map, prefix), leaf, &nodes);
	return nodes == 1;
}

bool map_put(Map *map, const char *k, const void *value)
{
	size_t len = strlen(k);
	const uint8_t *bytes = (const uint8_t *)k;
	Map *n;
	Node *newn;
	size_t byte_num;
	uint8_t bit_num, new_dir;
	char *key;

	if (!value) {
		errno = EINVAL;
		return false;
	}

	if (!(key = strdup(k))) {
		errno = ENOMEM;
		return false;
	}

	/* Empty map? */
	if (!map->u.n) {
		map->u.s = key;
		map->v = (void *)value;
		return true;
	}

	/* Find closest existing key. */
	n = closest(map, key);

	/* Find where they differ. */
	for (byte_num = 0; n->u.s[byte_num] == key[byte_num]; byte_num++) {
		if (key[byte_num] == '\0') {
			/* All identical! */
			free(key);
			errno = EEXIST;
			return false;
		}
	}

	/* Find which bit differs */
	uint8_t diff = (uint8_t)n->u.s[byte_num] ^ bytes[byte_num];
	/* TODO: bit_num = 31 - __builtin_clz(diff); ? */
	for (bit_num = 0; diff >>= 1; bit_num++);

	/* Which direction do we go at this bit? */
	new_dir = ((bytes[byte_num]) >> bit_num) & 1;

	/* Allocate new node. */
	newn = malloc(sizeof(*newn));
	if (!newn) {
		free(key);
		errno = ENOMEM;
		return false;
	}
	newn->byte_num = byte_num;
	newn->bit_num = bit_num;
	newn->child[new_dir].v = (void *)value;
	newn->child[new_dir].u.s = key;

	/* Find where to insert: not closest, but first which differs! */
	n = map;
	while (!n->v) {
		uint8_t direction = 0;

		if (n->u.n->byte_num > byte_num)
			break;
		/* Subtle: bit numbers are "backwards" for comparison */
		if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num)
			break;

		if (n->u.n->byte_num < len) {
			uint8_t c = bytes[n->u.n->byte_num];
			direction = (c >> n->u.n->bit_num) & 1;
		}
		n = &n->u.n->child[direction];
	}

	newn->child[!new_dir] = *n;
	n->u.n = newn;
	n->v = NULL;
	return true;
}

void *map_delete(Map *map, const char *key)
{
	size_t len = strlen(key);
	const uint8_t *bytes = (const uint8_t *)key;
	Map *parent = NULL, *n;
	void *value = NULL;
	uint8_t direction;

	/* Empty map? */
	if (!map->u.n) {
		errno = ENOENT;
		return NULL;
	}

	/* Find closest, but keep track of parent. */
	n = map;
	/* Anything with NULL value is a node. */
	while (!n->v) {
		uint8_t c = 0;

		parent = n;
		if (n->u.n->byte_num < len) {
			c = bytes[n->u.n->byte_num];
			direction = (c >> n->u.n->bit_num) & 1;
		} else {
			direction = 0;
		}
		n = &n->u.n->child[direction];
	}

	/* Did we find it? */
	if (strcmp(key, n->u.s)) {
		errno = ENOENT;
		return NULL;
	}

	free((char*)n->u.s);
	value = n->v;

	if (!parent) {
		/* We deleted last node. */
		map->u.n = NULL;
	} else {
		Node *old = parent->u.n;
		/* Raise other node to parent. */
		*parent = old->child[!direction];
		free(old);
	}

	return value;
}

static bool iterate(Map n, bool (*handle)(const char *, void *, void *), const void *data)
{
	if (n.v)
		return handle(n.u.s, n.v, (void *)data);

	return iterate(n.u.n->child[0], handle, data)
		&& iterate(n.u.n->child[1], handle, data);
}

void map_iterate(const Map *map, bool (*handle)(const char *, void *, void *), const void *data)
{
	/* Empty map? */
	if (!map->u.n)
		return;

	iterate(*map, handle, data);
}

typedef struct {
	const char *key;
	void *value;
} KeyValue;

static bool first(const char *key, void *value, void *data)
{
	KeyValue *kv = data;
	kv->key = key;
	kv->value = value;
	return false;
}

void *map_first(const Map *map, const char **key)
{
	KeyValue kv = { 0 };
	map_iterate(map, first, &kv);
	if (key && kv.key)
		*key = kv.key;
	return kv.value;
}

const Map *map_prefix(const Map *map, const char *prefix)
{
	const Map *n, *top;
	size_t len = strlen(prefix);
	const uint8_t *bytes = (const uint8_t *)prefix;

	/* Empty map -> return empty map. */
	if (!map->u.n)
		return map;

	top = n = map;

	/* We walk to find the top, but keep going to check prefix matches. */
	while (!n->v) {
		uint8_t c = 0, direction;

		if (n->u.n->byte_num < len)
			c = bytes[n->u.n->byte_num];

		direction = (c >> n->u.n->bit_num) & 1;
		n = &n->u.n->child[direction];
		if (c)
			top = n;
	}

	if (strncmp(n->u.s, prefix, len)) {
		/* Convenient return for prefixes which do not appear in map. */
		static const Map empty_map;
		return &empty_map;
	}

	return top;
}

bool map_prefix_delete(Map *map, const char *prefix)
{
	bool ret = false;
	do {
		const char *conflict = NULL;
		const Map *conflicts = map_prefix(map, prefix);
		if (!map_first(conflicts, &conflict))
			break;
		ret = map_delete(map, conflict);
	} while (ret);
	return ret;
}

static void clear(Map n)
{
	if (!n.v) {
		clear(n.u.n->child[0]);
		clear(n.u.n->child[1]);
		free(n.u.n);
	} else {
		free((char*)n.u.s);
	}
}

void map_clear(Map *map)
{
	if (map->u.n)
		clear(*map);
	map->u.n = NULL;
	map->v = NULL;
}

static bool copy(Map *dest, Map n)
{
	if (!n.v) {
		return copy(dest, n.u.n->child[0]) &&
		       copy(dest, n.u.n->child[1]);
	} else {
		if (!map_put(dest, n.u.s, n.v) && map_get(dest, n.u.s) != n.v) {
			map_delete(dest, n.u.s);
			return map_put(dest, n.u.s, n.v);
		}
		return true;
	}
}

bool map_copy(Map *dest, Map *src)
{
	if (!src || !src->u.n)
		return true;

	return copy(dest, *src);
}

bool map_empty(const Map *map)
{
	return map->u.n == NULL;
}

Map *map_new(void)
{
	return calloc(1, sizeof(Map));
}

void map_free(Map *map)
{
	if (!map)
		return;
	map_clear(map);
	free(map);
}

static bool free_elem(const char *key, void *value, void *data)
{
	free(value);
	return true;
}

void map_free_full(Map *map)
{
	if (!map)
		return;
	map_iterate(map, free_elem, NULL);
	map_free(map);
}