Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Macros | Functions
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

Required Macro Definitions:

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

#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]xThe number of bits.
#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]xThe number of bits.
#define PINS_TO_BYTES (   x)    ((x) * RBT_PIN_SIZE)

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

Parameters
[in]xThe number of pins.
#define RBT_DIVMOD (   a,
  b,
  c,
 
)
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]aThe dividend.
[in]bThe divisor.
[out]cThe quotient.
[out]dThe remainder.
#define RBT_PIN_SIZE   sizeof(RBT_PIN_T)

The number of bytes in the pin type.

#define RBT_PIN_SIZE_BITS   (RBT_PIN_SIZE * BITS_PER_BYTE)

The number of bits in the pin type.

Function Documentation

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]aThe first key.
[in]bThe second key.
[in]maxThe maximum number of bits to check.
Returns
The number of common bits.
Todo:
Investigate ways to optimize this (e.g. asm).
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]fdThe output file descriptor.
[in]keyThe key to print.
[in]nThe number of bits to print.
[in]skipThe number of bits from the start to skip.