RedBlacktree-Index impl

Implement RedBlacktree-Index.

Summary
RedBlacktree-Index implImplement RedBlacktree-Index.
CopyrightThis program is free software.
Files
C-kern/api/ds/inmem/redblacktree.hHeader file of RedBlacktree-Index.
C-kern/ds/inmem/redblacktree.cImplementation file of RedBlacktree-Index impl.
redblacktree_t
internal macros
COLORReturns the color bit of the node.
ISBLACKReturns true if color is black.
ISREDReturns true if color is red.
PARENTAccess parent pointer from node.
SETBLACKSets the color of node to black.
SETREDSets the color of node to red.
SETPARENTSets the new parent of node and keeps the encoded color.
SETPARENTREDSets a new parent for node and sets its color to red.
SETPARENTBLACKSets a new parent for node and sets its color to black.
EVENADDRESSTest for node having an even address (bit 0 is clear).
KEYCOMPARECasts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt.
NODECOMPARECasts both nodes to type typeadapt_object_t and calls callcmpobj_typeadapt.
test
lifetime
search
change
iterate
Functions
test

Copyright

This program is free software.  You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

Author

© 2011 Jörg Seebohn

Files

C-kern/api/ds/inmem/redblacktree.h

Header file of RedBlacktree-Index.

C-kern/ds/inmem/redblacktree.c

Implementation file of RedBlacktree-Index impl.

redblacktree_t

Summary
internal macros
COLORReturns the color bit of the node.
ISBLACKReturns true if color is black.
ISREDReturns true if color is red.
PARENTAccess parent pointer from node.
SETBLACKSets the color of node to black.
SETREDSets the color of node to red.
SETPARENTSets the new parent of node and keeps the encoded color.
SETPARENTREDSets a new parent for node and sets its color to red.
SETPARENTBLACKSets a new parent for node and sets its color to black.
EVENADDRESSTest for node having an even address (bit 0 is clear).
KEYCOMPARECasts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt.
NODECOMPARECasts both nodes to type typeadapt_object_t and calls callcmpobj_typeadapt.
test
lifetime
search
change
iterate

internal macros

COLOR

#define COLOR(node) (((uintptr_t)1) & (uintptr_t)((node)->parent))

Returns the color bit of the node.

Returns

1color is black
0color is red

ISBLACK

#define ISBLACK(node) (0 != COLOR(node))

Returns true if color is black.

ISRED

#define ISRED(node) (0 == COLOR(node))

Returns true if color is red.

PARENT

#define PARENT(
   node
) ((redblacktree_node_t*) (((uintptr_t)-2) & (uintptr_t)((node)->parent)))

Access parent pointer from node.  The reason to use this this macro is that the color of a node is encoded in the lowest bit of the parent pointer.

SETBLACK

#define SETBLACK(
   node
) (node)->parent = (redblacktree_node_t*) (((uintptr_t)1) | (uintptr_t)((node)->parent))

Sets the color of node to black.

SETRED

#define SETRED(node) (node)->parent = PARENT(node)

Sets the color of node to red.

SETPARENT

#define SETPARENT(
   node,
   newparent
) (node)->parent = (redblacktree_node_t*) (COLOR(node) | (uintptr_t)newparent)

Sets the new parent of node and keeps the encoded color.  The least bit of newparent must be cleared.

SETPARENTRED

#define SETPARENTRED(node,
newparent) (node)->parent = newparent

Sets a new parent for node and sets its color to red.  The least bit of newparent must be cleared.

SETPARENTBLACK

#define SETPARENTBLACK(
   node,
   newparent
) (node)->parent = (redblacktree_node_t*) (((uintptr_t)1) | (uintptr_t)newparent)

Sets a new parent for node and sets its color to black.  The least bit of newparent must be cleared.

EVENADDRESS

#define EVENADDRESS(node) ((1u & (uintptr_t)(node)) == 0)

Test for node having an even address (bit 0 is clear).

KEYCOMPARE

#define KEYCOMPARE(
   key,
   node
) callcmpkeyobj_typeadaptmember(&tree->nodeadp, key, memberasobject_typeadaptmember(&tree->nodeadp, node))

Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt.  This macro expects variable name tree to point to redblacktree_t.

NODECOMPARE

#define NODECOMPARE(
   lnode,
   rnode
) callcmpobj_typeadaptmember(&tree->nodeadp, memberasobject_typeadaptmember(&tree->nodeadp, lnode), memberasobject_typeadaptmember(&tree->nodeadp, rnode))

Casts both nodes to type typeadapt_object_t and calls callcmpobj_typeadapt.  This macro expects variable name tree to point to redblacktree_t.

test

lifetime

search

change

iterate

Functions

test

Interface to red black tree which allows access to a set of sorted elements in O(log n).
Implement RedBlacktree-Index.
#define COLOR(node) (((uintptr_t)1) & (uintptr_t)((node)->parent))
Returns the color bit of the node.
#define ISBLACK(node) (0 != COLOR(node))
Returns true if color is black.
#define ISRED(node) (0 == COLOR(node))
Returns true if color is red.
#define PARENT(
   node
) ((redblacktree_node_t*) (((uintptr_t)-2) & (uintptr_t)((node)->parent)))
Access parent pointer from node.
#define SETBLACK(
   node
) (node)->parent = (redblacktree_node_t*) (((uintptr_t)1) | (uintptr_t)((node)->parent))
Sets the color of node to black.
#define SETRED(node) (node)->parent = PARENT(node)
Sets the color of node to red.
#define SETPARENT(
   node,
   newparent
) (node)->parent = (redblacktree_node_t*) (COLOR(node) | (uintptr_t)newparent)
Sets the new parent of node and keeps the encoded color.
#define SETPARENTRED(node,
newparent) (node)->parent = newparent
Sets a new parent for node and sets its color to red.
#define SETPARENTBLACK(
   node,
   newparent
) (node)->parent = (redblacktree_node_t*) (((uintptr_t)1) | (uintptr_t)newparent)
Sets a new parent for node and sets its color to black.
#define EVENADDRESS(node) ((1u & (uintptr_t)(node)) == 0)
Test for node having an even address (bit 0 is clear).
#define KEYCOMPARE(
   key,
   node
) callcmpkeyobj_typeadaptmember(&tree->nodeadp, key, memberasobject_typeadaptmember(&tree->nodeadp, node))
Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt.
typedef struct typeadapt_object_t typeadapt_object_t
Declares abstract object type.
#define callcmpkeyobj_typeadapt(
   typeadp,
   ...
) callcmpkeyobj_typeadaptcomparator(&(typeadp)->comparator, typeadp, __VA_ARGS__)
Implements typeadapt_t.callcmpkeyobj_typeadapt.
#define NODECOMPARE(
   lnode,
   rnode
) callcmpobj_typeadaptmember(&tree->nodeadp, memberasobject_typeadaptmember(&tree->nodeadp, lnode), memberasobject_typeadaptmember(&tree->nodeadp, rnode))
Casts both nodes to type typeadapt_object_t and calls callcmpobj_typeadapt.
#define callcmpobj_typeadapt(
   typeadp,
   ...
) callcmpobj_typeadaptcomparator(&(typeadp)->comparator, typeadp, __VA_ARGS__)
Implements typeadapt_t.callcmpobj_typeadapt.
Close