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

["Hao Hao (Code Review)" <ge...@cloudera.org>]

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 <ha...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: David Ribeiro Alves <da...@gmail.com>
Gerrit-Reviewer: Kudu Jenkins
Gerrit-Reviewer: Tidy Bot
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>