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


Generated on Fri May 9 20:27:40 2008 for libcoveb by  doxygen 1.5.5