[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 10: Code-Review+2


--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 10
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Thu, 28 Sep 2017 23:49:30 +
Gerrit-HasComments: No

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has submitted this change and it was merged. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
in-place given a list of intervals. The operation to construct such one
is O(nlg n + n) where 'n' is the number of intervals. This util can be
used when log block manager coalesces block deletions belonging to the
same container.

For example, given the input interval list:
   [--2---) [-1-)
   [--3--)[---5--)[4)

The output sorted disjoint interval list is:
   [--1--)  [-2-)

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Reviewed-on: http://gerrit.cloudera.org:8080/8041
Tested-by: Kudu Jenkins
Reviewed-by: Dan Burkert 
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 194 insertions(+), 0 deletions(-)

Approvals:
  Kudu Jenkins: Verified
  Dan Burkert: Looks good to me, approved

--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 11
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Tidy Bot, Alexey Serbin, Dan Burkert, David Ribeiro Alves, Kudu Jenkins, 
Andrew Wong, Adar Dembo, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#10).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
in-place given a list of intervals. The operation to construct such one
is O(nlg n + n) where 'n' is the number of intervals. This util can be
used when log block manager coalesces block deletions belonging to the
same container.

For example, given the input interval list:
   [--2---) [-1-)
   [--3--)[---5--)[4)

The output sorted disjoint interval list is:
   [--1--)  [-2-)

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 194 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/10
--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 10
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 9: Code-Review+2


--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 9
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Thu, 28 Sep 2017 21:25:14 +
Gerrit-HasComments: No

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 8:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc
File src/kudu/util/sorted_disjoint_interval_list-test.cc:

http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc@45
PS7, Line 45: an
> nit: "an" here and below
Done


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc@57
PS7, Line 57: an interval list with adjacent rang
> nit: Since the input is unsorted, at first glance, it wasn't clear to me ho
Done


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@43
PS7, Line 43: [--2---) [-1-)
: //   [--3--)[---5--)[4)
: //
: // The output sorted disjoint interval list:
: //
: //   [--1--)  [-2-)
> [---) ?
Done


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@81
PS7, Line 81: // some intervals, 'head' and 'tail' will not be adjacent. If so, 
move 'tail'
:   // to the next 'head' to make sure we do not include any of 
the previously-coalesced
:   // intervals.
> nit: maybe move this comment just above the "++head;" and reword it to desc
Done


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@85
PS7, Line 85: if (hea
> nit: maybe pull this into the while loop condition? eg:
Done


http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h@95
PS6, Line 95:
> Is this if check necessary?  I would think vector::erase would check if it'
Will remove the check. Right, I think vector::erase would not truncate if 'head 
== tail'.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 8
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Thu, 28 Sep 2017 04:30:45 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Tidy Bot, Alexey Serbin, Dan Burkert, David Ribeiro Alves, Kudu Jenkins, 
Andrew Wong, Adar Dembo, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#8).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
in-place given a list of intervals. The operation to construct such one
is O(nlg n + n) where 'n' is the number of intervals. This util can be
used when log block manager coalesces block deletions belonging to the
same container.

For example, given the input interval list:
   [--2---) [-1-)
   [--3--)[---5--)[4)

The output sorted disjoint interval list is:
   [--1--)  [-2-)

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 193 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/8
--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 8
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Andrew Wong (Code Review)]

Andrew Wong has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 7:

(7 comments)

Just some nits

http://gerrit.cloudera.org:8080/#/c/8041/7//COMMIT_MSG
Commit Message:

http://gerrit.cloudera.org:8080/#/c/8041/7//COMMIT_MSG@15
PS7, Line 15: For example, given the input interval list:
:|--2---| |-1-|
:|--3--||---5--||4|
:
: The output sorted disjoint interval list is:
:|--1--|  |-2-|
nit: update to [), here and elsewhere?


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc
File src/kudu/util/sorted_disjoint_interval_list-test.cc:

http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc@45
PS7, Line 45: a
nit: "an" here and below


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list-test.cc@57
PS7, Line 57: {{4, 7}, {3, 4}, {1, 2}, {-23, 1}};
nit: Since the input is unsorted, at first glance, it wasn't clear to me how 
this was different from the below test. maybe comment above here too:
"Coalesce adjacent intervals."?


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@43
PS7, Line 43: |--2---| |-1-|
: //   |--3--||---5--||4|
: //
: // The output sorted disjoint interval list:
: //
: //   |--1--|  |-2-|
[---) ?


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@61
PS7, Line 61: auto&
nit: const auto&?


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@81
PS7, Line 81: else {
:   ++head;
:   // Fill the gap between 'head' and 'tail', if they are not 
adjacent.
nit: maybe move this comment just above the "++head;" and reword it to describe 
why this is necessary? Something like:

"The two intervals are disjoint. If the 'head' previously coalesced some 
intervals, 'head' and 'tail' will not be adjacent. If so, make sure the next 
'head' does not include any of the previously-coalesced intervals."


http://gerrit.cloudera.org:8080/#/c/8041/7/src/kudu/util/sorted_disjoint_interval_list.h@85
PS7, Line 85: ++tail;
nit: maybe pull this into the while loop condition? eg:

 while (++tail != intervals->end()) { ... }

That way we could get rid of this line, L74, and L80. Although might be worse 
for readability. Up to you.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 7
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Wed, 27 Sep 2017 01:38:56 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 7: Code-Review+2


--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 7
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 26 Sep 2017 21:51:16 +
Gerrit-HasComments: No

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Tidy Bot, Alexey Serbin, Dan Burkert, David Ribeiro Alves, Kudu Jenkins, 
Andrew Wong, Adar Dembo, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#7).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
in-place given a list of intervals. The operation to construct such one
is O(nlg n + n) where 'n' is the number of intervals. This util can be
used when log block manager coalesces block deletions belonging to the
same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 192 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/7
--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 7
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h@88
PS6, Line 88:   if (tail != cur_tail) {
> not affect the correctness of the output but will affect the performance

ah ok, interesting, hadn't realized that.

> We may want to check how many times the move operations are actually 
> performed in the test case

Don't worry about it, I'm more concerned about correctness.  There's probably a 
way to detect the # of moves using a class with a custom move ctor, but I think 
that's overkill here.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 26 Sep 2017 17:36:32 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h@88
PS6, Line 88:   if (tail != cur_tail) {
> I believe this is supposed to be 'head != cur_tail'.  'tail != cur_tail' is
I don't know what to say that I put the opposite one here when renaming...But 
thanks a lot for catching that!

The reason that the current test cases did not discover it is 'tail != 
cur_tail' is always true here, that result in '*head = std::move(*cur_tail);' 
always gets executed. This should not affect the correctness of the output but 
will affect the performance (there could be a extra move operation which is not 
needed). We may want to check how many times the move operations are actually 
performed in the test case, but not sure what is the best way to do that?



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Mon, 25 Sep 2017 19:41:10 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@73
PS5, Line 73: // interval.
> Hmm I would expect that error replacing IntervalIterator with auto, or doin
Ah, sorry, I misunderstood your recommendation previously. Yeah, with the 
latter it would work. Will update it. Thanks!



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Mon, 25 Sep 2017 18:52:36 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h@88
PS6, Line 88:   if (tail != cur_tail) {
I believe this is supposed to be 'head != cur_tail'.  'tail != cur_tail' is a 
tautology because of how cur_tail is defined.  Please add tests for this case, 
this is showing a big lack of coverage.

Also, perhaps simpler as:

} else {
++head;
if (head != tail) {
*head = std::move(*tail);
}
++ tail;
}


http://gerrit.cloudera.org:8080/#/c/8041/6/src/kudu/util/sorted_disjoint_interval_list.h@95
PS6, Line 95:   if (++head != tail) intervals->erase(head, tail);
Is this if check necessary?  I would think vector::erase would check if it's 0 
length already.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Mon, 25 Sep 2017 18:51:14 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Andrew Wong (Code Review)]

Andrew Wong has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@73
PS5, Line 73: // interval.
> It seems not possible to use auto here. Throws 'requires an initializer' er
Hmm I would expect that error replacing IntervalIterator with auto, or doing 
something like:
 auto start = end = intervals->begin();
Would this work?
 auto start = intervals->begin(), end = intervals->begin();



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Mon, 25 Sep 2017 17:29:17 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 6:

(4 comments)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@73
PS5, Line 73: // interval.
> Is auto possible here? If so, we can avoid the IntervalIterator typedef.
It seems not possible to use auto here. Throws 'requires an initializer' error.

Yes, I agree with you 'start', 'end' may not be a good name here. May be 
'head', 'tail' are better. Will update.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@81
PS5, Line 81:   if (tail->second > head->second)  head->second = 
std::move(tail->second);
> In both branches, is there a way to move the point values instead of copyin
Done


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@82
PS5, Line 82:   ++tail;
> I think this branch should just be moving *end into *(start + 1), so I don'
Done. Yeah, we should only move if there is a gap between the two.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@94
PS5, Line 94:   // Truncate the rest useless elements, if any.
> This might be better as
Done



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Sun, 24 Sep 2017 20:50:48 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Tidy Bot, Alexey Serbin, Dan Burkert, David Ribeiro Alves, Kudu Jenkins, 
Andrew Wong, Adar Dembo, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#6).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
in-place given a list of intervals. The operation to construct such one
is O(nlg n + n) where 'n' is the number of intervals. This util can be
used when log block manager coalesces block deletions belonging to the
same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 180 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/6
--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 6
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@32
PS5, Line 32: // In-place constructing a sorted disjoint interval list given a 
list of intervals.
> How about "Constructs a sorted disjoint interval list in-place given a list
Done


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@63
PS5, Line 63: IllegalState
> I think IllegalArgument is more appropriate here.
Done


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@75
PS5, Line 75: for (; end != intervals->end();) {
> nit: use a while loop?
Done


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@76
PS5, Line 76: overlaps
> s/overlaps/overlap
Done


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@79
PS5, Line 79:   start->second = end->second;
> Shouldn't this be setting it to the larger end of the two?  I think as is t
Right, good catch! Thanks!


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64:
> It's kind of ambiguous what [0, 0) even means.
I think [0, 0) should be invalid mathematically. But either let LBM to filter 
those blocks or drop those before coalescing them, or even just consider it to 
be valid and do nothing, seems to be equivalent from the output perspective. So 
I will just stick to the third option (just consider it to be valid) if no 
objections.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 22:18:33 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Andrew Wong (Code Review)]

Andrew Wong has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@73
PS5, Line 73: start = end = intervals->begin();
Is auto possible here? If so, we can avoid the IntervalIterator typedef.

nit: Also imo "start" and "end" seem a bit confusing, as they refer to 
intervals, but they sound like they refer to points. Maybe head/tail, 
first/second, even interval1,interval2? May want others' thoughts on this. I 
don't feel super strongly about this, but I think it's worth considering.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@75
PS5, Line 75: for (; end != intervals->end();) {
nit: use a while loop?



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 20:03:05 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64: interval.first > interval.second
> It would also be OK to drop those empty blocks just before coalescing them.
It's kind of ambiguous what [0, 0) even means.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 4
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 18:41:54 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Adar Dembo (Code Review)]

Adar Dembo has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64:
> I personally think it's fine as is.  If the LBM wants to guarantee that, th
It would also be OK to drop those empty blocks just before coalescing them. 
There's nothing to actually delete, after all.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 18:27:31 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64: interval.first > interval.second
> Hmm, right. Maybe we should consider length 0 interval as empty not invalid
I personally think it's fine as is.  If the LBM wants to guarantee that, then 
it can CHECK_OK on the returned status.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 4
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 18:17:30 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64:
> I'm a little concerned about this. Can we guarantee that the LBM never trie
Hmm, right. Maybe we should consider length 0 interval as empty not invalid?



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 18:16:06 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@63
PS5, Line 63: IllegalState
I think IllegalArgument is more appropriate here.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@76
PS5, Line 76: overlaps
s/overlaps/overlap


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@79
PS5, Line 79:   start->second = end->second;
Shouldn't this be setting it to the larger end of the two?  I think as is this 
would fail with a nested interval, e.g:

[-)
[--)

Perhaps a missing test case?


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@81
PS5, Line 81: } else {
In both branches, is there a way to move the point values instead of copying?  
This might make a difference for long string values.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@82
PS5, Line 82:   IntervalIterator cur_end = end;
I think this branch should just be moving *end into *(start + 1), so I don't 
think a std::copy should be required.  std::copy makes me nervous because it 
effectively turns this into an n^2 algorithm.

Edit: on second thought, that move/copy should only occur if (start + 1) > end 
(e.g. there's a gap between start and end), otherwise that's just copying end 
into itself.


http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@94
PS5, Line 94: intervals->erase(++start, end);
This might be better as

if (++start != end) {
  intervals->erase(start, end);
}



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 18:14:08 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Adar Dembo (Code Review)]

Adar Dembo has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/5/src/kudu/util/sorted_disjoint_interval_list.h@32
PS5, Line 32: // In-place constructing a sorted disjoint interval list given a 
list of intervals.
How about "Constructs a sorted disjoint interval list in-place given a list of 
intervals?


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64:
> Changed the interval to be ''half-open" as Dan suggested, so interval with
I'm a little concerned about this. Can we guarantee that the LBM never tries to 
coalesce empty blocks?



-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 17:05:33 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 5:

(7 comments)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@37
PS4, Line 37: holdi
> holding
Done


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@54
PS4, Line 54: template
> Couple of notes on the algorithm:
Done.


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@55
PS4, Line 55: intType
> This is a little confusing because you've mapped 'beginning' to false and e
Removed the logic as Dan suggested.


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@56
PS4, Line 56: edef type
> indicate
Done


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@64
PS4, Line 64:
> nit: might be worth noting somewhere that an interval can be width 0 (assum
Changed the interval to be ''half-open" as Dan suggested, so interval with 
length 0 is no longer valid.


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@75
PS4, Line 75: ->end
> uses
Done


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@86
PS4, Line 86:   if (start != cur_end) {
> Under what circumstances would this fail?
It will fail if the number of intervals' start and end points are not matching, 
which should never happen.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Fri, 22 Sep 2017 00:12:51 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Tidy Bot, Alexey Serbin, Dan Burkert, David Ribeiro Alves, Kudu Jenkins, 
Andrew Wong, Adar Dembo, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#5).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds a utility to construct a sorted disjoint interval list
given a list of intervals. The operation to construct such one is
O(klg k + k) where 'k' is the number of points in the intervals. This
util can be used when log block manager coalesces block deletions
belonging to the same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlapped, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 179 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/5
--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 5
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Dan Burkert (Code Review)]

Dan Burkert has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/8041 )

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@54
PS4, Line 54: Status CoalesceIntervals(std::vector>* intervals) {
Couple of notes on the algorithm:

- Since this is meant to be a general utility, it'd be better if it operated on 
[closed, open) interval, since it's always possible to convert a closed 
interval to a [closed, open) interval, but it's not possible to convert a 
closed intervals of strings to [closed, open).  I think this algorithm would be 
useful in a few places where we have string interval sets (see 
partition_pruner.cc).

- This algorithm can be implemented in-place without allocating a new vector.  
It's also simpler since you don't need / can't have a separate Point type.  It 
requires scanning over the original vector with two pointers from left to 
right, coalescing/copying ranges as you go, until you get to the end and remove 
a suffix of now unused elements (from what I can tell the existing 
implementation over Points is doing something similar).  The algorithmic 
complexity is n*log(n) where n is the number of input intervals.



--
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-Change-Number: 8041
Gerrit-PatchSet: 4
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Dan Burkert 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Thu, 21 Sep 2017 21:08:44 +
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Andrew Wong (Code Review)]

Andrew Wong has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

PS4, Line 64: interval.first > interval.second
nit: might be worth noting somewhere that an interval can be width 0 (assuming 
that's intended)?


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Adar Dembo (Code Review)]

Adar Dembo has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(7 comments)

http://gerrit.cloudera.org:8080/#/c/8041/4//COMMIT_MSG
Commit Message:

PS4, Line 9: an
a


PS4, Line 22: overlap
overlapped


http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

PS4, Line 37: holds
holding


PS4, Line 55: boolean
This is a little confusing because you've mapped 'beginning' to false and end 
to 'true'.

Instead, could you define a local enum with the values BEGINNING and END? Or 
would that mess up the std::sort?


PS4, Line 56: indicates
indicate


PS4, Line 75: using
uses


Line 86:   CHECK_EQ(active, 0);
Under what circumstances would this fail?


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/3/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

Line 67: }
> warning: do not use 'else' after 'return' [readability-else-after-return]
Done. This is not shown in my local 'make tidy' build on OSX.


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#4).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds an utility to construct a sorted disjoint interval list
given a list of intervals. The operation to construct such one is
O(klg k + k) where 'k' is the number of points in the intervals. This
util can be used when log block manager coalesces block deletions
belonging to the same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlap, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 170 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/4
-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 4
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 3:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

Line 94
> but since k = 2*n, those are the same big-O (just a constant factor involve
Sounds good to me.


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 3:

(5 comments)

The failed test cases ITClientStress.testManyShortClientsGeneratingScanTokens
and TestKuduClient.testCloseShortlyAfterOpen are not relevant to this patch. 
However from a short glance I cannot locate the reason for failures.

http://gerrit.cloudera.org:8080/#/c/8041/2/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

Line 57:   typedef std::pair Point;
> do we still need a traits class if it's just a single point type involved?
Done


Line 88:   return Status::OK();
> this going into the error log will probably never get noticed.
Done


PS2, Line 95: 
: 
: 
: 
> is this comparator necessary? I think the default comparator for std::pair<
Done


Line 108
> style: add {}s around if statement
Done


PS2, Line 111: 
> do you need ClosedInterval here? emplace_back already takes a variable leng
Done


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#3).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds an utility to construct a sorted disjoint interval list
given a list of intervals. The operation to construct such one is
O(klg k + k) where 'k' is the number of points in the intervals. This
util can be used when log block manager coalesces block deletions
belonging to the same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlap, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 171 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/3
-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 3
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Todd Lipcon (Code Review)]

Todd Lipcon has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

Line 94:   IntervalVector sorted_intervals = Traits::sort(intervals);
> Thanks a lot for the proposal! Yeah this would work and simplify the templa
but since k = 2*n, those are the same big-O (just a constant factor involved). 
And I think practically it's the same, since the previous comparison operation 
could make two comparisons (start and end bound) whereas the new one makes one 
comparison (just the point), which washes out any constant factor difference.


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Todd Lipcon (Code Review)]

Todd Lipcon has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 2:

(5 comments)

http://gerrit.cloudera.org:8080/#/c/8041/2/src/kudu/util/sorted_disjoint_interval_list.h
File src/kudu/util/sorted_disjoint_interval_list.h:

Line 57: template
do we still need a traits class if it's just a single point type involved?


Line 88: LOG(ERROR) << strings::Substitute("invalid interval: [$0, $1]",
this going into the error log will probably never get noticed.

Why not make this whole algorithm just be a method like:

template
Status CoalesceIntervals(std::vector>* 
intervals);

rather than being a class?


PS2, Line 95: , [](const Point& a, const Point& b) {
:   if (a.first == b.first) return a.second < b.second;
:   return a.first < b.first;
: 
is this comparator necessary? I think the default comparator for std::pair<> 
already does lexicographic comparison 
(http://en.cppreference.com/w/cpp/utility/pair/operator_cmp)


Line 108:   cur_start = point.first;
style: add {}s around if statement


PS2, Line 111: ClosedInterval
do you need ClosedInterval here? emplace_back already takes a variable length 
argument list which is forwarded to the constructor of the container element 
type


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hao Hao has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..


Patch Set 2:

(21 comments)

http://gerrit.cloudera.org:8080/#/c/8041/1//COMMIT_MSG
Commit Message:

PS1, Line 9: This patch adds an utility to construct a sorted disjoint interval 
list
   : given a list of intervals. The operation to construct such one is
   : O(klg k + k) where 'k' is the number of points in
> maybe mention a bit what this is for? easier to review for perf if we know 
Done


http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval-test.cc
File src/kudu/util/sorted_disjoint_interval-test.cc:

Line 29
> warning: using decl 'Substitute' is unused [misc-unused-using-decls]
Done


PS1, Line 36: 
> Should this be a class/structure template as well (with type for the  left 
Done


PS1, Line 37: 
> If not using a class template for this ClosedInterval, consider making the 
Done


Line 46
> nit: const?
Done


Line 47
> int: const?
Done


PS1, Line 50: 
: 
: 
: 
: 
: 
> nit: why does this need to be its own struct? why not a lambda within sort(
Done, but I do not see much difference between these two?


PS1, Line 58: 
> nit: consider IntIntervalTraits or something? Or just IntInterval?
Done


PS1, Line 85: 
: 
: 
> nit: here and below consider replacing with something like
Done


Line 132
> I don't see any coverage for single element intervals, like
Done


http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

PS1, Line 17: 
: 
> Use #pragma once for C++11 !
Done


PS1, Line 27: 
: 
> nit: How about, "A set of sorted disjoint intervals holds a list of non-ove
Done


PS1, Line 33: 
> nit: to emphasize the sortedness of the sorted disjoint interval set, maybe
Done


PS1, Line 40: 
> immutable?
Done


PS1, Line 46: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
: 
> Is there a way to encapsulate this into some sort of templatized abstract b
I have rewrite the logic of constructing a sorted disjoint interval list to 
avoid too many template functions.


PS1, Line 66: 
> nit: it's more of a SortedDisjointIntervalList
Done


PS1, Line 65: 
: 
> Why does SortedDisjointInterval need its own class; could it just be a temp
If we have other implementations of interval list may be we can do that. But I 
feel that is too abstract at least for the use case I encounter at LBM, which 
is specific for sorted and disjoint intervals.


PS1, Line 89: 
> Maybe, just move it inside the class definition above?
Done


Line 94
> just looking at this quickly... curious why we need a specific Traits::sort
Thanks a lot for the proposal! Yeah this would work and simplify the template 
definition. Only the operation complexity would change from, O(nlg n + n) where 
'n' is the number of intervals, to O(klg k + k) where 'k' is the number of 
'point'. But I guess it is ok.


PS1, Line 98: 
> Two questions here:
1) right, we need to check that.
2) removed the following logic.


PS1, Line 106: 
> ++cur might be better since it doesn't need to store the prev iterator valu
Rewritten the logic here.


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Hao Hao 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

[Hao Hao (Code Review)]

Hello Kudu Jenkins,

I'd like you to reexamine a change.  Please visit

http://gerrit.cloudera.org:8080/8041

to look at the new patch set (#2).

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval list
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list

This patch adds an utility to construct a sorted disjoint interval list
given a list of intervals. The operation to construct such one is
O(klg k + k) where 'k' is the number of points in the intervals. This
util can be used when log block manager coalesces block deletions
belonging to the same container.

For example, given the input interval list:
   |--2---| |-1-|
   |--3--||---5--||4|

The output sorted disjoint interval list is:
   |--1--|  |-2-|

It also adds unit test to verify given overlap, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval_list-test.cc
A src/kudu/util/sorted_disjoint_interval_list.h
3 files changed, 211 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/2
-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 2
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

[Todd Lipcon (Code Review)]

Todd Lipcon has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval
..


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

Line 94:   IntervalVector sorted_intervals = Traits::sort(intervals);
just looking at this quickly... curious why we need a specific Traits::sort for 
sorting intervals. Given the problem statement, I expected to see something 
like the following algorithm:

// bool = false for starting points, true for end points
vector> points;
for each interval:
  CHECK(interval.start <= interval.end) (or return error)
  points.emplace(interval.start, false);
  points.emplace(interval.end, true);
sort(points)

int active = 0;
for each (point, is_end) in points:
  if !is_end:
if (active++ == 0):
  cur_start = point
  else:
if (--active == 0):
  result.emplace_back(cur_start, point)
 
CHECK_EQ(active, 0)

Wouldn't this work without having to define any interval comparator or 
Traits::Overlap, etc, so long as the 'point_type' itself is naturally 
comparable using operatorhttp://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon 
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

[David Ribeiro Alves (Code Review)]

David Ribeiro Alves has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval
..


Patch Set 1:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/8041/1//COMMIT_MSG
Commit Message:

PS1, Line 9: This patch adds an utility to construct a sorted disjoint interval 
set
   : given a set of intervals. The operation to construct such one is
   : O(nlgn + n) where 'n' is the number of intervals.
maybe mention a bit what this is for? easier to review for perf if we know the 
context...


http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

PS1, Line 40: a static
immutable?


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: David Ribeiro Alves 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

[Andrew Wong (Code Review)]

Andrew Wong has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval
..


Patch Set 1:

(8 comments)

http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval-test.cc
File src/kudu/util/sorted_disjoint_interval-test.cc:

PS1, Line 50: struct DisjointIntervalComparator {
:   bool operator() (const ClosedInterval& first, const 
ClosedInterval& second) const {
: if (first.left == second.left) return first.right < 
second.right;
: return first.left < second.left;
:   }
: };
nit: why does this need to be its own struct? why not a lambda within sort()?


PS1, Line 58: IntTraits
nit: consider IntIntervalTraits or something? Or just IntInterval?


http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

PS1, Line 17: #ifndef KUDU_UTIL_SORTED_DISJOINT_INTERVAL_H
: #define KUDU_UTIL_SORTED_DISJOINT_INTERVAL_H
Use #pragma once for C++11 !


PS1, Line 27: A sorted disjoint interval is a data structure which stores a set 
of intervals that
: // are sorted and disjoint. 
nit: How about, "A set of sorted disjoint intervals holds a list of 
non-overlapping ranges."


PS1, Line 33: |--1---| |-2-|
nit: to emphasize the sortedness of the sorted disjoint interval set, maybe 
flip 1 and 2?


PS1, Line 46:  The Traits class should have the following members:
: //   Traits::point_type
: // a typedef for what a "point" in the range is
: //
: //   Traits::interval_type
: // a typedef for an interval
: //
: //   static vector sort(const 
vector& interval)
: // sort the given intervals.
: //
: //   static bool valid(const interval_type& interval)
: // return true if the interval is valid.
: //
: //   static interval_type coalesce(const interval_type& a, const 
interval_type& b)
: // coalesce two intervals.
: //
: //   static bool overlap(const interval_type& a, const 
interval_type& b)
: // return true if two intervals are overlapped.
Is there a way to encapsulate this into some sort of templatized abstract base 
class? Not sure how easy/difficult that'd be with the templates.


PS1, Line 65: template
: class SortedDisjointInterval {
Why does SortedDisjointInterval need its own class; could it just be a 
templatized utility method that takes in a vector of s and returns a 
vector of s?


PS1, Line 66: SortedDisjointInterval
nit: it's more of a SortedDisjointIntervalList


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Andrew Wong 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

[Alexey Serbin (Code Review)]

Alexey Serbin has posted comments on this change.

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval
..


Patch Set 1:

(9 comments)

http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval-test.cc
File src/kudu/util/sorted_disjoint_interval-test.cc:

PS1, Line 36: struct ClosedInterval {
Should this be a class/structure template as well (with type for the  left and 
right point)?


PS1, Line 37: int left, int right
If not using a class template for this ClosedInterval, consider making the 
parameters for this constructor and the left and right members of the same type.


Line 46:   int64_t left; // Inclusive
nit: const?


Line 47:   int64_t right; // Inclusive
int: const?


PS1, Line 85:   vector expected;
:   expected.emplace_back(-23, 2);
:   expected.emplace_back(3, 7);
nit: here and below consider replacing with something like

const vector expected = { {-23, 2}, {3, 7} };


Line 132: 
I don't see any coverage for single element intervals, like

{ {0, 0}, {0, 1}, {1, 1} }

etc.

Consider adding tests for that as well.


http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h
File src/kudu/util/sorted_disjoint_interval.h:

PS1, Line 89: inline 
Maybe, just move it inside the class definition above?


PS1, Line 98: !Traits::valid(*cur)
Two questions here:
1. Is it necessary to check for the end of the container here?
2. Why not to move this under the for () cycle below?


PS1, Line 106: cur++
++cur might be better since it doesn't need to store the prev iterator value.


-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: comment
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao 
Gerrit-Reviewer: Alexey Serbin 
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-HasComments: Yes

[kudu-CR] KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

[Hao Hao (Code Review)]

Hao Hao has uploaded a new change for review.

  http://gerrit.cloudera.org:8080/8041

Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint 
interval
..

KUDU-2055 [part 2]: Add util to construct sorted disjoint interval

This patch adds an utility to construct a sorted disjoint interval set
given a set of intervals. The operation to construct such one is
O(nlgn + n) where 'n' is the number of intervals.

For example, given the input interval set:
   |--1---| |-2-|
   |--3--||---4--||5|

The output sorted disjoint interval set is:
   |--1--|  |-2-|

It also adds unit test to verify given overlap, duplicate, invalid
intervals, the implementation works as expected.

Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
---
M src/kudu/util/CMakeLists.txt
A src/kudu/util/sorted_disjoint_interval-test.cc
A src/kudu/util/sorted_disjoint_interval.h
3 files changed, 261 insertions(+), 0 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/41/8041/1
-- 
To view, visit http://gerrit.cloudera.org:8080/8041
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-MessageType: newchange
Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87
Gerrit-PatchSet: 1
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-Owner: Hao Hao