common.h File Reference

#include <limits.h>

Include dependency graph for common.h:

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

Go to the source code of this file.

Macros
#define	_RBT_TOKEN_2(a, b)   _ ## a ## b
	Identical to RBT_TOKEN_2() except that the resulting token is prefixed with an underscore. More...
#define	_RBT_TOKEN_2_W(a, b)   _RBT_TOKEN_2(a,b)
	A wrapper for _RBT_TOKEN_2() to ensure macro expansion. More...
#define	BITS_PER_BYTE   CHAR_BIT
	The number of bits in a byte.
#define	BYTE_T   char
	A byte type.
#define	DIV_UP(x, y)   ((x) ? (1 + (x-1)/y) : 0)
	Ceiling division of a positive integer. More...
#define	FIRST_BIT_IS_1(x)   (MOST_SIGNIFICANT_BIT(typeof(x)) & (x))
	Determine if the most significant bit is 1. More...
#define	MAX(a, b)   (((a) > (b)) ? (a) : (b))
	Return the maximum of a or b. More...
#define	MIN(a, b)   (((a) < (b)) ? (a) : (b))
	Return the minimum of a or b. More...
#define	MOST_SIGNIFICANT_BIT(x)   (((x) ~ 0) ^ (((x) ~ 0) >> 1))
	The most significant bit of the given integer's type. More...
#define	MOST_SIGNIFICANT_BIT_W(x)   MOST_SIGNIFICANT_BIT(x)
	A wrapper for MOST_SIGNIFICANT_BIT() to ensure macro expansion. More...
#define	N_BIT_IS_1(x, n)   (MOST_SIGNIFICANT_BIT(typeof(x)) & (x << n))
	Determine if the nth bit is 1. More...
#define	RBT_TOKEN_2(a, b)   a ## b
	Combine a and b into a single token. More...
#define	RBT_TOKEN_2_W(a, b)   RBT_TOKEN_2(a,b)
	A wrapper for RBT_TOKEN_2() to ensure macro expansion. More...

Enumerations
enum	rbt_query_action_t {   RBT_QUERY_ACTION_DELETE ,   RBT_QUERY_ACTION_INSERT ,   RBT_QUERY_ACTION_RETRIEVE ,   RBT_QUERY_ACTION_RETRIEVE_AND_INSERT ,   RBT_QUERY_ACTION_SWAP }
	Query action for RBT_NODE_QUERY(). More...
enum	rbt_retrieve_action_t {   RBT_RETRIEVE_ACTION_NOTHING ,   RBT_RETRIEVE_ACTION_INSERT ,   RBT_RETRIEVE_ACTION_INSERT_OR_REPLACE ,   RBT_RETRIEVE_ACTION_PREFIX_SUBTREE }
	Retrieval action for RBT_NODE_RETRIEVE(). More...

Functions
const char *	rbt_query_action_string (rbt_query_action_t action)
	Return a string representing a query action. More...
const char *	rbt_retrieve_action_string (rbt_retrieve_action_t action)
	Return a string representing a retrieval action. More...

Detailed Description

Author

Xyne

Copyright

GPL2 only

Macro Definition Documentation

_RBT_TOKEN_2

#define _RBT_TOKEN_2	(		a,
			b
	)		_ ## a ## b

Identical to RBT_TOKEN_2() except that the resulting token is prefixed with an underscore.

Parameters

[in]	a	The first part.
[in]	b	The second part.

_RBT_TOKEN_2_W

#define _RBT_TOKEN_2_W	(		a,
			b
	)		_RBT_TOKEN_2(a,b)

A wrapper for _RBT_TOKEN_2() to ensure macro expansion.

Parameters

[in]	a	The first part. This may be a macro.
[in]	b	The second part. This may be a macro.

DIV_UP

#define DIV_UP	(		x,
			y
	)		((x) ? (1 + (x-1)/y) : 0)

Ceiling division of a positive integer.

Divide dividend by divisor, rounding any remainder up. This catches overflows.

Parameters

[in]	x	The dividend.
[in]	y	The divisor.

FIRST_BIT_IS_1

#define FIRST_BIT_IS_1

(

x

)

(MOST_SIGNIFICANT_BIT(typeof(x)) & (x))

