/*
 * Copyright (c) 2015 Gilles Chanteperdrix
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include <errno.h>
#include <memory.h>

#ifdef AVL_PSHARED
#define __AVL(__decl)	shavl_ ## __decl
#define __AVLH(__decl)	shavlh_ ## __decl
#define __AVL_T(__type)	sh ## __type
#else
#define __AVL(__decl)	avl_ ## __decl
#define __AVLH(__decl)	avlh_ ## __decl
#define __AVL_T(__type)	__type
#endif

struct __AVL_T (avlh) * __AVL(inorder)(const struct __AVL_T(avl) * const avl,
				       struct __AVL_T(avlh) * holder,
				       const int dir)
{
	/* Assume dir == AVL_RIGHT in comments. */
	struct __AVL_T (avlh) * next;

	/*
	 * If the current node is not right threaded, then go down left,
	 * starting from its right child.
	 */
	if (__AVLH(has_child)(avl, holder, dir)) {
		const int opp_dir = avl_opposite(dir);
		holder = __AVLH(link)(avl, holder, dir);
		while ((next = __AVLH(child)(avl, holder, opp_dir)))
			holder = next;
		next = holder;
	} else {
		for (;;) {
			next = __AVLH(up)(avl, holder);
			if (next == __AVL(anchor)(avl))
				return NULL;
			if (holder->type != dir)
				break;
			holder = next;
		}
	}

	return next;
}

struct __AVL_T (avlh) * __AVL(postorder)(const struct __AVL_T(avl) * const avl,
					 struct __AVL_T(avlh) * const holder,
					 const int dir)
{
	/* Assume dir == AVL_RIGHT in comments. */
	struct __AVL_T (avlh) * next = __AVLH(up)(avl, holder);

	if (holder->type != dir)
		/*
		 * If the current node is not a right node, follow the nodes in
		 * inorder until we find a right threaded node.
		 */
		while (__AVLH(has_child)(avl, next, dir))
			next = __AVL(inorder)(avl, next, dir);
	else
		/*
		 * else the current node is a right node, its parent is the
		 * next in postorder.
		 */
		if (next == __AVL(anchor)(avl))
			next = NULL;

	return next;
}

struct __AVL_T (avlh) * __AVL(preorder)(const struct __AVL_T(avl) * const avl,
					struct __AVL_T(avlh) * holder,
					const int dir)
{
	struct __AVL_T (avlh) * next;
	/* Assume dir == AVL_RIGHT in comments. */
	/*
	 * If the current node has a left child (hence is not left threaded),
	 * then return it.
	 */

	if (__AVLH(has_child)(avl, holder, avl_opposite(dir)))
		return __AVLH(link)(avl, holder, avl_opposite(dir));

	/*
	 * Else follow the right threads until we find a node which is not right
	 * threaded (hence has a right child) and return its right child.
	 */
	next = holder;

	while (!__AVLH(has_child)(avl, next, dir)) {
		next = __AVL(inorder)(avl, next, dir);
		if (next == NULL)
			return NULL;
	}

	return __AVLH(link)(avl, next, dir);
}

static inline unsigned int avlh_thr(const struct __AVL_T (avl) * const avl,
				    const struct __AVL_T (avlh) * h)
{
	unsigned int result = 0;

	if (__AVLH(link)(avl, h, AVL_LEFT) == NULL)
		result |= AVL_THR_LEFT;
	if (__AVLH(link)(avl, h, AVL_RIGHT) == NULL)
		result |= AVL_THR_RIGHT;

	return result;
}

static inline void
avlh_set_parent_link(struct __AVL_T (avl) * const avl,
		     struct __AVL_T (avlh) * lhs, struct __AVL_T (avlh) * rhs)
{
	__AVLH(set_link)(avl, __AVLH(up)(avl, lhs), lhs->type, rhs);
}

static inline void
avlh_set_left(struct __AVL_T (avl) * const avl, struct __AVL_T (avlh) * lhs,
	      struct __AVL_T (avlh) * rhs)
{
	__AVLH(set_link)(avl, lhs, AVL_LEFT, rhs);
}

