#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) |
uint32_t coveb_bq_addresses_full | ( | const struct coveb_bq * | q | ) |
Test if the queue contains all 32-bit unsigned integers or not.
q | bitwise priority queue to be tested |
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.
Copies a bitwise priority queue.
q | bitwise priority queue to be copied |
uint32_t coveb_bq_contains | ( | const struct coveb_bq * | q, | |
uint32_t | x | |||
) |
Determines whether or not the queue contains a specific element.
q | pointer to input bitwise priority queue | |
x | 32-bit unsigned integer to search for in the queue |
uint32_t coveb_bq_extractmin | ( | struct coveb_bq * | q | ) |
Remove the smallest element from the queue.
q | pointer to input bitwise priority queue |
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.
q | bitwise priority queue to be deallocated |
void coveb_bq_insert | ( | struct coveb_bq * | q, | |
uint32_t | x | |||
) |
Insert an element into the queue.
q | bitwise priority queue to be scanned | |
x | 32-bit unsigned integer to be inserted |
This function inserts the element x into the queue. If the element is already in the queue, this function has no effect.
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.
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 |
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.
uint32_t coveb_bq_max | ( | const struct coveb_bq * | q | ) |
Find the maximum element in the queue.
q | pointer to input bitwise priority 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.
q | pointer to input bitwise priority 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.
uint32_t coveb_bq_remove | ( | struct coveb_bq * | q, | |
uint32_t | x | |||
) |
Remove an element from the queue.
q | pointer to input bitwise priority queue | |
x | value to be removed |
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.
q | pointer to input bitwise priority queue |
An empty queue returns a size of 0.
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.
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 |
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.