@@ -36,6 +36,9 @@ const MAGIC_NUMBER: u32 = 1581511376;
3636/// unlike the v1 magic, so the two are told apart by byte order as well as value.
3737const MAGIC_NUMBER_64 : u32 = 1681511377 ;
3838const MAGIC_NUMBER_SIZE_BYTES : u64 = 4 ;
39+ /// Adjacent deleted positions walked one by one before switching to
40+ /// `next_range` in [`DeletionVector::deleted_ranges`].
41+ const RUN_PROBE_LEN : u32 = 4 ;
3942/// Size of the `bitmapLength` prefix and of the trailing CRC. Mirrors Java
4043/// `Bitmap64DeletionVector.LENGTH_SIZE_BYTES` / `CRC_SIZE_BYTES`; a v2 entry
4144/// counts both in `DeletionFile.length()` while a v1 entry counts neither.
@@ -93,6 +96,50 @@ impl DeletionVector {
9396 self . bitmap . is_empty ( )
9497 }
9598
99+ /// Deleted positions as ascending inclusive `(start, end)` runs.
100+ ///
101+ /// Short runs are walked with `next`; once a run is longer than
102+ /// [`RUN_PROBE_LEN`], the rest of it is taken with `next_range`, one roaring
103+ /// container at a time. `next_range` alone is slower than `next` on
104+ /// scattered deletes.
105+ pub ( crate ) fn deleted_ranges ( & self ) -> impl Iterator < Item = ( u32 , u32 ) > + ' _ {
106+ let mut iter = self . bitmap . iter ( ) ;
107+ let mut pending: Option < ( u32 , u32 ) > = None ;
108+ std:: iter:: from_fn ( move || {
109+ let ( start, mut end) = match pending. take ( ) {
110+ Some ( run) => run,
111+ None => {
112+ let pos = iter. next ( ) ?;
113+ ( pos, pos)
114+ }
115+ } ;
116+ let mut walked = end - start;
117+ while walked < RUN_PROBE_LEN {
118+ match iter. next ( ) {
119+ Some ( pos) if end. checked_add ( 1 ) == Some ( pos) => {
120+ end = pos;
121+ walked += 1 ;
122+ }
123+ Some ( pos) => {
124+ pending = Some ( ( pos, pos) ) ;
125+ return Some ( ( start, end) ) ;
126+ }
127+ None => return Some ( ( start, end) ) ,
128+ }
129+ }
130+ // A run split at a container boundary comes back in pieces; join them.
131+ while let Some ( run) = iter. next_range ( ) {
132+ if end. checked_add ( 1 ) == Some ( * run. start ( ) ) {
133+ end = * run. end ( ) ;
134+ } else {
135+ pending = Some ( ( * run. start ( ) , * run. end ( ) ) ) ;
136+ break ;
137+ }
138+ }
139+ Some ( ( start, end) )
140+ } )
141+ }
142+
96143 /// Serialize using Java `BitmapDeletionVector` format:
97144 /// `i32 bitmapLength | i32 magic | roaring bitmap bytes | i32 crc`.
98145 pub ( crate ) fn serialize_to_bytes ( & self ) -> crate :: Result < Vec < u8 > > {
@@ -588,4 +635,61 @@ mod tests {
588635 // Positions above u32::MAX cannot exist in a roaring32 bitmap -> not deleted.
589636 assert ! ( !dv. is_deleted( u64 :: from( u32 :: MAX ) + 1 ) ) ;
590637 }
638+
639+ /// Runs of `bitmap.iter()`, the obvious way.
640+ fn model_ranges ( bitmap : & RoaringBitmap ) -> Vec < ( u32 , u32 ) > {
641+ let mut ranges: Vec < ( u32 , u32 ) > = Vec :: new ( ) ;
642+ for pos in bitmap {
643+ match ranges. last_mut ( ) {
644+ Some ( ( _, end) ) if end. checked_add ( 1 ) == Some ( pos) => * end = pos,
645+ _ => ranges. push ( ( pos, pos) ) ,
646+ }
647+ }
648+ ranges
649+ }
650+
651+ fn assert_ranges ( bitmap : RoaringBitmap ) {
652+ let expected = model_ranges ( & bitmap) ;
653+ let dv = DeletionVector :: from_bitmap ( bitmap) ;
654+ assert_eq ! ( dv. deleted_ranges( ) . collect:: <Vec <_>>( ) , expected) ;
655+ }
656+
657+ #[ test]
658+ fn test_deleted_ranges_edges ( ) {
659+ assert_ranges ( RoaringBitmap :: new ( ) ) ;
660+ assert_ranges ( RoaringBitmap :: from ( [ 7 ] ) ) ;
661+ // Runs right at the probe length, and one past it.
662+ assert_ranges ( ( 10 ..14 ) . chain ( 20 ..25 ) . chain ( 30 ..31 ) . collect ( ) ) ;
663+ // One run across several roaring containers, then a short one.
664+ assert_ranges ( ( 65_530 ..200_000 ) . chain ( [ 200_002 ] ) . collect ( ) ) ;
665+ // A long run followed by an adjacent-container run that does not touch it.
666+ assert_ranges ( ( 0 ..65_535 ) . chain ( 65_537 ..70_000 ) . collect ( ) ) ;
667+ // Runs ending at u32::MAX.
668+ assert_ranges ( [ u32:: MAX ] . into_iter ( ) . collect ( ) ) ;
669+ assert_ranges ( ( u32:: MAX - 70_000 ..=u32:: MAX ) . collect ( ) ) ;
670+ }
671+
672+ #[ test]
673+ fn test_deleted_ranges_match_model_on_random_bitmaps ( ) {
674+ let mut state = 0x2545_f491_4f6c_dd1du64 ;
675+ let mut next = move || {
676+ state ^= state << 13 ;
677+ state ^= state >> 7 ;
678+ state ^= state << 17 ;
679+ state
680+ } ;
681+ for round in 0 ..128 {
682+ let max_gap = [ 2u64 , 30 , 3_000 , 100_000 ] [ round % 4 ] ;
683+ let max_len = [ 3u64 , 50 , 3_000 , 70_000 ] [ ( round / 4 ) % 4 ] ;
684+ let mut bitmap = RoaringBitmap :: new ( ) ;
685+ let mut pos = ( next ( ) % 200_000 ) as u32 ;
686+ for _ in 0 ..40 {
687+ let len = 1 + ( next ( ) % max_len) as u32 ;
688+ let end = pos. saturating_add ( len) ;
689+ bitmap. insert_range ( pos..end) ;
690+ pos = end. saturating_add ( 1 + ( next ( ) % max_gap) as u32 ) ;
691+ }
692+ assert_ranges ( bitmap) ;
693+ }
694+ }
591695}
0 commit comments