xref: /external/chromium_org/third_party/bintrees/bintrees/ctrees.c

/*
 * ctrees.c
 *
 *  Author: mozman
 *  Copyright (c) 2010-2013 by Manfred Moitzi
 *  License: MIT-License
 */

#include "ctrees.h"
#include "stack.h"
#include <Python.h>

#define LEFT 0
#define RIGHT 1
#define KEY(node) (node->key)
#define VALUE(node) (node->value)
#define LEFT_NODE(node) (node->link[LEFT])
#define RIGHT_NODE(node) (node->link[RIGHT])
#define LINK(node, dir) (node->link[dir])
#define XDATA(node) (node->xdata)
#define RED(node) (node->xdata)
#define BALANCE(node) (node->xdata)

static node_t *
ct_new_node(PyObject *key, PyObject *value, int xdata)
{
	node_t *new_node = PyMem_Malloc(sizeof(node_t));
	if (new_node != NULL) {
		KEY(new_node) = key;
		Py_INCREF(key);
		VALUE(new_node) = value;
		Py_INCREF(value);
		LEFT_NODE(new_node) = NULL;
		RIGHT_NODE(new_node) = NULL;
		XDATA(new_node) = xdata;
	}
	return new_node;
}

static void
ct_delete_node(node_t *node)
{
	if (node != NULL) {
		Py_XDECREF(KEY(node));
		Py_XDECREF(VALUE(node));
		LEFT_NODE(node) = NULL;
		RIGHT_NODE(node) = NULL;
		PyMem_Free(node);
	}
}

extern void
ct_delete_tree(node_t *root)
{
	if (root == NULL)
		return;
	if (LEFT_NODE(root) != NULL) {
		ct_delete_tree(LEFT_NODE(root));
	}
	if (RIGHT_NODE(root) != NULL) {
		ct_delete_tree(RIGHT_NODE(root));
	}
	ct_delete_node(root);
}

static void
ct_swap_data(node_t *node1, node_t *node2)
{
	PyObject *tmp;
	tmp = KEY(node1);
	KEY(node1) = KEY(node2);
	KEY(node2) = tmp;
	tmp = VALUE(node1);
	VALUE(node1) = VALUE(node2);
	VALUE(node2) = tmp;
}

int
ct_compare(PyObject *key1, PyObject *key2)
{
	int res;

	res = PyObject_RichCompareBool(key1, key2, Py_LT);
	if (res > 0)
		return -1;
	else if (res < 0) {
		PyErr_SetString(PyExc_TypeError, "invalid type for key");
		return 0;
		}
	/* second compare:
	+1 if key1 > key2
	 0 if not -> equal
	-1 means error, if error, it should happend at the first compare
	*/
	return PyObject_RichCompareBool(key1, key2, Py_GT);
}

extern node_t *
ct_find_node(node_t *root, PyObject *key)
{
	int res;
	while (root != NULL) {
		res = ct_compare(key, KEY(root));
		if (res == 0) /* key found */
			return root;
		else {
			root = LINK(root, (res > 0));
		}
	}
	return NULL; /* key not found */
}

extern PyObject *
ct_get_item(node_t *root, PyObject *key)
{
	node_t *node;
	PyObject *tuple;

	node = ct_find_node(root, key);
	if (node != NULL) {
		tuple = PyTuple_New(2);
		PyTuple_SET_ITEM(tuple, 0, KEY(node));
		PyTuple_SET_ITEM(tuple, 1, VALUE(node));
		return tuple;
	}
	Py_RETURN_NONE;
}

extern node_t *
ct_max_node(node_t *root)
/* get node with largest key */
{
	if (root == NULL)
		return NULL;
	while (RIGHT_NODE(root) != NULL)
		root = RIGHT_NODE(root);
	return root;
}

extern node_t *
ct_min_node(node_t *root)
// get node with smallest key
{
	if (root == NULL)
		return NULL;
	while (LEFT_NODE(root) != NULL)
		root = LEFT_NODE(root);
	return root;
}

