VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/table/avl_Base.cpp.h@ 18603

Last change on this file since 18603 was 8155, checked in by vboxsync, 17 years ago

The Big Sun Rebranding Header Change

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 16.7 KB
Line 
1/* $Id: avl_Base.cpp.h 8155 2008-04-18 15:16:47Z vboxsync $ */
2/** @file
3 * kAVLBase - basic routines for all AVL trees.
4 */
5
6/*
7 * Copyright (C) 2001-2002 knut st. osmundsen (bird-src-spam@anduin.net)
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 *
26 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27 * Clara, CA 95054 USA or visit http://www.sun.com if you need
28 * additional information or have any questions.
29 */
30
31#ifndef _kAVLBase_h_
32#define _kAVLBase_h_
33
34
35/** @page pg_rt_kAVL kAVL Template configuration.
36 * @internal
37 *
38 * This is a template made to implement multiple AVL trees. The differences
39 * among the implementations are related to the key used.
40 *
41 * \#define KAVL_FN
42 * Use this to alter the names of the AVL functions.
43 * Must be defined.
44 *
45 * \#define KAVL_EQUAL_ALLOWED
46 * Define this to tell us that equal keys are allowed.
47 * Then Equal keys will be put in a list pointed to by pList in the KAVLNODECORE.
48 * This is by default not defined.
49 *
50 * \#define KAVL_CHECK_FOR_EQUAL_INSERT
51 * Define this to enable insert check for equal nodes.
52 * This is by default not defined.
53 *
54 * \#define KAVL_MAX_STACK
55 * Use this to specify the number of stack entries the stack will use when inserting
56 * and removing nodes from the tree. I think the size should be about
57 * log2(<max nodes>) + 3
58 * Must be defined.
59 *
60 */
61
62/*******************************************************************************
63* Defined Constants And Macros *
64*******************************************************************************/
65#define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
66
67/** @def KAVL_GET_POINTER
68 * Reads a 'pointer' value.
69 *
70 * @returns The native pointer.
71 * @param pp Pointer to the pointer to read.
72 */
73
74/** @def KAVL_GET_POINTER_NULL
75 * Reads a 'pointer' value which can be KAVL_NULL.
76 *
77 * @returns The native pointer.
78 * @returns NULL pointer if KAVL_NULL.
79 * @param pp Pointer to the pointer to read.
80 */
81
82/** @def KAVL_SET_POINTER
83 * Writes a 'pointer' value.
84 * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
85 *
86 * @returns stored pointer.
87 * @param pp Pointer to where to store the pointer.
88 * @param p Native pointer to assign to *pp.
89 */
90
91/** @def KAVL_SET_POINTER_NULL
92 * Writes a 'pointer' value which can be KAVL_NULL.
93 *
94 * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
95 * if p is not KAVL_NULL of course.
96 *
97 * @returns stored pointer.
98 * @param pp Pointer to where to store the pointer.
99 * @param pp2 Pointer to where to pointer to assign to pp. This can be KAVL_NULL
100 */
101
102#ifndef KAVL_GET_POINTER
103# ifdef KAVL_OFFSET
104# define KAVL_GET_POINTER(pp) ( (PKAVLNODECORE)((intptr_t)(pp) + *(pp)) )
105# define KAVL_GET_POINTER_NULL(pp) ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
106# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = ((intptr_t)(p) - (intptr_t)(pp)) )
107# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) != KAVL_NULL ? (intptr_t)KAVL_GET_POINTER(pp2) - (intptr_t)(pp) : KAVL_NULL )
108# else
109# define KAVL_GET_POINTER(pp) ( *(pp) )
110# define KAVL_GET_POINTER_NULL(pp) ( *(pp) )
111# define KAVL_SET_POINTER(pp, p) ( (*(pp)) = (p) )
112# define KAVL_SET_POINTER_NULL(pp, pp2) ( (*(pp)) = *(pp2) )
113# endif
114#endif
115
116
117/** @def KAVL_NULL
118 * The NULL 'pointer' equivalent.
119 */
120#ifndef KAVL_NULL
121# ifdef KAVL_OFFSET
122# define KAVL_NULL 0
123# else
124# define KAVL_NULL NULL
125# endif
126#endif
127
128#ifndef KAVL_RANGE
129# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
130# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E) KAVL_E(key1B, key2B)
131#endif
132
133
134
135/*******************************************************************************
136* Structures and Typedefs *
137*******************************************************************************/
138/*
139 * A stack used to avoid recursive calls...
140 */
141typedef struct _kAvlStack
142{
143 unsigned cEntries;
144 PPKAVLNODECORE aEntries[KAVL_MAX_STACK];
145} KAVLSTACK, *PKAVLSTACK;
146
147typedef struct _kAvlStack2
148{
149 unsigned cEntries;
150 PKAVLNODECORE aEntries[KAVL_MAX_STACK];
151 char achFlags[KAVL_MAX_STACK];
152} KAVLSTACK2, *PLAVLSTACK2;
153
154
155
156/**
157 * Rewinds a stack of pointers to pointers to nodes, rebalancing the tree.
158 * @param pStack Pointer to stack to rewind.
159 * @sketch LOOP thru all stack entries
160 * BEGIN
161 * Get pointer to pointer to node (and pointer to node) from the stack.
162 * IF 2 higher left subtree than in right subtree THEN
163 * BEGIN
164 * IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
165 * * n+2|n+3
166 * / \ / \
167 * n+2 n ==> n+1 n+1|n+2
168 * / \ / \
169 * n+1 n|n+1 n|n+1 n
170 *
171 * Or with keys:
172 *
173 * 4 2
174 * / \ / \
175 * 2 5 ==> 1 4
176 * / \ / \
177 * 1 3 3 5
178 *
179 * ELSE
180 * * n+2
181 * / \ / \
182 * n+2 n n+1 n+1
183 * / \ ==> / \ / \
184 * n n+1 n L R n
185 * / \
186 * L R
187 *
188 * Or with keys:
189 * 6 4
190 * / \ / \
191 * 2 7 ==> 2 6
192 * / \ / \ / \
193 * 1 4 1 3 5 7
194 * / \
195 * 3 5
196 * END
197 * ELSE IF 2 higher in right subtree than in left subtree THEN
198 * BEGIN
199 * Same as above but left <==> right. (invert the picture)
200 * ELSE
201 * IF correct height THEN break
202 * ELSE correct height.
203 * END
204 */
205DECLINLINE(void) KAVL_FN(Rebalance)(PKAVLSTACK pStack)
206{
207 while (pStack->cEntries > 0)
208 {
209 /** @todo Perhaps some of these KAVL_SET_POINTER_NULL() cases could be optimized away.. */
210 PPKAVLNODECORE ppNode = pStack->aEntries[--pStack->cEntries];
211 PKAVLNODECORE pNode = KAVL_GET_POINTER(ppNode);
212 PKAVLNODECORE pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
213 unsigned char uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
214 PKAVLNODECORE pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
215 unsigned char uchRightHeight = AVL_HEIGHTOF(pRightNode);
216
217 if (uchRightHeight + 1 < uchLeftHeight)
218 {
219 PKAVLNODECORE pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
220 PKAVLNODECORE pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
221 unsigned char uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
222
223 if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
224 {
225 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
226 KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
227 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
228 KAVL_SET_POINTER(ppNode, pLeftNode);
229 }
230 else
231 {
232 KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
233 KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
234 KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
235 KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
236 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
237 pLeftRightNode->uchHeight = uchLeftHeight;
238 KAVL_SET_POINTER(ppNode, pLeftRightNode);
239 }
240 }
241 else if (uchLeftHeight + 1 < uchRightHeight)
242 {
243 PKAVLNODECORE pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
244 unsigned char uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
245 PKAVLNODECORE pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
246
247 if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
248 {
249 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
250 KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
251 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
252 KAVL_SET_POINTER(ppNode, pRightNode);
253 }
254 else
255 {
256 KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
257 KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
258 KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
259 KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
260 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
261 pRightLeftNode->uchHeight = uchRightHeight;
262 KAVL_SET_POINTER(ppNode, pRightLeftNode);
263 }
264 }
265 else
266 {
267 register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
268 if (uchHeight == pNode->uchHeight)
269 break;
270 pNode->uchHeight = uchHeight;
271 }
272 }
273
274}
275
276
277
278
279/**
280 * Inserts a node into the AVL-tree.
281 * @returns TRUE if inserted.
282 * FALSE if node exists in tree.
283 * @param ppTree Pointer to the AVL-tree root node pointer.
284 * @param pNode Pointer to the node which is to be added.
285 * @sketch Find the location of the node (using binary tree algorithm.):
286 * LOOP until KAVL_NULL leaf pointer
287 * BEGIN
288 * Add node pointer pointer to the AVL-stack.
289 * IF new-node-key < node key THEN
290 * left
291 * ELSE
292 * right
293 * END
294 * Fill in leaf node and insert it.
295 * Rebalance the tree.
296 */
297RTDECL(bool) KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
298{
299 KAVLSTACK AVLStack;
300 PPKAVLNODECORE ppCurNode = ppTree;
301 register KAVLKEY Key = pNode->Key; NOREF(Key);
302#ifdef KAVL_RANGE
303 register KAVLKEY KeyLast = pNode->KeyLast; NOREF(KeyLast);
304#endif
305 register PKAVLNODECORE pCurNode;
306
307 AVLStack.cEntries = 0;
308
309#ifdef KAVL_RANGE
310 if (Key > KeyLast)
311 return false;
312#endif
313
314 for (;;)
315 {
316 if (*ppCurNode != KAVL_NULL)
317 pCurNode = KAVL_GET_POINTER(ppCurNode);
318 else
319 break;
320
321 kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
322 AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
323#ifdef KAVL_EQUAL_ALLOWED
324 if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
325 {
326 /*
327 * If equal then we'll use a list of equal nodes.
328 */
329 pNode->pLeft = pNode->pRight = KAVL_NULL;
330 pNode->uchHeight = 0;
331 KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
332 KAVL_SET_POINTER(&pCurNode->pList, pNode);
333 return true;
334 }
335#endif
336#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
337 if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
338 return false;
339#endif
340 if (KAVL_G(pCurNode->Key, Key))
341 ppCurNode = &pCurNode->pLeft;
342 else
343 ppCurNode = &pCurNode->pRight;
344 }
345
346 pNode->pLeft = pNode->pRight = KAVL_NULL;
347#ifdef KAVL_EQUAL_ALLOWED
348 pNode->pList = KAVL_NULL;
349#endif
350 pNode->uchHeight = 1;
351 KAVL_SET_POINTER(ppCurNode, pNode);
352
353 KAVL_FN(Rebalance)(SSToDS(&AVLStack));
354 return true;
355}
356
357
358/**
359 * Removes a node from the AVL-tree.
360 * @returns Pointer to the node.
361 * @param ppTree Pointer to the AVL-tree root node pointer.
362 * @param Key Key value of the node which is to be removed.
363 * @sketch Find the node which is to be removed:
364 * LOOP until not found
365 * BEGIN
366 * Add node pointer pointer to the AVL-stack.
367 * IF the keys matches THEN break!
368 * IF remove key < node key THEN
369 * left
370 * ELSE
371 * right
372 * END
373 * IF found THEN
374 * BEGIN
375 * IF left node not empty THEN
376 * BEGIN
377 * Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
378 * Start at left node.
379 * LOOP until right node is empty
380 * BEGIN
381 * Add to stack.
382 * go right.
383 * END
384 * Link out the found node.
385 * Replace the node which is to be removed with the found node.
386 * Correct the stack entry for the pointer to the left tree.
387 * END
388 * ELSE
389 * BEGIN
390 * Move up right node.
391 * Remove last stack entry.
392 * END
393 * Balance tree using stack.
394 * END
395 * return pointer to the removed node (if found).
396 */
397RTDECL(PKAVLNODECORE) KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
398{
399 KAVLSTACK AVLStack;
400 PPKAVLNODECORE ppDeleteNode = ppTree;
401 register PKAVLNODECORE pDeleteNode;
402
403 AVLStack.cEntries = 0;
404
405 for (;;)
406 {
407 if (*ppDeleteNode != KAVL_NULL)
408 pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
409 else
410 return NULL;
411
412 kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
413 AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
414 if (KAVL_E(pDeleteNode->Key, Key))
415 break;
416
417 if (KAVL_G(pDeleteNode->Key, Key))
418 ppDeleteNode = &pDeleteNode->pLeft;
419 else
420 ppDeleteNode = &pDeleteNode->pRight;
421 }
422
423 if (pDeleteNode->pLeft != KAVL_NULL)
424 {
425 /* find the rightmost node in the left tree. */
426 const unsigned iStackEntry = AVLStack.cEntries;
427 PPKAVLNODECORE ppLeftLeast = &pDeleteNode->pLeft;
428 register PKAVLNODECORE pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
429
430 while (pLeftLeast->pRight != KAVL_NULL)
431 {
432 kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
433 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
434 ppLeftLeast = &pLeftLeast->pRight;
435 pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
436 }
437
438 /* link out pLeftLeast */
439 KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
440
441 /* link it in place of the delete node. */
442 KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
443 KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
444 pLeftLeast->uchHeight = pDeleteNode->uchHeight;
445 KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
446 AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
447 }
448 else
449 {
450 KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
451 AVLStack.cEntries--;
452 }
453
454 KAVL_FN(Rebalance)(SSToDS(&AVLStack));
455 return pDeleteNode;
456}
457
458#endif
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette