Issue 3604005: AU: Ranges class to managing unordered collection of blocks/extents.

Issue 3604005: AU: Ranges class to managing unordered collection of blocks/extents. (Closed)

Created:
10 years, 2 months ago by adlr

Modified:
9 years ago

Reviewers:
petkov

CC:
chromium-os-reviews_chromium.org, petkov, adlr

Base URL:
ssh://git@chromiumos-git/update_engine.git

Visibility:
Public.

Description

AU: Ranges class to managing unordered collection of blocks/extents. Sometimes it's useful to have an unordered collection of ranges and manipulate them. For example, we may want to do set subtraction on two collections of extents. This class helps facilitate that. BUG=7294 TEST=attached unittest Committed: http://chrome-svn/viewvc/chromeos?view=rev&revision=5fdae4a

Patch Set 1 #

Total comments: 68

Patch Set 2 : fixes for review #

Patch Set 3 : unittest whitespace fix #

Total comments: 4

Created: 10 years, 2 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+532 lines, -1 line)			Patch
M	SConstruct	View	1	3 chunks	+3 lines, -1 line	0 comments	Download
A	extent_ranges.h	View		1 chunk	+73 lines, -0 lines	4 comments	Download
A	extent_ranges.cc	View		1 chunk	+219 lines, -0 lines	0 comments	Download
A	extent_ranges_unittest.cc	View	2	1 chunk	+237 lines, -0 lines	0 comments	Download

Messages

Total messages: 5 (0 generated)

Expand Messages | Collapse Messages

petkov

10 years, 2 months ago (2010-10-04 17:43:34 UTC) #2

adlr

10 years, 2 months ago (2010-10-05 03:07:13 UTC) #3

thanks for the review. ptal

http://codereview.chromium.org/3604005/diff/1/3
File ranges.cc (right):

