libBLOC

/*
 * Copyright (C) 2023 Barry
 *
 * This file is part of Barry's Little Objects in C Library (libBLOC).
 *
 * libBLOC 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.
 *
 * libBLOC is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTIBILITY 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
 * libBLOC.  If not, see <https://www.gnu.org/licenses/>.
 */

#include <BLOC/object.h>
#include <BLOC/tree.h>
#include "../assert.h"
#include "tree.h"

/* Find a node recursively */
static struct TreeNode *
_tree_find(Tree *t, struct TreeNode *root, void *obj)
{
	if (!root)
		return NULL;
	if (root->header.obj == obj)
		return root;
	if (t->compare(root->header.obj, obj) > 0)
		return _tree_find(t, root->left, obj);
	else
		return _tree_find(t, root->right, obj);
}

/* Remove a node from a tree recursively */
static struct TreeNode *
_tree_remove_r(Tree *t, struct TreeNode *parent, struct TreeNode *child)
{
	/* Remove node */
	struct TreeNode *tmp;
	if (t->compare(parent->header.obj, child->header.obj) > 0) {
		parent->left = _tree_remove_r(t, parent->left, child);
	} else if (t->compare(parent->header.obj, child->header.obj) < 0) {
		parent->right = _tree_remove_r(t, parent->right, child);
	} else {
		/* Less than two children: adopt child if available */
		if (!child->left)
			return child->right;
		if (!child->right)
			return child->left;
		/* Two children: swap for logical successor */
		tmp = (struct TreeNode *) child->header.next;
		if (child->right != tmp)
			tmp->right = _tree_remove_r(t, child->right, tmp);
		tmp->left = child->left;
		return tmp;
	}

	/* Balance */
	if (_tree_count(parent->right) > _tree_count(parent->left) + 1)
		return _tree_rotate_left(parent);
	if (_tree_count(parent->left) > _tree_count(parent->right) + 1)
		return _tree_rotate_right(parent);
	return parent;
}

/* Remove an object from a tree */
void
tree_remove(Tree *tree, void *obj)
{
	ASSERT(tree);
	ASSERT(obj);
	ASSERT(obj_verify(obj));
	if (!tree->header.start)
		return;
	if (tree->type && tree->type != obj_type(obj))
		return;
	obj_lock(tree);

	/* Search for object */
	struct TreeNode *node = _tree_find(tree, tree->root, obj);
	if (!node) {
		obj_unlock(tree);
		return;
	}

	/* Unlink from tree */
	tree->root = _tree_remove_r(tree, tree->root, node);

	/* Unlink from linear list */
	if (tree->header.start == &node->header)
		tree->header.start = node->header.next;
	if (tree->header.end == &node->header)
		tree->header.end = node->header.prev;
	if (node->header.prev)
		node->header.prev->next = node->header.next;
	if (node->header.next)
		node->header.next->prev = node->header.prev;

	obj_put(node->header.obj);
	tree->header.entries--;
	free(node);

	obj_unlock(tree);
}