coveb-tree.h File Reference

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures
struct	FastAllocFreeNode
struct	FastAllocArena
struct	FastAllocController
struct	vEBPNodeTypeIndicator
struct	vEBMPNodeTypeIndicator
struct	coveb_bq
struct	coveb_mq
struct	vEBFullNode
struct	vEBMPayloadStatic
	payload of up to 32 bytes More...
struct	vEBSingleNode
struct	vEBMPDatum
	32-bit unsigned integer with payload of up to 32 bytes More...
struct	vEBMSingleNode
struct	vEBMFullNode
struct	vEBSimpleBitTable
struct	vEBPNode
struct	vEBMPNode
struct	vEBPSearchResult
struct	vEBMPSearchResult
Defines
#define	USE_FAST_ALLOCATOR   1
#define	MAXBLOCKSIZES   32
#define	COVEB_KEYTYPE   uint32_t
#define	MASK_TOTFULL   0x00000010
#define	MASK_TOPSIDE   0x00000020
#define	MAXDIRECTK   5
Functions
struct coveb_bq *	coveb_bq_new (void)
struct coveb_bq *	coveb_bq_clone (const struct coveb_bq *q)
void	coveb_bq_free (struct coveb_bq *q)
void	coveb_bq_insert (struct coveb_bq *q, uint32_t x)
uint32_t	coveb_bq_extractmin (struct coveb_bq *q)
uint32_t	coveb_bq_remove (struct coveb_bq *q, uint32_t m)
uint32_t	coveb_bq_size (const struct coveb_bq *q)
uint32_t	coveb_bq_contains (const struct coveb_bq *q, uint32_t x)
uint32_t	coveb_bq_addresses_full (const struct coveb_bq *q)
void	coveb_bq_locate_smallest_not_less_than (const struct coveb_bq *q, uint32_t incl_lower_bound, uint32_t *result_x, uint32_t *gotresult)
void	coveb_bq_successor (const struct coveb_bq *q, uint32_t excl_lower_bound, uint32_t *result_x, uint32_t *gotresult)
uint32_t	coveb_bq_max (const struct coveb_bq *q)
uint32_t	coveb_bq_min (const struct coveb_bq *q)
void	coveb_failout (const char *msg)
struct coveb_mq *	coveb_mq_new (uint32_t payload_bits)
struct coveb_mq *	coveb_mq_clone (const struct coveb_mq *q)
void	coveb_mq_free (struct coveb_mq *q)
void	coveb_mq_insert (struct coveb_mq *q, struct vEBMPDatum x)
struct vEBMPDatum	coveb_mq_extractmin (struct coveb_mq *q)
struct vEBMPDatum	coveb_mq_min (const struct coveb_mq *q)
struct vEBMPDatum	coveb_mq_max (const struct coveb_mq *q)
void	coveb_mq_locate_smallest_not_less_than (const struct coveb_mq *q, uint32_t incl_lower_bound, struct vEBMPDatum *result_x, uint32_t *gotresult)
struct vEBMPDatum	fetch_from_bottom_table (struct vEBMPNode *v, uint32_t ind)
void	store_to_bottom_table (struct vEBMPNode *v, struct vEBMPDatum d, uint32_t ind)
uint32_t	coveb_mq_remove (struct coveb_mq *q, uint32_t x)
uint32_t	coveb_mq_addresses_full (const struct coveb_mq *q)
uint32_t	coveb_mq_size (const struct coveb_mq *q)
uint32_t	coveb_mq_contains (const struct coveb_mq *q, uint32_t x)
void	coveb_mq_successor (const struct coveb_mq *q, uint32_t num, struct vEBMPDatum *result_x, uint32_t *gotresult)

---

Detailed Description

---

Function Documentation

uint32_t coveb_bq_addresses_full

(

const struct coveb_bq *

q

)

Test if the queue contains all 32-bit unsigned integers or not.

Parameters:

q

bitwise priority queue to be tested

Returns:

1 if the queue is completely full and contains all possible 32-bit unsigned integers, or 0 otherwise.

This function is necessary to determine if the queue contains 2 ** 32 or (2 ** 32) - 1 entries. When the queue has either of these two sizes, coveb_bq_size() returns (2 ** 32) - 1 to avoid integer overflow. This function provides a way to get the exact size in this exceptional case.

See also:

coveb_bq_size()

struct coveb_bq* coveb_bq_clone

(

const struct coveb_bq *

q

)

[read]

Copies a bitwise priority queue.

Parameters:

q

bitwise priority queue to be copied

Returns:

pointer to a new and identical bitwise priority queue

uint32_t coveb_bq_contains	(	const struct coveb_bq *	q,
		uint32_t	x
	)