static inline void
avlh_set_up(struct __AVL_T (avl) * const avl, struct __AVL_T (avlh) * lhs,
	    struct __AVL_T (avlh) * rhs)
{
	__AVLH(set_link)(avl, lhs, AVL_UP, rhs);
}

static inline void
avlh_set_right(struct __AVL_T (avl) * const avl, struct __AVL_T (avlh) * lhs,
	       struct __AVL_T (avlh) * rhs)
{
	__AVLH(set_link)(avl, lhs, AVL_RIGHT, rhs);
}

static inline void avl_set_top(struct __AVL_T (avl) * const avl,
			       struct __AVL_T (avlh) * holder)
{
	__AVLH(set_link)(avl, __AVL(anchor)(avl), AVL_RIGHT, holder);
}

static inline void avl_set_head(struct __AVL_T (avl) * const avl,
				struct __AVL_T (avlh) * holder)
{
	__AVL(set_end)(avl, AVL_LEFT, holder);
}

static inline void avl_set_tail(struct __AVL_T (avl) * const avl,
				struct __AVL_T (avlh) * holder)
{
	__AVL(set_end)(avl, AVL_RIGHT, holder);
}

/* Internal functions used for rebalancing (for insertion and deletion). */
static inline struct __AVL_T (avlh) *
	avlh_rotate(struct __AVL_T (avl) * const avl,
		    struct __AVL_T (avlh) * const holder, const int dir)
{
	const int opp_dir = avl_opposite(dir);
	struct __AVL_T (avlh) * const nexttop =
		__AVLH(link)(avl, holder, opp_dir);
	struct __AVL_T (avlh) * const subtree =
		__AVLH(child)(avl, nexttop, dir);

	if (subtree) {
		__AVLH(set_link)(avl, holder, opp_dir, subtree);
		avlh_set_up(avl, subtree, holder);
		subtree->type = opp_dir;
	} else
		__AVLH(set_link)(avl, holder, opp_dir, NULL);

	__AVLH(set_link)(avl, nexttop, dir, holder);
	avlh_set_up(avl, nexttop, __AVLH(up)(avl, holder));
	nexttop->type = holder->type;
	avlh_set_up(avl, holder, nexttop);
	holder->type = dir;

	avlh_set_parent_link(avl, nexttop, nexttop);

	return nexttop;
}

static inline struct __AVL_T (avlh) *
	avlh_dbl_rotate(struct __AVL_T (avl) * const avl,
			struct __AVL_T (avlh) * const holder, const int dir)
{
	const int opp = avl_opposite(dir);

	avlh_rotate(avl, __AVLH(link)(avl, holder, opp), opp);
	return avlh_rotate(avl, holder, dir);
}

static struct __AVL_T (avlh) *
	avlh_rebalance(struct __AVL_T (avl) * const avl, struct __AVL_T (avlh) * holder,
		       const int delta)
{

	int dir = delta;
	struct __AVL_T (avlh) * const heavy_side =
		__AVLH(link)(avl, holder, dir);

	if (heavy_side->balance == -delta) {
		/* heavy_side->balance == -delta, double rotation needed. */
		holder = avlh_dbl_rotate(avl, holder, avl_opposite(dir));

		/*
		 * recompute balances, there are three nodes involved, two of
		 * which balances become null.
		 */
		dir = holder->balance ? : AVL_RIGHT;
		__AVLH(link)(avl, holder, dir)->balance = 0;
		__AVLH(link)(avl, holder, avl_opposite(dir))->balance
			= -holder->balance;
		holder->balance = 0;
	} else {
		/*
		 * heavy_side->balance == delta or 0, simple rotation needed.
		 * the case 0 occurs only when deleting, never when inserting.
		 */

		/* heavy_side becomes the new root. */
		avlh_rotate(avl, holder, avl_opposite(dir));

		/* recompute balances. */
		holder->balance -= heavy_side->balance;
		heavy_side->balance -= delta;

		holder = heavy_side;
	}
	return holder;
}

/*
 * The avlh_rebalance functions was split in two parts to allow inlining in
 * the simplest case.
 */
