Struct CompressedBitmap 

pub struct CompressedBitmap { /* private fields */ }

A sparse, 2-level bitmap with a low memory footprint, optimised for reads.

A CompressedBitmap splits the bitmap up into blocks of usize bits, and uses a second bitmap to mark populated blocks, lazily allocating them as required. This strategy represents a sparsely populated bitmap such as:

   ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
   │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │
   └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

As two bitmaps, here initialising only a single blocks of usize bits in the second bitmap:

                 ┌───┬───┬───┬───┐
      Block map: │ 0 │ 1 │ 0 │ 0 │
                 └───┴─┬─┴───┴───┘
                       └──────┐
    ┌ ─ ┬ ─ ┬ ─ ┬ ─ ┐ ┌───┬───▼───┬───┐ ┌ ─ ┬ ─ ┬ ─ ┬ ─ ┐
      0   0   0   0   │ 1 │ 0 │ 0 │ 1 │   0   0   0   0
    └ ─ ┴ ─ ┴ ─ ┴ ─ ┘ └───┴───┴───┴───┘ └ ─ ┴ ─ ┴ ─ ┴ ─ ┘

This amortised O(1) insert operation takes ~4ns, while reading a value takes a constant time ~1ns on a Core i7 @ 2.60GHz.

In practice inserting large numbers of values into a CompressedBitmap can be slow - for higher write performance, use a VecBitmap and later convert to a CompressedBitmap when possible.

Features

If the serde feature is enabled, a CompressedBitmap supports (de)serialisation with serde.

Implementations

impl CompressedBitmap

pub fn new(max_key: usize) -> Self

Construct a CompressedBitmap for space to hold up to max_key number of bits.

pub fn size(&self) -> usize

pub fn shrink_to_fit(&mut self)

Reduces the allocated memory usage of the bitmap to the minimum required for the current bitmap contents.

This is useful to minimise the memory footprint of a populated, read-only CompressedBitmap.

See Vec::shrink_to_fit.

pub fn clear(&mut self)

Resets the state of the bitmap.

An efficient way to remove all elements in the bitmap to allow it to be reused. Does not shrink the allocated backing memory, instead retaining the capacity to avoid reallocations.

pub fn set(&mut self, key: usize, value: bool)

Inserts key into the bitmap.

Panics

This method MAY panic if key is more than the max_key value provided when initialising the bitmap.

If debug_assertions are enabled (such as in debug builds) inserting key > max will always panic. In release builds, this may not panic for values of key that are only slightly larger than max_key for performance reasons.

pub fn get(&self, key: usize) -> bool

Returns the value at key.

If a value for key was not previously set, false is returned.

Panics

This method MAY panic if key is more than the max_key value provided when initialising the bitmap.

pub fn or(&self, other: &Self) -> Self

Perform a bitwise OR against self and other, returning the resulting merged CompressedBitmap.

Panics

This method panics if other was not configured with the same max_key.

Trait Implementations

impl Bitmap for CompressedBitmap

fn get(&self, key: usize) -> bool

Return true if the given bit index was previously set to true.

fn set(&mut self, key: usize, value: bool)

Set bit indexed by key to value.

fn byte_size(&self) -> usize

Return the size of the bitmap in bytes.

fn or(&self, other: &Self) -> Self

Return the bitwise OR of both self and other.`

fn new_with_capacity(max_key: usize) -> Self

Construct a new Bitmap impl with capacity to hold at least max_key number of bits.

impl Clone for CompressedBitmap

fn clone(&self) -> CompressedBitmap

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for CompressedBitmap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for CompressedBitmap

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl From<VecBitmap> for CompressedBitmap

fn from(bitmap: VecBitmap) -> Self

Converts to this type from the input type.

impl PartialEq for CompressedBitmap

fn eq(&self, other: &CompressedBitmap) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for CompressedBitmap

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for CompressedBitmap

impl StructuralPartialEq for CompressedBitmap