cgul_rbtree_node.h File Reference

red-black tree node More...

#include "cgul_common.h"
#include "cgul_exception.h"

Include dependency graph for cgul_rbtree_node.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_rbtree_node *	cgul_rbtree_node_t

Functions
CGUL_EXPORT void *	cgul_rbtree_node__get_key (cgul_exception_t *cex, cgul_rbtree_node_t n)
CGUL_EXPORT void *	cgul_rbtree_node__get_value (cgul_exception_t *cex, cgul_rbtree_node_t n)
CGUL_EXPORT void	cgul_rbtree_node__set_value (cgul_exception_t *cex, cgul_rbtree_node_t n, const void *value)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree_node__get_prev (cgul_exception_t *cex, cgul_rbtree_node_t n)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree_node__get_next (cgul_exception_t *cex, cgul_rbtree_node_t n)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree_node__get_older (cgul_exception_t *cex, cgul_rbtree_node_t n)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree_node__get_younger (cgul_exception_t *cex, cgul_rbtree_node_t n)

Detailed Description

This class implements a red-black tree node which holds one key/value pair.

Author

Paul Serice

Typedef Documentation

cgul_rbtree_node_t

typedef typedefCGUL_BEGIN_C struct cgul_rbtree_node* cgul_rbtree_node_t

Opaque pointer to cgul_rbtree_node instance.

Function Documentation

cgul_rbtree_node__get_key()

CGUL_EXPORT void* cgul_rbtree_node__get_key	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the key stored in this node. The key is used to determine the sort order of the node. If you want to set the value of the key, there is no method to do so because changing the value of a key requires changing the node's position in the cgul_rbtree. Thus, if you need to change the value of a key, you should delete the node from the cgul_rbtree and insert a new node with the new value for the key.

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

key

Referenced by cgul_multimap_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_pairs(), cgul_multimap_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_pairs(), and cgul_rbtree_node_cxx::get_key().

cgul_rbtree_node__get_value()

CGUL_EXPORT void* cgul_rbtree_node__get_value	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the value stored in this node.

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

value

Referenced by cgul_rbtree_cxx::foldl_pairs(), cgul_rbtree_cxx::foldl_values(), cgul_rbtree_cxx::foldr_pairs(), cgul_rbtree_cxx::foldr_values(), and cgul_rbtree_node_cxx::get_value().

cgul_rbtree_node__set_value()

CGUL_EXPORT void cgul_rbtree_node__set_value	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n,
		const void *	value
	)

Set the value stored in this node.

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance
[in]	value

Referenced by cgul_rbtree_node_cxx::set_value().

cgul_rbtree_node__get_prev()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree_node__get_prev	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the previous node. Together with cgul_rbtree_node__get_next(), this method lets you traverse the tree in sorted order. If there is no previous node, this method returns NULL.

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

previous node

Referenced by cgul_multimap_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_pairs(), cgul_rbtree_cxx::foldr_values(), and cgul_rbtree_node_cxx::get_prev().

cgul_rbtree_node__get_next()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree_node__get_next	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the next node. Together with cgul_rbtree_node__get_prev(), this method lets you traverse the tree in sorted order. If there is no next node, this method returns NULL.

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

next node

Referenced by cgul_multimap_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_pairs(), cgul_rbtree_cxx::foldl_values(), cgul_rbtree_node_cxx::get_next(), and cgul_rbtree_cxx::traverse_range().

cgul_rbtree_node__get_older()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree_node__get_older	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the next older node. Together with cgul_rbtree_node__get_younger(), this method lets you traverse the tree in chronological order. If there is no older node, this method returns NULL.

cgul_rbtree_node__get_older() and cgul_rbtree_node__get_younger() are faster than cgul_rbtree_node__get_prev() and cgul_rbtree_node__get_next() because the latter pair of functions has to walk the tree to find the previous and next nodes in sort order, but the former pair has direct pointers to the younger and older nodes.

The following example shows how to iterate over the entire tree in reverse chronological order. Notice that you have to start with the youngest node when calling cgul_rbtree_node__get_older():

    cgul_rbtree_node_t n = cgul_rbtree__get_youngest(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_older(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

older node

Referenced by cgul_rbtree_node_cxx::get_older().

cgul_rbtree_node__get_younger()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree_node__get_younger	(	cgul_exception_t *	cex,
		cgul_rbtree_node_t	n
	)

Return the next younger node. Together with cgul_rbtree_node__get_older(), this method lets you traverse the tree in chronological order. If there is no younger node, this method returns NULL.

cgul_rbtree_node__get_older() and cgul_rbtree_node__get_younger() are faster than cgul_rbtree_node__get_prev() and cgul_rbtree_node__get_next() because the latter pair of functions has to walk the tree to find the previous and next nodes in sort order, but the former pair has direct pointers to the younger and older nodes.

The following example shows how to iterate over the entire tree in chronological order. Notice that you have to start with the oldest node when calling cgul_rbtree_node__get_younger():

    cgul_rbtree_node_t n = cgul_rbtree__get_oldest(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_younger(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	n	cgul_rbtree_node instance

Returns

younger node

Referenced by cgul_rbtree_node_cxx::get_younger().