key.h File Reference

#include <stdio.h>
#include "common.h"
#include "debug.h"

Include dependency graph for key.h:

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

Go to the source code of this file.

Macros
#define	BITS_TO_PINS(x)   DIV_UP(x, RBT_PIN_SIZE_BITS)
#define	BITS_TO_PINS_TO_BYTES(x)   PINS_TO_BYTES(BITS_TO_PINS(x))
#define	PINS_TO_BYTES(x)   ((x) * RBT_PIN_SIZE)
#define	RBT_DIVMOD(a, b, c, d)
#define	RBT_PIN_SIZE   sizeof(RBT_PIN_T)
#define	RBT_PIN_SIZE_BITS   (RBT_PIN_SIZE * BITS_PER_BYTE)

Functions
RBT_KEY_SIZE_T	RBT_COMMON_BIT_PREFIX_LEN (RBT_PIN_T *a, RBT_PIN_T *b, RBT_KEY_SIZE_T max)
void	RBT_FPRINT_BITS (FILE *fd, RBT_PIN_T *key, RBT_KEY_SIZE_T n, RBT_KEY_SIZE_T skip)

Detailed Description

Author

Xyne

Copyright

GPL2 only

Required Macro Definitions:

• RBT_KEY_H_PREFIX_

  The prefix for visible variable and function declarations in this header.

• RBT_PIN_T

  The type of array element used to hold the key bits interally. This is independent of the actual key type. It must be an unsigned integer type. Smaller types use space more efficiently but they are not always the fastest type. For example, GCC supports built-in functions (__builtin_clz() etc.) for some larger integer types but not for 8-bit integer types. These functions can have a significant effect on tree traversal.

  Note that the pin type is independent of the key type and size.

• RBT_KEY_SIZE_T

  An unsigned integer type large enough to count the bits in all possible keys. Let be the (maximum) number of bytes in a key and let be the number of bits per byte. The maximum number of bits in a key is then . The key size type must be an unsigned integer type that can store this number.

  Let be the size in bytes of our key size type. The maximum value that this type can represent is and thus the necessary condition is

  The minimum required size in bytes of the key size type is therefore

  

  of, if you prefer thinking in bits,

  

  where is the size of the key size type in bits and is the maximum number of bits in the key.

  For fixed-width types, will be equal to the value returned by sizeof. For variable width types, an upper limit will have to be anticipated.

• RBT_KEY_SIZE_T_FORMAT

  The printf format parameter for RBT_KEY_SIZE_T, e.g. "u". When using integer formats from stdint.h, use the matching parameters from inttypes.h.

Examples

Fixed Width 128 Bit Keys

uint_fast32_t will make use of GCC's __builtin_clz(). The minimum required size of the key size type is 7.011..., so an 8-bit type will suffice.

#define RBT_PIN_T uint_fast32_t
#define RBT_KEY_SIZE_T uint_fast8_t

Variable Width String Keys

Again, uint_fast_32_t is used for the reason given above. If string keys would not exceed 10 characters thenuing_fast8_twould suffice as the key size type, but 10 characters is very restrictive. By usinguint_fast32_t`, keys up to 100000000 characters can be used.

#define RBT_PIN_T uint_fast32_t
#define RBT_KEY_SIZE_T uint_fast32_t

Macro Definition Documentation

BITS_TO_PINS

#define BITS_TO_PINS

(

x

)

DIV_UP(x, RBT_PIN_SIZE_BITS)

Calculate the number of pins required to hold a given number of bits.

Parameters

[in]

x

The number of bits.

BITS_TO_PINS_TO_BYTES

#define BITS_TO_PINS_TO_BYTES

(

x

)

PINS_TO_BYTES(BITS_TO_PINS(x))

Calculate the number of bytes required to hold a number of bits using an array of pins. This will differ from the number of bytes required to hold the bits directly if the number of bits is not an integral multiple of the pin size.

Parameters

[in]

x

The number of bits.

PINS_TO_BYTES

#define PINS_TO_BYTES

(

x

)

((x) * RBT_PIN_SIZE)

Calculate the number of bytes required to hold a given number of pins.

Parameters

[in]

x

The number of pins.

RBT_DIVMOD

#define RBT_DIVMOD	(		a,
			b,
			c,
			d
	)

Value:

c = a / b; \
d = a % b

Calculate the quotient and remainder of integer division. This should be optimized by the compiler to a single division operation.

Parameters

[in]	a	The dividend.
[in]	b	The divisor.
[out]	c	The quotient.
[out]	d	The remainder.

RBT_PIN_SIZE

#define RBT_PIN_SIZE   sizeof(RBT_PIN_T)

The number of bytes in the pin type.

RBT_PIN_SIZE_BITS

#define RBT_PIN_SIZE_BITS   (RBT_PIN_SIZE * BITS_PER_BYTE)

The number of bits in the pin type.

Function Documentation

RBT_COMMON_BIT_PREFIX_LEN()

RBT_KEY_SIZE_T RBT_COMMON_BIT_PREFIX_LEN	(	RBT_PIN_T *	a,
		RBT_PIN_T *	b,
		RBT_KEY_SIZE_T	max
	)

Determine the number of common bits at the beginning of two keys.

Parameters

[in]	a	The first key.
[in]	b	The second key.
[in]	max	The maximum number of bits to check.

Returns

The number of common bits.

Todo:

Investigate ways to optimize this (e.g. asm).

RBT_FPRINT_BITS()

void RBT_FPRINT_BITS	(	FILE *	fd,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	n,
		RBT_KEY_SIZE_T	skip
	)

Print a string representation of the bits in a key.

Parameters

[in]	fd	The output file descriptor.
[in]	key	The key to print.
[in]	n	The number of bits to print.
[in]	skip	The number of bits from the start to skip.