Hello Mike Percy, Todd Lipcon,
I'd like you to do a code review. Please visit
http://gerrit.cloudera.org:8080/12944
to review the following change.
Change subject: generic_iterators: switch MergeIterator to intrusive list of
states
......................................................................
generic_iterators: switch MergeIterator to intrusive list of states
I originally wanted this for dominance because, in that world, a state is
either linked to the main list or to another state's dominated list. We're
going to go in a different direction, but an intrusive list still makes
sense because:
1. We don't need random access into states_, and
2. An intrusive list will yield O(1) erase without increasing the total
number of allocations.
I also changed the MergeIterator tests to use int64_t instead of uint32_t
for values, as the latter reliably overflowed the non-overlapped input test
when num_lists >= 30.
Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
---
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
2 files changed, 91 insertions(+), 67 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/44/12944/1
--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo <[email protected]>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy <[email protected]>
Gerrit-Reviewer: Todd Lipcon <[email protected]>
