libcoveb Documentation

1.0.4

libcoveb by Rudi Cilibrasi (cilibrar@cilibrar.com)

The open source cache oblivious van Emde Boas priority queue and tree library.

libcoveb is an optimized ordered container for 32-bit unsigned keys that supports fast insertion and removal from one end as well as fast range location.

This library has two queue types coveb_bq and coveb_mq. One is called the bitwise queue (coveb_bq) , and the other is called the mapping queue (coveb_mq). The bitwise queue is the smallest and fastest, but stores only 32-bit unsigned integers with no extra data. The mapping priority queue is able to store payloads of specific sizes attached to each entry that hold whatever is appropriate according to user defined needs.

See also:

coveb_bq_new() and coveb_mq_new() for more details.

libcoveb has been optimized for high performance in any caching situation. It uses customized allocators for maximum speed. It supports O(log (log N)) type performance for range location, insertion, and extraction of the minimum value. It can outperform balanced binary trees and hash tables in many situations, depending on the number of elements involved and the distribution of the data. The data structure used in libcoveb is like a stratified tree. If you have more than ten thousand items or so, this data structure may speed up performance compared to other comparison based structures like trees.