moved source files into commit repository

1 files changed, 876 insertions, 0 deletions

diff --git a/src/map.c b/src/map.c
new file mode 100644
index 00000000..052e5445
--- /dev/null
+++ b/src/map.c
@@ -0,0 +1,876 @@
+/*
+ * Copyright 2010-2018 Adrian Thurston <thurston@colm.net>
+ *
+ * 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 <colm/map.h>
+
+#include <assert.h>
+#include <stdbool.h>
+
+#include <colm/pdarun.h>
+#include <colm/pool.h>
+#include <colm/bytecode.h>
+
+struct colm_struct *colm_map_el_get( struct colm_program *prg,
+		map_el_t *map_el, word_t gen_id, word_t field )
+{
+	struct generic_info *gi = &prg->rtd->generic_info[gen_id];
+	map_el_t *result = 0;
+	switch ( field ) {
+		case 0: 
+			result = map_el->prev;
+			break;
+		case 1: 
+			result = map_el->next;
+			break;
+		default:
+			assert( 0 );
+			break;
+	}
+
+	struct colm_struct *s = result != 0 ?
+			colm_struct_container( result, gi->el_offset ) : 0;
+	return s;
+}
+
+struct colm_struct *colm_map_get( struct colm_program *prg,
+		map_t *map, word_t gen_id, word_t field )
+{
+	struct generic_info *gi = &prg->rtd->generic_info[gen_id];
+	map_el_t *result = 0;
+	switch ( field ) {
+		case 0: 
+			result = map->head;
+			break;
+		case 1: 
+			result = map->tail;
+			break;
+		default:
+			assert( 0 );
+			break;
+	}
+
+	struct colm_struct *s = result != 0 ?
+			colm_struct_container( result, gi->el_offset ) : 0;
+	return s;
+}
+
+void map_list_abandon( map_t *map )
+{
+	map->head = map->tail = 0;
+}
+
+void map_list_add_before( map_t *map, map_el_t *next_el, map_el_t *new_el )
+{
+	/* Set the next pointer of the new element to next_el. We do
+	 * this regardless of the state of the list. */
+	new_el->next = next_el; 
+
+	/* Set reverse pointers. */
+	if ( next_el == 0 ) {
+		/* There is no next elememnt. We are inserting at the tail. */
+		new_el->prev = map->tail;
+		map->tail = new_el;
+	} 
+	else {
+		/* There is a next element and we can access next's previous. */
+		new_el->prev = next_el->prev;
+		next_el->prev = new_el;
+	} 
+
+	/* Set forward pointers. */
+	if ( new_el->prev == 0 ) {
+		/* There is no previous element. Set the head pointer.*/
+		map->head = new_el;
+	}
+	else {
+		/* There is a previous element, set it's next pointer to new_el. */
+		new_el->prev->next = new_el;
+	}
+}
+
+void map_list_add_after( map_t *map, map_el_t *prev_el, map_el_t *new_el )
+{
+	/* Set the previous pointer of new_el to prev_el. We do
+	 * this regardless of the state of the list. */
+	new_el->prev = prev_el; 
+
+	/* Set forward pointers. */
+	if (prev_el == 0) {
+		/* There was no prev_el, we are inserting at the head. */
+		new_el->next = map->head;
+		map->head = new_el;
+	} 
+	else {
+		/* There was a prev_el, we can access previous next. */
+		new_el->next = prev_el->next;
+		prev_el->next = new_el;
+	} 
+
+	/* Set reverse pointers. */
+	if (new_el->next == 0) {
+		/* There is no next element. Set the tail pointer. */
+		map->tail = new_el;
+	}
+	else {
+		/* There is a next element. Set it's prev pointer. */
+		new_el->next->prev = new_el;
+	}
+}
+
+
+map_el_t *map_list_detach( map_t *map, map_el_t *el )
+{
+	/* Set forward pointers to skip over el. */
+	if ( el->prev == 0 ) 
+		map->head = el->next; 
+	else
+		el->prev->next = el->next; 
+
+	/* Set reverse pointers to skip over el. */
+	if ( el->next == 0 ) 
+		map->tail = el->prev; 
+	else
+		el->next->prev = el->prev; 
+
+	/* Update List length and return element we detached. */
+	return el;
+}
+
+
+/* Once an insertion position is found, attach a element to the tree. */
+void map_attach_rebal( map_t *map, map_el_t *element, map_el_t *parent_el, map_el_t *last_less )
+{
+	/* Increment the number of element in the tree. */
+	map->tree_size += 1;
+
+	/* Set element's parent. */
+	element->parent = parent_el;
+
+	/* New element always starts as a leaf with height 1. */
+	element->left = 0;
+	element->right = 0;
+	element->height = 1;
+
+	/* Are we inserting in the tree somewhere? */
+	if ( parent_el != 0 ) {
+		/* We have a parent so we are somewhere in the tree. If the parent
+		 * equals lastLess, then the last traversal in the insertion went
+		 * left, otherwise it went right. */
+		if ( last_less == parent_el ) {
+			parent_el->left = element;
+
+			map_list_add_before( map, parent_el, element );
+		}
+		else {
+			parent_el->right = element;
+
+			map_list_add_after( map, parent_el, element );
+		}
+	}
+	else {
+		/* No parent element so we are inserting the root. */
+		map->root = element;
+
+		map_list_add_after( map, map->tail, element );
+	}
+
+	/* Recalculate the heights. */
+	map_recalc_heights( map, parent_el );
+
+	/* Find the first unbalance. */
+	map_el_t *ub = mapFindFirstUnbalGP( map, element );
+
+	/* rebalance. */
+	if ( ub != 0 )
+	{
+		/* We assert that after this single rotation the 
+		 * tree is now properly balanced. */
+		map_rebalance( map, ub );
+	}
+}
+
+#if 0
+/* Recursively delete all the children of a element. */
+void map_delete_children_of( map_t *map, map_el_t *element )
+{
+	/* Recurse left. */
+	if ( element->left ) {
+		map_delete_children_of( map, element->left );
+
+		/* Delete left element. */
+		delete element->left;
+		element->left = 0;
+	}
+
+	/* Recurse right. */
+	if ( element->right ) {
+		map_delete_children_of( map, element->right );
+
+		/* Delete right element. */
+		delete element->right;
+		element->left = 0;
+	}
+}
+
+void map_empty( map_t *map )
+{
+	if ( map->root ) {
+		/* Recursively delete from the tree structure. */
+		map_delete_children_of( map, map->root );
+		delete map->root;
+		map->root = 0;
+		map->tree_size = 0;
+
+		map_list_abandon( map );
+	}
+}
+#endif
+
+/* rebalance from a element whose gradparent is unbalanced. Only
+ * call on a element that has a grandparent. */
+map_el_t *map_rebalance( map_t *map, map_el_t *n )
+{
+	long lheight, rheight;
+	map_el_t *a, *b, *c;
+	map_el_t *t1, *t2, *t3, *t4;
+
+	map_el_t *p = n->parent; /* parent (Non-NUL). L*/
+	map_el_t *gp = p->parent; /* Grand-parent (Non-NULL). */
+	map_el_t *ggp = gp->parent; /* Great grand-parent (may be NULL). */
+
+	if (gp->right == p)
+	{
+		/*  gp
+		 *   		 *    p
+		 p
+		 */
+		if (p->right == n)
+		{
+			/*  gp
+			 *   			 *    p
+			 p
+			 *     			 *      n
+			 n
+			 */
+			a = gp;
+			b = p;
+			c = n;
+			t1 = gp->left;
+			t2 = p->left;
+			t3 = n->left;
+			t4 = n->right;
+		}
+		else
+		{
+			/*  gp
+			 *     			 *       p
+			 p
+			 *      /
+			 *     n
+			 */
+			a = gp;
+			b = n;
+			c = p;
+			t1 = gp->left;
+			t2 = n->left;
+			t3 = n->right;
+			t4 = p->right;
+		}
+	}
+	else
+	{
+		/*    gp
+		 *   /
+		 *  p
+		 */
+		if (p->right == n)
+		{
+			/*      gp
+			 *    /
+			 *  p
+			 *   			 *    n
+			 n
+			 */
+			a = p;
+			b = n;
+			c = gp;
+			t1 = p->left;
+			t2 = n->left;
+			t3 = n->right;
+			t4 = gp->right;
+		}
+		else
+		{
+			/*      gp
+			 *     /
+			 *    p
+			 *   /
+			 *  n
+			 */
+			a = n;
+			b = p;
+			c = gp;
+			t1 = n->left;
+			t2 = n->right;
+			t3 = p->right;
+			t4 = gp->right;
+		}
+	}
+
+	/* Perform rotation.
+	*/
+
+	/* Tie b to the great grandparent. */
+	if ( ggp == 0 )
+		map->root = b;
+	else if ( ggp->left == gp )
+		ggp->left = b;
+	else
+		ggp->right = b;
+	b->parent = ggp;
+
+	/* Tie a as a leftchild of b. */
+	b->left = a;
+	a->parent = b;
+
+	/* Tie c as a rightchild of b. */
+	b->right = c;
+	c->parent = b;
+
+	/* Tie t1 as a leftchild of a. */
+	a->left = t1;
+	if ( t1 != 0 ) t1->parent = a;
+
+	/* Tie t2 as a rightchild of a. */
+	a->right = t2;
+	if ( t2 != 0 ) t2->parent = a;
+
+	/* Tie t3 as a leftchild of c. */
+	c->left = t3;
+	if ( t3 != 0 ) t3->parent = c;
+
+	/* Tie t4 as a rightchild of c. */
+	c->right = t4;
+	if ( t4 != 0 ) t4->parent = c;
+
+	/* The heights are all recalculated manualy and the great
+	 * grand-parent is passed to recalcHeights() to ensure
+	 * the heights are correct up the tree.
+	 *
+	 * Note that recalcHeights() cuts out when it comes across
+	 * a height that hasn't changed.
+	 */
+
+	/* Fix height of a. */
+	lheight = a->left ? a->left->height : 0;
+	rheight = a->right ? a->right->height : 0;
+	a->height = (lheight > rheight ? lheight : rheight) + 1;
+
+	/* Fix height of c. */
+	lheight = c->left ? c->left->height : 0;
+	rheight = c->right ? c->right->height : 0;
+	c->height = (lheight > rheight ? lheight : rheight) + 1;
+
+	/* Fix height of b. */
+	lheight = a->height;
+	rheight = c->height;
+	b->height = (lheight > rheight ? lheight : rheight) + 1;
+
+	/* Fix height of b's parents. */
+	map_recalc_heights( map, ggp );
+	return ggp;
+}
+
+/* Recalculates the heights of all the ancestors of element. */
+void map_recalc_heights( map_t *map, map_el_t *element )
+{
+	while ( element != 0 )
+	{
+		long lheight = element->left ? element->left->height : 0;
+		long rheight = element->right ? element->right->height : 0;
+
+		long new_height = (lheight > rheight ? lheight : rheight) + 1;
+
+		/* If there is no chage in the height, then there will be no
+		 * change in any of the ancestor's height. We can stop going up.
+		 * If there was a change, continue upward. */
+		if (new_height == element->height)
+			return;
+		else
+			element->height = new_height;
+
+		element = element->parent;
+	}
+}
+
+/* Finds the first element whose grandparent is unbalanced. */
+map_el_t *mapFindFirstUnbalGP( map_t *map, map_el_t *element )
+{
+	long lheight, rheight, balance_prop;
+	map_el_t *gp;
+
+	if ( element == 0 || element->parent == 0 ||
+			element->parent->parent == 0 )
+		return 0;
+
+	/* Don't do anything if we we have no grandparent. */
+	gp = element->parent->parent;
+	while ( gp != 0 )
+	{
+		lheight = gp->left ? gp->left->height : 0;
+		rheight = gp->right ? gp->right->height : 0;
+		balance_prop = lheight - rheight;
+
+		if ( balance_prop < -1 || balance_prop > 1 )
+			return element;
+
+		element = element->parent;
+		gp = gp->parent;
+	}
+	return 0;
+}
+
+
+
+/* Finds the first element that is unbalanced. */
+map_el_t *map_find_first_unbal_el( map_t *map, map_el_t *element )
+{
+	if ( element == 0 )
+		return 0;
+
+	while ( element != 0 )
+	{
+		long lheight = element->left ?
+			element->left->height : 0;
+		long rheight = element->right ?
+			element->right->height : 0;
+		long balance_prop = lheight - rheight;
+
+		if ( balance_prop < -1 || balance_prop > 1 )
+			return element;
+
+		element = element->parent;
+	}
+	return 0;
+}
+
+/* Replace a element in the tree with another element not in the tree. */
+void map_replace_el( map_t *map, map_el_t *element, map_el_t *replacement )
+{
+	map_el_t *parent = element->parent,
+			*left = element->left,
+			*right = element->right;
+
+	replacement->left = left;
+	if (left)
+		left->parent = replacement;
+	replacement->right = right;
+	if (right)
+		right->parent = replacement;
+
+	replacement->parent = parent;
+	if (parent)
+	{
+		if (parent->left == element)
+			parent->left = replacement;
+		else
+			parent->right = replacement;
+	}
+	else {
+		map->root = replacement;
+	}
+
+	replacement->height = element->height;
+}
+
+
+/* Removes a element from a tree and puts filler in it's place.
+ * Filler should be null or a child of element. */
+void map_remove_el( map_t *map, map_el_t *element, map_el_t *filler )
+{
+	map_el_t *parent = element->parent;
+
+	if ( parent )
+	{
+		if ( parent->left == element )
+			parent->left = filler;
+		else
+			parent->right = filler;
+	}
+	else {
+		map->root = filler;
+	}
+
+	if ( filler )
+		filler->parent = parent;
+
+	return;
+}
+
+#if 0
+/* Recursive worker for tree copying. */
+map_el_t *map_copy_branch( program_t *prg, map_t *map, map_el_t *el, kid_t *old_next_down, kid_t **new_next_down )
+{
+	/* Duplicate element. Either the base element's copy constructor or defaul
+	 * constructor will get called. Both will suffice for initting the
+	 * pointers to null when they need to be. */
+	map_el_t *new_el = map_el_allocate( prg );
+
+	if ( (kid_t*)el == old_next_down )
+		*new_next_down = (kid_t*)new_el;
+
+	/* If the left tree is there, copy it. */
+	if ( new_el->left ) {
+		new_el->left = map_copy_branch( prg, map, new_el->left, old_next_down, new_next_down );
+		new_el->left->parent = new_el;
+	}
+
+	map_list_add_after( map, map->tail, new_el );
+
+	/* If the right tree is there, copy it. */
+	if ( new_el->right ) {
+		new_el->right = map_copy_branch( prg, map, new_el->right, old_next_down, new_next_down );
+		new_el->right->parent = new_el;
+	}
+
+	return new_el;
+}
+#endif
+
+static long map_cmp( program_t *prg, map_t *map, const tree_t *tree1, const tree_t *tree2 )
+{
+	if ( map->generic_info->key_type == TYPE_TREE ) {
+		return colm_cmp_tree( prg, tree1, tree2 );
+	}
+	else {
+		if ( (long)tree1 < (long)tree2 )
+			return -1;
+		else if ( (long)tree1 > (long)tree2)
+			return 1;
+		return 0;
+	}
+}
+
+map_el_t *map_insert_el( program_t *prg, map_t *map, map_el_t *element, map_el_t **last_found )
+{
+	long key_relation;
+	map_el_t *cur_el = map->root, *parent_el = 0;
+	map_el_t *last_less = 0;
+
+	while ( true ) {
+		if ( cur_el == 0 ) {
+			/* We are at an external element and did not find the key we were
+			 * looking for. Attach underneath the leaf and rebalance. */
+			map_attach_rebal( map, element, parent_el, last_less );
+
+			if ( last_found != 0 )
+				*last_found = element;
+			return element;
+		}
+
+		key_relation = map_cmp( prg, map,
+			element->key, cur_el->key );
+
+		/* Do we go left? */
+		if ( key_relation < 0 ) {
+			parent_el = last_less = cur_el;
+			cur_el = cur_el->left;
+		}
+		/* Do we go right? */
+		else if ( key_relation > 0 ) {
+			parent_el = cur_el;
+			cur_el = cur_el->right;
+		}
+		/* We have hit the target. */
+		else {
+			if ( last_found != 0 )
+				*last_found = cur_el;
+			return 0;
+		}
+	}
+}
+
+#if 0
+map_el_t *map_insert_key( program_t *prg, map_t *map, tree_t *key, map_el_t **last_found )
+{
+	long key_relation;
+	map_el_t *cur_el = map->root, *parent_el = 0;
+	map_el_t *last_less = 0;
+
+	while ( true ) {
+		if ( cur_el == 0 ) {
+			/* We are at an external element and did not find the key we were
+			 * looking for. Create the new element, attach it underneath the leaf
+			 * and rebalance. */
+			map_el_t *element = map_el_allocate( prg );
+			element->key = key;
+			map_attach_rebal( map, element, parent_el, last_less );
+
+			if ( last_found != 0 )
+				*last_found = element;
+			return element;
+		}
+
+		key_relation = map_cmp( prg, map, key, cur_el->key );
+
+		/* Do we go left? */
+		if ( key_relation < 0 ) {
+			parent_el = last_less = cur_el;
+			cur_el = cur_el->left;
+		}
+		/* Do we go right? */
+		else if ( key_relation > 0 ) {
+			parent_el = cur_el;
+			cur_el = cur_el->right;
+		}
+		/* We have hit the target. */
+		else {
+			if ( last_found != 0 )
+				*last_found = cur_el;
+			return 0;
+		}
+	}
+}
+#endif
+
+map_el_t *colm_map_insert( program_t *prg, map_t *map, map_el_t *map_el )
+{
+	return map_insert_el( prg, map, map_el, 0 );
+}
+
+map_el_t *colm_vmap_insert( program_t *prg, map_t *map, struct_t *key, struct_t *value )
+{
+	struct colm_struct *s = colm_struct_new( prg, map->generic_info->el_struct_id );
+
+	colm_struct_set_field( s, struct_t*, map->generic_info->el_offset, key );
+	colm_struct_set_field( s, struct_t*, 0, value );
+
+	map_el_t *map_el = colm_struct_get_addr( s, map_el_t*, map->generic_info->el_offset );
+
+	return colm_map_insert( prg, map, map_el );
+}
+
+map_el_t *colm_vmap_remove( program_t *prg, map_t *map, tree_t *key )
+{
+	map_el_t *map_el = colm_map_find( prg, map, key );
+	if ( map_el != 0 )
+		colm_map_detach( prg, map, map_el );
+	return 0;
+}
+
+tree_t *colm_vmap_find( program_t *prg, map_t *map, tree_t *key )
+{
+	map_el_t *map_el = colm_map_find( prg, map, key );
+	if ( map_el != 0 ) {
+		struct_t *s = colm_generic_el_container( prg, map_el,
+				map->generic_info - prg->rtd->generic_info );
+		tree_t *val = colm_struct_get_field( s, tree_t*, 0 );
+
+		if ( map->generic_info->value_type == TYPE_TREE )
+			colm_tree_upref( prg, val );
+
+		return val;
+	}
+	return 0;
+}
+
+void colm_map_detach( program_t *prg, map_t *map, map_el_t *map_el )
+{
+	map_detach( prg, map, map_el );
+}
+
+map_el_t *colm_map_find( program_t *prg, map_t *map, tree_t *key )
+{
+	return map_impl_find( prg, map, key );
+}
+
+/**
+ * \brief Find a element in the tree with the given key.
+ *
+ * \returns The element if key exists, null if the key does not exist.
+ */
+map_el_t *map_impl_find( program_t *prg, map_t *map, tree_t *key )
+{
+	map_el_t *cur_el = map->root;
+	long key_relation;
+
+	while ( cur_el != 0 ) {
+		key_relation = map_cmp( prg, map, key, cur_el->key );
+
+		/* Do we go left? */
+		if ( key_relation < 0 )
+			cur_el = cur_el->left;
+		/* Do we go right? */
+		else if ( key_relation > 0 )
+			cur_el = cur_el->right;
+		/* We have hit the target. */
+		else {
+			return cur_el;
+		}
+	}
+	return 0;
+}
+
+
+/**
+ * \brief Find a element, then detach it from the tree. 
+ * 
+ * The element is not deleted.
+ *
+ * \returns The element detached if the key is found, othewise returns null.
+ */
+map_el_t *map_detach_by_key( program_t *prg, map_t *map, tree_t *key )
+{
+	map_el_t *element = map_impl_find( prg, map, key );
+	if ( element )
+		map_detach( prg, map, element );
+
+	return element;
+}
+
+/**
+ * \brief Detach a element from the tree. 
+ *
+ * If the element is not in the tree then undefined behaviour results.
+ * 
+ * \returns The element given.
+ */
+map_el_t *map_detach( program_t *prg, map_t *map, map_el_t *element )
+{
+	map_el_t *replacement, *fixfrom;
+	long lheight, rheight;
+
+	/* Remove the element from the ordered list. */
+	map_list_detach( map, element );
+
+	/* Update treeSize. */
+	map->tree_size--;
+
+	/* Find a replacement element. */
+	if (element->right)
+	{
+		/* Find the leftmost element of the right subtree. */
+		replacement = element->right;
+		while (replacement->left)
+			replacement = replacement->left;
+
+		/* If replacing the element the with its child then we need to start
+		 * fixing at the replacement, otherwise we start fixing at the
+		 * parent of the replacement. */
+		if (replacement->parent == element)
+			fixfrom = replacement;
+		else
+			fixfrom = replacement->parent;
+
+		map_remove_el( map, replacement, replacement->right );
+		map_replace_el( map, element, replacement );
+	}
+	else if (element->left)
+	{
+		/* Find the rightmost element of the left subtree. */
+		replacement = element->left;
+		while (replacement->right)
+			replacement = replacement->right;
+
+		/* If replacing the element the with its child then we need to start
+		 * fixing at the replacement, otherwise we start fixing at the
+		 * parent of the replacement. */
+		if (replacement->parent == element)
+			fixfrom = replacement;
+		else
+			fixfrom = replacement->parent;
+
+		map_remove_el( map, replacement, replacement->left );
+		map_replace_el( map, element, replacement );
+	}
+	else
+	{
+		/* We need to start fixing at the parent of the element. */
+		fixfrom = element->parent;
+
+		/* The element we are deleting is a leaf element. */
+		map_remove_el( map, element, 0 );
+	}
+
+	/* If fixfrom is null it means we just deleted
+	 * the root of the tree. */
+	if ( fixfrom == 0 )
+		return element;
+
+	/* Fix the heights after the deletion. */
+	map_recalc_heights( map, fixfrom );
+
+	/* Fix every unbalanced element going up in the tree. */
+	map_el_t *ub = map_find_first_unbal_el( map, fixfrom );
+	while ( ub )
+	{
+		/* Find the element to rebalance by moving down from the first unbalanced
+		 * element 2 levels in the direction of the greatest heights. On the
+		 * second move down, the heights may be equal ( but not on the first ).
+		 * In which case go in the direction of the first move. */
+		lheight = ub->left ? ub->left->height : 0;
+		rheight = ub->right ? ub->right->height : 0;
+		assert( lheight != rheight );
+		if (rheight > lheight)
+		{
+			ub = ub->right;
+			lheight = ub->left ?
+				ub->left->height : 0;
+			rheight = ub->right ?
+				ub->right->height : 0;
+			if (rheight > lheight)
+				ub = ub->right;
+			else if (rheight < lheight)
+				ub = ub->left;
+			else
+				ub = ub->right;
+		}
+		else
+		{
+			ub = ub->left;
+			lheight = ub->left ?
+				ub->left->height : 0;
+			rheight = ub->right ?
+				ub->right->height : 0;
+			if (rheight > lheight)
+				ub = ub->right;
+			else if (rheight < lheight)
+				ub = ub->left;
+			else
+				ub = ub->left;
+		}
+
+
+		/* rebalance returns the grandparant of the subtree formed
+		 * by the element that were rebalanced.
+		 * We must continue upward from there rebalancing. */
+		fixfrom = map_rebalance( map, ub );
+
+		/* Find the next unbalaced element. */
+		ub = map_find_first_unbal_el( map, fixfrom );
+	}
+
+	return element;
+}
+
+
+