← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/virtualbox-ose/gutsy

« back to all changes in this revision

Viewing changes to src/VBox/Runtime/table/avl_Base.cpp.h

  • Committer: Bazaar Package Importer
  • Author(s): Steve Kowalik
  • Date: 2007-09-08 16:44:58 UTC
  • Revision ID: james.westby@ubuntu.com-20070908164458-wao29470vqtr8ksy
Tags: upstream-1.5.0-dfsg2
Import upstream version 1.5.0-dfsg2

Show diffs side-by-side

added added

removed removed

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