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

extent_ranges.h

Index: extent_ranges.h
diff --git a/extent_ranges.h b/extent_ranges.h
new file mode 100644
index 0000000000000000000000000000000000000000..ff089703cc2b8f5a95c40c4220efeeca6c9ee539
--- /dev/null
+++ b/extent_ranges.h
@@ -0,0 +1,73 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__

[petkov, 2010/10/05 05:56:26]

CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_RANGES_H__

[adlr, 2010/10/05 17:47:59]

Done.

+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__
+
+#include <map>
+#include <set>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/delta_diff_generator.h"
+#include "update_engine/graph_types.h"
+#include "update_engine/update_metadata.pb.h"
+
+// An ExtentRanges object represents an unordered collection of extents
+// (and therefore blocks). Such an object may be modified by adding or
+// subtracting blocks (think: set addition or set subtraction).
+
+namespace chromeos_update_engine {
+
+struct ExtentLess
+{

[petkov, 2010/10/05 05:56:26]

move { to the previous line

[adlr, 2010/10/05 17:47:59]

Done.

+  bool operator()(const Extent& x, const Extent& y) const {
+    return x.start_block() < y.start_block();
+  }
+};
+
+Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks);
+
+class ExtentRanges {
+ public:
+  typedef std::set<Extent, ExtentLess> ExtentSet;
+
+  ExtentRanges() : blocks_(0) {}
+  void AddBlock(uint64_t block);
+  void SubtractBlock(uint64_t block);
+  void AddExtent(Extent extent);
+  void SubtractExtent(const Extent& extent);
+  void AddExtents(const std::vector<Extent>& extents);
+  void SubtractExtents(const std::vector<Extent>& extents);
+  void AddRepeatedExtents(
+      const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+  void SubtractRepeatedExtents(
+      const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+  void AddRanges(const ExtentRanges& ranges);
+  void SubtractRanges(const ExtentRanges& ranges);
+
+  static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b);
+  static bool ExtentsOverlap(const Extent& a, const Extent& b);
+
+  // Dumps contents to the log file. Useful for debugging.
+  void Dump() const;
+  
+  uint64_t blocks() const { return blocks_; }
+  const ExtentSet& extent_set() const { return extent_set_; }
+
+  // Returns an ordered vector of extents for |count| blocks,
+  // using extents in extent_set_. The returned extents are not
+  // removed from extent_set_. |count| must be less than or equal to
+  // the number of blocks in this extent set.
+  std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const;
+
+ private:
+  ExtentSet extent_set_;
+  uint64_t blocks_;
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_RANGES_H__