AU: Some graph types and a couple utility functions

src/platform/update_engine/graph_utils.cc

Index: src/platform/update_engine/graph_utils.cc
diff --git a/src/platform/update_engine/graph_utils.cc b/src/platform/update_engine/graph_utils.cc
new file mode 100644
index 0000000000000000000000000000000000000000..658616768775d687c427f820d737b58822efbeba
--- /dev/null
+++ b/src/platform/update_engine/graph_utils.cc
@@ -0,0 +1,37 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/graph_utils.h"
+#include "base/basictypes.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+uint64 EdgeWeight(const Graph& graph, const Edge& edge) {
+  uint64 ret = 0;

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

s/ret/weight/

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

Done.

+  const vector<Extent>& extents =
+      graph[edge.first].out_edges.find(edge.second)->second.extents;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    ret += it->num_blocks();
+  }
+  return ret;
+}
+
+void AppendBlockToExtents(uint64 block, vector<Extent>* extents) {

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

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

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

Done.

+  if (!extents->empty()) {
+    Extent& extent = extents->back();

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

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

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

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}

+    if (extent.start_block() + extent.num_blocks() == block) {
+      extent.set_num_blocks(extent.num_blocks() + 1);
+      return;
+    }
+  }
+  Extent new_extent;
+  new_extent.set_start_block(block);
+  new_extent.set_num_blocks(1);
+  extents->push_back(new_extent);
+}
+
+}  // namespace chromeos_update_engine