path: root/src/tree.c

/*
 * Tree data structure
 *
 * Copyright (C) 2017  Patrick McDermott
 *
 * This file is part of Marquee.
 *
 * Marquee is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Marquee is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Marquee.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "tree.h"

#include <inttypes.h>

#include <glib.h>

#if MQ_TREE_DEBUG

#include <math.h>

#define PRIWxPTR ((int) (logl(UINTPTR_MAX) / logl(16)))

static void
debug_print_tree_recurse(MqTree *node, gsize indent)
{
	gsize i;

	for (; node; node = node->next) {
		for (i = 0; i < indent; ++i) {
			g_print("\t");
		}
		g_print("\t0x%0*" PRIxPTR " (size %d, position %d)\n",
			PRIWxPTR, (uintptr_t) node, node->size, node->position);
		for (i = 0; i < indent; ++i) {
			g_print("\t");
		}
		g_print("\t\t\t(parent   0x%0*" PRIxPTR ")\n",
			PRIWxPTR, (uintptr_t) node->parent);
		for (i = 0; i < indent; ++i) {
			g_print("\t");
		}
		g_print("\t\t\t(siblings 0x%0*" PRIxPTR " and "
			"0x%0*" PRIxPTR ")\n",
			PRIWxPTR, (uintptr_t) node->prev,
			PRIWxPTR, (uintptr_t) node->next);
		for (i = 0; i < indent; ++i) {
			g_print("\t");
		}
		g_print("\t\t\t(children 0x%0*" PRIxPTR " to  "
			"0x%0*" PRIxPTR ")\n",
			PRIWxPTR, (uintptr_t) node->first_child,
			PRIWxPTR, (uintptr_t) node->last_child);

		if (node->first_child) {
			debug_print_tree_recurse(node->first_child, indent + 1);
		}
	}
}

static void
debug_print_tree(const gchar *msg, MqTree *node)
{
	g_print("%s 0x%0*" PRIxPTR ", ", msg, PRIWxPTR, (uintptr_t) node);
	node = node->root;
	g_print("new tree (size %d):\n", node->size);
	debug_print_tree_recurse(node, 0);
}

static void
debug_print_node(MqTree *node)
{
	g_print("\t0x%0*" PRIxPTR "\n", PRIWxPTR, (uintptr_t) node);
}

static void
debug_print_head(const gchar *head, MqTree *node)
{
	g_print("%s, starting at 0x%0*" PRIxPTR "\n",
		head, PRIWxPTR, (uintptr_t) node);
}

#else  /* MQ_TREE_DEBUG */

#define debug_print_tree(msg, node)
#define debug_print_node(node)
#define debug_print_head(head, node)

#endif  /* MQ_TREE_DEBUG */

MqTree *
mq_tree_insert_root_allocated(MqTree *node, gpointer data)
{
	node->root = node;
	node->size = 1;
	node->data = data;

	return node;
}

static void
update_sizes(MqTree *node, gint step)
{
	if (node) {
		node->size += step;
		update_sizes(node->parent, step);
	}
}

static gboolean
update_position(MqTree *node, gpointer user_data)
{
	gint *step;

	step = (gint *) user_data;

	node->position += *step;

	return MQ_TREE_CONTINUE;
}

static void
update_positions(MqTree *node, gint step)
{
	debug_print_head("Updating positions", node);

	mq_tree_foreach_from(node, update_position, &step);
}

MqTree *
mq_tree_append_child_allocated(MqTree *node, MqTree *parent, gpointer data)
{
	/* Copy ancestor pointers. */
	node->root   = parent->root;
	node->parent = parent;

	if (parent->last_child) {
		/* Parent has children, so get position from sibling and append
		 * to list of children. */
		node->position = parent->last_child->position;
		node->prev = parent->last_child;
		parent->last_child->next = node;
	} else {
		/* Parent has no children, so get position from parent and add
		 * first child to parent. */
		node->position = parent->position;
		parent->first_child = node;
	}
	parent->last_child = node;
	update_positions(node, 1);

	node->size = 0;
	update_sizes(node, 1);

	node->data = data;

	debug_print_tree("Appended child", node);

	return node;
}

