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

Generated on Fri Apr 4 23:53:35 2008 for libcoveb by  doxygen 1.5.5