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.

			GSK Reference Manual
Top \| Description