Add a function to move the iterator to be equal or smaller than a value about croaring HOT 5 CLOSED

Can't you use roaring_uint32_iterator_previous?

from croaring.

Can't you use roaring_uint32_iterator_previous?

I don’t think it can perform well given there are a large number of bits between the end of the range to search and the last value in the roaring bitmap. My assumption is by using that function, the implementation needs to iterates backwards from the last value.

from croaring.

I'd recommend making a benchmark showing an unreasonable performance loss.

Keep in mind that Roaring bitmaps are compressed bitmaps, going back to the previous set bit will never have to do much work. For instance, in:

roaring_bitmap_t *r = roaring_bitmap_from(1, UINT32_MAX);
roaring_uint32_iterator_t it;
roaring_iterator_init(r, &it);
roaring_uint32_iterator_move_equalorlarger(&it, 2); // Iterator points at UINT32_MAX
roaring_uint32_iterator_previous(&it);              // Iterator points at 1

both roaring_uint32_iterator_move_equalorlarger and roaring_uint32_iterator_previous will be very quick, as the iterator is able to skip directly between the two values.

from croaring.

This being said, if you want to implement the desired functionality, a pull request would be given full consideration. It could lead to more elegant code.

from croaring.

Thank you all. The proposed flow of euqlorlarger then going back to find the value should perform well. I'm closing the issue as a result.

from croaring.