RoaringBitmap / RoaringBitmap/CRoaring

Misc Missing Functionality for Roaring64 bitmaps

Open
#549 9 comments 3 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
1.9k
Forks
334
Avg merge
2d 5h
Merged PRs (30d)
17

Description

This is just a list of functionality which I noticed was missing in comparison to roaring_bitmap_t as I was adding bindings to croaring-rs. I may add more if I find anything else, rather than making more issues.

  • roaring64_bitmap_clear, to remove all data, and start from an empty bitmap
    (can this be done more efficiently than roaring64_bitmap_remove_range_closed(0, UINT64_MAX)). It seems like roaring64_bitmap_remove_range_closed could be optimized, it appears to loop through all high 48 bit combos, rather than skipping around using the ART. roaring64_bitmap_remove_range_closed(0, UINT64_MAX) is now efficient.
  • The ability to do external iteration (an iterator type that the caller controls arbitrarily)
  • roaring64_bitmap_internal_validate, mostly useful for tests, to ensure our assumptions are never broken (max art depth, things which should be sorted are, etc).
  • roaring64_bitmap_flip
  • roaring64_bitmap_range_cardinality is exclusive only, it's unfortunate that roaring64_bitmap_cardinality(r) can't be emulated by roaring64_bitmap_range_cardinality(r, 0, UINT64_MAX)
  • roaring64_bitmap_steal_roaring32(roaring_bitmap_t *) which steals the containers from the passed 32 bit bitmap. (naming?) #649
  • roaring64_bitmap_remove_run_compression
  • roaring64_bitmap_add_offset
  • roaring64_bitmap_overwrite
  • CoW support (not sure this is something we even want to support?)
  • Debug Printing (roaring64_bitmap_printf/roaring64_bitmap_printf_describe)
  • Iterator skipping (roaring64_iterator_skip/roaring64_iterator_skip_backward)

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the three unchecked entry points: CoW support, debug printing through roaring64_bitmap_printf or roaring64_bitmap_printf_describe, and iterator skipping through roaring64_iterator_skip or roaring64_iterator_skip_backward. Compare their intended behavior with the corresponding roaring_bitmap_t functionality and the croaring-rs bindings, then define a focused scope before implementing anything.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
15/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.