Trait dag::iddagstore::IdDagStore

source · 
pub trait IdDagStore: Send + Sync + 'static {

Show 18 methods    fn max_level(&self) -> Result<Level>;
    fn find_segment_by_head_and_level(
        &self,
        head: Id,
        level: u8
    ) -> Result<Option<Segment>>;
    fn find_flat_segment_including_id(&self, id: Id) -> Result<Option<Segment>>;
    fn insert_segment(&mut self, segment: Segment) -> Result<()>;
    fn remove_flat_segment_unchecked(&mut self, segment: &Segment) -> Result<()>;
    fn all_ids_in_groups(&self, groups: &[Group]) -> Result<IdSet>;
    fn next_segments(&self, id: Id, level: Level) -> Result<Vec<Segment>>;
    fn iter_segments_descending<'a>(
        &'a self,
        max_high_id: Id,
        level: Level
    ) -> Result<Box<dyn Iterator<Item = Result<Segment>> + 'a>>;
    fn iter_segments_ascending<'a>(
        &'a self,
        min_high_id: Id,
        level: Level
    ) -> Result<Box<dyn Iterator<Item = Result<Segment>> + Send + Sync + 'a>>;
    fn iter_flat_segments_with_parent_span<'a>(
        &'a self,
        parent_span: Span
    ) -> Result<Box<dyn Iterator<Item = Result<(Id, Segment)>> + 'a>>;
    fn iter_flat_segments_with_parent<'a>(
        &'a self,
        parent: Id
    ) -> Result<Box<dyn Iterator<Item = Result<Segment>> + 'a>>;
    fn remove_non_master(&mut self) -> Result<()>;

    fn insert(
        &mut self,
        flags: SegmentFlags,
        level: Level,
        low: Id,
        high: Id,
        parents: &[Id]
    ) -> Result<()> { ... }
    fn remove_flat_segment(&mut self, segment: &Segment) -> Result<()> { ... }
    fn resize_flat_segment(
        &mut self,
        segment: &Segment,
        new_high: Option<Id>
    ) -> Result<()> { ... }
    fn all_ids_in_segment_level(&self, level: Level) -> Result<IdSet> { ... }
    fn segments_in_span_ascending(
        &self,
        span: Span,
        level: Level
    ) -> Result<Vec<Segment>> { ... }
    fn maybe_merged_flat_segment(
        &self,
        segment: &Segment
    ) -> Result<Option<Segment>> { ... }

}

Required Methods§

Maximum level segment in the store

Find segment by level and head.

Find flat segment containing the given id.

Actual implementation of the segment removal part of resize_flat_segment without checks. This should only be called via resize_flat_segment for integrity.

Return all ids from given groups. This is useful to implement the all() operation.

With discontinuous segments, this might return multiple spans for a single group.

Find segments that covers id.. range at the given level, within a same group.

Iterate through segments at the given level in descending order.

Iterate through segments at the given level in ascending order.

Iterate through (parent_id, segment) for master flat segments that have a parent in the given span.

The order of returned segments is implementation-specific. Different stores might return different order.

Iterate through flat segments that have the given parent.

The order of returned segments is implementation-specific. Different stores might return different order.

Remove all non master Group identifiers from the DAG.

Provided Methods§

Add a new segment.

For simplicity, it does not check if the new segment overlaps with an existing segment (which is a logic error). Those checks can be offline.

Remove a flat segment. The segment cannot have descendants.

Remove or truncate a flat segment.

  • If new_high is None, remove the flat segment. The segment cannot have descendants.
  • If new_high is set, trucnate the flat segment by resetting high to the given value. If new_high is smaller than high, then descendants(new_high+1:high) must be empty.

Find all ids covered by a specific level of segments.

This function assumes that segments are built in order, and higher level segments do not cover more than lower levels.

That is, if range Id(x)..Id(y) is covered by segment level n. Then segment level n+1 would cover Id(x)..Id(p) and not cover Id(p)..Id(y) (x <= p <= y). In other words, the following cases are forbidden:

    level n     [-------covered-------]
    level n+1   [covered] gap [covered]

    level n     [---covered---]
    level n+1   gap [covered]

    level n     [covered] gap
    level n+1   [---covered---]

The following cases are okay:

    level n     [---covered---]
    level n+1   [covered] gap

    level n     [---covered---]
    level n+1   [---covered---]

Find segments that fully covers the given range. Return segments in ascending order.

Attempt to merge the flat segment with the last flat segment to reduce fragmentation.

[---last segment---] [---segment---]
                   ^---- the only parent of segment
[---merged segment-----------------]

Return the merged segment if it’s mergeable.

Implementors§