static inline struct __AVL_T (avlh) *
	avlh_balance_add(struct __AVL_T (avl) * const avl,
			 struct __AVL_T (avlh) * const holder, const int delta)
{
	if (holder->balance == delta)
		/* we need to rebalance the current subtree. */
		return avlh_rebalance(avl, holder, delta);

	/* the current subtree does not need rebalancing */
	holder->balance += delta;
	return holder;
}

static inline void
avlh_link_child(struct __AVL_T (avl) * const avl,
		struct __AVL_T (avlh) * const oldh,
		struct __AVL_T (avlh) * const newh, const int side)
{
	struct __AVL_T (avlh) * const child = __AVLH(link)(avl, oldh, side);

	__AVLH(set_link)(avl, newh, side, child);
	if (__AVLH(has_child)(avl, oldh, side))
		avlh_set_up(avl, child, newh);
}

static inline void
avlh_replace(struct __AVL_T (avl) * const avl,
	     struct __AVL_T (avlh) * const oldh,
	     struct __AVL_T (avlh) * const newh)
{
	newh->type = oldh->type;
	/* Do not update the balance, this has to be done by the caller. */

	avlh_set_up(avl, newh, __AVLH(up)(avl, oldh));
	avlh_set_parent_link(avl, oldh, newh);

	avlh_link_child(avl, oldh, newh, AVL_LEFT);
	avlh_link_child(avl, oldh, newh, AVL_RIGHT);
}

/* Deletion helpers. */
static void avl_delete_leaf(struct __AVL_T (avl) * const avl,
			    struct __AVL_T (avlh) * const node)
{
	/*
	 * Node has no child at all. It disappears and its father becomes
	 * threaded on the side id was.
	 */

	struct __AVL_T (avlh) * const new_node = __AVLH(up)(avl, node);
	const int dir = node->type;

	/* Suppress node. */
	__AVLH(set_link)(avl, new_node, dir, __AVLH(link)(avl, node, dir));

	if (node == __AVL(end)(avl, dir))
		__AVL(set_end)(avl, dir, new_node);
}

static struct __AVL_T (avlh) * avl_delete_1child(struct __AVL_T (avl) *
						 const avl,
						 struct __AVL_T (avlh) *
						 const node, const int dir)
{
	/*
	 * Node is threaded on one side and has a child on the other
	 * side. In this case, node is replaced by its child.
	 */

	struct __AVL_T (avlh) * const new_node = __AVLH(link)(avl, node, dir);

	/*
	 * Change links as if new_node was suppressed before calling
	 * avlh_replace.
	 */
	__AVLH(set_link)(avl, node, dir, __AVLH(link)(avl, new_node, dir));
	avlh_replace(avl, node, new_node);

	if (node == __AVL(end)(avl, avl_opposite(dir)))
		__AVL(set_end)(avl, avl_opposite(dir), new_node);
	/* new_node->balance 0, which is correct. */
	return new_node;
}

static int avl_delete_2children(struct __AVL_T (avl) * const avl,
				struct __AVL_T (avlh) * const node);

/* Insertion helpers. */
static inline void
avlh_attach(struct __AVL_T (avl) * const avl,
	    struct __AVL_T (avlh) * const parent,
	    struct __AVL_T (avlh) * const child, const int side)
{
	avlh_set_left(avl, child, NULL);
	avlh_set_right(avl, child, NULL);
	avlh_set_up(avl, child, parent);
	__AVLH(set_link)(avl, parent, side, child);
	child->type = side;
}

/*
 * Insert a node, given its parent and the side where it should be inserted.
 * Helper for all insertion functions.
 */
