gskrbtreemacros

gskrbtreemacros — Flexible Red-Black Trees implemented as macros

Synopsis




#define     GSK_RBTREE_INSERT               (tree, node, collision_node)
#define     GSK_RBTREE_REMOVE               (tree, node)
#define     GSK_RBTREE_LOOKUP               (tree, key, out)
#define     GSK_RBTREE_LOOKUP_COMPARATOR    (tree, key, key_comparator, out)
#define     GSK_RBTREE_FIRST                (tree, out)
#define     GSK_RBTREE_LAST                 (tree, out)
#define     GSK_RBTREE_NEXT                 (tree, in, out)
#define     GSK_RBTREE_PREV                 (tree, in, out)
#define     GSK_RBTREE_SUPREMUM             (tree, key, out)
#define     GSK_RBTREE_SUPREMUM_COMPARATOR  (tree, key, key_comparator, out)
#define     GSK_RBTREE_INFIMUM              (tree, key, out)
#define     GSK_RBTREE_INFIMUM_COMPARATOR   (tree, key, key_comparator, out)
#define     GSK_RBCTREE_INSERT              (tree, node, collision_node)
#define     GSK_RBCTREE_REMOVE              (tree, node)
#define     GSK_RBCTREE_LOOKUP              (tree, key, out)
#define     GSK_RBCTREE_LOOKUP_COMPARATOR   (tree, key, key_comparator, out)
#define     GSK_RBCTREE_FIRST               (tree, out)
#define     GSK_RBCTREE_LAST                (tree, out)
#define     GSK_RBCTREE_NEXT                (tree, in, out)
#define     GSK_RBCTREE_PREV                (tree, in, out)
#define     GSK_RBCTREE_SUPREMUM            (tree, key, out)
#define     GSK_RBCTREE_SUPREMUM_COMPARATOR (tree, key, key_comparator, out)
#define     GSK_RBCTREE_INFIMUM             (tree, key, out)
#define     GSK_RBCTREE_INFIMUM_COMPARATOR  (tree, key, key_comparator, out)
#define     GSK_RBCTREE_GET_BY_INDEX        (tree, index, out)
#define     GSK_RBCTREE_GET_BY_INDEX_UNCHECKED(tree, index, out)
#define     GSK_RBCTREE_GET_NODE_INDEX      (tree, node, index_out)

Description

The macros defined here allow you to implement efficient red-black trees which put their data in existing node structures. Besides efficiency, this can be much more convenient because the same node may be a member of multiple trees. It shares these characteristics in common with the gsklistmacros, so that a member of a rbtree may be a member of a gsk-list, etc etc. all simultanteously.

TODO: Description of what an rbtree is.

The actual rbtree consists of a macro with eight arguments:

top

...

type*

...

is_red

...

set_is_red

...

parent

...

left, right

...

comparator

...

TODO: Description of what an rbctree is.

The actual rbctree consists of a macro with ten arguments:

top

...

type*

...

is_red

...

set_is_red

...

get_count

...

set_count

...

parent

...

left, right

...

comparator

...

TODO: example use cases.

TODO: Some example programs.

Details

GSK_RBTREE_INSERT()

#define     GSK_RBTREE_INSERT(tree, node, collision_node)

Add a new node into the rbtree, potentially removing another node of the same key, which will be returned in collision_node.

tree : The RBTree (a macro that expands to eight arguments) to affect.
node : The node to insert. It should not be in the tree initially. Its parent, left and right pointers will be initialized.
collision_node : A variable that will be set to NULL if there was no collision, or the node that was replaced if there was a collision.

GSK_RBTREE_REMOVE()

#define     GSK_RBTREE_REMOVE(tree, node)

Remove a new from the tree.

tree : The RBTree (a macro that expands to eight arguments) to affect.
node : The node to remove from the tree.

GSK_RBTREE_LOOKUP()

#define     GSK_RBTREE_LOOKUP(tree, key, out)

Lookup a node in the tree.

