path: root/src/map.c

/*
 *	Maps (key-value pairs)
 *	Copyright Jan Engelhardt, 2009
 *
 *	This file is part of libHX. libHX is free software; you can
 *	redistribute it and/or modify it under the terms of the GNU Lesser
 *	General Public License as published by the Free Software Foundation;
 *	either version 2.1 or (at your option) any later version.
 *
 *	Incorporates Public Domain code from Bob Jenkins's lookup3 (May 2006)
 */
#include <errno.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <libHX/list.h>
#include <libHX/map.h>
#include <libHX/string.h>
#include "internal.h"
#include "map_int.h"

typedef void *(*clonefunc_t)(const void *, size_t);

#ifdef NONPRIME_HASH
/*
 * If a hash function is good, it will yield an even distribution even with
 * a non-prime-sized bucket set.
 */
EXPORT_SYMBOL const unsigned int HXhash_primes[] = {
	1 <<  4, 1 <<  5, 1 <<  6,  1 <<  7,
	1 <<  8, 1 <<  9, 1 << 10,  1 << 11,
	1 << 12, 1 << 13, 1 << 14,  1 << 15,
	1 << 16, 1 << 17, 1 << 18,  1 << 19,
	1 << 20, 1 << 21, 1 << 22,  1 << 23,
	1 << 24, 1 << 25, 1 << 26,  1 << 27,
	1 << 28, 1 << 29, 1 << 30, 1U << 31,
};
#else
/*
 * http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 * 23 and 3221.. added by j.eng.
 */
EXPORT_SYMBOL const unsigned int HXhash_primes[] = {
	23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157,
	98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
	25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
	1610612741, 3221225473U,
};
#endif

static void HXhmap_free(struct HXhmap *hmap)
{
	struct HXhmap_node *drop, *dnext;
	unsigned int i;

	for (i = 0; i < HXhash_primes[hmap->power]; ++i) {
		HXlist_for_each_entry_safe(drop, dnext,
		    &hmap->bk_array[i], anchor) {
			if (hmap->super.ops.k_free != NULL)
				hmap->super.ops.k_free(drop->key);
			if (hmap->super.ops.d_free != NULL)
				hmap->super.ops.d_free(drop->data);
			free(drop);
		}
	}

	free(hmap->bk_array);
	free(hmap);
}

static void HXrbtree_free_dive(const struct HXrbtree *btree,
    struct HXrbtree_node *node)
{
	/*
	 * Recursively dives into the tree and destroys elements. Note that you
	 * shall use this when destroying a complete tree instead of iterated
	 * deletion with HXrbtree_del(). Since this functions is meant to free
	 * it all, it does not need to care about rebalancing.
	 */
	if (node->sub[RBT_LEFT] != NULL)
		HXrbtree_free_dive(btree, node->sub[RBT_LEFT]);
	if (node->sub[RBT_RIGHT] != NULL)
		HXrbtree_free_dive(btree, node->sub[RBT_RIGHT]);
	if (btree->super.ops.k_free != NULL)
		btree->super.ops.k_free(node->key);
	if (btree->super.ops.d_free != NULL)
		btree->super.ops.d_free(node->data);
	free(node);
}

static void HXrbtree_free(struct HXrbtree *btree)
{
	if (btree->root != NULL)
		HXrbtree_free_dive(btree, btree->root);
	free(btree);
}

EXPORT_SYMBOL void HXmap_free(struct HXmap *xmap)
{
	void *vmap = xmap;
	const struct HXmap_private *map = vmap;

	switch (map->type) {
	case HXMAPT_HASH:
		return HXhmap_free(vmap);
	case HXMAPT_RBTREE:
		return HXrbtree_free(vmap);
	default:
		break;
	}
}

static int HXmap_valuecmp(const void *pa, const void *pb, size_t len)
{
	/*
	 * Cannot use "pa - pb" as that could underflow.
	 * Also, while "return (pa > pb) - (pa < pb)" does not use a branch,
	 * it compiles to more instructions and seems to be slower on x86.
	 */
	return (pa > pb) ? 1 : (pa < pb) ? -1 : 0;
}

static void *HXmap_valuecpy(const void *p, size_t len)
{
	return const_cast1(void *, p);
}

#define jrot(x,k) (((x) << (k)) | ((x) >> (32 - (k))))

EXPORT_SYMBOL unsigned long HXhash_jlookup3(const void *vkey, size_t length)
{
	static const unsigned int JHASH_GOLDEN_RATIO = 0x9e3779b9;
	const uint8_t *key = vkey;
	uint32_t a, b, c;

	a = b = c = JHASH_GOLDEN_RATIO + length;
	/* All but the last block: affect some 32 bits of (a,b,c) */
	for (; length > 12; length -= 12, key += 12) {
		a += key[0] + ((uint32_t)key[1] << 8) +
		     ((uint32_t)key[2] << 16) + ((uint32_t)key[3] << 24);
		b += key[4] + ((uint32_t)key[5] << 8) +
		     ((uint32_t)key[6] << 16) + ((uint32_t)key[7] << 24);
		c += key[8] + ((uint32_t)key[9] << 8) +
		     ((uint32_t)key[10] << 16)+ ((uint32_t)key[11] << 24);
		/* jhash_mix - mix 3 32-bit values reversibly. */
		a -= c; a ^= jrot(c,  4); c += b;
		b -= a; b ^= jrot(a,  6); a += c;
		c -= b; c ^= jrot(b,  8); b += a;
		a -= c; a ^= jrot(c, 16); c += b;
		b -= a; b ^= jrot(a, 19); a += c;
		c -= b; c ^= jrot(b,  4); b += a;
	}

	switch (length) {
	case 12: c += ((uint32_t)key[11]) << 24;
	case 11: c += ((uint32_t)key[10]) << 16;
	case 10: c += ((uint32_t)key[9])  << 8;
	case  9: c += key[8];
	case  8: b += ((uint32_t)key[7]) << 24;
	case  7: b += ((uint32_t)key[6]) << 16;
	case  6: b += ((uint32_t)key[5]) << 8;
	case  5: b += key[4];
	case  4: a += ((uint32_t)key[3]) << 24;
	case  3: a += ((uint32_t)key[2]) << 16;
	case  2: a += ((uint32_t)key[1]) << 8;
	case  1: a += key[0];
		break;
	case  0: return c;
	}
	/* jhash_final */
	c ^= b; c -= jrot(b, 14);
	a ^= c; a -= jrot(c, 11);
	b ^= a; b -= jrot(a, 25);
	c ^= b; c -= jrot(b, 16);
	a ^= c; a -= jrot(c,  4);
	b ^= a; b -= jrot(a, 14);
	c ^= b; c -= jrot(b, 24);
	return c;
}

