Struct idlset::IDLBitRange

pub struct IDLBitRange { /* fields omitted */ }

An ID List of u64 values, that uses a compressed representation of u64 to speed up set operations, improve cpu cache behaviour and consume less memory.

This is essentially a Vec<u64>, but requires less storage with large values and natively supports logical operations for set manipulation. Today this supports And, Or, AndNot. Future types may be added such as xor.

How does it work?

The IDLBitRange stores a series of tuples (IDRange) that represents a range prefix u64 and a u64 mask of bits representing the presence of that integer in the set. For example, the number 1 when inserted would create an idl range of: IDRange { range: 0, mask: 2 }. The mask has the "second" bit set, so we add range and recieve 1. (if mask was 1, this means the value 0 is present!)

Other examples would be IDRange { range: 0, mask: 3 }. Because 3 means "the first and second bit is set" this would extract to [0, 1] IDRange { range: 0, mask: 38} represents the set [1, 2, 5] as the. second, third and sixth bits are set. Finally, a value of IDRange { range: 64, mask: 4096 } represents the set [76, ].

Using this, we can store up to 64 integers in an IDRange. Once there are at least 3 bits set in mask, the compression is now saving memory space compared to raw unpacked Vec<u64>.

The set operations can now be performed by applying u64 bitwise operations on the mask components for a given matching range prefix. If the range prefix is not present in the partner set, we choose a correct course of action (Or copies the range to the result, And skips the range entirely)

As an example, if we had the values IDRange { range: 0, mask: 38 } ([1, 2, 5]) and IDRange { range: 0, mask: 7 } ([0, 1, 2]), and we were to perform an & operation on these sets, the result would be 7 & 38 == 6. The result now is IDRange { range: 0, mask: 6 }, which decompresses to [1, 2] - the correct result of our set And operation.

The important note here is that with a single cpu & operation, we were able to intersect up to 64 values at once. Contrast to a Vec<u64> where we would need to perform cpu equality on each value. For our above example this would have taken at most 4 cpu operations with the Vec<u64>, where as the IDLBitRange performed 2 (range eq and mask &).

Worst case behaviour is sparse u64 sets where each IDRange only has a single populated value. This yields a slow down of approx 20% compared to the Vec<u64>. However, as soon as the IDRange contains at least 2 values they are equal in performance, and three values begins to exceed. This applies to all operation types and data sizes.

Examples

use idlset::IDLBitRange;
use std::iter::FromIterator;

let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);

// Conduct an and (intersection) of the two lists to find commont members.
let idl_result = idl_a & idl_b;

let idl_expect = IDLBitRange::from_iter(vec![2]);
assert_eq!(idl_result, idl_expect);

Implementations

impl IDLBitRange

pub fn new() -> Self

Construct a new, empty set.

pub fn from_u64(id: u64) -> Self

Construct a set containing a single initial value. This is a special use case for database indexing where single value equality indexes are store uncompressed on disk.

pub fn contains(&self, id: u64) -> bool

Returns true if the id u64 value exists within the set.

pub fn insert_id(&mut self, value: u64)

Insert an id into the set, correctly sorted.

pub fn remove_id(&mut self, value: u64)

Remove an id from the set, leaving it correctly sorted.

If the value is not present, no action is taken.

pub unsafe fn push_id(&mut self, value: u64)

Push an id into the set. The value is inserted onto the tail of the set which may cause you to break the structure if your input isn't sorted. You probably want insert_id instead.

pub fn len(&self) -> usize

Returns the number of ids in the set. This operation iterates over the set, decompressing it to count the ids, which MAY be slow. If you want to see if the set is empty, us is_empty()

pub fn below_threshold(&self, threshold: usize) -> bool

Returns if the number of ids in this set exceed this threshold. While this must iterate to determine if this is true, since we shortcut return in the check, on long sets we will not iterate over the complete content making it faster than len() < thresh.

Returns true if the set is smaller than threshold.

pub fn is_empty(&self) -> bool

Show if this IDL set contains no elements

pub fn len_range(&self) -> usize

Show how many ranges we hold in this idlset.

Trait Implementations

impl AndNot<IDLBitRange> for IDLBitRange

type Output = Self

The type of set implementation to return.

pub fn andnot(self, rhs: Self) -> Self

Perform an AndNot (exclude) operation between two sets. This returns a new set containing the results. The set on the right is the candidate set to exclude from the set of the left.

Examples

// Note the change to import the AndNot trait.
use idlset::{IDLBitRange, AndNot};

let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);

let idl_result = idl_a.andnot(idl_b);

let idl_expect = IDLBitRange::from_iter(vec![1, 3]);
assert_eq!(idl_result, idl_expect);

// Note the change to import the AndNot trait.
use idlset::{IDLBitRange, AndNot};

let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);

// Note how reversing a and b here will return an empty set.
let idl_result = idl_b.andnot(idl_a);

let idl_expect = IDLBitRange::new();
assert_eq!(idl_result, idl_expect);

impl BitAnd<IDLBitRange> for IDLBitRange

type Output = Self

The resulting type after applying the & operator.

pub fn bitand(self, rhs: Self) -> Self

Perform an And (intersection) operation between two sets. This returns a new set containing the results.

Examples

let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);

let idl_result = idl_a & idl_b;

let idl_expect = IDLBitRange::from_iter(vec![2]);
assert_eq!(idl_result, idl_expect);

impl BitOr<IDLBitRange> for IDLBitRange

type Output = Self

The resulting type after applying the | operator.

pub fn bitor(self, rhs: Self) -> Self

Perform an Or (union) operation between two sets. This returns a new set containing the results.

Examples

let idl_a = IDLBitRange::from_iter(vec![1, 2, 3]);
let idl_b = IDLBitRange::from_iter(vec![2]);

let idl_result = idl_a | idl_b;

let idl_expect = IDLBitRange::from_iter(vec![1, 2, 3]);
assert_eq!(idl_result, idl_expect);

impl Clone for IDLBitRange

pub fn clone(&self) -> IDLBitRange

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for IDLBitRange

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for IDLBitRange

pub fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Display for IDLBitRange

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

Formats the value using the given formatter.

impl FromIterator<u64> for IDLBitRange

pub fn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self

Build an IDLBitRange from at iterator. If you provide a sorted input, a fast append mode is used. Unsorted inputs use a slower insertion sort method instead.

impl<'a> IntoIterator for &'a IDLBitRange

type Item = u64

The type of the elements being iterated over.

type IntoIter = IDLBitRangeIter<'a>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> IDLBitRangeIter<'a>

Creates an iterator from a value.

impl PartialEq<IDLBitRange> for IDLBitRange

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

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

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

This method tests for !=.

impl Serialize for IDLBitRange

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

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for IDLBitRange