coveb-map.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include "coveb-tree.h"
#include "bigmac.h"

Defines
#define	OUTERCALLOC(a, b)   calloc(a,b)
#define	OUTERFREE(a)   free(a)
#define	INNERCALLOC(a, b)   calloc(a,b)
#define	INNERFREE(a)   free(a)
Functions
struct vEBMPDatum	coveb_mq_min (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	__coveb_fetch_from_bottom_table (struct vEBMPNode *v, uint32_t ind)
void	__coveb_store_to_bottom_table (struct vEBMPNode *v, struct vEBMPDatum d, uint32_t ind)
struct vEBMPDatum	coveb_mq_max (const struct coveb_mq *q)
uint32_t	coveb_mq_remove (struct coveb_mq *q, uint32_t x)
struct vEBMPDatum	coveb_mq_extractmin (struct coveb_mq *q)
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)
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_successor (const struct coveb_mq *q, uint32_t num, struct vEBMPDatum *result_x, uint32_t *gotresult)
void	coveb_mq_insert (struct coveb_mq *q, struct vEBMPDatum x)

---

Detailed Description

---

Function Documentation

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()

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
	)

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

Parameters:

	q	mapping 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._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. The payload is accessible via ._p._pl[].

See also:

coveb_mq_successor()

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 vEBMPDatum coveb_mq_min

(

const struct coveb_mq *

q

)

[read]

Find the minimum element in the queue.

Parameters:

q

pointer to input mapping priority queue

Returns:

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

It is illegal to try to take the minimum 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()