static unsigned long HXhash_jlookup3v(const void *p, size_t z)
{
	return HXhash_jlookup3(&p, sizeof(p));
}

EXPORT_SYMBOL unsigned long HXhash_jlookup3s(const void *p, size_t z)
{
	return HXhash_jlookup3(p, strlen(p));
}

EXPORT_SYMBOL unsigned long HXhash_djb2(const void *p, size_t z)
{
	const char *c = p;
	unsigned long v = 5381;

	while (*c != '\0')
		v = ((v << 5) + v) ^ *c++;
		/* v = v * 33 ^ *c++; */

	return v;
}

/**
 * Set up the operations for a map based on flags, and then override with
 * user-specified functions.
 */
static void HXmap_ops_setup(struct HXmap_private *super,
    const struct HXmap_ops *new_ops)
{
	struct HXmap_ops *ops = &super->ops;

	ops->k_clone = HXmap_valuecpy;
	ops->d_clone = HXmap_valuecpy;

	if (super->flags & HXMAP_SKEY)
		ops->k_compare = static_cast(void *, strcmp);
	else if (super->key_size == 0)
		ops->k_compare = HXmap_valuecmp;
	else
		ops->k_compare = memcmp;

	if (super->flags & HXMAP_CKEY) {
		ops->k_clone = (super->flags & HXMAP_SKEY) ?
		               reinterpret_cast(clonefunc_t, HX_strdup) :
		               HX_memdup;
		ops->k_free  = free;
	}
	if (super->flags & HXMAP_CDATA) {
		ops->d_clone = (super->flags & HXMAP_SDATA) ?
		               reinterpret_cast(clonefunc_t, HX_strdup) :
		               HX_memdup;
		ops->d_free  = free;
	}

	if (super->type == HXMAPT_HASH) {
		if (super->flags & HXMAP_SKEY)
			ops->k_hash = HXhash_djb2;
		else if (super->key_size != 0)
			ops->k_hash = HXhash_jlookup3;
		else
			ops->k_hash = HXhash_jlookup3v;
	}

	if (new_ops == NULL)
		return;

	/* Update with user-supplied functions */
	if (new_ops->k_compare != NULL)
		ops->k_compare = new_ops->k_compare;
	if (new_ops->k_clone != NULL)
		ops->k_clone   = new_ops->k_clone;
	if (new_ops->k_free != NULL)
		ops->k_free    = new_ops->k_free;
	if (new_ops->d_clone != NULL)
		ops->d_clone   = new_ops->d_clone;
	if (new_ops->d_free != NULL)
		ops->d_free    = new_ops->d_free;
	if (super->type == HXMAPT_HASH && new_ops->k_hash != NULL)
		ops->k_hash    = new_ops->k_hash;
}

/**
 * @n:	nominator of fraction
 * @d:	denominator of fraction
 * @v:	value
 *
 * Calculates @v * (@n / @d) without floating point or risk of overflow
 * (when @n <= @d).
 */
static __inline__ unsigned int
x_frac(unsigned int n, unsigned int d, unsigned int v)
{
	return (v / d) * n + (v % d) * n / d;
}

/**
 * HXhmap_move - move elements from one map to another
 * @bk_array:	target bucket array
 * @bk_number:	number of buckets
 * @hmap:	old hash table
 */
static void HXhmap_move(struct HXlist_head *bk_array, unsigned int bk_number,
    struct HXhmap *hmap)
{
	struct HXhmap_node *drop, *dnext;
	unsigned int bk_idx, i;

#ifdef NONPRIME_HASH
	--bk_number;
#endif
	for (i = 0; i < HXhash_primes[hmap->power]; ++i)
		HXlist_for_each_entry_safe(drop, dnext,
		    &hmap->bk_array[i], anchor) {
#ifdef NONPRIME_HASH
			bk_idx = hmap->super.ops.k_hash(drop->key,
			         hmap->super.key_size) & bk_number;
#else
			bk_idx = hmap->super.ops.k_hash(drop->key,
			         hmap->super.key_size) % bk_number;
#endif
			HXlist_del(&drop->anchor);
			HXlist_add_tail(&bk_array[bk_idx], &drop->anchor);
		}
}

/**
 * HXhmap_layout - resize and rehash table
 * @hmap:	hash map
 * @prime_idx:	requested new table size (prime power thereof)
 */
static int HXhmap_layout(struct HXhmap *hmap, unsigned int power)
{
	const unsigned int bk_number = HXhash_primes[power];
	struct HXlist_head *bk_array, *old_array = NULL;
	unsigned int i;

	bk_array = malloc(bk_number * sizeof(*bk_array));
	if (bk_array == NULL)
		return -errno;
	for (i = 0; i < bk_number; ++i)
		HXlist_init(&bk_array[i]);
	if (hmap->bk_array != NULL) {
		HXhmap_move(bk_array, bk_number, hmap);
		old_array = hmap->bk_array;
		/*
		 * It is ok to increment the TID this late. @map->bk_array is
		 * only emptied, and the new @bk_array is not yet visible to
		 * traversers, so no elements appear twice.
		 */
		++hmap->tid;
	}
	hmap->power    = power;
	hmap->min_load = (power != 0) ? HXhash_primes[power] / 4 : 0;
	hmap->max_load = x_frac(7, 10, HXhash_primes[power]);
	hmap->bk_array = bk_array;
	free(old_array);
	return 1;
}

