Adar Dembo has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/12944 )
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 Reviewed-on: http://gerrit.cloudera.org:8080/12944 Reviewed-by: Mike Percy <[email protected]> Tested-by: Kudu Jenkins --- M src/kudu/common/generic_iterators-test.cc M src/kudu/common/generic_iterators.cc 2 files changed, 89 insertions(+), 67 deletions(-) Approvals: Mike Percy: Looks good to me, approved Kudu Jenkins: Verified -- 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: merged Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65 Gerrit-Change-Number: 12944 Gerrit-PatchSet: 5 Gerrit-Owner: Adar Dembo <[email protected]> Gerrit-Reviewer: Adar Dembo <[email protected]> Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Mike Percy <[email protected]> Gerrit-Reviewer: Todd Lipcon <[email protected]>