This will use the same comparator as the normal tree lookup, so the key should probably be something that looks like a node. See GSK_RBTREE_LOOKUP_COMPARATOR for a method to do the lookup using a key that is in a different format.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : A node whose equivalent we are trying to find.
out : The node that was found, or NULL if no node was found.

GSK_RBTREE_LOOKUP_COMPARATOR()

#define     GSK_RBTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)

Lookup a node in the tree.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : A key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : The node that was found, or NULL if no node was found.

GSK_RBTREE_FIRST()

#define     GSK_RBTREE_FIRST(tree, out)

Get the first element of the tree. (The first element is the least element, as determined by the comparator)

tree : The RBTree (a macro that expands to eight arguments) to query.
out : A variable which will be set to the first element in the tree, or NULL if the tree is empty.

GSK_RBTREE_LAST()

#define     GSK_RBTREE_LAST(tree, out)

Get the last element of the tree. (The last element is the greatest element, as determined by the comparator)

tree :
out : A variable which will be set to the last element in the tree, or NULL if the tree is empty.

GSK_RBTREE_NEXT()

#define     GSK_RBTREE_NEXT(tree, in, out)

Get the next element in the tree, after a given element.

in and out may be the same variable.

tree : The RBTree (a macro that expands to eight arguments) to traverse.
in : The starting element (must be non-NULL)
out : A variable which will be set to the next element in the tree, or NULL if in was the last element.

GSK_RBTREE_PREV()

#define     GSK_RBTREE_PREV(tree, in, out)

Get the previous element in the tree, after a given element.

in and out may be the same variable.

tree : The RBTree (a macro that expands to eight arguments) to traverse.
in : The starting element (must be non-NULL)
out : A variable which will be set to the previous element in the tree, or NULL if in was the first element.

GSK_RBTREE_SUPREMUM()

#define     GSK_RBTREE_SUPREMUM(tree, key, out)

Find the first node in the tree which is after or equal to key.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : The key to lookup.
out : Set the the first node in the tree which is after or equal to key, according to the usual tree comparator, or NULL if no element is greater than or equal to key.

GSK_RBTREE_SUPREMUM_COMPARATOR()

#define     GSK_RBTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)

Find the first node in the tree which is after or equal to key.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : The key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : Set the the first node in the tree which is after or equal to key, according to key_comparator, or NULL if no element is greater than or equal to key.

GSK_RBTREE_INFIMUM()

#define     GSK_RBTREE_INFIMUM(tree, key, out)

Find the last node in the tree which is before or equal to key.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : The key to lookup.
out : Set the the last node in the tree which is before or equal to key, according to the usual tree comparator, or NULL if no element is less than or equal to key.

GSK_RBTREE_INFIMUM_COMPARATOR()

#define     GSK_RBTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)

Find the last node in the tree which is before or equal to key.

tree : The RBTree (a macro that expands to eight arguments) to query.
key : The key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : Set the the last node in the tree which is before or equal to key, according to key_comparator, or NULL if no element is less than or equal to key.

GSK_RBCTREE_INSERT()

#define     GSK_RBCTREE_INSERT(tree, node, collision_node)

Add a new node into the rbtree, potentially removing another node of the same key, which will be returned in collision_node.

tree : The RBCTree (a macro that expands to ten arguments) to affect.
node : The node to insert. It should not be in the tree initially. Its parent, left and right pointers will be initialized.
collision_node : A variable that will be set to NULL if there was no collision, or the node that was replaced if there was a collision.

GSK_RBCTREE_REMOVE()

#define     GSK_RBCTREE_REMOVE(tree, node)

Remove a new from the tree.

tree : The RBCTree (a macro that expands to ten arguments) to affect.
node : The node to remove from the tree.

GSK_RBCTREE_LOOKUP()

#define     GSK_RBCTREE_LOOKUP(tree, key, out)

Lookup a node in the tree.

This will use the same comparator as the normal tree lookup, so the key should probably be something that looks like a node. See GSK_RBCTREE_LOOKUP_COMPARATOR for a method to do the lookup using a key that is in a different format.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : A node whose equivalent we are trying to find.
out : The node that was found, or NULL if no node was found.