static struct HXmap *HXhashmap_init4(unsigned int flags,
    const struct HXmap_ops *ops, size_t key_size, size_t data_size)
{
	struct HXmap_private *super;
	struct HXhmap *hmap;
	int saved_errno;

	if ((hmap = calloc(1, sizeof(*hmap))) == NULL)
		return NULL;

	super            = &hmap->super;
	super->flags     = flags;
	super->items     = 0;
	super->type      = HXMAPT_HASH;
	super->key_size  = key_size;
	super->data_size = data_size;
	HXmap_ops_setup(super, ops);
	hmap->tid = 1;
	errno = HXhmap_layout(hmap, 0);
	if (hmap->bk_array == NULL)
		goto out;

	errno = 0;
	return static_cast(void *, hmap);

 out:
	saved_errno = errno;
	HXhmap_free(hmap);
	errno = saved_errno;
	return NULL;
}

static struct HXmap *HXrbtree_init4(unsigned int flags,
    const struct HXmap_ops *ops, size_t key_size, size_t data_size)
{
	struct HXmap_private *super;
	struct HXrbtree *btree;

	BUILD_BUG_ON(offsetof(struct HXrbtree, root) +
	             offsetof(struct HXrbtree_node, sub[0]) !=
	             offsetof(struct HXrbtree, root));

	if ((btree = calloc(1, sizeof(*btree))) == NULL)
		return NULL;

	super            = &btree->super;
	super->type      = HXMAPT_RBTREE;
	super->flags     = flags;
	super->items     = 0;
	super->key_size  = key_size;
	super->data_size = data_size;
	HXmap_ops_setup(super, ops);

	/*
	 * TID must not be zero, otherwise the traverser functions will not
	 * start off correctly, since trav->tid is 0, but trav->tid must not
	 * equal btree->transact because that would mean the traverser is in
	 * sync with the tree.
	 */
	btree->tid  = 1;
	btree->root = NULL;
	return static_cast(void *, btree);
}

EXPORT_SYMBOL struct HXmap *HXmap_init5(enum HXmap_type type,
    unsigned int flags, const struct HXmap_ops *ops, size_t key_size,
    size_t data_size)
{
	if ((flags & HXMAP_SINGULAR) &&
	    (flags & (HXMAP_CDATA | HXMAP_SDATA) || data_size != 0))
		fprintf(stderr, "WARNING: libHX-map: When HXMAP_SINGULAR is "
		        "set, HXMAP_CDATA, HXMAP_SDATA and/or data_size != 0 "
		        "has no effect.\n");

	switch (type) {
	case HXMAPT_HASH:
		return HXhashmap_init4(flags, ops, key_size, data_size);
	case HXMAPT_RBTREE:
		return HXrbtree_init4(flags, ops, key_size, data_size);
	default:
		errno = -ENOENT;
		return NULL;
	}
}

EXPORT_SYMBOL struct HXmap *HXmap_init(enum HXmap_type type,
    unsigned int flags)
{
	/*
	 * We cannot check this in HXmap_init5, since a custom ops may
	 * allow key_size==0/data_size==0.
	 */
	if ((flags & HXMAP_SCKEY) == HXMAP_CKEY) {
		fprintf(stderr, "%s: zero key_size with standard memcpy ops "
		        "won't work.\n", __func__);
		errno = EINVAL;
		return NULL;
	}
	if ((flags & HXMAP_SCDATA) == HXMAP_CDATA) {
		fprintf(stderr, "%s: zero data_size with standard memcpy ops "
		        "won't work.\n", __func__);
		errno = EINVAL;
		return NULL;
	}
	return HXmap_init5(type, flags, NULL, 0, 0);
}

static struct HXhmap_node *HXhmap_find(const struct HXhmap *hmap,
    const void *key)
{
	struct HXhmap_node *drop;
	unsigned int bk_idx;

#ifdef NONPRIME_HASH
	bk_idx = hmap->super.ops.k_hash(key, hmap->super.key_size) &
	         (HXhash_primes[hmap->power] - 1);
#else
	bk_idx = hmap->super.ops.k_hash(key, hmap->super.key_size) %
	         HXhash_primes[hmap->power];
#endif
	HXlist_for_each_entry(drop, &hmap->bk_array[bk_idx], anchor)
		if (hmap->super.ops.k_compare(key, drop->key,
		    hmap->super.key_size) == 0)
			return drop;
	return NULL;
}

static const struct HXmap_node *HXrbtree_find(const struct HXrbtree *btree,
    const void *key)
{
	struct HXrbtree_node *node = btree->root;
	int res;

	while (node != NULL) {
		if ((res = btree->super.ops.k_compare(key,
		    node->key, btree->super.key_size)) == 0)
			return static_cast(const void *, &node->key);
		node = node->sub[res > 0];
	}

	return NULL;
}

EXPORT_SYMBOL const struct HXmap_node *
HXmap_find(const struct HXmap *xmap, const void *key)
{
	const void *vmap = xmap;
	const struct HXmap_private *map = vmap;

	switch (map->type) {
	case HXMAPT_HASH: {
		const struct HXhmap_node *node = HXhmap_find(vmap, key);
		if (node == NULL)
			return NULL;
		return static_cast(const void *, &node->key);
	}
	case HXMAPT_RBTREE:
		return HXrbtree_find(vmap, key);
	default:
		errno = EINVAL;
		return NULL;
	}
}

