AU: Some graph types and a couple utility functions

AU: Some graph types and a couple utility functions

These will be used by the delta diff generator.

[Daniel Erat, 2010-02-05 17:55:19]

LGTM with some suggestions

http://codereview.chromium.org/578009/diff/1/3
File src/platform/update_engine/graph_types.h (right):

http://codereview.chromium.org/578009/diff/1/3#newcode47
src/platform/update_engine/graph_types.h:47: const VertexIndex
kInvalidVertexIndex = -1;
can you move this into Vertex, i.e. Vertex::kInvalidIndex?  similarly, can you
move the VertexIndex typedef into Vertex and rename it to Index?

http://codereview.chromium.org/578009/diff/1/4
File src/platform/update_engine/graph_utils.cc (right):

http://codereview.chromium.org/578009/diff/1/4#newcode13
src/platform/update_engine/graph_utils.cc:13: uint64 ret = 0;
s/ret/weight/

http://codereview.chromium.org/578009/diff/1/4#newcode23
src/platform/update_engine/graph_utils.cc:23: void AppendBlockToExtents(uint64
block, vector<Extent>* extents) {
i think that the opposite parameter order is more common, i.e. list the in-out
'extents' param that's being operated on first and the block to append to it
second.  feel free to leave it this way if you disagree though

http://codereview.chromium.org/578009/diff/1/4#newcode25
src/platform/update_engine/graph_utils.cc:25: Extent& extent = extents->back();
you're just checking the last extent here.  does this function require that
blocks get appended in-order?  if so, it'd be good to add:

  CHECK_LT(extent.start_block() + extent.num_blocks() - 1,
           block);

to enforce this

http://codereview.chromium.org/578009/diff/1/5
File src/platform/update_engine/graph_utils.h (right):

http://codereview.chromium.org/578009/diff/1/5#newcode18
src/platform/update_engine/graph_utils.h:18: uint64 EdgeWeight(const Graph&
graph, const Edge& edge);
mind moving these into a graph_utils namespace?  it makes it easier to find
where functions like this are defined later

http://codereview.chromium.org/578009/diff/1/5#newcode22
src/platform/update_engine/graph_utils.h:22: // into an arbitrary place in the
extents
nit: add trailing period

http://codereview.chromium.org/578009/diff/1/6
File src/platform/update_engine/graph_utils_unittest.cc (right):

http://codereview.chromium.org/578009/diff/1/6#newcode18
src/platform/update_engine/graph_utils_unittest.cc:18:
graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
this would all be a bit more readable if you just created a vector<Extent>
instead of using Graph

http://codereview.chromium.org/578009/diff/1/7
File src/platform/update_engine/utils.h (right):

http://codereview.chromium.org/578009/diff/1/7#newcode84
src/platform/update_engine/utils.h:84: bool VectorContainsValue(const T& value,
const std::vector<T>& vect) {
this is easier (from <algorithm>):

return std::find(vect.begin(), vect.end(), value) != vect.end();

the parameter order here feels backwards too

[adlr, 2010-02-22 23:27:31]

thanks. made the corrections and submitted

http://codereview.chromium.org/578009/diff/1/3
File src/platform/update_engine/graph_types.h (right):

http://codereview.chromium.org/578009/diff/1/3#newcode47
src/platform/update_engine/graph_types.h:47: const VertexIndex
kInvalidVertexIndex = -1;
On 2010/02/05 17:55:19, Daniel Erat wrote:
> can you move this into Vertex, i.e. Vertex::kInvalidIndex?  similarly, can you
> move the VertexIndex typedef into Vertex and rename it to Index?

Done.

http://codereview.chromium.org/578009/diff/1/4
File src/platform/update_engine/graph_utils.cc (right):

http://codereview.chromium.org/578009/diff/1/4#newcode13
src/platform/update_engine/graph_utils.cc:13: uint64 ret = 0;
On 2010/02/05 17:55:19, Daniel Erat wrote:
> s/ret/weight/

Done.

http://codereview.chromium.org/578009/diff/1/4#newcode23
src/platform/update_engine/graph_utils.cc:23: void AppendBlockToExtents(uint64
block, vector<Extent>* extents) {
On 2010/02/05 17:55:19, Daniel Erat wrote:
> i think that the opposite parameter order is more common, i.e. list the in-out
> 'extents' param that's being operated on first and the block to append to it
> second.  feel free to leave it this way if you disagree though

Done.

http://codereview.chromium.org/578009/diff/1/4#newcode25
src/platform/update_engine/graph_utils.cc:25: Extent& extent = extents->back();
On 2010/02/05 17:55:19, Daniel Erat wrote:
> you're just checking the last extent here.  does this function require that
> blocks get appended in-order?  if so, it'd be good to add:
> 
>   CHECK_LT(extent.start_block() + extent.num_blocks() - 1,
>            block);
> 
> to enforce this

no, blocks do not need to be appended in order. I simply want to avoid wasteful
representation. For example, blocks 2, 3, 4, 5, 8, 9, 1 could be encoded as the
following extents:

{2, 4}, {8, 2}, {1, 1}, but less optimally:
{2, 1}, {3, 3}, {8, 2}, {1, 1}

http://codereview.chromium.org/578009/diff/1/5
File src/platform/update_engine/graph_utils.h (right):

http://codereview.chromium.org/578009/diff/1/5#newcode18
src/platform/update_engine/graph_utils.h:18: uint64 EdgeWeight(const Graph&
graph, const Edge& edge);
On 2010/02/05 17:55:19, Daniel Erat wrote:
> mind moving these into a graph_utils namespace?  it makes it easier to find
> where functions like this are defined later

Done.

http://codereview.chromium.org/578009/diff/1/5#newcode22
src/platform/update_engine/graph_utils.h:22: // into an arbitrary place in the
extents
On 2010/02/05 17:55:19, Daniel Erat wrote:
> nit: add trailing period

Done.

http://codereview.chromium.org/578009/diff/1/6
File src/platform/update_engine/graph_utils_unittest.cc (right):

http://codereview.chromium.org/578009/diff/1/6#newcode18
src/platform/update_engine/graph_utils_unittest.cc:18:
graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
On 2010/02/05 17:55:19, Daniel Erat wrote:
> this would all be a bit more readable if you just created a vector<Extent>
> instead of using Graph

Did a little cleanup. Created a reference to avoid the graph[0].out_edges[1]
repetition

http://codereview.chromium.org/578009/diff/1/7
File src/platform/update_engine/utils.h (right):

http://codereview.chromium.org/578009/diff/1/7#newcode84
src/platform/update_engine/utils.h:84: bool VectorContainsValue(const T& value,
const std::vector<T>& vect) {
On 2010/02/05 17:55:19, Daniel Erat wrote:
> this is easier (from <algorithm>):
> 
> return std::find(vect.begin(), vect.end(), value) != vect.end();
> 
> the parameter order here feels backwards too

Done.