http://codereview.chromium.org/3604005/diff/1/3#newcode1
ranges.cc:1: // Copyright (c) 2010 The Chromium Authors. All rights reserved.
On 2010/10/04 17:43:34, petkov wrote:
> Chromium OS Authors
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode5
ranges.cc:5: #include "update_engine/ranges.h"
On 2010/10/04 17:43:34, petkov wrote:
> add empty line after
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode8
ranges.cc:8: #include <base/logging.h>
On 2010/10/04 17:43:34, petkov wrote:
> add empty line before
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode36
ranges.cc:36: Extent extent;
On 2010/10/04 17:43:34, petkov wrote:
> return AddExtent(ExtentForRange(block, 1));
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode43
ranges.cc:43: Extent extent;
On 2010/10/04 17:43:34, petkov wrote:
> return SubtractExtent(ExtentForRange(block, 1));
> 
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode53
ranges.cc:53: if (set_.empty()) {
On 2010/10/04 17:43:34, petkov wrote:
> Do you really need this block? Wouldn't the code below just work?
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode64
ranges.cc:64: end_del = it;
On 2010/10/04 17:43:34, petkov wrote:
> end_del = it + 1?
> 

set iterator doesn't support operator+

http://codereview.chromium.org/3604005/diff/1/3#newcode69
ranges.cc:69: if (it->start_block() < extent.start_block()) {
On 2010/10/04 17:43:34, petkov wrote:
> This code seems a bit convoluted. A couple of suggestions:
> 
> 1. Extract it into a separate helper routine -- e.g., UnionOverlappingExtents.
> 
> 2. Simplify it a bit for readability. Something along the lines:
> 
> new_start = min(it->start, extent->start)
> new_end = max(it->start + it->blocks, extent->start + extent->num_blocks)
> extent.set_start(new_start)
> extent.set_num_blocks(new_end - new_start)
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode95
ranges.cc:95: if (set_.empty()) {
On 2010/10/04 17:43:34, petkov wrote:
> Again, do you need this if or would the code below just work?
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode102
ranges.cc:102: set<Extent, ExtentLess> new_extents;
On 2010/10/04 17:43:34, petkov wrote:
> Isn't this ExtentSet?
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode109
ranges.cc:109: end_del = it;
On 2010/10/04 17:43:34, petkov wrote:
> end_del = it + 1;
> 

same as before

http://codereview.chromium.org/3604005/diff/1/3#newcode114
ranges.cc:114: if (it->start_block() >= extent.start_block()) {
On 2010/10/04 17:43:34, petkov wrote:
> Again, this code seems too convoluted. How about extracting into a separate
> routine and maybe simplifying a bit, something like:
> 
> Extent intersection = IntersectOverlappingExtents(it, extent);
> 
> (Intersect, just like Union, can just do min/max on the Extent ranges).
> 
> Extent diff1, diff2;  // the low and high diffs, either may have end up empty
> diff1.set_start_block(it.start_block);
> diff1.set_num_blocks(intersection.start_block - diff1.start_block);
> diff2.set_start_block(intersection.start_block + intersection.num_blocks);
> diff2.set_num_blocks(it.start_block + it.num_blocks - diff2.start_block)
> 
> if (diff1.num_blocks > 0)
>   new_extents.insert(diff1)
> if (diff2.num_blocks > 0)
>   new_extents.insert(diff2)
> ...
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode156
ranges.cc:156: for (ExtentSet::const_iterator it = ranges.set_.begin(), e =
ranges.set_.end(); it != e; ++it) {
On 2010/10/04 17:43:34, petkov wrote:
> 80 chars
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode161
ranges.cc:161: bool ExtentRanges::SubtractRanges(const ExtentRanges& ranges) {
On 2010/10/04 17:43:34, petkov wrote:
> add an empty line before
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode162
ranges.cc:162: for (ExtentSet::const_iterator it = ranges.set_.begin(), e =
ranges.set_.end(); it != e; ++it) {
On 2010/10/04 17:43:34, petkov wrote:
> 80 chars
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode176
ranges.cc:176: bool ExtentRanges::SubtractExtents(const vector<Extent>& extents)
{
On 2010/10/04 17:43:34, petkov wrote:
> add an empty line before
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode184
ranges.cc:184: bool ExtentRanges::AddRepeatedExtents(
On 2010/10/04 17:43:34, petkov wrote:
> add an empty line before
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode191
ranges.cc:191: 
On 2010/10/04 17:43:34, petkov wrote:
> remove empty line
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode193
ranges.cc:193: bool ExtentRanges::SubtractRepeatedExtents(
On 2010/10/04 17:43:34, petkov wrote:
> add an empty line before
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode201
ranges.cc:201: 
On 2010/10/04 17:43:34, petkov wrote:
> remove one empty line
> 

Done.

http://codereview.chromium.org/3604005/diff/1/3#newcode218
ranges.cc:218: std::vector<Extent> ExtentRanges::OrderedBlocks(uint64_t count)
const {
On 2010/10/04 17:43:34, petkov wrote:
> If |count| is 0, this will return one empty Extent (with 0 blocks) rather than
> an empty vector. Is this intentional?
> 

No, good catch. fixed.

http://codereview.chromium.org/3604005/diff/1/4
File ranges.h (right):

http://codereview.chromium.org/3604005/diff/1/4#newcode1
ranges.h:1: // Copyright (c) 2010 The Chromium Authors. All rights reserved.
On 2010/10/04 17:43:34, petkov wrote:
> Chromium OS Authors
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode5
ranges.h:5: #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__
On 2010/10/04 17:43:34, petkov wrote:
> It seems that extent_ranges.h/.cc is the right base name for these files...
It's
> up to you though.
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode11
ranges.h:11: #include <base/basictypes.h>
On 2010/10/04 17:43:34, petkov wrote:
> add empty lines before and after
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode20
ranges.h:20: bool operator()(const Extent& x, const Extent y) const {
On 2010/10/04 17:43:34, petkov wrote:
> pass by reference "y" doesn't work?
> 

typo. fixed

http://codereview.chromium.org/3604005/diff/1/4#newcode27
ranges.h:27: class ExtentRanges {
On 2010/10/04 17:43:34, petkov wrote:
> Add some documentation summary about the class.
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode27
ranges.h:27: class ExtentRanges {
On 2010/10/04 17:43:34, petkov wrote:
> It might be nice to reduce the use of raw vector<Extent> throughout the code
and
> switch to this class instead...
> 

Yeah, the only thing is vector<Extent> is an ordered list, and this class is
unordered. Often (but not always) when we use vector<Extent> we want ordered.

It might be nice to have a wrapper class for vector<Extent> anyway, which
maintains the number of blocks.

http://codereview.chromium.org/3604005/diff/1/4#newcode32
ranges.h:32: bool AddExtent(Extent extent);
On 2010/10/04 17:43:34, petkov wrote:
> What's the return value? It seems you never return so you may as well just
> switch all methods to void. If not, document the return values.
> 

I thought they would return true for success, but yeah, never really needed it.
Changed to void.

http://codereview.chromium.org/3604005/diff/1/4#newcode42
ranges.h:42: // bool Replace(const ExtentRanges& existing_extents,
On 2010/10/04 17:43:34, petkov wrote:
> remove
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode44
ranges.h:44: static bool ExtentsOverlapOrTouch(const Extent& a, const Extent&
b);
On 2010/10/04 17:43:34, petkov wrote:
> Why static rather than OverlapsOrTouches(const Extent& b) const? This will
also
> make the method naming more consistent (start with verb, etc.).
> 
> 

Extent != ExtentRanges.

Sometimes I just want to test if two Extents overlap.

http://codereview.chromium.org/3604005/diff/1/4#newcode49
ranges.h:49: typedef std::set<Extent, ExtentLess> ExtentSet;
On 2010/10/04 17:43:34, petkov wrote:
> typedef should be first declaration after public:
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode50
ranges.h:50: const ExtentSet& GetExtents() const { return set_; }
On 2010/10/04 17:43:34, petkov wrote:
> AddExtents operates on vectors, while GetExtents returns a set. I'd be
explicit
> here and rename to GetExtentSet() or simply extent_set() (assuming you rename
> the set_ field to extent_set_).
> 

Done.

http://codereview.chromium.org/3604005/diff/1/4#newcode54
ranges.h:54: std::vector<Extent> OrderedBlocks(uint64_t count) const;
On 2010/10/04 17:43:34, petkov wrote:
> Maybe GetExtentsForBlockCount, or GetBlocks, or something like that? Mention
> that the returned extents aren't removed from the set. |count| must be less
than
> or equal to the number of blocks in this extent set.
> 

Done.

http://codereview.chromium.org/3604005/diff/1/5
File ranges_unittest.cc (right):

http://codereview.chromium.org/3604005/diff/1/5#newcode6
ranges_unittest.cc:6: #include <gtest/gtest.h>
On 2010/10/04 17:43:34, petkov wrote:
> add empty line before and after
> 

Done.

petkov

LGTM http://codereview.chromium.org/3604005/diff/9001/8006 File extent_ranges.h (right): http://codereview.chromium.org/3604005/diff/9001/8006#newcode5 extent_ranges.h:5: #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__ CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_RANGES_H__ http://codereview.chromium.org/3604005/diff/9001/8006#newcode25 extent_ranges.h:25: { move { ...

10 years, 2 months ago (2010-10-05 05:56:26 UTC) #4

adlr

10 years, 2 months ago (2010-10-05 17:47:59 UTC) #5

thanks! fixed and committed

http://codereview.chromium.org/3604005/diff/9001/8006
File extent_ranges.h (right):

http://codereview.chromium.org/3604005/diff/9001/8006#newcode5
extent_ranges.h:5: #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__
On 2010/10/05 05:56:26, petkov wrote:
> CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_RANGES_H__
> 

Done.

http://codereview.chromium.org/3604005/diff/9001/8006#newcode25
extent_ranges.h:25: {
On 2010/10/05 05:56:26, petkov wrote:
> move { to the previous line
> 

Done.

Expand Messages | Collapse Messages