Struct bloom2::CompressedBitmap

pub struct CompressedBitmap { /* fields omitted */ }

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

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.

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 shrink_to_fit(&mut self)

Reduces the allocated memory usage of the filter to the minimum required for the current filter 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 filter.

An efficient way to remove all elements in the filter 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 filter.

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.

Trait Implementations

impl Bitmap for CompressedBitmap

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

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

impl Clone for CompressedBitmap

pub fn clone(&self) -> CompressedBitmap

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for CompressedBitmap

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

Formats the value using the given formatter.

impl Eq for CompressedBitmap

impl PartialEq<CompressedBitmap> for CompressedBitmap

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl StructuralEq for CompressedBitmap

impl StructuralPartialEq for CompressedBitmap