You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@tsfile.apache.org by "jt2594838 (via GitHub)" <gi...@apache.org> on 2026/07/30 08:57:38 UTC
[PR] Add range mark query APIs to BitMap [tsfile]
jt2594838 opened a new pull request, #884:
URL: https://github.com/apache/tsfile/pull/884
## Summary
- add `isRangeAnyMarked(int start, int length)` to detect whether a range contains a marked bit
- add `isRangeAllMarked(int start, int length)` to detect whether every bit in a range is marked
- add `isRangeNoneMarked(int start, int length)` to detect whether a range contains no marked bits
- share the implementation across long-backed and byte-array-backed bitmaps
- add exhaustive range and invalid-argument coverage
## Semantics
- empty ranges return `false` for `isRangeAnyMarked`
- empty ranges return `true` for `isRangeAllMarked` and `isRangeNoneMarked`
- negative or out-of-bounds ranges throw `IndexOutOfBoundsException`
- range checks process up to 64 bits per iteration
## Verification
- `mvn -P with-java -pl java/tsfile -am -Dtest=BitMapTest -Dsurefire.failIfNoSpecifiedTests=false test`
- 18 tests passed with no failures or errors
- Checkstyle and Spotless passed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@tsfile.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add range mark query APIs to BitMap [tsfile]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #884:
URL: https://github.com/apache/tsfile/pull/884#issuecomment-5128936765
## [Codecov](https://app.codecov.io/gh/apache/tsfile/pull/884?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `0%` with `20 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 60.49%. Comparing base ([`46cf0a1`](https://app.codecov.io/gh/apache/tsfile/commit/46cf0a126548e7d9292fa5953a0adb53a7eeff26?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`3dacbaa`](https://app.codecov.io/gh/apache/tsfile/commit/3dacbaa4552f8bf028e6bbe3227bb090f891788f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
| [Files with missing lines](https://app.codecov.io/gh/apache/tsfile/pull/884?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [.../main/java/org/apache/tsfile/utils/BitMapImpl.java](https://app.codecov.io/gh/apache/tsfile/pull/884?src=pr&el=tree&filepath=java%2Fcommon%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Ftsfile%2Futils%2FBitMapImpl.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-amF2YS9jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL3RzZmlsZS91dGlscy9CaXRNYXBJbXBsLmphdmE=) | 0.00% | [17 Missing :warning: ](https://app.codecov.io/gh/apache/tsfile/pull/884?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [.../src/main/java/org/apache/tsfile/utils/BitMap.java](https://app.codecov.io/gh/apache/tsfile/pull/884?src=pr&el=tree&filepath=java%2Fcommon%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Ftsfile%2Futils%2FBitMap.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-amF2YS9jb21tb24vc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL3RzZmlsZS91dGlscy9CaXRNYXAuamF2YQ==) | 0.00% | [3 Missing :warning: ](https://app.codecov.io/gh/apache/tsfile/pull/884?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## develop #884 +/- ##
===========================================
- Coverage 60.51% 60.49% -0.03%
===========================================
Files 744 744
Lines 49081 49101 +20
Branches 7797 7801 +4
===========================================
+ Hits 29703 29704 +1
- Misses 17978 17995 +17
- Partials 1400 1402 +2
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/tsfile/pull/884?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@tsfile.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add range mark query APIs to BitMap [tsfile]
Posted by "jt2594838 (via GitHub)" <gi...@apache.org>.
jt2594838 commented on code in PR #884:
URL: https://github.com/apache/tsfile/pull/884#discussion_r3681373160
##########
java/common/src/main/java/org/apache/tsfile/utils/BitMap.java:
##########
@@ -54,6 +54,35 @@ public boolean isMarked(int position) {
return implementation.isMarked(position);
}
+ /**
+ * Returns whether at least one bit in the specified range is marked. An empty range returns
+ * {@code false}.
+ *
+ * @throws IndexOutOfBoundsException if the range is outside this bitmap
+ */
+ public boolean isRangeAnyMarked(int start, int length) {
Review Comment:
These public APIs distinguish any, all, and none semantics without forcing callers to scan individual bits. The Javadocs explicitly define empty-range results and preserve the existing bitmap range-error convention for invalid input.
##########
java/common/src/main/java/org/apache/tsfile/utils/BitMapImpl.java:
##########
@@ -39,6 +41,32 @@ int getSize() {
abstract boolean isMarked(int position);
+ boolean isRangeAnyMarked(int start, int length) {
Review Comment:
The shared implementation keeps long-backed and byte-array-backed bitmaps behaviorally identical by reusing `extractBits` in batches of up to 64 bits. Range validation uses `start > size - length` instead of `start + length > size` so an overflowing sum cannot bypass the bounds check.
##########
java/tsfile/src/test/java/org/apache/tsfile/utils/BitMapTest.java:
##########
@@ -217,6 +218,45 @@ public void testIsAllUnmarkedInRange() {
assertFalse(bitMap.isAllUnmarked(10));
}
+ @Test
+ public void testRangeMarkedQueries() {
Review Comment:
This test checks every valid subrange against a per-bit oracle for empty, array-backed, and long-backed bitmaps, including ranges that cross byte and 64-bit boundaries. It also verifies negative, out-of-bounds, and integer-overflow arguments.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@tsfile.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add range mark query APIs to BitMap [tsfile]
Posted by "jt2594838 (via GitHub)" <gi...@apache.org>.
jt2594838 merged PR #884:
URL: https://github.com/apache/tsfile/pull/884
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@tsfile.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add range mark query APIs to BitMap [tsfile]
Posted by "jt2594838 (via GitHub)" <gi...@apache.org>.
jt2594838 commented on PR #884:
URL: https://github.com/apache/tsfile/pull/884#issuecomment-5129613111
Thanks for the detailed analysis. Addressed in 031deadf:
- moved the range-query implementations into `BitMapLongImpl` and `BitMapArrayImpl`, keeping shared range validation in `BitMapImpl`
- added the long shifted-mask path and array first/last-byte plus complete-middle-byte scan
- added the requested `(0, 64)`, `(1, 63)`, and `(64, 64)` range benchmark cases
- added explicit full-64-bit and 64-bit-boundary-crossing `isRangeAllMarked` cases
I reran:
`mvn -P with-java -pl java/tsfile -am -Dtest=BitMapPerformanceTest#testRangeMarkedQueryImplementations -Dtsfile.runPerformanceTests=true -Dsurefire.failIfNoSpecifiedTests=false test`
The Maven configuration runs the selected test twice. Both runs showed:
| representation / range | current helper | new API |
| --- | ---: | ---: |
| array-backed prefix | 3.125 ns/op, 0 B/op | 3.125 ns/op, 0 B/op |
| array-backed partial | 3.125 ns/op, 0 B/op | 3.125 ns/op, 0 B/op |
| array-backed next block | 3.125 ns/op, 0 B/op | 3.125 ns/op, 0 B/op |
| long-backed prefix | 1.563 ns/op, 0 B/op | 1.563 ns/op, 0 B/op |
| long-backed partial | 6.250-7.813 ns/op, 32 B/op | 1.563 ns/op, 0 B/op |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@tsfile.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org