[−][src]Struct bloom2::CompressedBitmap
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 operatoin 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
[src]
pub fn new(max_key: usize) -> Self
[src]
Construct a CompressedBitmap
for space to hold up to max_key
number
of bits.
pub fn shrink_to_fit(&mut self)
[src]
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)
[src]
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)
[src]
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
[src]
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
[src]
impl Clone for CompressedBitmap
[src]
fn clone(&self) -> CompressedBitmap
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl Debug for CompressedBitmap
[src]
impl Eq for CompressedBitmap
[src]
impl PartialEq<CompressedBitmap> for CompressedBitmap
[src]
fn eq(&self, other: &CompressedBitmap) -> bool
[src]
fn ne(&self, other: &CompressedBitmap) -> bool
[src]
impl StructuralEq for CompressedBitmap
[src]
impl StructuralPartialEq for CompressedBitmap
[src]
Auto Trait Implementations
impl RefUnwindSafe for CompressedBitmap
impl Send for CompressedBitmap
impl Sync for CompressedBitmap
impl Unpin for CompressedBitmap
impl UnwindSafe for CompressedBitmap
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,