extern int
ct_bintree_remove(node_t **rootaddr, PyObject *key)
/* attention: rootaddr is the address of the root pointer */
{
	node_t *node, *parent, *replacement;
	int direction, cmp_res, down_dir;

	node = *rootaddr;

	if (node == NULL)
		return 0; /* root is NULL */
	parent = NULL;
	direction = 0;

	while (1) {
		cmp_res = ct_compare(key, KEY(node));
		if (cmp_res == 0) /* key found, remove node */
		{
			if ((LEFT_NODE(node) != NULL) && (RIGHT_NODE(node) != NULL)) {
				/* find replacement node: smallest key in right-subtree */
				parent = node;
				direction = RIGHT;
				replacement = RIGHT_NODE(node);
				while (LEFT_NODE(replacement) != NULL) {
					parent = replacement;
					direction = LEFT;
					replacement = LEFT_NODE(replacement);
				}
				LINK(parent, direction) = RIGHT_NODE(replacement);
				/* swap places */
				ct_swap_data(node, replacement);
				node = replacement; /* delete replacement node */
			}
			else {
				down_dir = (LEFT_NODE(node) == NULL) ? RIGHT : LEFT;
				if (parent == NULL) /* root */
				{
					*rootaddr = LINK(node, down_dir);
				}
				else {
					LINK(parent, direction) = LINK(node, down_dir);
				}
			}
			ct_delete_node(node);
			return 1; /* remove was success full */
		}
		else {
			direction = (cmp_res < 0) ? LEFT : RIGHT;
			parent = node;
			node = LINK(node, direction);
			if (node == NULL)
				return 0; /* error key not found */
		}
	}
}

extern int
ct_bintree_insert(node_t **rootaddr, PyObject *key, PyObject *value)
/* attention: rootaddr is the address of the root pointer */
{
	node_t *parent, *node;
	int direction, cval;
	node = *rootaddr;
	if (node == NULL) {
		node = ct_new_node(key, value, 0); /* new node is also the root */
		if (node == NULL)
			return -1; /* got no memory */
		*rootaddr = node;
	}
	else {
		direction = LEFT;
		parent = NULL;
		while (1) {
			if (node == NULL) {
				node = ct_new_node(key, value, 0);
				if (node == NULL)
					return -1; /* get no memory */
				LINK(parent, direction) = node;
				return 1;
			}
			cval = ct_compare(key, KEY(node));
			if (cval == 0) {
				/* key exists, replace value object */
				Py_XDECREF(VALUE(node)); /* release old value object */
				VALUE(node) = value; /* set new value object */
				Py_INCREF(value); /* take new value object */
				return 0;
			}
			else {
				parent = node;
				direction = (cval < 0) ? LEFT : RIGHT;
				node = LINK(node, direction);
			}
		}
	}
	return 1;
}

static int
is_red (node_t *node)
{
	return (node != NULL) && (RED(node) == 1);
}

#define rb_new_node(key, value) ct_new_node(key, value, 1)

static node_t *
rb_single(node_t *root, int dir)
{
	node_t *save = root->link[!dir];

	root->link[!dir] = save->link[dir];
	save->link[dir] = root;

	RED(root) = 1;
	RED(save) = 0;
	return save;
}

static node_t *
rb_double(node_t *root, int dir)
{
	root->link[!dir] = rb_single(root->link[!dir], !dir);
	return rb_single(root, dir);
}

#define rb_new_node(key, value) ct_new_node(key, value, 1)

extern int
rb_insert(node_t **rootaddr, PyObject *key, PyObject *value)
{
	node_t *root = *rootaddr;

	if (root == NULL) {
		/*
		 We have an empty tree; attach the
		 new node directly to the root
		 */
		root = rb_new_node(key, value);
		if (root == NULL)
			return -1; // got no memory
	}
	else {
		node_t head; /* False tree root */
		node_t *g, *t; /* Grandparent & parent */
		node_t *p, *q; /* Iterator & parent */
		int dir = 0;
		int last = 0;
		int new_node = 0;

		/* Set up our helpers */
		t = &head;
		g = NULL;
		p = NULL;
		RIGHT_NODE(t) = root;
		LEFT_NODE(t) = NULL;
		q = RIGHT_NODE(t);

		/* Search down the tree for a place to insert */
		for (;;) {
			int cmp_res;
			if (q == NULL) {
				/* Insert a new node at the first null link */
				q = rb_new_node(key, value);
				p->link[dir] = q;
				new_node = 1;
				if (q == NULL)
					return -1; // get no memory
			}
			else if (is_red(q->link[0]) && is_red(q->link[1])) {
				/* Simple red violation: color flip */
				RED(q) = 1;
				RED(q->link[0]) = 0;
				RED(q->link[1]) = 0;
			}

			if (is_red(q) && is_red(p)) {
				/* Hard red violation: rotations necessary */
				int dir2 = (t->link[1] == g);

				if (q == p->link[last])
					t->link[dir2] = rb_single(g, !last);
				else
					t->link[dir2] = rb_double(g, !last);
			}

			/*  Stop working if we inserted a new node. */
			if (new_node)
				break;

			cmp_res = ct_compare(KEY(q), key);
			if (cmp_res == 0) {       /* key exists?              */
				Py_XDECREF(VALUE(q)); /* release old value object */
				VALUE(q) = value;     /* set new value object     */
				Py_INCREF(value);     /* take new value object    */
				return 0;
			}
			last = dir;
			dir = (cmp_res < 0);

			/* Move the helpers down */
			if (g != NULL)
				t = g;

			g = p;
			p = q;
			q = q->link[dir];
		}
		/* Update the root (it may be different) */
		root = head.link[1];
	}

	/* Make the root black for simplified logic */
	RED(root) = 0;
	(*rootaddr) = root;
	return 1;
}

