Crate insertion_set

Performs a set of batched insertions on a vector.

Vec::insert(index, value) takes O(n) time to move internal memory, so calling it in a loop can cause quadratic blowup.

If you batch multiple values together with an InsertionSet you can defer the expensive movement of the vector’s memory till the of the loop.

This code was originally copied from the first prototype compiler for DuckLogic. It was inspired by the way the B3 JIT handles insertions.

Structs

Insertion

A value that is pending insertion

InsertionSet

A set of pending insertions on a Vec

Enums

OriginalLocation

The original location of an element (before a set of insertions are applied)

Functions

apply_bulk_insertions

Applies all the specified insertions into the target vector.

compute_updated_locations

Compute the updated locations of all elements (original + inserted).