Determines whether or not the queue contains a specific element.

Parameters:

	q	pointer to input bitwise priority queue
	x	32-bit unsigned integer to search for in the queue

Returns:

unsigned integer flag indicating if the value was found (1) or not (0).

uint32_t coveb_bq_extractmin

(

struct coveb_bq *

q

)

Remove the smallest element from the queue.

Parameters:

q

pointer to input bitwise priority queue

Returns:

32-bit unsigned integer representing the element that was removed

It is illegal to call this function with an empty (coveb_bq_size() == 0) queue. The value that was removed from the queue is returned.

void coveb_bq_free

(

struct coveb_bq *

q

)

Deallocate (or free) a bitwise priority queue.

Parameters:

q

bitwise priority queue to be deallocated

Returns:

nothing

void coveb_bq_insert	(	struct coveb_bq *	q,
		uint32_t	x
	)

Insert an element into the queue.

Parameters:

	q	bitwise priority queue to be scanned
	x	32-bit unsigned integer to be inserted

Returns:

nothing

This function inserts the element x into the queue. If the element is already in the queue, this function has no effect.

See also:

coveb_bq_extractmin()

void coveb_bq_locate_smallest_not_less_than	(	const struct coveb_bq *	q,
		uint32_t	incl_lower_bound,
		uint32_t *	result_x,
		uint32_t *	gotresult
	)

Find the smallest element in the queue at least as big as a given lower boundary point.

Parameters:

	q	bitwise priority queue to be scanned
	incl_lower_bound	32-bit unsigned integer lower boundary point
	result_x	pointer to 32-bit unsigned integer output result buffer
	gotresult	pointer to 32-bit unsigned integer flag

Returns:

nothing

If an entry is found in the queue that is greater than or equal to incl_lower_bound, the smallest such entry is returned in *result_x and *gotresult will be set to 1. If no element is found above num, then *gotresult will be set to 0. This function can be used to iterate through the queue.

See also:

coveb_bq_successor()

uint32_t coveb_bq_max

(

const struct coveb_bq *

q

)

Find the maximum element in the queue.

Parameters:

q

pointer to input bitwise priority queue

Returns:

32-bit unsigned integer representing the maximum value in the queue.

It is illegal to try to take the maximum value from an empty queue.

uint32_t coveb_bq_min

(

const struct coveb_bq *

q

)

Find the minimum element in the queue.

Parameters:

q

pointer to input bitwise priority queue

Returns:

32-bit unsigned integer representing the minimum value in the queue.

It is illegal to try to take the minimum value from an empty queue.

struct coveb_bq* coveb_bq_new

(

void

)

[read]

Allocates a new bitwise priority queue. A bitwise priority queue holds a set of 32-bit unsigned integers.

Returns:

pointer to a new and empty bitwise priority queue.

uint32_t coveb_bq_remove	(	struct coveb_bq *	q,
		uint32_t	x
	)

Remove an element from the queue.

Parameters:

	q	pointer to input bitwise priority queue
	x	value to be removed

Returns:

unsigned integer flag indicating whether the operation succeeded in removing an element (0) or failed to remove an element (1).

It is illegal to try to remove an element from an empty queue. If the element to be removed is not in the queue, the call has no effect and the value 1 is returned.

uint32_t coveb_bq_size

(

const struct coveb_bq *

q

)

Returns the number of elements stored in a priority queue.

Parameters:

q

pointer to input bitwise priority queue

Returns:

32-bit unsigned integer representing the number of elements stored.

An empty queue returns a size of 0.

See also:

coveb_bq_addresses_full()

void coveb_bq_successor	(	const struct coveb_bq *	q,
		uint32_t	num,
		uint32_t *	result_x,
		uint32_t *	gotresult
	)

Find the element in the queue after a given lower boundary point.

Parameters:

	q	bitwise priority queue to be scanned
	num	32-bit unsigned integer lower boundary point
	result_x	pointer to 32-bit unsigned integer output result buffer
	gotresult	pointer to 32-bit unsigned integer flag

Returns:

nothing

If an entry is found in the queue that is greater than num, the smallest is returned in *result_x and *gotresult will be set to 1. If no element is found above num, then *gotresult will be set to 0. This function can be used to iterate through the queue.

See also:

coveb_bq_locate_smallest_not_less_than()

uint32_t coveb_mq_addresses_full

(

const struct coveb_mq *

q

)

Test if the queue contains all 32-bit unsigned integers or not.

Parameters:

q

mapping priority queue to be tested

Returns:

1 if the queue is completely full and contains all possible 32-bit unsigned integers, or 0 otherwise.

