3 * Copyright (C) 2003 ReactOS Team
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; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 /* $Id: splaytree.c,v 1.2 2004/08/05 18:17:37 ion Exp $
21 * COPYRIGHT: See COPYING in the top level directory
22 * PROJECT: ReactOS system libraries
23 * PURPOSE: Splay-Tree implementation
24 * FILE: lib/rtl/splaytree.c
27 #include <ddk/ntddk.h>
33 /* FUNCTIONS *****************************************************************/
41 PRTL_SPLAY_LINKS Links
54 PRTL_SPLAY_LINKS Links
,
55 PRTL_SPLAY_LINKS
*Root
68 PRTL_SPLAY_LINKS Links
81 PRTL_SPLAY_LINKS Links
94 PRTL_SPLAY_LINKS Links
105 PRTL_SPLAY_LINKS STDCALL
106 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links
)
108 PRTL_SPLAY_LINKS Child
;
110 Child
= Links
->RightChild
;
114 if (Child
->LeftChild
== NULL
)
117 /* Get left-most child */
118 while (Child
->LeftChild
!= NULL
)
119 Child
= Child
->LeftChild
;
127 PRTL_SPLAY_LINKS STDCALL
128 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links
)
130 PRTL_SPLAY_LINKS Child
;
132 Child
= Links
->LeftChild
;
136 if (Child
->RightChild
== NULL
)
139 /* Get right-most child */
140 while (Child
->RightChild
!= NULL
)
141 Child
= Child
->RightChild
;