EXPORT_SYMBOL void *HXmap_get(const struct HXmap *map, const void *key)
{
	const struct HXmap_node *node;

	if ((node = HXmap_find(map, key)) == NULL) {
		errno = ENOENT;
		return NULL;
	}
	errno = 0;
	return node->data;
}

/**
 * HXhmap_replace - replace value in a drop
 */
static int HXhmap_replace(const struct HXhmap *hmap, struct HXhmap_node *drop,
    const void *value)
{
	void *old_value, *new_value;

	if (hmap->super.flags & HXMAP_NOREPLACE)
		return -EEXIST;

	new_value = hmap->super.ops.d_clone(value, hmap->super.data_size);
	if (new_value == NULL && value != NULL)
		return -errno;
	old_value  = drop->data;
	drop->data = new_value;
	if (hmap->super.ops.d_free != NULL)
		hmap->super.ops.d_free(old_value);
	return 1;
}

static int HXhmap_add(struct HXhmap *hmap, const void *key, const void *value)
{
	struct HXhmap_node *drop;
	unsigned int bk_idx;
	int ret, saved_errno;

	if ((drop = HXhmap_find(hmap, key)) != NULL)
		return HXhmap_replace(hmap, drop, value);

	if (hmap->super.items >= hmap->max_load &&
	    hmap->power < ARRAY_SIZE(HXhash_primes) - 1) {
		if ((ret = HXhmap_layout(hmap, hmap->power + 1)) <= 0)
			return ret;
	} else if (hmap->super.items < hmap->min_load && hmap->power > 0) {
		if ((ret = HXhmap_layout(hmap, hmap->power - 1)) <= 0)
			return ret;
	}

	/* New node */
	if ((drop = malloc(sizeof(*drop))) == NULL)
		return -errno;
	HXlist_init(&drop->anchor);
	drop->key = hmap->super.ops.k_clone(key, hmap->super.key_size);
	if (drop->key == NULL && key != NULL)
		goto out;
	drop->data = hmap->super.ops.d_clone(value, hmap->super.data_size);
	if (drop->data == NULL && value != NULL)
		goto out;

#ifdef NONPRIME_HASH
	bk_idx = hmap->super.ops.k_hash(key, hmap->super.key_size) &
	         (HXhash_primes[hmap->power] - 1);
#else
	bk_idx = hmap->super.ops.k_hash(key, hmap->super.key_size) %
	         HXhash_primes[hmap->power];
#endif
	HXlist_add_tail(&hmap->bk_array[bk_idx], &drop->anchor);
	++hmap->super.items;
	return 1;

 out:
	saved_errno = errno;
	if (hmap->super.ops.k_free != NULL)
		hmap->super.ops.k_free(drop->key);
	free(drop);
	return -(errno = saved_errno);
}

/**
 * HXrbtree_amov - do balance (move) after addition of a node
 * @path:	path from the root to the new node
 * @dir:	direction vectors
 * @depth:	current index in @path and @dir
 * @tid:	pointer to transaction ID which may need updating
 */
static void HXrbtree_amov(struct HXrbtree_node **path,
    const unsigned char *dir, unsigned int depth, unsigned int *tid)
{
	struct HXrbtree_node *uncle, *parent, *grandp, *newnode;

	/*
	 * The newly inserted node (or the last rebalanced node) at
	 * @path[depth-1] is red, so the parent must not be.
	 *
	 * Use an iterative approach to not waste time with recursive function
	 * calls. The @LR variable is used to handle the symmetric case without
	 * code duplication.
	 */
	do {
		unsigned int LR = dir[depth-2];

		grandp = path[depth-2];
		parent = path[depth-1];
		uncle  = grandp->sub[!LR];

		if (uncle != NULL && uncle->color == RBT_RED) {
			/*
			 * Case 3 (WP): Only colors have to be swapped to keep
			 * the black height. But rebalance needs to continue.
			 */
			parent->color = RBT_BLACK;
			uncle->color  = RBT_BLACK;
			grandp->color = RBT_RED;
			depth        -= 2;
			continue;
		}

		/*
		 * Case 4 (WP): New node is the right child of its parent, and
		 * the parent is the left child of the grandparent. A left
		 * rotate is done at the parent to transform it into a case 5.
		 */
		if (dir[depth-1] != LR) {
			newnode          = parent->sub[!LR];
			parent->sub[!LR] = newnode->sub[LR];
			newnode->sub[LR] = parent;
			grandp->sub[LR]  = newnode;
			/* relabel */
			parent  = grandp->sub[LR];
			/* unused assignment: newnode = parent->sub[LR]; */
		} else {
			/* unused assignment: newnode = path[depth]; */
		}

		/*
		 * Case 5: New node is the @LR child of its parent which is
		 * the @LR child of the grandparent. A right rotation on
		 * @grandp is performed.
		 */
		grandp->sub[LR]  = parent->sub[!LR];
		parent->sub[!LR] = grandp;
		path[depth-3]->sub[dir[depth-3]] = parent;
		grandp->color    = RBT_RED;
		parent->color    = RBT_BLACK;
		++*tid;
		break;
	} while (depth >= 3 && path[depth-1]->color == RBT_RED);
}

static int HXrbtree_replace(const struct HXrbtree *btree,
    struct HXrbtree_node *node, const void *value)
{
	void *old_value, *new_value;

	if (!(btree->super.flags & HXMAP_NOREPLACE))
		return -(errno = EEXIST);

	new_value = btree->super.ops.d_clone(value, btree->super.data_size);
	if (new_value == NULL && value != NULL)
		return -errno;
	old_value  = node->data;
	node->data = new_value;
	if (btree->super.ops.d_free != NULL)
		btree->super.ops.d_free(old_value);
	return 1;
}