extern int
rb_remove(node_t **rootaddr, PyObject *key)
{
	node_t *root = *rootaddr;

	node_t head = { { NULL } }; /* False tree root */
	node_t *q, *p, *g; /* Helpers */
	node_t *f = NULL; /* Found item */
	int dir = 1;

	if (root == NULL)
		return 0;

	/* Set up our helpers */
	q = &head;
	g = p = NULL;
	RIGHT_NODE(q) = root;

	/*
	 Search and push a red node down
	 to fix red violations as we go
	 */
	while (q->link[dir] != NULL) {
		int last = dir;
		int cmp_res;

		/* Move the helpers down */
		g = p, p = q;
		q = q->link[dir];

		cmp_res =  ct_compare(KEY(q), key);

		dir = cmp_res < 0;

		/*
		 Save the node with matching data and keep
		 going; we'll do removal tasks at the end
		 */
		if (cmp_res == 0)
			f = q;

		/* Push the red node down with rotations and color flips */
		if (!is_red(q) && !is_red(q->link[dir])) {
			if (is_red(q->link[!dir]))
				p = p->link[last] = rb_single(q, dir);
			else if (!is_red(q->link[!dir])) {
				node_t *s = p->link[!last];

				if (s != NULL) {
					if (!is_red(s->link[!last]) &&
						!is_red(s->link[last])) {
						/* Color flip */
						RED(p) = 0;
						RED(s) = 1;
						RED(q) = 1;
					}
					else {
						int dir2 = g->link[1] == p;

						if (is_red(s->link[last]))
							g->link[dir2] = rb_double(p, last);
						else if (is_red(s->link[!last]))
							g->link[dir2] = rb_single(p, last);

						/* Ensure correct coloring */
						RED(q) = RED(g->link[dir2]) = 1;
						RED(g->link[dir2]->link[0]) = 0;
						RED(g->link[dir2]->link[1]) = 0;
					}
				}
			}
		}
	}

	/* Replace and remove the saved node */
	if (f != NULL) {
		ct_swap_data(f, q);
		p->link[p->link[1] == q] = q->link[q->link[0] == NULL];
		ct_delete_node(q);
	}

	/* Update the root (it may be different) */
	root = head.link[1];

	/* Make the root black for simplified logic */
	if (root != NULL)
		RED(root) = 0;
	*rootaddr = root;
	return (f != NULL);
}

#define avl_new_node(key, value) ct_new_node(key, value, 0)
#define height(p) ((p) == NULL ? -1 : (p)->xdata)
#define avl_max(a, b) ((a) > (b) ? (a) : (b))

static node_t *
avl_single(node_t *root, int dir)
{
  node_t *save = root->link[!dir];
	int rlh, rrh, slh;

	/* Rotate */
	root->link[!dir] = save->link[dir];
	save->link[dir] = root;

	/* Update balance factors */
	rlh = height(root->link[0]);
	rrh = height(root->link[1]);
	slh = height(save->link[!dir]);

	BALANCE(root) = avl_max(rlh, rrh) + 1;
	BALANCE(save) = avl_max(slh, BALANCE(root)) + 1;

	return save;
}

static node_t *
avl_double(node_t *root, int dir)
{
	root->link[!dir] = avl_single(root->link[!dir], !dir);
	return avl_single(root, dir);
}