Determine if the most significant bit is 1.

Parameters

[in]

x

The number containing the bit to check.

MAX

#define MAX	(		a,
			b
	)		(((a) > (b)) ? (a) : (b))

Return the maximum of a or b.

Parameters

[in]	a	The first number.
[in]	b	The second number.

MIN

#define MIN	(		a,
			b
	)		(((a) < (b)) ? (a) : (b))

Return the minimum of a or b.

Parameters

[in]	a	The first number.
[in]	b	The second number.

MOST_SIGNIFICANT_BIT

#define MOST_SIGNIFICANT_BIT

(

x

)

(((x) ~ 0) ^ (((x) ~ 0) >> 1))

The most significant bit of the given integer's type.

Parameters

[in]

x

The number to check.

MOST_SIGNIFICANT_BIT_W

#define MOST_SIGNIFICANT_BIT_W

(

x

)

MOST_SIGNIFICANT_BIT(x)

A wrapper for MOST_SIGNIFICANT_BIT() to ensure macro expansion.

Parameters

[in]

x

The number to check.

N_BIT_IS_1

#define N_BIT_IS_1	(		x,
			n
	)		(MOST_SIGNIFICANT_BIT(typeof(x)) & (x << n))

Determine if the nth bit is 1.

Parameters

[in]	x	The number containing the bit to check.
[in]	n	The number of the bit to check.

RBT_TOKEN_2

#define RBT_TOKEN_2	(		a,
			b
	)		a ## b

Combine a and b into a single token.

Parameters

[in]	a	The first part.
[in]	b	The second part.

RBT_TOKEN_2_W

#define RBT_TOKEN_2_W	(		a,
			b
	)		RBT_TOKEN_2(a,b)

A wrapper for RBT_TOKEN_2() to ensure macro expansion.

Parameters

[in]	a	The first part. This may be a macro.
[in]	b	The second part. This may be a macro.

Enumeration Type Documentation

rbt_query_action_t

enum rbt_query_action_t

Query action for RBT_NODE_QUERY().

Enumerator
RBT_QUERY_ACTION_DELETE	Delete a key-value pair.
RBT_QUERY_ACTION_INSERT	Insert a key-value pair. Existing values will be overwritten.
RBT_QUERY_ACTION_RETRIEVE	Retrieve a value associated with a key.
RBT_QUERY_ACTION_RETRIEVE_AND_INSERT	Retrieve a value associated with a key and replace it with a new value.
RBT_QUERY_ACTION_SWAP	Directly insert a key-value pair and return an existing value if present. For statically allocated values this will be identical to RBT_QUERY_ACTION_RETRIEVE_AND_INSERT. For dynamically allocated values, this will directly swap the pointers without any freeing or allocation.

rbt_retrieve_action_t

enum rbt_retrieve_action_t

Retrieval action for RBT_NODE_RETRIEVE().

Enumerator
RBT_RETRIEVE_ACTION_NOTHING	No additional action is performed.
RBT_RETRIEVE_ACTION_INSERT	An insertion is made if the target node does not exist. Existing values are not modified.
RBT_RETRIEVE_ACTION_INSERT_OR_REPLACE	An insertion is made if the target node does not exist. Existing values are modified.
RBT_RETRIEVE_ACTION_PREFIX_SUBTREE	There are three possibilities when matching a prefix. 1) No node contains the prefix. 2) One node's associated key is equal to the prefix. All children of this node also contain the prefix in their associated keys. 3) One node's associated key is the first to contain the prefix. All children of this node also contain the prefix in their associated keys. Case 1 returns NULL without ambiguity. For cases 2 and 3, information about the eventual key difference is required. This can be retrieved by updating the bits field of the passed parent_node_ptr in the retrieve function. Todo: Update with reference to example wrapper.

Function Documentation

rbt_query_action_string()

const char * rbt_query_action_string

(

rbt_query_action_t

action

)

Return a string representing a query action.

Parameters

[in]

action

The action for which to return a string.

rbt_retrieve_action_string()

const char * rbt_retrieve_action_string

(

rbt_retrieve_action_t

action

)

Return a string representing a retrieval action.

Parameters

[in]

action

The action for which to return a string.