static int HXrbtree_add(struct HXrbtree *btree,
    const void *key, const void *value)
{
	struct HXrbtree_node *node, *path[RBT_MAXDEP];
	unsigned char dir[RBT_MAXDEP];
	unsigned int depth = 0;
	int saved_errno;

	/*
	 * Since our struct HXrbtree_node runs without a ->parent pointer,
	 * the path "upwards" from @node needs to be recorded somehow,
	 * here with @path. Another array, @dir is used to speedup direction
	 * decisions. (WP's "n->parent == grandparent(n)->left" is just slow.)
	 */
	path[depth]  = reinterpret_cast(struct HXrbtree_node *, &btree->root);
	dir[depth++] = 0;
	node = btree->root;

	while (node != NULL) {
		int res = btree->super.ops.k_compare(key,
		          node->key, btree->super.key_size);
		if (res == 0)
			/*
			 * The node already exists (found the key), overwrite
			 * the data.
			 */
			return HXrbtree_replace(btree, node, value);

		res          = res > 0;
		path[depth]  = node;
		dir[depth++] = res;
		node         = node->sub[res];
	}

	if ((node = malloc(sizeof(struct HXrbtree_node))) == NULL)
		return -errno;

	/* New node, push data into it */
	node->key = btree->super.ops.k_clone(key, btree->super.key_size);
	if (node->key == NULL && key != NULL)
		goto out;
	node->data = btree->super.ops.d_clone(value, btree->super.data_size);
	if (node->data == NULL && value != NULL)
		goto out;

	/*
	 * Add the node to the tree. In trying not to hit a rule 2 violation
	 * (each simple path has the same number of black nodes), it is colored
	 * red so that below we only need to check for rule 1 violations.
	 */
	node->sub[RBT_LEFT] = node->sub[RBT_RIGHT] = NULL;
	node->color = RBT_RED;
	path[depth-1]->sub[dir[depth-1]] = node;
	++btree->super.items;

	/*
	 * WP: [[Red-black_tree]] says:
	 * Case 1: @node is root node - just color it black (see below).
	 * Case 2: @parent is black - no action needed (skip).
	 * No rebalance needed for a 2-node tree.
	 */
	if (depth >= 3 && path[depth-1]->color == RBT_RED)
		HXrbtree_amov(path, dir, depth, &btree->tid);

	btree->root->color = RBT_BLACK;
	return 1;

 out:
	saved_errno = errno;
	if (btree->super.ops.k_free != NULL)
		btree->super.ops.k_free(node->key);
	if (btree->super.ops.d_free != NULL)
		btree->super.ops.d_free(node->key);
	free(node);
	return -(errno = saved_errno);
}

EXPORT_SYMBOL int HXmap_add(struct HXmap *xmap,
    const void *key, const void *value)
{
	void *vmap = xmap;
	struct HXmap_private *map = vmap;

	if ((map->flags & HXMAP_SINGULAR) && value != NULL) {
		fprintf(stderr, "libHX-map: adding value!=NULL "
		        "into a set not allowed\n");
		return -EINVAL;
	}

	switch (map->type) {
	case HXMAPT_HASH:
		return HXhmap_add(vmap, key, value);
	case HXMAPT_RBTREE:
		return HXrbtree_add(vmap, key, value);
	default:
		return -EINVAL;
	}
}

static void *HXhmap_del(struct HXhmap *hmap, const void *key)
{
	struct HXhmap_node *drop;
	void *value;

	if ((drop = HXhmap_find(hmap, key)) == NULL) {
		errno = ENOENT;
		return NULL;
	}

	HXlist_del(&drop->anchor);
	++hmap->tid;
	--hmap->super.items;
	if (hmap->super.items < hmap->min_load && hmap->power > 0)
		/*
		 * Ignore return value. If it failed, it will continue to use
		 * the current bk_array.
		 */
		HXhmap_layout(hmap, hmap->power - 1);

	value = drop->data;
	if (hmap->super.ops.k_free != NULL)
		hmap->super.ops.k_free(drop->key);
	if (hmap->super.ops.d_free != NULL)
		hmap->super.ops.d_free(drop->data);
	free(drop);
	errno = 0;
	return value;
}

static unsigned int HXrbtree_del_mm(struct HXrbtree_node **path,
    unsigned char *dir, unsigned int depth)
{
	/* Both subtrees exist */
	struct HXrbtree_node *io_node, *io_parent, *orig_node = path[depth];
	unsigned char color;
	unsigned int spos;

	io_node    = orig_node->sub[RBT_RIGHT];
	dir[depth] = RBT_RIGHT;

	if (io_node->sub[RBT_LEFT] == NULL) {
		/* Right subtree node is direct inorder */
		io_node->sub[RBT_LEFT] = orig_node->sub[RBT_LEFT];
		color                = io_node->color;
		io_node->color       = orig_node->color;
		orig_node->color     = color;

		path[depth-1]->sub[dir[depth-1]] = io_node;
		path[depth++]        = io_node;
		return depth;
	}

	/*
	 * Walk down to the leftmost element, keep track of inorder node
	 * and its parent.
	 */
	spos = depth++;

	do {
		io_parent    = io_node;
		path[depth]  = io_parent;
		dir[depth++] = RBT_LEFT;
		io_node      = io_parent->sub[RBT_LEFT];
	} while (io_node->sub[RBT_LEFT] != NULL);

	/* move node up */
	path[spos-1]->sub[dir[spos-1]] = path[spos] = io_node;
	io_parent->sub[RBT_LEFT]         = io_node->sub[RBT_RIGHT];
	io_node->sub[RBT_LEFT]           = orig_node->sub[RBT_LEFT];
	io_node->sub[RBT_RIGHT]          = orig_node->sub[RBT_RIGHT];

	color          = io_node->color;
	io_node->color = orig_node->color;

	/*
	 * The nodes (@io_node and @orig_node) have been swapped. While
	 * @orig_node has no pointers to it, it still exists and decisions are
	 * made upon its properties in HXrbtree_del() and btree_dmov() until it
	 * is freed later. Hence we need to keep the color.
	 */
	orig_node->color = color;
	return depth;
}