This function is necessary to determine if the queue contains 2 ** 32 or (2 ** 32) - 1 entries. When the queue has either of these two sizes, coveb_mq_size() returns (2 ** 32) - 1 to avoid integer overflow. This function provides a way to get the exact size in this exceptional case.

See also:

coveb_mq_size()

struct coveb_mq* coveb_mq_clone

(

const struct coveb_mq *

q

)

[read]

Copies a mapping priority queue.

Parameters:

q

mapping priority queue to be copied

Returns:

pointer to a new and identical mapping priority queue

uint32_t coveb_mq_contains	(	const struct coveb_mq *	q,
		uint32_t	x
	)

Determines whether or not the queue contains a specific element.

Parameters:

	q	pointer to input mapping priority queue
	x	32-bit unsigned integer to search for in the queue

Returns:

unsigned integer flag indicating if the value was found (1) or not (0).

struct vEBMPDatum coveb_mq_extractmin

(

struct coveb_mq *

q

)

[read]

Remove the smallest element from the queue.

Parameters:

q

pointer to input mapping priority queue

Returns:

32-bit unsigned integer and payload representing the element that was removed

It is illegal to call this function with an empty (coveb_mq_size() == 0) queue. The value that was removed from the queue is returned. The 32-bit unsigned integer key is accessed through field _x. The payload is accessed through the 8-element array of unsigned 32-bit integers called _p._pl[0] through _p._pl[7].

void coveb_mq_free

(

struct coveb_mq *

q

)

Deallocate (or free) a mapping priority queue.

Parameters:

q

mapping priority queue to be deallocated

Returns:

nothing

void coveb_mq_insert	(	struct coveb_mq *	q,
		struct vEBMPDatum	x
	)

Insert an element into the queue.

Parameters:

	q	mapping priority queue to be scanned
	x	32-bit unsigned integer _x to be inserted with payload _p.

Returns:

nothing

This function inserts the element x into the queue. If the element is already in the queue, this function has no effect.

See also:

coveb_mq_extractmin()

struct vEBMPDatum coveb_mq_max

(

const struct coveb_mq *

q

)

[read]

Find the maximum element in the queue.

Parameters:

q

pointer to input mapping priority queue

Returns:

32-bit unsigned integer and payload representing the maximum value in the queue.

It is illegal to try to take the maximum value from an empty queue. To access the integer part, use the _x field. Use the _p._pl[0..7] fields for the payload.

struct coveb_mq* coveb_mq_new

(

uint32_t

payload_bits

)

[read]

Allocates a new mapping priority queue. A mapping priority queue has extra space reserved for a user-defined payload of a specific number of bits. This number is called payload_bits and must be an even power of two between 1 and 256, inclusive. This is the amount of space that can be stored with each unsigned 32-bit integer entry in a mapping priority queue. This data structure makes it easy to extend the basic fast priority queue operations with your own special custom data structures and operations. Just use a 32-bit payload to store pointers to your own objects, or store them directly in 4, 8, 16, or 32 bytes.

Parameters:

payload_bits

number of bits of space to store per entry in this queue

Returns:

pointer to a new empty mapping priority queue

uint32_t coveb_mq_remove	(	struct coveb_mq *	q,
		uint32_t	x
	)

Remove an element from the queue.

Parameters:

	q	pointer to input mapping priority queue
	x	value to be removed

Returns:

unsigned integer flag indicating whether the operation succeeded in removing an element (0) or failed to remove an element (1).

It is illegal to try to remove an element from an empty queue. If the element to be removed is not in the queue, the call has no effect and the value 1 is returned.

uint32_t coveb_mq_size

(

const struct coveb_mq *

q

)

Returns the number of elements stored in a priority queue.

Parameters:

q

pointer to input mapping priority queue

Returns:

32-bit unsigned integer representing the number of elements stored.

An empty queue returns a size of 0.

See also:

coveb_mq_addresses_full()

void coveb_mq_successor	(	const struct coveb_mq *	q,
		uint32_t	num,
		struct vEBMPDatum *	result_x,
		uint32_t *	gotresult
	)

Find the element in the queue after a given lower boundary point.

Parameters:

	q	mapping priority queue to be scanned
	num	32-bit unsigned integer lower boundary point
	result_x	pointer to struct vEBMPDatum output result buffer
	gotresult	pointer to 32-bit unsigned integer flag

Returns:

nothing

If an entry is found in the queue that is greater than num, the smallest is returned in *result (_x field) and *gotresult will be set to 1. If no element is found above num, then *gotresult will be set to 0. This function can be used to iterate through the queue. The payloads are accessed through the _p._pl eight-element unsigned 32-bit integer array.

See also:

coveb_mq_locate_smallest_not_less_than()