2 * Implementation of RTL_SPLAY_LINKS functions of libcaptive
3 * Copyright (C) 2002 Jan Kratochvil <project-captive@jankratochvil.net>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; exactly version 2 of June 1991 is required
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #include "reactos/ntos/rtltypes.h" /* self */
23 #include <glib/gmessages.h>
28 * @Links: Node to delete.
29 * %NULL value is forbidden.
31 * Deletes the given node from its tree.
33 * Returns: New root of the given tree. It may be %NULL if the tree becomes empty.
35 PRTL_SPLAY_LINKS RtlDelete(PRTL_SPLAY_LINKS Links)
37 RTL_SPLAY_LINKS *root,**selfp;
39 g_return_val_if_fail(Links!=NULL,NULL);
41 for (root=Links;root->Parent!=root;) {
42 g_assert(root->Parent!=NULL);
47 else if (Links->Parent->LeftChild==Links)
48 selfp=&Links->Parent->LeftChild;
49 else if (Links->Parent->RightChild==Links)
50 selfp=&Links->Parent->RightChild;
51 else g_assert_not_reached(); /* should not happen if the structures are valid */
53 if (!Links->LeftChild)
54 *selfp=Links->RightChild;
55 else if (!Links->RightChild)
56 *selfp=Links->LeftChild;
57 else g_assert_not_reached(); /* FIXME: NOT IMPLEMENTED YET */
59 /* FIXME: rebalance: NOT IMPLEMENTED YET */
67 * @Links: Root of the tree to rebalance.
68 * %NULL value is forbidden.
70 * Rebalances the tree for optimal heights and effective operations.
71 * FIXME: Currently a NOP in libcaptive.
73 * Returns: New root of the rebalanced tree.
74 * It may or it may not be equal to the given @Links.
76 PRTL_SPLAY_LINKS RtlSplay(PRTL_SPLAY_LINKS Links)
78 g_return_val_if_fail(Links!=NULL,NULL);
80 /* FIXME: rebalance: NOT IMPLEMENTED YET */