static void HXrbtree_dmov(struct HXrbtree_node **path, unsigned char *dir,
    unsigned int depth)
{
	struct HXrbtree_node *w, *x;

	while (true) {
		unsigned char LR = dir[depth - 1];
		x = path[depth - 1]->sub[LR];

		if (x != NULL && x->color == RBT_RED) {
			/* (WP) "delete_one_child" */
			x->color = RBT_BLACK;
			break;
		}

		if (depth < 2)
			/* Case 1 */
			break;

		/* @w is the sibling of @x (the current node). */
		w = path[depth - 1]->sub[!LR];
		if (w->color == RBT_RED) {
			/*
			 * Case 2. @w is of color red. In order to collapse
			 * cases, a left rotate is performed at @x's parent and
			 * colors are swapped to make @w a black node.
			 */
			w->color = RBT_BLACK;
			path[depth - 1]->color = RBT_RED;
			path[depth - 1]->sub[!LR] = w->sub[LR];
			w->sub[LR] = path[depth - 1];
			path[depth - 2]->sub[dir[depth - 2]] = w;
			path[depth] = path[depth - 1];
			dir[depth]  = LR;
			path[depth - 1] = w;
			w = path[++depth - 1]->sub[!LR];
		}

		if ((w->sub[LR] == NULL || w->sub[LR]->color == RBT_BLACK) &&
		   (w->sub[!LR] == NULL || w->sub[!LR]->color == RBT_BLACK)) {
			/* Case 3/4: @w has no red children. */
			w->color = RBT_RED;
			--depth;
			continue;
		}

		if (w->sub[!LR] == NULL || w->sub[!LR]->color == RBT_BLACK) {
			/* Case 5 */
			struct HXrbtree_node *y = w->sub[LR];
			y->color = RBT_BLACK;
			w->color = RBT_RED;
			w->sub[LR] = y->sub[!LR];
			y->sub[!LR] = w;
			w = path[depth - 1]->sub[!LR] = y;
		}

		/* Case 6 */
		w->color = path[depth - 1]->color;
		path[depth - 1]->color = RBT_BLACK;
		w->sub[!LR]->color = RBT_BLACK;
		path[depth - 1]->sub[!LR] = w->sub[LR];
		w->sub[LR] = path[depth - 1];
		path[depth - 2]->sub[dir[depth - 2]] = w;
		break;
	}
}

static void *HXrbtree_del(struct HXrbtree *btree, const void *key)
{
	struct HXrbtree_node *path[RBT_MAXDEP], *node;
	unsigned char dir[RBT_MAXDEP];
	unsigned int depth = 0;
	void *itemptr;

	if (btree->root == NULL)
		return NULL;

	path[depth]  = reinterpret_cast(struct HXrbtree_node *, &btree->root);
	dir[depth++] = 0;
	node         = btree->root;

	while (node != NULL) {
		int res = btree->super.ops.k_compare(key,
		          node->key, btree->super.key_size);
		if (res == 0)
			break;
		res          = res > 0;
		path[depth]  = node;
		dir[depth++] = res;
		node         = node->sub[res];
	}

	if (node == NULL) {
		errno = ENOENT;
		return NULL;
	}

	/*
	 * Return the data for the node. But it is not going to be useful
	 * if ARBtree was directed to copy it (because it will be released
	 * below.)
	 */
	itemptr = node->data;
	/* Removal of the node from the tree */
	--btree->super.items;
	++btree->tid;

	path[depth] = node;
	if (node->sub[RBT_RIGHT] == NULL)
		/* Simple case: No right subtree, replace by left subtree. */
		path[depth-1]->sub[dir[depth-1]] = node->sub[RBT_LEFT];
	else if (node->sub[RBT_LEFT] == NULL)
		/* Simple case: No left subtree, replace by right subtree. */
		path[depth-1]->sub[dir[depth-1]] = node->sub[RBT_RIGHT];
	else
		/*
		 * Find minimum/maximum element in right/left subtree and
		 * do appropriate deletion while updating @path and @depth.
		 */
		depth = HXrbtree_del_mm(path, dir, depth);

	/*
	 * Deleting a red node does not violate either of the rules, so it is
	 * not necessary to rebalance in such a case.
	 */
	if (node->color == RBT_BLACK)
		HXrbtree_dmov(path, dir, depth);

	if (btree->super.ops.k_free != NULL)
		btree->super.ops.k_free(node->key);
	if (btree->super.ops.d_free != NULL)
		btree->super.ops.d_free(node->data);
	free(node);
	errno = 0;
	/*
	 * In case %HXBT_CDATA was specified, the @itemptr value will be
	 * useless in most cases as it points to freed memory.
	 */
	return itemptr;
}

EXPORT_SYMBOL void *HXmap_del(struct HXmap *xmap, const void *key)
{
	void *vmap = xmap;
	struct HXmap_private *map = vmap;

	switch (map->type) {
	case HXMAPT_HASH:
		return HXhmap_del(vmap, key);
	case HXMAPT_RBTREE:
		return HXrbtree_del(vmap, key);
	default:
		errno = EINVAL;
		return NULL;
	}
}

static void HXhmap_keysvalues(const struct HXhmap *hmap,
    struct HXmap_node *array)
{
	const struct HXhmap_node *node;
	unsigned int i;

	for (i = 0; i < HXhash_primes[hmap->power]; ++i)
		HXlist_for_each_entry(node, &hmap->bk_array[i], anchor) {
			array->key  = node->key;
			array->data = node->data;
			++array;
		}
}

static struct HXmap_node *HXrbtree_keysvalues(const struct HXrbtree_node *node,
    struct HXmap_node *array)
{
	if (node->sub[0] != NULL)
		array = HXrbtree_keysvalues(node->sub[0], array);
	array->key  = node->key;
	array->data = node->data;
	++array;
	if (node->sub[1] != NULL)
		array = HXrbtree_keysvalues(node->sub[1], array);
	return array;
}