static inline void avl_insert_inner(struct __AVL_T (avl) * const avl,
				    struct __AVL_T (avlh) * parent,
				    struct __AVL_T (avlh) * const node,
				    const int side)
{
	avlh_attach(avl, parent ? : __AVL(anchor)(avl), node, side);
	++__AVL(count)(avl);

	if (parent == NULL)
		goto insert_first_and_ret;	/* Get away from fast path */

	if (parent == __AVL(end)(avl, side))
		__AVL(set_end)(avl, side, node);

	parent->balance += side;

	while (parent->balance) {
		const int delta = parent->type;
		parent = __AVLH(up)(avl, parent);
		if (parent == __AVL(anchor)(avl))
			goto inc_height_and_ret;	/* Get away from fast path */
		parent = avlh_balance_add(avl, parent, delta);
	}

	return;

insert_first_and_ret:
	avl_set_head(avl, node);
	avl_set_tail(avl, node);
inc_height_and_ret:
	++__AVL(height)(avl);
}

/* External functions. */
int __AVL(delete)(struct __AVL_T(avl) * const avl, struct __AVL_T(avlh) * node)
{
	if (!--__AVL(count)(avl)) {
		goto delete_last_and_ret;
	}

	switch (avlh_thr(avl, node)) {
	case (AVL_THR_LEFT | AVL_THR_RIGHT):	/* thr is 5 */
		avl_delete_leaf(avl, node);
		break;

	case AVL_THR_LEFT:	/* only AVL_LEFT bit is on, thr is 1. */
		node = avl_delete_1child(avl, node, AVL_RIGHT);
		break;

	case AVL_THR_RIGHT:	/* only AVL_RIGHT bit is on, thr is 4. */
		node = avl_delete_1child(avl, node, AVL_LEFT);
		break;

	case 0:
		return avl_delete_2children(avl, node);
	}

	/* node is the first node which needs to be rebalanced.
	   The tree is rebalanced, and contrarily to what happened for insertion,
	   the rebalancing stops when a node which is NOT balanced is met. */
	while (!node->balance) {
		const int delta = -node->type;
		node = __AVLH(up)(avl, node);
		if (node == __AVL(anchor)(avl))
			goto dec_height_and_ret;
		node = avlh_balance_add(avl, node, delta);
	}

	return 0;

delete_last_and_ret:
	avl_set_top(avl, NULL);
	avl_set_head(avl, NULL);
	avl_set_tail(avl, NULL);
dec_height_and_ret:
	--__AVL(height)(avl);
	return 0;
}

static int avl_delete_2children(struct __AVL_T (avl) * const avl,
				struct __AVL_T (avlh) * const node)
{
	const int dir = node->balance ? node->balance : 1;
	struct __AVL_T (avlh) * const new_node =
		__AVL(inorder)(avl, node, dir);
	__AVL(delete)(avl, new_node);
	++__AVL(count)(avl);
	avlh_replace(avl, node, new_node);
	new_node->balance = node->balance;
	if (__AVL(end)(avl, dir) == node)
		__AVL(set_end)(avl, dir, new_node);
	return 0;
}

int __AVL(prepend)(struct __AVL_T(avl) * const avl,
		   struct __AVL_T(avlh) * const holder,
		   const struct __AVL_T(avl_searchops) * ops)
{
	struct __AVL_T (avlh) * const parent = __AVL(head)(avl);
	int type = parent == NULL ? AVL_RIGHT : AVL_LEFT;

	if (parent == NULL || ops->cmp(holder, parent) < 0) {
		avl_insert_inner(avl, parent, holder, type);
		return 0;
	}

	return -EINVAL;
}

int __AVL(insert_at)(struct __AVL_T(avl) * const avl,
		     struct __AVL_T(avlh) * parent, int dir,
		     struct __AVL_T(avlh) * child)
{
	if (parent == NULL)
		dir = AVL_RIGHT;
	else {
		if (!__AVLH(thr_tst)(avl, parent, dir))
			return -EINVAL;
	}

	avl_insert_inner(avl, parent, child, dir);
	return 0;
}

int __AVL(insert)(struct __AVL_T(avl) * const avl,
		  struct __AVL_T(avlh) * const holder,
		  const struct __AVL_T(avl_searchops) * ops)
{
	int delta;
	struct __AVL_T (avlh) * parent;

	parent = __AVL(search_inner)(avl, holder, &delta, ops);
	if (delta == 0)
		return -EBUSY;

	avl_insert_inner(avl, parent, holder, delta);

	return 0;
}