extern int
avl_insert(node_t **rootaddr, PyObject *key, PyObject *value)
{
	node_t *root = *rootaddr;

	if (root == NULL) {
		root = avl_new_node(key, value);
		if (root == NULL)
			return -1; // got no memory
	}
	else {
		node_t *it, *up[32];
		int upd[32], top = 0;
		int done = 0;
		int cmp_res;

		it = root;
		/* Search for an empty link, save the path */
		for (;;) {
			/* Push direction and node onto stack */
			cmp_res = ct_compare(KEY(it), key);
			if (cmp_res == 0) {
				Py_XDECREF(VALUE(it)); // release old value object
				VALUE(it) = value; // set new value object
				Py_INCREF(value); // take new value object
				return 0;
			}
			// upd[top] = it->data < data;
			upd[top] = (cmp_res < 0);
			up[top++] = it;

			if (it->link[upd[top - 1]] == NULL)
				break;
			it = it->link[upd[top - 1]];
		}

		/* Insert a new node at the bottom of the tree */
		it->link[upd[top - 1]] = avl_new_node(key, value);
		if (it->link[upd[top - 1]] == NULL)
			return -1; // got no memory

		/* Walk back up the search path */
		while (--top >= 0 && !done) {
			// int dir = (cmp_res < 0);
			int lh, rh, max;

			cmp_res = ct_compare(KEY(up[top]), key);

			lh = height(up[top]->link[upd[top]]);
			rh = height(up[top]->link[!upd[top]]);

			/* Terminate or rebalance as necessary */
			if (lh - rh == 0)
				done = 1;
			if (lh - rh >= 2) {
				node_t *a = up[top]->link[upd[top]]->link[upd[top]];
				node_t *b = up[top]->link[upd[top]]->link[!upd[top]];

				if (height( a ) >= height( b ))
					up[top] = avl_single(up[top], !upd[top]);
				else
					up[top] = avl_double(up[top], !upd[top]);

				/* Fix parent */
				if (top != 0)
					up[top - 1]->link[upd[top - 1]] = up[top];
				else
					root = up[0];
				done = 1;
			}
			/* Update balance factors */
			lh = height(up[top]->link[upd[top]]);
			rh = height(up[top]->link[!upd[top]]);
			max = avl_max(lh, rh);
			BALANCE(up[top]) = max + 1;
		}
	}
	(*rootaddr) = root;
	return 1;
}

extern int
avl_remove(node_t **rootaddr, PyObject *key)
{
	node_t *root = *rootaddr;
	int cmp_res;

	if (root != NULL) {
		node_t *it, *up[32];
		int upd[32], top = 0;

		it = root;
		for (;;) {
			/* Terminate if not found */
			if (it == NULL)
				return 0;
			cmp_res = ct_compare(KEY(it), key);
			if (cmp_res == 0)
				break;

			/* Push direction and node onto stack */
			upd[top] = (cmp_res < 0);
			up[top++] = it;
			it = it->link[upd[top - 1]];
		}

		/* Remove the node */
		if (it->link[0] == NULL ||
			it->link[1] == NULL) {
			/* Which child is not null? */
			int dir = it->link[0] == NULL;

			/* Fix parent */
			if (top != 0)
				up[top - 1]->link[upd[top - 1]] = it->link[dir];
			else
				root = it->link[dir];

			ct_delete_node(it);
		}
		else {
			/* Find the inorder successor */
			node_t *heir = it->link[1];

			/* Save the path */
			upd[top] = 1;
			up[top++] = it;

			while ( heir->link[0] != NULL ) {
				upd[top] = 0;
				up[top++] = heir;
				heir = heir->link[0];
			}
			/* Swap data */
			ct_swap_data(it, heir);
			/* Unlink successor and fix parent */
			up[top - 1]->link[up[top - 1] == it] = heir->link[1];
			ct_delete_node(heir);
		}

		/* Walk back up the search path */
		while (--top >= 0) {
			int lh = height(up[top]->link[upd[top]]);
			int rh = height(up[top]->link[!upd[top]]);
			int max = avl_max(lh, rh);

			/* Update balance factors */
			BALANCE(up[top]) = max + 1;

			/* Terminate or rebalance as necessary */
			if (lh - rh == -1)
				break;
			if (lh - rh <= -2) {
				node_t *a = up[top]->link[!upd[top]]->link[upd[top]];
				node_t *b = up[top]->link[!upd[top]]->link[!upd[top]];

				if (height(a) <= height(b))
					up[top] = avl_single(up[top], upd[top]);
				else
					up[top] = avl_double(up[top], upd[top]);

				/* Fix parent */
				if (top != 0)
					up[top - 1]->link[upd[top - 1]] = up[top];
				else
					root = up[0];
			}
		}
	}
	(*rootaddr) = root;
	return 1;
}

