Sux Documentation

Welcome to the C++ part of the Sux project.

Available classes

The classes we provide fall into three categories:

All classes are heavily asserted. For testing speed, remember to use -DNDEBUG.

All provided classes are templates, so you just have to copy the files in the sux directory somewhere in your include path.


Memory allocation

Almost all data structures make it possible to allocate memory in different ways, and in particular to use transparent large pages (usually, 2MiB) on Linux. All allocations are based on the class sux::util::Vector, which is a zero-cost wrapper around an array (no bound checks), and has a template parameter for choosing the allocation strategy depending on an item of sux::util::AllocType.

For example,

    #include <sux/util/FenwickFixedF.hpp>

    sux::util::FenwickFixedF<10000, MALLOC> f(v, n)

creates a Fenwick tree as above, using a standard malloc() call, which is usually the default, and the most compatible approach, but

    #include <sux/util/FenwickFixedF.hpp>

    sux::util::FenwickFixedF<10000, TRANSHUGEPAGE> f(v, n)

will try to use transparent huge pages instead, if available.


    #include <sux/function/RecSplit.hpp>

    sux::function::RecSplit<8, TRANSHUGEPAGE> rs(keys, 100)

creates a RecSplit instance using transparent huge pages.

If you want to test a static rank/select structure using a certain allocation strategy, it is usually a good idea to allocate both the underlying bit vector and the rank/select structure using the same method. You can use sux::util::Vector to this purpose:

    #include <sux/util/Vector.hpp>
    #include <sux/bits/Rank9.hpp>

    sux::util::Vector<uint64_t, SMALLPAGE> v(1000);
    // Modify v
    sux::bits::Rank9<SMALLPAGE> r(&v, num_bits);

where num_bits is less than 64000. The & operator applied to an instance of sux::util::Vector returns a pointer to its backing array.