MqTree *
mq_tree_append_sibling_allocated(MqTree *node, MqTree *sibling, gpointer data)
{
	/* Copy ancestor pointers. */
	node->root   = sibling->root;
	node->parent = sibling->parent;

	/* Link new node and parent's last child. */
	node->prev = node->parent->last_child;
	if (node->prev) {
		node->prev->next = node;
	}

	/* Set parent's new last child. */
	node->parent->last_child = node;

	node->position = node->parent->position + node->parent->size - 1;
	update_positions(node, 1);

	node->size = 0;
	update_sizes(node, 1);

	node->data = data;

	debug_print_tree("Appended sibling", node);

	return node;
}

void
mq_tree_remove_allocated(MqTree *node)
{
	MqTree *child;

	/* Link siblings to children or each other. */
	if (node->prev) {
		node->prev->next = node->first_child ?
			node->first_child : node->next;
	}
	if (node->next) {
		node->next->prev = node->last_child ?
			node->last_child : node->prev;
	}

	/* Update parent's links. */
	if (node->parent->first_child == node) {
		node->parent->first_child = node->first_child ?
			node->first_child : node->next;
	}
	if (node->parent->last_child == node) {
		node->parent->last_child = node->last_child ?
			node->last_child : node->prev;
	}

	/* Link children to siblings (may be NULL). */
	if (node->first_child) {
		node->first_child->prev = node->prev;
	}
	if (node->last_child) {
		node->last_child->next = node->next;
	}

	/* Link children to parent. */
	for (child = node->first_child; child; child = child->next) {
		child->parent = node->parent;
	}
	
	update_positions(node, -1);

	update_sizes(node, -1);

	debug_print_tree("Removed node", node);
}

static MqTree *
seek(MqTree *node, gint offset)
{
	/* Skip forward to the containing subtree. */
	while (node && node->position + node->size <= offset) {
		node = node->next;
	}

	/* Check whether we've gone past the end of the tree. */
	if (!node) {
		return NULL;
	}

	/* Check whether the sibling we've reached is the node we want. */
	if (node->position == offset) {
		return node;
	}

	/* Recurse down the subtree. */
	return seek(node->first_child, offset);
}

MqTree *
mq_tree_seek(MqTree *node, gint offset)
{
	/* XXX: Only forward seeking from a tree's root is supported. */
	g_assert(node);
	g_assert(node->position == 0);
	g_assert(offset > 0);

	return seek(node, offset);
}

static gboolean
foreach_down(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	for (; node; node = node->next) {
		/* XXX: Warning: Does not skip root node */
		debug_print_node(node);
		if (cb(node, user_data) == MQ_TREE_STOP) {
			return MQ_TREE_STOP;
		}

		if (node->first_child) {
			if (foreach_down(node->first_child, cb, user_data) ==
					MQ_TREE_STOP) {
				return MQ_TREE_STOP;
			}
		}
	}

	return MQ_TREE_CONTINUE;
}

void
mq_tree_foreach(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	debug_print_head("Traversing full tree", node);

	foreach_down(node->root->first_child, cb, user_data);
}

static gboolean
foreach_up(MqTree *node, gboolean (*cb)(MqTree *node, gpointer user_data),
	gpointer user_data)
{
	node = node->parent;
	if (!node) {
		return MQ_TREE_CONTINUE;
	}

	if (foreach_down(node->next, cb, user_data) == MQ_TREE_STOP) {
		return MQ_TREE_STOP;
	}

	if (foreach_up(node, cb, user_data) == MQ_TREE_STOP) {
		return MQ_TREE_STOP;
	}

	return MQ_TREE_CONTINUE;
}

void
mq_tree_foreach_from(MqTree *node,
	gboolean (*cb)(MqTree *node, gpointer user_data), gpointer user_data)
{
	debug_print_head("Traversing tree from position", node);

	if (foreach_down(node, cb, user_data) == MQ_TREE_CONTINUE) {
		foreach_up(node, cb, user_data);
	}
}