library/stdlib_red_black.c
/*
* $Id: stdlib_red_black.c,v 1.6 2006-01-08 12:04:26 obarthel Exp $
*
* :ts=4
*
* Portable ISO 'C' (1994) runtime library for the Amiga computer
* Copyright (c) 2002-2015 by Olaf Barthel <obarthel (at) gmx.net>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Neither the name of Olaf Barthel nor the names of contributors
* may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef _STDLIB_HEADERS_H
#include "stdlib_headers.h"
#endif /* _STDLIB_HEADERS_H */
/****************************************************************************/
#ifndef _STDLIB_MEMORY_H
#include "stdlib_memory.h"
#endif /* _STDLIB_MEMORY_H */
/****************************************************************************/
#if defined(__USE_MEM_TREES) && defined(__MEM_DEBUG)
/****************************************************************************/
/* Red-Black Tree 'C' code adapted from Emin Martinian's implementation
(see <http://www.csua.berkeley.edu/~emin/source_code/red_black_tree>) */
/****************************************************************************/
STATIC VOID
help_insertion (struct MemoryTree * tree, struct MemoryNode * z)
{
struct MemoryNode *nil = &tree->mt_NullNode;
struct MemoryNode *x;
struct MemoryNode *y;
z->mn_Left = z->mn_Right = nil;
y = tree->mt_Root;
x = tree->mt_Root->mn_Left;
while (x != nil)
{
y = x;
if (x->mn_Allocation > z->mn_Allocation)
x = x->mn_Left;
else
x = x->mn_Right;
}
z->mn_Parent = y;
if (y == tree->mt_Root || y->mn_Allocation > z->mn_Allocation)
y->mn_Left = z;
else
y->mn_Right = z;
}
STATIC VOID
rotate_left (struct MemoryTree * tree, struct MemoryNode * x)
{
struct MemoryNode *nil = &tree->mt_NullNode;
struct MemoryNode *y;
y = x->mn_Right;
x->mn_Right = y->mn_Left;
if (y->mn_Left != nil)
y->mn_Left->mn_Parent = x;
y->mn_Parent = x->mn_Parent;
if (x == x->mn_Parent->mn_Left)
x->mn_Parent->mn_Left = y;
else
x->mn_Parent->mn_Right = y;
y->mn_Left = x;
x->mn_Parent = y;
}
STATIC VOID
rotate_right (struct MemoryTree * tree, struct MemoryNode * y)
{
struct MemoryNode *nil = &tree->mt_NullNode;
struct MemoryNode *x;
x = y->mn_Left;
y->mn_Left = x->mn_Right;
if (nil != x->mn_Right)
x->mn_Right->mn_Parent = y;
x->mn_Parent = y->mn_Parent;
if (y == y->mn_Parent->mn_Left)
y->mn_Parent->mn_Left = x;
else
y->mn_Parent->mn_Right = x;
x->mn_Right = y;
y->mn_Parent = x;
}
/****************************************************************************/
STATIC struct MemoryNode *
get_successor (struct MemoryTree * tree, struct MemoryNode * x)
{
struct MemoryNode *nil = &tree->mt_NullNode;
struct MemoryNode *root = tree->mt_Root;
struct MemoryNode *result;
struct MemoryNode *y;
if (nil != (y = x->mn_Right))
{
while (y->mn_Left != nil)
y = y->mn_Left;
result = y;
}
else
{
y = x->mn_Parent;
while (x == y->mn_Right)
{
x = y;
y = y->mn_Parent;
}
if (y == root)
result = nil;
else
result = y;
}
return (result);
}
STATIC VOID
remove_fixup (struct MemoryTree * tree, struct MemoryNode * x)
{
struct MemoryNode *root = tree->mt_Root->mn_Left;
struct MemoryNode *w;
while (NOT x->mn_IsRed && root != x)
{
if (x == x->mn_Parent->mn_Left)
{
w = x->mn_Parent->mn_Right;
if (w->mn_IsRed)
{
w->mn_IsRed = FALSE;
x->mn_Parent->mn_IsRed = TRUE;
rotate_left (tree, x->mn_Parent);
w = x->mn_Parent->mn_Right;
}
if (NOT w->mn_Right->mn_IsRed && NOT w->mn_Left->mn_IsRed)
{
w->mn_IsRed = TRUE;
x = x->mn_Parent;
}
else
{
if (NOT w->mn_Right->mn_IsRed)
{
w->mn_Left->mn_IsRed = FALSE;
w->mn_IsRed = TRUE;
rotate_right (tree, w);
w = x->mn_Parent->mn_Right;
}
w->mn_IsRed = x->mn_Parent->mn_IsRed;
x->mn_Parent->mn_IsRed = FALSE;
w->mn_Right->mn_IsRed = FALSE;
rotate_left (tree, x->mn_Parent);
x = root;
}
}
else
{
w = x->mn_Parent->mn_Left;
if (w->mn_IsRed)
{
w->mn_IsRed = FALSE;
x->mn_Parent->mn_IsRed = TRUE;
rotate_right (tree, x->mn_Parent);
w = x->mn_Parent->mn_Left;
}
if (NOT w->mn_Right->mn_IsRed && NOT w->mn_Left->mn_IsRed)
{
w->mn_IsRed = TRUE;
x = x->mn_Parent;
}
else
{
if (NOT w->mn_Left->mn_IsRed)
{
w->mn_Right->mn_IsRed = FALSE;
w->mn_IsRed = TRUE;
rotate_left (tree, w);
w = x->mn_Parent->mn_Left;
}
w->mn_IsRed = x->mn_Parent->mn_IsRed;
x->mn_Parent->mn_IsRed = FALSE;
w->mn_Left->mn_IsRed = FALSE;
rotate_right (tree, x->mn_Parent);
x = root;
}
}
}
x->mn_IsRed = FALSE;
}
/****************************************************************************/
void
__initialize_red_black_tree (struct MemoryTree *new_tree)
{
struct MemoryNode *temp;
temp = &new_tree->mt_NullNode;
temp->mn_Parent = temp->mn_Left = temp->mn_Right = temp;
temp->mn_IsRed = FALSE;
temp->mn_Allocation = NULL;
temp = new_tree->mt_Root = &new_tree->mt_RootNode;
temp->mn_Parent = temp->mn_Left = temp->mn_Right = &new_tree->mt_NullNode;
temp->mn_IsRed = FALSE;
temp->mn_Allocation = NULL;
}
/****************************************************************************/
void
__red_black_tree_insert (struct MemoryTree * tree, struct MemoryNode *x)
{
struct MemoryNode *y;
help_insertion (tree, x);
x->mn_IsRed = TRUE;
while (x->mn_Parent->mn_IsRed)
{
if (x->mn_Parent == x->mn_Parent->mn_Parent->mn_Left)
{
y = x->mn_Parent->mn_Parent->mn_Right;
if (y->mn_IsRed)
{
x->mn_Parent->mn_IsRed = FALSE;
y->mn_IsRed = FALSE;
x->mn_Parent->mn_Parent->mn_IsRed = TRUE;
x = x->mn_Parent->mn_Parent;
}
else
{
if (x == x->mn_Parent->mn_Right)
{
x = x->mn_Parent;
rotate_left (tree, x);
}
x->mn_Parent->mn_IsRed = FALSE;
x->mn_Parent->mn_Parent->mn_IsRed = TRUE;
rotate_right (tree, x->mn_Parent->mn_Parent);
}
}
else
{
y = x->mn_Parent->mn_Parent->mn_Left;
if (y->mn_IsRed)
{
x->mn_Parent->mn_IsRed = FALSE;
y->mn_IsRed = FALSE;
x->mn_Parent->mn_Parent->mn_IsRed = TRUE;
x = x->mn_Parent->mn_Parent;
}
else
{
if (x == x->mn_Parent->mn_Left)
{
x = x->mn_Parent;
rotate_right (tree, x);
}
x->mn_Parent->mn_IsRed = FALSE;
x->mn_Parent->mn_Parent->mn_IsRed = TRUE;
rotate_left (tree, x->mn_Parent->mn_Parent);
}
}
}
tree->mt_Root->mn_Left->mn_IsRed = FALSE;
}
/****************************************************************************/
struct MemoryNode *
__red_black_tree_find(struct MemoryTree * tree,void * allocation)
{
struct MemoryNode * x = tree->mt_Root->mn_Left;
struct MemoryNode * nil = &tree->mt_NullNode;
struct MemoryNode * result = NULL;
while(x != nil)
{
if(x->mn_Allocation > allocation)
{
x = x->mn_Left;
}
else if (x->mn_Allocation < allocation)
{
x = x->mn_Right;
}
else
{
result = x;
break;
}
}
return(result);
}
/****************************************************************************/
void
__red_black_tree_remove (struct MemoryTree * tree, struct MemoryNode * z)
{
struct MemoryNode *nil = &tree->mt_NullNode;
struct MemoryNode *root = tree->mt_Root;
struct MemoryNode *y;
struct MemoryNode *x;
y = (z->mn_Left == nil || z->mn_Right == nil) ? z : get_successor (tree, z);
x = (y->mn_Left == nil) ? y->mn_Right : y->mn_Left;
if (root == (x->mn_Parent = y->mn_Parent))
{
root->mn_Left = x;
}
else
{
if (y == y->mn_Parent->mn_Left)
y->mn_Parent->mn_Left = x;
else
y->mn_Parent->mn_Right = x;
}
if (NOT y->mn_IsRed)
remove_fixup (tree, x);
if (y != z)
{
y->mn_Left = z->mn_Left;
y->mn_Right = z->mn_Right;
y->mn_Parent = z->mn_Parent;
y->mn_IsRed = z->mn_IsRed;
z->mn_Left->mn_Parent = z->mn_Right->mn_Parent = y;
if (z == z->mn_Parent->mn_Left)
z->mn_Parent->mn_Left = y;
else
z->mn_Parent->mn_Right = y;
}
}
/****************************************************************************/
#endif /* __USE_MEM_TREES && __MEM_DEBUG */