GSK_RBCTREE_LOOKUP_COMPARATOR()

#define     GSK_RBCTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)

Lookup a node in the tree.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : A key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : The node that was found, or NULL if no node was found.

GSK_RBCTREE_FIRST()

#define     GSK_RBCTREE_FIRST(tree, out)

Get the first element of the tree. (The first element is the least element, as determined by the comparator)

tree : The RBCTree (a macro that expands to ten arguments) to query.
out : A variable which will be set to the first element in the tree, or NULL if the tree is empty.

GSK_RBCTREE_LAST()

#define     GSK_RBCTREE_LAST(tree, out)

Get the last element of the tree. (The last element is the greatest element, as determined by the comparator)

tree :
out : A variable which will be set to the last element in the tree, or NULL if the tree is empty.

GSK_RBCTREE_NEXT()

#define     GSK_RBCTREE_NEXT(tree, in, out)

Get the next element in the tree, after a given element.

in and out may be the same variable.

tree : The RBCTree (a macro that expands to ten arguments) to traverse.
in : The starting element (must be non-NULL)
out : A variable which will be set to the next element in the tree, or NULL if in was the last element.

GSK_RBCTREE_PREV()

#define     GSK_RBCTREE_PREV(tree, in, out)

Get the previous element in the tree, after a given element.

in and out may be the same variable.

tree : The RBCTree (a macro that expands to ten arguments) to traverse.
in : The starting element (must be non-NULL)
out : A variable which will be set to the previous element in the tree, or NULL if in was the first element.

GSK_RBCTREE_SUPREMUM()

#define     GSK_RBCTREE_SUPREMUM(tree, key, out)

Find the first node in the tree which is after or equal to key.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : The key to lookup.
out : Set the the first node in the tree which is after or equal to key, according to the usual tree comparator, or NULL if no element is greater than or equal to key.

GSK_RBCTREE_SUPREMUM_COMPARATOR()

#define     GSK_RBCTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)

Find the first node in the tree which is after or equal to key.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : The key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : Set the the first node in the tree which is after or equal to key, according to key_comparator, or NULL if no element is greater than or equal to key.

GSK_RBCTREE_INFIMUM()

#define     GSK_RBCTREE_INFIMUM(tree, key, out)

Find the last node in the tree which is before or equal to key.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : The key to lookup.
out : Set the the last node in the tree which is before or equal to key, according to the usual tree comparator, or NULL if no element is less than or equal to key.

GSK_RBCTREE_INFIMUM_COMPARATOR()

#define     GSK_RBCTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)

Find the last node in the tree which is before or equal to key.

tree : The RBCTree (a macro that expands to ten arguments) to query.
key : The key to lookup.
key_comparator : A macro that takes three arguments: the key, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
out : Set the the last node in the tree which is before or equal to key, according to key_comparator, or NULL if no element is less than or equal to key.

GSK_RBCTREE_GET_BY_INDEX()

#define     GSK_RBCTREE_GET_BY_INDEX(tree, index, out)

Find the N-th node in the tree.

tree : The RBCTree (a macro that expands to ten arguments) to query.
index : The index of the node which you want to find.
out : variable to store the index-th node in, or NULL if index is out-of-range.

GSK_RBCTREE_GET_BY_INDEX_UNCHECKED()

#define     GSK_RBCTREE_GET_BY_INDEX_UNCHECKED(tree, index, out)

Find the N-th node in the tree, assuming that index is valid.

tree : The RBCTree (a macro that expands to ten arguments) to query.
index : The index of the node which you want to find.
out : variable to store the index-th node in. This routine will crash if index is out-of-range.

GSK_RBCTREE_GET_NODE_INDEX()

#define     GSK_RBCTREE_GET_NODE_INDEX(tree, node, index_out)

Get the index of an arbitrary node.

tree : The RBCTree (a macro that expands to ten arguments) to query.
node : The node to obtain the index of.
index_out : variable to store the index of node in.

See Also

gskqsortmacro