extern node_t *
ct_succ_node(node_t *root, PyObject *key)
{
	node_t *succ = NULL;
	node_t *node = root;
	int cval;

	while (node != NULL) {
		cval = ct_compare(key, KEY(node));
		if (cval == 0)
			break;
		else if (cval < 0) {
			if ((succ == NULL) ||
				(ct_compare(KEY(node), KEY(succ)) < 0))
				succ = node;
			node = LEFT_NODE(node);
		} else
			node = RIGHT_NODE(node);
	}
	if (node == NULL)
		return NULL;
	/* found node of key */
	if (RIGHT_NODE(node) != NULL) {
		/* find smallest node of right subtree */
		node = RIGHT_NODE(node);
		while (LEFT_NODE(node) != NULL)
			node = LEFT_NODE(node);
		if (succ == NULL)
			succ = node;
		else if (ct_compare(KEY(node), KEY(succ)) < 0)
			succ = node;
	}
	return succ;
}

extern node_t *
ct_prev_node(node_t *root, PyObject *key)
{
	node_t *prev = NULL;
	node_t *node = root;
	int cval;

	while (node != NULL) {
		cval = ct_compare(key, KEY(node));
		if (cval == 0)
			break;
		else if (cval < 0)
			node = LEFT_NODE(node);
		else {
			if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0))
				prev = node;
			node = RIGHT_NODE(node);
		}
	}
	if (node == NULL) /* stay at dead end (None) */
		return NULL;
	/* found node of key */
	if (LEFT_NODE(node) != NULL) {
		/* find biggest node of left subtree */
		node = LEFT_NODE(node);
		while (RIGHT_NODE(node) != NULL)
			node = RIGHT_NODE(node);
		if (prev == NULL)
			prev = node;
		else if (ct_compare(KEY(node), KEY(prev)) > 0)
			prev = node;
	}
	return prev;
}

extern node_t *
ct_floor_node(node_t *root, PyObject *key)
{
	node_t *prev = NULL;
	node_t *node = root;
	int cval;

	while (node != NULL) {
		cval = ct_compare(key, KEY(node));
		if (cval == 0)
			return node;
		else if (cval < 0)
			node = LEFT_NODE(node);
		else {
			if ((prev == NULL) || (ct_compare(KEY(node), KEY(prev)) > 0))
				prev = node;
			node = RIGHT_NODE(node);
		}
	}
	return prev;
}

extern node_t *
ct_ceiling_node(node_t *root, PyObject *key)
{
	node_t *succ = NULL;
	node_t *node = root;
	int cval;

	while (node != NULL) {
		cval = ct_compare(key, KEY(node));
		if (cval == 0)
			return node;
		else if (cval < 0) {
			if ((succ == NULL) ||
				(ct_compare(KEY(node), KEY(succ)) < 0))
				succ = node;
			node = LEFT_NODE(node);
		} else
			node = RIGHT_NODE(node);
	}
	return succ;
}

extern int
ct_index_of(node_t *root, PyObject *key)
/*
get index of item <key>, returns -1 if key not found.
*/
{
	node_t *node = root;
	int index = 0;
	int go_down = 1;
	node_stack_t *stack;
	stack = stack_init(32);

	for (;;) {
		if ((LEFT_NODE(node) != NULL) && go_down) {
			stack_push(stack, node);
			node = LEFT_NODE(node);
		}
		else {
			if (ct_compare(KEY(node), key) == 0) {
				stack_delete(stack);
				return index;
			}
			index++;
			if (RIGHT_NODE(node) != NULL) {
				node = RIGHT_NODE(node);
				go_down = 1;
			}
			else {
				if (stack_is_empty(stack)) {
					stack_delete(stack);
					return -1;
				}
				node = stack_pop(stack);
				go_down = 0;
			}
		}
	}
}

extern node_t *
ct_node_at(node_t *root, int index)
{
/*
root -- root node of tree
index -- index of wanted node

return NULL if index out of range
*/
	node_t *node = root;
	int counter = 0;
	int go_down = 1;
	node_stack_t *stack;

	if (index < 0) return NULL;

	stack = stack_init(32);

	for(;;) {
		if ((LEFT_NODE(node) != NULL) && go_down) {
			stack_push(stack, node);
			node = LEFT_NODE(node);
		}
		else {
			if (counter == index) {
				/* reached wanted index */
				stack_delete(stack);
				return node;
			}
			counter++;
			if (RIGHT_NODE(node) != NULL) {
				node = RIGHT_NODE(node);
				go_down = 1;
			}
			else {
				if (stack_is_empty(stack)) { /* index out of range */
					stack_delete(stack);
					return NULL;
                }
				node = stack_pop(stack);
				go_down = 0;
			}
		}
    }
}