coveb-tree.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
void	coveb_failout (const char *msg)
uint32_t	coveb_bq_max (const struct coveb_bq *q)
uint32_t	coveb_bq_min (const struct coveb_bq *q)
uint32_t	coveb_bq_remove (struct coveb_bq *q, uint32_t x)
uint32_t	coveb_bq_extractmin (struct coveb_bq *q)
uint32_t	coveb_bq_addresses_full (const struct coveb_bq *q)
uint32_t	coveb_bq_size (const struct coveb_bq *q)
uint32_t	coveb_bq_contains (const struct coveb_bq *q, uint32_t x)
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_successor (const struct coveb_bq *q, uint32_t num, uint32_t *result_x, uint32_t *gotresult)
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_insert (struct coveb_bq *q, uint32_t x)
struct vEBPSearchResult	coveb_search (struct vEBPNode *v, COVEB_KEYTYPE x)

---

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