EXPORT_SYMBOL struct HXmap_node *HXmap_keysvalues(const struct HXmap *xmap)
{
	const void *vmap = xmap;
	const struct HXmap_private *map = vmap;
	struct HXmap_node *array;

	switch (map->type) {
	case HXMAPT_HASH:
	case HXMAPT_RBTREE:
		break;
	default:
		errno = EINVAL;
		return NULL;
	}

	if ((array = malloc(sizeof(*array) * map->items)) == NULL)
		return NULL;

	switch (map->type) {
	case HXMAPT_HASH:
		HXhmap_keysvalues(vmap, array);
		break;
	case HXMAPT_RBTREE:
		HXrbtree_keysvalues(
			static_cast(const struct HXrbtree *, vmap)->root,
			array);
		break;
	}
	return array;
}

static void *HXhmap_travinit(const struct HXhmap *hmap, unsigned int flags)
{
	struct HXhmap_trav *trav;

	if ((trav = malloc(sizeof(*trav))) == NULL)
		return NULL;
	/* We cannot offer DTRAV. */
	trav->super.flags = flags & ~HXMAP_DTRAV;
	trav->super.type = HXMAPT_HASH;
	trav->hmap = hmap;
	trav->head = NULL;
	trav->bk_current = 0;
	trav->tid = hmap->tid;
	return trav;
}

static void *HXrbtrav_init(const struct HXrbtree *btree, unsigned int flags)
{
	struct HXrbtrav *trav;

	if ((trav = calloc(1, sizeof(*trav))) == NULL)
		return NULL;
	trav->super.flags = flags;
	trav->super.type = HXMAPT_RBTREE;
	trav->tree = btree;
	return trav;
}

EXPORT_SYMBOL struct HXmap_trav *HXmap_travinit(const struct HXmap *xmap,
    unsigned int flags)
{
	const void *vmap = xmap;
	const struct HXmap_private *map = vmap;

	switch (map->type) {
	case HXMAPT_HASH:
		return HXhmap_travinit(vmap, flags);
	case HXMAPT_RBTREE:
		return HXrbtrav_init(vmap, flags);
	default:
		errno = EINVAL;
		return NULL;
	}
}

static const struct HXmap_node *HXhmap_traverse(struct HXhmap_trav *trav)
{
	const struct HXhmap *hmap = trav->hmap;
	const struct HXhmap_node *drop;

	if (trav->head == NULL) {
		trav->head = hmap->bk_array[trav->bk_current].next;
	} else if (trav->tid != hmap->tid) {
		if (trav->bk_current >= HXhash_primes[hmap->power])
			/* bk_array shrunk underneath us, we're done */
			return NULL;
		/*
		 * Reset head so that the while loop will be entered and we
		 * advance to the next bucket.
		 */
		trav->head = &hmap->bk_array[trav->bk_current];
		trav->tid  = hmap->tid;
	} else {
		trav->head = trav->head->next;
	}

	while (trav->head == &hmap->bk_array[trav->bk_current]) {
		if (++trav->bk_current >= HXhash_primes[hmap->power])
			return false;
		trav->head = hmap->bk_array[trav->bk_current].next;
	}

	drop = HXlist_entry(trav->head, struct HXhmap_node, anchor);
	return static_cast(const void *, &drop->key);
}

static void HXrbtrav_checkpoint(struct HXrbtrav *trav,
    const struct HXrbtree_node *node)
{
	const struct HXrbtree *tree = trav->tree;

	if (tree->super.flags & HXMAP_DTRAV) {
		void *old_key = trav->checkpoint;

		trav->checkpoint = tree->super.ops.k_clone(node->key,
		                   tree->super.key_size);
		if (tree->super.ops.k_free != NULL)
			tree->super.ops.k_free(old_key);
	} else {
		trav->checkpoint = node->key;
	}
}

static struct HXrbtree_node *HXrbtrav_next(struct HXrbtrav *trav)
{
	if (trav->current->sub[RBT_RIGHT] != NULL) {
		/* Got a right child */
		struct HXrbtree_node *node;

		trav->dir[trav->depth++] = RBT_RIGHT;
		node = trav->current->sub[RBT_RIGHT];

		/* Which might have left childs (our inorder successors!) */
		while (node != NULL) {
			trav->path[trav->depth] = node;
			node = node->sub[RBT_LEFT];
			trav->dir[trav->depth++] = RBT_LEFT;
		}
		trav->current = trav->path[--trav->depth];
	} else if (trav->depth == 0) {
		/* No right child, no more parents */
		return trav->current = NULL;
	} else if (trav->dir[trav->depth-1] == RBT_LEFT) {
		/* We are the left child of the parent, move on to parent */
		trav->current = trav->path[--trav->depth];
	} else if (trav->dir[trav->depth-1] == RBT_RIGHT) {
		/*
		 * There is no right child, and we are the right child of the
		 * parent, so move on to the next inorder node (a distant
		 * parent). This works by walking up the path until we are the
		 * left child of a parent.
		 */
		while (true) {
			if (trav->depth == 0)
				/* No more parents */
				return trav->current = NULL;
			if (trav->dir[trav->depth-1] != RBT_RIGHT)
				break;
			--trav->depth;
		}
		trav->current = trav->path[--trav->depth];
	}

	HXrbtrav_checkpoint(trav, trav->current);
	return trav->current;
}

static struct HXrbtree_node *HXrbtrav_rewalk(struct HXrbtrav *trav)
{
	/*
	 * When the binary tree has been distorted (or the traverser is
	 * uninitilaized), by either addition or deletion of an object, our
	 * path recorded so far is (probably) invalid too. rewalk() will go and
	 * find the node we were last at.
	 */
	const struct HXrbtree *btree = trav->tree;
	struct HXrbtree_node *node   = btree->root;
	bool go_next = false;

