From f3ca60606f557f24b615860e1142c70c93802fc5 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 5 Oct 2009 16:47:57 +0000 Subject: Begin kD splay tree implementation. --- libdimension/kD_splay_tree.c | 68 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100644 libdimension/kD_splay_tree.c (limited to 'libdimension/kD_splay_tree.c') diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c new file mode 100644 index 0000000..24987c4 --- /dev/null +++ b/libdimension/kD_splay_tree.c @@ -0,0 +1,68 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library 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 * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +#include "dimension_impl.h" +#include + +static dmnsn_kD_splay_node * +dmnsn_new_kD_splay_node() +{ + dmnsn_kD_splay_node *node = malloc(sizeof(dmnsn_kD_splay_node)); + if (!node) { + dmnsn_error(DMNSN_SEVERITY_HIGH, "kD splay tree node allocation failed."); + } + return node; +} + +static void +dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node) +{ + free(node); +} + +/* Return an empty tree */ +dmnsn_kD_splay_node * +dmnsn_new_kD_splay_tree() +{ + return NULL; +} + +/* Copy a kD splay tree */ +dmnsn_kD_splay_node *dmnsn_kD_splay_copy(dmnsn_kD_splay_node *root) +{ + dmnsn_kD_splay_node *node = NULL; + if (root) { + node = dmnsn_new_kD_splay_node(); + *node = *root; + node->left = dmnsn_kD_splay_copy(node->left); + node->right = dmnsn_kD_splay_copy(node->right); + } + return node; +} + +void +dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_node *root) +{ + if (root) { + dmnsn_delete_kD_splay_tree(root->left); + dmnsn_delete_kD_splay_tree(root->right); + dmnsn_delete_kD_splay_node(root); + } +} -- cgit v1.2.3