Man Linux: Main Page and Category List


       coveb - cache oblivious high speed 32-bit priority queue for large data


       coveb : library for space and time efficient manipulation  of  unsigned
       32-bit integers.


       please see coveb-tree.h or the included README for details.

       #include <coveb.h>

       struct coveb_bq *q;

       q = coveb_bq_new();

       This  allocates  a new cache-oblivious bitwise priority queue. To free,



       Insertion of 32-bit unsigned integer values:

       void coveb_bq_insert(struct coveb_bq *q, uint32_t x);

       places  a  new  value  into  the queue, or does nothing if it’s already

       Removal of values:

       uint32_t coveb_bq_extractmin(struct coveb_bq *q);

       removes  the smallest value (min) from the queue and returns it.  It is
       illegal to try to remove a value from an empty (size = 0) queue.   This
       is the fastest way to remove elements.

       uint32_t coveb_bq_remove(struct coveb_bq *q, uint32_t x);

       This  generic  function  removes any specific value from the queue.  It
       returns 0 if the object was already in the queue, and 1 if not.

       Queue status monitoring:

       When   the   queue   is   completely  full  (containing  four  ’binary’
       gigasamples), it consumes about one gigabyte  of  memory.   This  means
       that  it  uses  about  2 bits per sample on average when full.  This is
       only about twice as big as the literal storage cost of a typical  queue
       state.   Because  this  size is not reportable as a 32-bit integer, the
       following function is available to detect the full queue condition:

       uint32_t coveb_bq_addresses_full(const struct coveb_bq *q);

       Returns  1  if  all  2 ** 32 elements are in the queue, or 0 otherwise.
       When the queue is  not  full,  the  normal  size  function  is  exactly

       uint32_t coveb_bq_size(const struct coveb_bq *q);

       returns  the count of integers currently stored in the queue.  This can
       be used to see if an element can be extracted safely (size > 0).   Note
       that  in  the  special  case  where  the  queue  is completely full and
       therefore the number of elements in the queue is one greater  than  the
       maximum  value  of  an  unsigned 32-bit integer, the size function will
       return instead one less than the actual number of elements.  To  detect
       this uncommon condition use coveb_bq_addresses_full.

       Extrema functions

       uint32_t coveb_bq_max(const struct coveb_bq *q);

        returns the largest integer stored in the queue without removal.

       uint32_t coveb_bq_min(const struct coveb_bq *q);

        returns the smallest integer stored in the queue without removal.

       Rangefinding functions

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

       searches  for  an  integer  stored  in  the queue that is not less than
       incl_lower_bound.  If there is more than one such integer, the smallest
       is  returned.   If an integer is found, *gotresult will be set to 1 and
       *result_x will hold the integer that was found.  If no such integer  is
       found in the queue, then *gotresult with be set to 0 and *result_x will
       be untouched.  The queue is not modified in any case.

       void    coveb_bq_successor(const    struct    coveb_bq   *q,   uint32_t
       excl_lower_bound, uint32_t *result_x, uint32_t *gotresult);

       This  function  scans  upward  for  an  integer  that  is  greater than
       excl_lower_bound.     It    is    otherwise    the    same    as    the
       coveb_bq_locate_smallest_not_less_than function.

       This library uses a data structure inspired by Peter van Emde Boas.



       The failout(msg) macro may be redefined using #define FAILOUT_FUNC(msg)