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).