[
https://issues.apache.org/jira/browse/CASSANDRA-9769?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14626334#comment-14626334
]
Branimir Lambov commented on CASSANDRA-9769:
--------------------------------------------
The code looks good. Some minor issues, mostly documentation:
[BTree|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR35]:
The last element is the size map, rather than just size. EMPTY_BRANCH is thus
invalid.
[BTree.build|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR97]:
Must source be sorted? Could the JavaDoc say whether it needs to be? Same for
update.
[BTree.build|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR104]:
To force odd just do {{size | 1}}.
[BTree.slice|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR195]:
JavaDoc says end inclusive, code says exclusive. Which one is wrong? JavaDoc
in next method also needs some correction in that respect.
[BTree.size|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR427]:
length / 2 - 1 in doc.
[BTree.Infinity|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR552]:
I would not implement {{compareTo}} here, as it makes it appear that it's ok
to place object among comparables, which isn't safe as it can't be used on the
right side of comparisons. It would be cleaner to just move the logic into
{{BTree.compare}}.
[BTree.Builder.mergeAll(int)|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-4b911b7d0959c6219175e2349968f3cdR666]:
Equal first values is rare to come by. I wouldn't complicate the code just for
that.
However, you could do something else that also covers this case, advance {{i}}
as long as {{a\[i\] <= a\[j\]}}, i.e. only break for {{c > 0}} at 669, and only
increase {{j}} if {{c == 0}}.
The special case 675-685 saves little, I'd remove it or replace it with {{if (j
== addEnd) return this;}}, which combined with the above would turn it into an
efficient treatment of {{this}} being a superset of the added values.
[BTreeSearchIterator|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-094cf1e0d2f3989d28ca14d63166f058R2]:
Bad reformatting of initial comment. Present in other files also.
[BTreeSearchIterator
43|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-094cf1e0d2f3989d28ca14d63166f058R43]:
s/ON_TIME/ON_ITEM/
[BTreeSet.slice|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-62305c56b59a7f421e347a6a3d829182R53]:
I don't see any reference where {{permitInversion}} is false. Remove flag if
it's not used.
[BTreeSet.last|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-62305c56b59a7f421e347a6a3d829182R190]:
Comment is at odds with code ({{this.size()}} _is_ used).
[NodeCursor
constructor|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-2caee7a8a153168b2ceb785366dbd1d7R53]:
This assumes branches have the same depth (otherwise child could be left null
but required). Is this guaranteed? Could you add a comment if it is?
[NodeCursor
97|https://github.com/apache/cassandra/compare/trunk...belliottsmith:btreelist#diff-2caee7a8a153168b2ceb785366dbd1d7R97]:
s/NodeIterator/NodeCursor/
> Improve BTree
> -------------
>
> Key: CASSANDRA-9769
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9769
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Benedict
> Assignee: Benedict
> Fix For: 3.0 beta 1
>
>
> Split out from CASSANDRA-9471, after discussion there. This patch contains
> all of the btree centric changes, as well as some minimally invasive
> replacement of TreeMap around the codebase.
> * Introduces "indexing" to the BTree class, permitting lookup by positional
> index, and binarySearch semantics (so inequality lookups yield the position a
> binarySearch of the equivalent array would)
> ** The size modulo remainder of a Leaf/Branch are flipped, so that a Branch
> has a spare slot at the end for an int[] index:
> *** if missing, this occupies at most 1 bit per entry in the set (often
> 1/32), if present, it occupies at most 2.5 bits, and typically around 1 bit.
> Sets with <= 32 items incur no cost.
> *** This index just contains the cumulative size of the tree preceding each
> branch key, rooted at the node in question
> * Reintroduces BTreeSet, with extra methods for accessing by index*, and
> simple implementations of missing NavigableMap methods using this new
> functionality
> * Introduces a simple BTreeSet.Builder, and replaces all suitable uses of
> TreeMap in the codebase with a BTreeSet.Builder -> BTreeSet
> * Rewrites btree.Cursor to make it far easier to understand, and to
> introduced IndexedSearchIterator, exposing the new indexing
> * Reintroduces LongBTreeTest, with cleaned up more exhaustive coverage of
> iterator functionality, and new NavigableMap methods
> This version further cleans up a few things, and switches to always indexing
> a btree, given the costs are fairly low (which permits eliminating quite a
> bit of code that would be required if the positions of items were not known,
> and providing just one iterator implementation)
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
