X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fstrmap%2Fstrmap.c;fp=ccan%2Fstrmap%2Fstrmap.c;h=7d03cca43ad7ff709bdcd9699ac31b5ad74fe309;hb=20f3b260313fb4d5566aeb0d0c5439574e914e2d;hp=0000000000000000000000000000000000000000;hpb=3dda2c8bfc6430ea97cbb3bc1040df2b793dab91;p=ccan

diff --git a/ccan/strmap/strmap.c b/ccan/strmap/strmap.c
new file mode 100644
index 00000000..7d03cca4
--- /dev/null
+++ b/ccan/strmap/strmap.c
@@ -0,0 +1,238 @@
+/* This code is based on ccan/strset.c. */
+#include <ccan/strmap/strmap.h>
+#include <ccan/short_types/short_types.h>
+#include <ccan/str/str.h>
+#include <ccan/ilog/ilog.h>
+#include <assert.h>
+#include <stdlib.h>
+
+struct node {
+	/* These point to strings or nodes. */
+	struct strmap child[2];
+	/* The byte number where first bit differs. */
+	size_t byte_num;
+	/* The bit where these children differ. */
+	u8 bit_num;
+};
+
+/* Closest member to this in a non-empty map. */
+static struct strmap *closest(struct strmap *n, const char *member)
+{
+	size_t len = strlen(member);
+	const u8 *bytes = (const u8 *)member;
+
+	/* Anything with NULL value is a node. */
+	while (!n->v) {
+		u8 direction = 0;
+
+		if (n->u.n->byte_num < len) {
+			u8 c = bytes[n->u.n->byte_num];
+			direction = (c >> n->u.n->bit_num) & 1;
+		}
+		n = &n->u.n->child[direction];
+	}
+	return n;
+}
+
+void *strmap_get_(const struct strmap *map, const char *member)
+{
+	struct strmap *n;
+
+	/* Empty map? */
+	if (!map->u.n)
+		return NULL;
+	n = closest((struct strmap *)map, member);
+	if (streq(member, n->u.s))
+		return n->v;
+	return NULL;
+}
+
+bool strmap_add_(struct strmap *map, const char *member, const void *value)
+{
+	size_t len = strlen(member);
+	const u8 *bytes = (const u8 *)member;
+	struct strmap *n;
+	struct node *newn;
+	size_t byte_num;
+	u8 bit_num, new_dir;
+
+	assert(value);
+
+	/* Empty map? */
+	if (!map->u.n) {
+		map->u.s = member;
+		map->v = (void *)value;
+		return true;
+	}
+
+	/* Find closest existing member. */
+	n = closest(map, member);
+
+	/* Find where they differ. */
+	for (byte_num = 0; n->u.s[byte_num] == member[byte_num]; byte_num++) {
+		if (member[byte_num] == '\0') {
+			/* All identical! */
+			return false;
+		}
+	}
+
+	/* Find which bit differs (if we had ilog8, we'd use it) */
+	bit_num = ilog32_nz((u8)n->u.s[byte_num] ^ bytes[byte_num]) - 1;
+	assert(bit_num < CHAR_BIT);
+
+	/* 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) {
+		/* FIXME */
+		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 = member;
+
+	/* Find where to insert: not closest, but first which differs! */
+	n = map;
+	while (!n->v) {
+		u8 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) {
+			u8 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;
+}
+
+char *strmap_del_(struct strmap *map, const char *member, void **valuep)
+{
+	size_t len = strlen(member);
+	const u8 *bytes = (const u8 *)member;
+	struct strmap *parent = NULL, *n;
+	const char *ret = NULL;
+	u8 direction = 0; /* prevent bogus gcc warning. */
+
+	/* Empty map? */
+	if (!map->u.n)
+		return NULL;
+
+	/* Find closest, but keep track of parent. */
+	n = map;
+	/* Anything with NULL value is a node. */
+	while (!n->v) {
+		u8 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 (!streq(member, n->u.s))
+		return NULL;
+
+	ret = n->u.s;
+	if (valuep)
+		*valuep = n->v;
+
+	if (!parent) {
+		/* We deleted last node. */
+		map->u.n = NULL;
+	} else {
+		struct node *old = parent->u.n;
+		/* Raise other node to parent. */
+		*parent = old->child[!direction];
+		free(old);
+	}
+
+	return (char *)ret;
+}
+
+static bool iterate(struct strmap n,
+		    bool (*handle)(const char *, void *, void *), void *data)
+{
+	if (n.v)
+		return handle(n.u.s, n.v, data);
+
+	return iterate(n.u.n->child[0], handle, data)
+		|| iterate(n.u.n->child[1], handle, data);
+}
+
+void strmap_iterate_(const struct strmap *map,
+		     bool (*handle)(const char *, void *, void *), void *data)
+{
+	/* Empty map? */
+	if (!map->u.n)
+		return;
+
+	iterate(*map, handle, data);
+}
+
+const struct strmap *strmap_prefix_(const struct strmap *map,
+				    const char *prefix)
+{
+	const struct strmap *n, *top;
+	size_t len = strlen(prefix);
+	const u8 *bytes = (const u8 *)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) {
+		u8 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 (!strstarts(n->u.s, prefix)) {
+		/* Convenient return for prefixes which do not appear in map. */
+		static const struct strmap empty_map;
+		return &empty_map;
+	}
+
+	return top;
+}
+
+static void clear(struct strmap n)
+{
+	if (!n.v) {
+		clear(n.u.n->child[0]);
+		clear(n.u.n->child[1]);
+		free(n.u.n);
+	}
+}
+
+void strmap_clear_(struct strmap *map)
+{
+	if (map->u.n)
+		clear(*map);
+	map->u.n = NULL;
+}