int __AVL(insert_front)(struct __AVL_T(avl) * const avl,
			struct __AVL_T(avlh) * const holder,
			const struct __AVL_T(avl_searchops) * ops)
{
	int delta;
	struct __AVL_T (avlh) * parent;

	parent = ops->search(avl, holder, &delta, AVL_LEFT);

	avl_insert_inner(avl, parent, holder, delta ? : AVL_LEFT);
	return 0;
}

int __AVL(insert_back)(struct __AVL_T(avl) * const avl,
		       struct __AVL_T(avlh) * const holder,
		       const struct __AVL_T(avl_searchops) * ops)
{
	int delta;
	struct __AVL_T (avlh) * parent;

	parent = ops->search(avl, holder, &delta, AVL_RIGHT);

	avl_insert_inner(avl, parent, holder, delta ? : AVL_RIGHT);
	return 0;
}

int __AVL(append)(struct __AVL_T(avl) * const avl,
		  struct __AVL_T(avlh) * const holder,
		  const struct __AVL_T(avl_searchops) * ops)
{
	struct __AVL_T (avlh) * const parent = __AVL(tail)(avl);

	if (parent == NULL || ops->cmp(holder, parent) > 0) {
		avl_insert_inner(avl, parent, holder, AVL_RIGHT);
		return 0;
	}

	return -EINVAL;
}

/*
 * Special case, when we know that replacing a node with another will not change
 * the avl, much faster than remove + add
 */
int __AVL(replace)(struct __AVL_T(avl) * avl, struct __AVL_T(avlh) * oldh,
		   struct __AVL_T(avlh) * newh,
		   const struct __AVL_T(avl_searchops) * ops)
{
	struct __AVL_T (avlh) * prev, *next;

	prev = __AVL(prev)(avl, oldh);
	next = __AVL(next)(avl, oldh);

	if ((prev && ops->cmp(newh, prev) < 0)
	    || (next && ops->cmp(newh, next) > 0))
		return -EINVAL;

	avlh_replace(avl, oldh, newh);
	if (oldh == __AVL(head)(avl))
		avl_set_head(avl, newh);
	if (oldh == __AVL(tail)(avl))
		avl_set_tail(avl, newh);
	newh->balance = oldh->balance;
	return 0;
}

struct __AVL_T (avlh) * __AVL(update)(struct __AVL_T(avl) * const avl,
				      struct __AVL_T(avlh) * const holder,
				      const struct __AVL_T(avl_searchops) * ops)
{
	int delta;
	struct __AVL_T (avlh) * const oldh =
		__AVL(search_inner)(avl, holder, &delta, ops);

	if (!delta) {
		__AVL(replace)(avl, oldh, holder, ops);
		return oldh;
	}

	return NULL;
}

struct __AVL_T (avlh) * __AVL(set)(struct __AVL_T(avl) * const avl,
				   struct __AVL_T(avlh) * const holder,
				   const struct __AVL_T(avl_searchops) * ops)
{
	int delta;
	struct __AVL_T (avlh) * const oldh =
		__AVL(search_inner)(avl, holder, &delta, ops);

	if (delta) {
		avl_insert_inner(avl, oldh, holder, delta);
		return NULL;
	}

	__AVL(replace)(avl, oldh, holder, ops);
	return oldh;
}

void __AVL(init)(struct __AVL_T(avl) * const avl)
{
	__AVLH(init)(__AVL(anchor)(avl));	/* this must be first. */
	__AVL(height)(avl) = 0;
	__AVL(count)(avl) = 0;
	avl_set_top(avl, NULL);

	avl_set_head(avl, NULL);
	avl_set_tail(avl, NULL);
}

void __AVL(destroy)(struct __AVL_T(avl) * const avl)
{
	__AVL(init)(avl);
}

void __AVL(clear)(struct __AVL_T(avl) * const avl,
		  void (*destruct)(struct __AVL_T(avlh) *))
{
	if (destruct) {
		struct __AVL_T (avlh) * next, *holder = __AVL(gethead)(avl);

		while (holder) {
			next = __AVL(postorder_next)(avl, holder);
			destruct(holder);
			holder = next;
		}
	}

	__AVL(init)(avl);
}

