Enum U64Segment 

pub enum U64Segment {
    Range(Range<u64>),
    RangeWithHoles {
        range: Range<u64>,
        holes: EncodedU64Array,
    },
    RangeWithBitmap {
        range: Range<u64>,
        bitmap: Bitmap,
    },
    SortedArray(EncodedU64Array),
    Array(EncodedU64Array),
}

Different ways to represent a sequence of distinct u64s.

This is designed to be especially efficient for sequences that are sorted, but not meaningfully larger than a Vec in the worst case.

The representation is chosen based on the properties of the sequence:

Sorted?───►Yes ───►Contiguous?─► Yes─► Range
│ ▼
│ No
│ ▼
│ Dense?─────► Yes─► RangeWithBitmap/RangeWithHoles │ ▼
│ No─────────────► SortedArray
▼
No──────────────────────────────► Array

“Dense” is decided based on the estimated byte size of the representation.

Size of RangeWithBitMap for N values: 8 bytes + 8 bytes + ceil((max - min) / 8) bytes Size of SortedArray for N values (assuming u16 packed): 8 bytes + 8 bytes + 8 bytes + 2 bytes * N

Variants

Range(Range<u64>)

A contiguous sorted range of row ids.

Total size: 16 bytes

RangeWithHoles

A sorted range of row ids, that is mostly contiguous.

Total size: 24 bytes + n_holes * 4 bytes Use when: 32 * n_holes < max - min

Fields

range: Range<u64>

holes: EncodedU64Array

Bitmap of offsets from the start of the range that are holes. This is sorted, so binary search can be used. It’s typically relatively small.

RangeWithBitmap

A sorted range of row ids, that is mostly contiguous.

Bitmap is 1 when the value is present, 0 when it’s missing.

Total size: 24 bytes + ceil((max - min) / 8) bytes Use when: max - min > 16 * len

Fields

range: Range<u64>

bitmap: Bitmap

SortedArray(EncodedU64Array)

A sorted array of row ids, that is sparse.

Total size: 24 bytes + 2 * n_values bytes

Array(EncodedU64Array)

An array of row ids, that is not sorted.

Implementations

impl U64Segment

pub fn from_slice(slice: &[u64]) -> Self

impl U64Segment

pub fn iter(&self) -> Box<dyn DoubleEndedIterator<Item = u64> + '_>

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn range(&self) -> Option<RangeInclusive<u64>>

Get the min and max value of the segment, excluding tombstones.

pub fn slice(&self, offset: usize, len: usize) -> Self

pub fn position(&self, val: u64) -> Option<usize>

pub fn get(&self, i: usize) -> Option<u64>

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

Check if a value is contained in the segment

pub fn with_new_high(self, val: u64) -> Result<Self>

Produce a new segment that has [val] as the new highest value in the segment

pub fn delete(&self, vals: &[u64]) -> Self

Delete a set of row ids from the segment. The row ids are assumed to be in the segment. (within the range, not already deleted.) They are also assumed to be ordered by appearance in the segment.

pub fn mask(&mut self, positions: &[u32])

Trait Implementations

impl Clone for U64Segment

fn clone(&self) -> U64Segment

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for U64Segment

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

Formats the value using the given formatter.

impl DeepSizeOf for U64Segment

fn deep_size_of_children(&self, context: &mut Context) -> usize

Returns an estimation of the heap-managed storage of this object. This does not include the size of the object itself.

fn deep_size_of(&self) -> usize

Returns an estimation of a total size of memory owned by the object, including heap-managed storage.

impl From<U64Segment> for U64Segment

fn from(segment: U64Segment) -> Self

Converts to this type from the input type.

impl FromIterator<u64> for U64Segment

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

Creates a value from an iterator.

impl PartialEq for U64Segment

fn eq(&self, other: &U64Segment) -> 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 TryFrom<U64Segment> for U64Segment

type Error = Error

The type returned in the event of a conversion error.

fn try_from(pb: U64Segment) -> Result<Self>

Performs the conversion.

impl Eq for U64Segment

impl StructuralPartialEq for U64Segment