sux::bits::SimpleSelectZero< AT > Class Template Reference

#include <SimpleSelectZero.hpp>

Public Member Functions
	SimpleSelectZero ()
	SimpleSelectZero (const uint64_t *const bits, const uint64_t num_bits, const int max_log2_longwords_per_subinventory)
uint64_t	selectZero (const uint64_t rank)
size_t	bitCount () const

Detailed Description

template<util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::SimpleSelectZero< AT >

A simple SelectZero implementation based on a two-level inventory, a spill list and broadword bit search.

This implementation uses around 13.75% additional space on evenly distributed bit arrays, and, under the same conditions, provide very fast selects. For very unevenly distributed arrays the space occupancy will grow significantly, and access time might vary wildly.

The constructors of this class only store a reference to a provided bit vector. Should the content of the bit vector change, the results will be unpredictable.

Template Parameters

AT	a type of memory allocation out of sux::util::AllocType.

Constructor & Destructor Documentation

SimpleSelectZero() [1/2]

template<util::AllocType AT = util::AllocType::MALLOC>

sux::bits::SimpleSelectZero< AT >::SimpleSelectZero ( )

inline

SimpleSelectZero() [2/2]

template<util::AllocType AT = util::AllocType::MALLOC>

sux::bits::SimpleSelectZero< AT >::SimpleSelectZero ( const uint64_t *const  bits, const uint64_t  num_bits, const int  max_log2_longwords_per_subinventory  )

inline

Creates a new instance using a given bit vector.

Parameters

bits	a bit vector of 64-bit words.
num_bits	the length (in bits) of the bit vector.
max_log2_longwords_per_subinventory	the number of words per subinventory: a larger value yields a faster map that uses more space; typical values are between 0 and 3.

Member Function Documentation

bitCount()

template<util::AllocType AT = util::AllocType::MALLOC>

size_t sux::bits::SimpleSelectZero< AT >::bitCount ( ) const

inline

Returns an estimate of the size (in bits) of this structure.

selectZero()

template<util::AllocType AT = util::AllocType::MALLOC>

uint64_t sux::bits::SimpleSelectZero< AT >::selectZero ( const uint64_t  rank )

inline

---

The documentation for this class was generated from the following file:

• sux/bits/SimpleSelectZero.hpp