static inline
void avl_dumper_visit(FILE * file, const struct __AVL_T (avl) * const avl,
		      struct __AVL_T (avlh) * node,
		      __AVL_T(avlh_prn_t) * prn, const char *blank,
		      unsigned int blank_sz, char *buf,
		      unsigned int indent, unsigned int len)
{
	char bal;

	if (__AVLH(has_child)(avl, node, AVL_RIGHT)) {
		if (blank_sz >= (unsigned int)(buf - blank)) {
			snprintf(buf, len + 3, "%*s\n", (int)len + 1, "bug!");
			fputs(buf - blank_sz, file);
		} else
			avl_dumper_visit(file, avl,
					 __AVLH(right)(avl, node),
					 prn, blank,
					 blank_sz + indent, buf, indent, len);
	}

	switch (node->balance) {
	case 0:
		bal = '.';
		break;
	case -1:
		bal = '-';
		break;
	case 1:
		bal = '+';
		break;
	default:
		bal = '?';	/* Bug. */
	}

	(*prn)(buf, len + 1, node);
	buf[len] = bal;
	buf[len + 1] = '\n';
	buf[len + 2] = '\0';

	fputs(buf - blank_sz, file);

	if (__AVLH(has_child)(avl, node, AVL_LEFT)) {
		if (blank_sz >= (unsigned int)(buf - blank)) {
			snprintf(buf, len + 3, "%*s\n", (int)len + 1, "bug!");
			fputs(buf - blank_sz, file);
		} else
			avl_dumper_visit(file, avl,
					 __AVLH(left)(avl, node),
					 prn, blank,
					 blank_sz + indent, buf, indent, len);
	}
}

void __AVL(dump)(FILE * file, const struct __AVL_T(avl) * const avl,
		 __AVL_T(avlh_prn_t) * prn, unsigned int indent,
		 unsigned int len)
{

	struct __AVL_T (avlh) * holder = __AVL(gettop)(avl);

	putc('\n', file);
	if (!holder)
		fputs("Empty.\n", file);
	else {
		size_t blank_sz = (__AVL(height)(avl) - 1) * indent;
		char buffer[blank_sz + len + 3];
		/* 3 == balance char + sizeof("\n\0") */
		memset(buffer, ' ', blank_sz);

		avl_dumper_visit(file, avl, holder, prn, buffer, 0,
				 buffer + blank_sz, indent, len);
	}
	fflush(file);
}

static int avl_check_visit(const struct __AVL_T (avl) * avl,
			   struct __AVL_T (avlh) * node, unsigned int level)
{
	int err;

	if (!__AVLH(has_child)(avl, node, AVL_RIGHT))
		goto check_balance;

	if (level > __AVL(height)(avl)) {
		fprintf(stderr, "too much recursion\n");
		return -EINVAL;
	}

	err = avl_check_visit(avl, __AVLH(right)(avl, node), level + 1);
	if (err < 0)
		return err;

check_balance:
	switch (node->balance) {
	case 0:
		break;
	case -1:
		break;
	case 1:
		break;
	default:
		fprintf(stderr, "invalid balance\n");
		return -EINVAL;
	}

	if (!__AVLH(has_child)(avl, node, AVL_LEFT))
		return 0;

	err = avl_check_visit(avl, __AVLH(left)(avl, node), level + 1);
	if (err < 0)
		return err;

	return 0;
}

int __AVL(check)(const struct __AVL_T(avl) * avl,
		 const struct __AVL_T(avl_searchops) * ops)
{
	struct __AVL_T (avlh) * holder = __AVL(gettop)(avl), *last;
	int err;

	if (!holder)
		return 0;

	err = avl_check_visit(avl, holder, 0);
	if (err < 0)
		return err;

	last = NULL;
	for (holder = __AVL(gethead)(avl); holder;
	     holder = __AVL(next)(avl, holder)) {
		if (last != NULL)
			if (ops->cmp(holder, last) < 0) {
				fprintf(stderr, "disordered nodes\n");
				return -EINVAL;
			}
		last = holder;
	}

	return 0;
}