	trav->depth = 0;

	if (trav->current == NULL) {
		/* Walk down the tree to the smallest element */
		while (node != NULL) {
			trav->path[trav->depth] = node;
			node = node->sub[RBT_LEFT];
			trav->dir[trav->depth++] = RBT_LEFT;
		}
	} else {
		/* Search for the specific node to rebegin traversal at. */
		const struct HXrbtree_node *newpath[RBT_MAXDEP];
		unsigned char newdir[RBT_MAXDEP];
		int newdepth = 0, res;
		bool found = false;

		while (node != NULL) {
			newpath[newdepth] = trav->path[trav->depth] = node;
			res = btree->super.ops.k_compare(trav->checkpoint,
			      node->key, btree->super.key_size);
			if (res == 0) {
				++trav->depth;
				found = true;
				break;
			}
			res = res > 0;
			trav->dir[trav->depth++] = res;

			/*
			 * This (working) code gets 1st place in being totally
			 * cryptic without comments, so here goes:
			 *
			 * Right turns do not need to be saved, because we do
			 * not need to stop at that particular node again but
			 * can go directly to the next in-order successor,
			 * which must be a parent somewhere upwards where we
			 * did a left turn. If we only ever did right turns,
			 * we would be at the last node already.
			 *
			 * Imagine a 32-element perfect binary tree numbered
			 * from 1..32, and walk to 21 (directions: RLRL).
			 * The nodes stored are 24 and 22. btrav_next will
			 * go to 22, do 23, then jump _directly_ back to 24,
			 * omitting the redundant check at 20.
			 */
			if (res == RBT_LEFT)
				newdir[newdepth++] = RBT_LEFT;

			node = node->sub[res];
		}

		if (found) {
			/*
			 * We found the node, but which HXbtraverse() has
			 * already returned. Advance to the next inorder node.
			 * (Code needs to come after @current assignment.)
			 */
			go_next = true;
		} else {
			/*
			 * If the node travp->current is actually deleted (@res
			 * will never be 0 above), traversal re-begins at the
			 * next inorder node, which happens to be the last node
			 * we turned left at.
			 */
			memcpy(trav->path, newpath, sizeof(trav->path));
			memcpy(trav->dir, newdir, sizeof(trav->dir));
			trav->depth = newdepth;
		}
	}

	if (trav->depth == 0) {
		/* no more elements */
		trav->current = NULL;
	} else {
		trav->current = trav->path[--trav->depth];
		if (trav->current == NULL)
			fprintf(stderr, "btrav_rewalk: problem: current==NULL\n");
		HXrbtrav_checkpoint(trav, trav->current);
	}

	trav->tid = btree->tid;
	if (go_next)
		return HXrbtrav_next(trav);
	else
		return trav->current;
}

static const struct HXmap_node *HXrbtree_traverse(struct HXrbtrav *trav)
{
	const struct HXrbtree_node *node;

	if (trav->tid != trav->tree->tid || trav->current == NULL)
		/*
		 * Every HXrbtree operation that significantly changes the
		 * B-tree, increments @tid so we can decide here to rewalk.
		 */
		node = HXrbtrav_rewalk(trav);
	else
		node = HXrbtrav_next(trav);

	return (node != NULL) ? static_cast(const void *, &node->key) : NULL;
}

EXPORT_SYMBOL const struct HXmap_node *HXmap_traverse(struct HXmap_trav *trav)
{
	void *xtrav = trav;

	if (xtrav == NULL)
		return NULL;

	switch (trav->type) {
	case HXMAPT_HASH:
		return HXhmap_traverse(xtrav);
	case HXMAPT_RBTREE:
		return HXrbtree_traverse(xtrav);
	default:
		errno = EINVAL;
		return NULL;
	}
}

static void HXrbtrav_free(struct HXrbtrav *trav)
{
	const struct HXmap_private *super = &trav->tree->super;

	if ((super->flags & HXMAP_DTRAV) && super->ops.k_free != NULL)
		super->ops.k_free(trav->checkpoint);
	free(trav);
}

EXPORT_SYMBOL void HXmap_travfree(struct HXmap_trav *trav)
{
	void *xtrav = trav;

	if (xtrav == NULL)
		return;
	switch (trav->type) {
	case HXMAPT_RBTREE:
		HXrbtrav_free(xtrav);
		break;
	default:
		free(xtrav);
		break;
	}
}

static void HXhmap_qfe(const struct HXhmap *hmap, qfe_fn_t fn, void *arg)
{
	const struct HXhmap_node *hnode;
	unsigned int i;

	for (i = 0; i < HXhash_primes[hmap->power]; ++i)
		HXlist_for_each_entry(hnode, &hmap->bk_array[i], anchor)
			if (!(*fn)(static_cast(const void *, &hnode->key), arg))
				return;
}

static void HXrbtree_qfe(const struct HXrbtree_node *node,
    qfe_fn_t fn, void *arg)
{
	if (node->sub[RBT_LEFT] != NULL)
		HXrbtree_qfe(node->sub[RBT_LEFT], fn, arg);
	if (!(*fn)(static_cast(const void *, &node->key), arg))
		return;
	if (node->sub[RBT_RIGHT] != NULL)
		HXrbtree_qfe(node->sub[RBT_RIGHT], fn, arg);
}

EXPORT_SYMBOL void HXmap_qfe(const struct HXmap *xmap, qfe_fn_t fn, void *arg)
{
	const void *vmap = xmap;
	const struct HXmap_private *map = vmap;

	switch (map->type) {
	case HXMAPT_HASH:
		HXhmap_qfe(vmap, fn, arg);
		errno = 0;
		break;
	case HXMAPT_RBTREE: {
		const struct HXrbtree *tree = vmap;
		if (tree->root != NULL)
			HXrbtree_qfe(tree->root, fn, arg);
		errno = 0;
		break;
	}
	default:
		errno = EINVAL;
	}
}