RoaringBitmap / RoaringBitmap/CRoaring

Fast/convenient masking operations

Open
#419 2 comments 0 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

Currently one can perform in-place or, andnot and xor operations with a range parameter through the addRange, removeRange and flip methods. Range-based and can be simulated by two consecutive calls to removeRange:

bitmap.removeRange(0, a);
bitmap.removeRange(b + 1, bitmap.maximum() + 1);

It would be more convenient to have a method family like, e.g., mask and maskClosed implementing the same functionality directly.

It would also be helpful to have a family of methods for performing range-restricted updates, i.e. something like

bitmap1.add(otherBitmap, rangeStart, rangeEnd);
bitmap2.flip(otherBitmap, rangeStart, rangeEnd);
bitmap3.andnot(otherBitmap, rangeStart, rangeEnd);

whose semantics would be

Roaring maskedOp;
maskedOp.addRange(rangeStart, rangeEnd);
maskedOp &= otherBitmap;

bitmap1 |= maskedOp;
bitmap2 ^= maskedOp;
bitmap3 -= maskedOp;

Specialized methods could probably be much faster and more memory-efficient than the mask-based solution above.

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 existing addRange, removeRange, and flip entry points and their range semantics. Compare the requested mask and range-restricted bitmap operations with the shown maskedOp behavior; done means the proposed method families have defined semantics, efficient implementations, and coverage for the supported range forms.

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
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.