diff options
| -rw-r--r-- | BUILD.gn | 3 | ||||
| -rw-r--r-- | label_manager.cc | 93 | ||||
| -rw-r--r-- | label_manager.h | 113 | ||||
| -rw-r--r-- | label_manager_unittest.cc | 137 | ||||
| -rw-r--r-- | zucchini_gen.cc | 1 | ||||
| -rw-r--r-- | zucchini_gen_unittest.cc | 1 |
6 files changed, 0 insertions, 348 deletions
@@ -43,8 +43,6 @@ static_library("zucchini_lib") { "image_utils.h", "io_utils.cc", "io_utils.h", - "label_manager.cc", - "label_manager.h", "patch_reader.cc", "patch_reader.h", "patch_utils.h", @@ -148,7 +146,6 @@ test("zucchini_unittests") { "image_index_unittest.cc", "image_utils_unittest.cc", "io_utils_unittest.cc", - "label_manager_unittest.cc", "mapped_file_unittest.cc", "patch_read_write_unittest.cc", "patch_utils_unittest.cc", diff --git a/label_manager.cc b/label_manager.cc deleted file mode 100644 index 4b74d8b..0000000 --- a/label_manager.cc +++ /dev/null @@ -1,93 +0,0 @@ -// Copyright 2017 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 "components/zucchini/label_manager.h" - -#include <algorithm> -#include <utility> - -#include "base/logging.h" -#include "components/zucchini/algorithm.h" - -namespace zucchini { - -/******** BaseLabelManager ********/ - -BaseLabelManager::BaseLabelManager() = default; -BaseLabelManager::BaseLabelManager(const BaseLabelManager&) = default; -BaseLabelManager::~BaseLabelManager() = default; - -/******** OrderedLabelManager ********/ - -OrderedLabelManager::OrderedLabelManager() = default; -OrderedLabelManager::OrderedLabelManager(const OrderedLabelManager&) = default; -OrderedLabelManager::~OrderedLabelManager() = default; - -offset_t OrderedLabelManager::IndexOfOffset(offset_t offset) const { - auto it = std::lower_bound(labels_.begin(), labels_.end(), offset); - if (it != labels_.end() && *it == offset) - return static_cast<offset_t>(it - labels_.begin()); - return kUnusedIndex; -} - -void OrderedLabelManager::InsertOffsets(const std::vector<offset_t>& offsets) { - labels_.insert(labels_.end(), offsets.begin(), offsets.end()); - SortAndUniquify(&labels_); -} - -void OrderedLabelManager::InsertTargets(ReferenceReader&& reader) { - for (auto ref = reader.GetNext(); ref.has_value(); ref = reader.GetNext()) - labels_.push_back(ref->target); - SortAndUniquify(&labels_); -} - -/******** UnorderedLabelManager ********/ - -UnorderedLabelManager::UnorderedLabelManager() = default; -UnorderedLabelManager::UnorderedLabelManager(const UnorderedLabelManager&) = - default; -UnorderedLabelManager::~UnorderedLabelManager() = default; - -offset_t UnorderedLabelManager::IndexOfOffset(offset_t offset) const { - auto it = labels_map_.find(offset); - return it != labels_map_.end() ? it->second : kUnusedIndex; -} - -void UnorderedLabelManager::Init(std::vector<offset_t>&& labels) { - labels_ = std::move(labels); - labels_map_.clear(); - gap_idx_ = 0; - - size_t used_index_count = 0; - for (offset_t label : labels) { - if (label != kUnusedIndex) - ++used_index_count; - } - labels_map_.reserve(used_index_count); - - offset_t size = static_cast<offset_t>(labels_.size()); - for (offset_t idx = 0; idx < size; ++idx) { - if (labels_[idx] != kUnusedIndex) { - DCHECK(labels_map_.find(labels_[idx]) == labels_map_.end()); - labels_map_[labels_[idx]] = idx; - } - } -} - -void UnorderedLabelManager::InsertNewOffset(offset_t offset) { - DCHECK(labels_map_.find(offset) == labels_map_.end()); - // Look for unused entry in |labels_|. - auto pos = std::find(labels_.begin() + gap_idx_, labels_.end(), kUnusedIndex); - // Either replace the unused entry, or insert at end. - if (pos != labels_.end()) { - gap_idx_ = pos - labels_.begin(); - *pos = offset; - } else { - gap_idx_ = labels_.size(); - labels_.push_back(offset); - } - labels_map_[offset] = static_cast<offset_t>(gap_idx_); -} - -} // namespace zucchini diff --git a/label_manager.h b/label_manager.h deleted file mode 100644 index 7c6606d..0000000 --- a/label_manager.h +++ /dev/null @@ -1,113 +0,0 @@ -// Copyright 2017 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. - -#ifndef COMPONENTS_ZUCCHINI_LABEL_MANAGER_H_ -#define COMPONENTS_ZUCCHINI_LABEL_MANAGER_H_ - -#include <stddef.h> - -#include <unordered_map> -#include <vector> - -#include "base/logging.h" -#include "components/zucchini/image_utils.h" - -namespace zucchini { - -// A LabelManager stores a list of Labels. By definition, all offsets and -// indices must be distinct. It also provides functions to: -// - Get the offset of a stored index. -// - Get the index of a stored offset. -// - Create new Labels. - -// Base class for OrderedLabelManager and UnorderedLabelManager. -class BaseLabelManager { - public: - BaseLabelManager(); - BaseLabelManager(const BaseLabelManager&); - virtual ~BaseLabelManager(); - - // Returns the offset of a given |index| if it is associated with a - // stored Label, or |kUnusedIndex| otherwise. - offset_t OffsetOfIndex(offset_t index) const { - return index < labels_.size() ? labels_[index] : kUnusedIndex; - } - - // If |offset| has an associated stored Label, returns its index. Otherwise - // returns |kUnusedIndex|. - virtual offset_t IndexOfOffset(offset_t offset) const = 0; - - size_t size() const { return labels_.size(); } - - protected: - // Main storage of distinct offsets. This allows O(1) look up of an offset - // from its index. UnorderedLabelManager may contain "gaps" with - // |kUnusedIndex|. - std::vector<offset_t> labels_; -}; - -// OrderedLabelManager is a LabelManager that prioritizes memory efficiency, -// storing Labels as a sorted list of offsets in |labels_|. Label insertions -// are performed in batch to reduce costs. Index-of-offset lookup is O(lg n) -// (binary search). -class OrderedLabelManager : public BaseLabelManager { - public: - OrderedLabelManager(); - OrderedLabelManager(const OrderedLabelManager&); - ~OrderedLabelManager() override; - - // BaseLabelManager: - offset_t IndexOfOffset(offset_t offset) const override; - - // Creates and stores a new Label for each unique offset in |offsets|. This - // invalidates all previous Label lookups. - void InsertOffsets(const std::vector<offset_t>& offsets); - - // For each unique target from |reader|, creates and stores a new Label. This - // invalidates all previous Label lookups. - void InsertTargets(ReferenceReader&& reader); - - const std::vector<offset_t>& Labels() const { return labels_; } -}; - -// UnorderedLabelManager is a LabelManager that does not requires Labels to be -// sorted. Therefore, it can be initialized from Labels given in any order. It -// also prioritizes speed for lookup and insertion, but uses more memory than -// OrderedLabelManager. In addition to using |labels_| to store *unsorted* -// distinct offsets, an unordered_map |labels_map_| is used for index-of-offset -// lookup. -class UnorderedLabelManager : public BaseLabelManager { - public: - UnorderedLabelManager(); - UnorderedLabelManager(const UnorderedLabelManager&); - ~UnorderedLabelManager() override; - - // BaseLabelManager: - offset_t IndexOfOffset(offset_t offset) const override; - - // Clears and reinitializes all stored data. Requires that |labels| consists - // of unique offsets, but it may have "gaps" in the form of |kUnusedIndex|. - void Init(std::vector<offset_t>&& labels); - - // Creates a new Label for |offset|. Behavior is undefined if |offset| is - // already associated with a stored Label. If |kUnusedIndex| gaps exist, tries - // to reused indices to create new Labels, otherwise it allocates new indices. - // Previous lookup results involving stored offsets / indexes remain valid. - void InsertNewOffset(offset_t offset); - - bool ContainsOffset(offset_t offset) const { - return labels_map_.find(offset) != labels_map_.end(); - } - - private: - // Inverse map of |labels_| (excludes |kUnusedIndex|). - std::unordered_map<offset_t, offset_t> labels_map_; - - // Index into |label_| to scan for |kUnusedIndex| entry in |labels_|. - size_t gap_idx_ = 0; -}; - -} // namespace zucchini - -#endif // COMPONENTS_ZUCCHINI_LABEL_MANAGER_H_ diff --git a/label_manager_unittest.cc b/label_manager_unittest.cc deleted file mode 100644 index 11dcdf9..0000000 --- a/label_manager_unittest.cc +++ /dev/null @@ -1,137 +0,0 @@ -// Copyright 2017 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 "components/zucchini/label_manager.h" - -#include <utility> -#include <vector> - -#include "components/zucchini/test_reference_reader.h" -#include "testing/gtest/include/gtest/gtest.h" - -namespace zucchini { - -namespace { - -constexpr auto BAD = kUnusedIndex; -using OffsetVector = std::vector<offset_t>; - -} // namespace - -TEST(LabelManagerTest, Ordered) { - OrderedLabelManager label_manager; - EXPECT_EQ(OffsetVector(), label_manager.Labels()); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0)); - - // Initialize with some data, test direct lookups. - label_manager.InsertOffsets({0x33, 0x11, 0x44, 0x11}); - EXPECT_EQ(OffsetVector({0x11, 0x33, 0x44}), label_manager.Labels()); - - EXPECT_EQ(0x11U, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(0x33U, label_manager.OffsetOfIndex(1)); - EXPECT_EQ(0x44U, label_manager.OffsetOfIndex(2)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(3)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(4)); - - EXPECT_EQ(0U, label_manager.IndexOfOffset(0x11)); - EXPECT_EQ(1U, label_manager.IndexOfOffset(0x33)); - EXPECT_EQ(2U, label_manager.IndexOfOffset(0x44)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x00)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x77)); - - // Insert more data, note that lookup results changed. - label_manager.InsertOffsets({0x66, 0x11, 0x11, 0x44, 0x00}); - EXPECT_EQ(OffsetVector({0x00, 0x11, 0x33, 0x44, 0x66}), - label_manager.Labels()); - - EXPECT_EQ(0x00U, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(0x11U, label_manager.OffsetOfIndex(1)); - EXPECT_EQ(0x33U, label_manager.OffsetOfIndex(2)); - EXPECT_EQ(0x44U, label_manager.OffsetOfIndex(3)); - EXPECT_EQ(0x66U, label_manager.OffsetOfIndex(4)); - - EXPECT_EQ(1U, label_manager.IndexOfOffset(0x11)); - EXPECT_EQ(2U, label_manager.IndexOfOffset(0x33)); - EXPECT_EQ(3U, label_manager.IndexOfOffset(0x44)); - EXPECT_EQ(0U, label_manager.IndexOfOffset(0x00)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x77)); -} - -TEST(LabelManagerTest, OrderedInsertTargets) { - OrderedLabelManager label_manager; - - // Initialize with some data. |location| does not matter. - TestReferenceReader reader1({{0, 0x33}, {1, 0x11}, {2, 0x44}, {3, 0x11}}); - label_manager.InsertTargets(std::move(reader1)); - EXPECT_EQ(OffsetVector({0x11, 0x33, 0x44}), label_manager.Labels()); - - // Insert more data. - TestReferenceReader reader2( - {{0, 0x66}, {1, 0x11}, {2, 0x11}, {3, 0x44}, {4, 0x00}}); - label_manager.InsertTargets(std::move(reader2)); - EXPECT_EQ(OffsetVector({0x00, 0x11, 0x33, 0x44, 0x66}), - label_manager.Labels()); -} - -TEST(LabelManagerTest, Unordered) { - UnorderedLabelManager label_manager; - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0)); - - // Initialize with some data, test direct lookups. - label_manager.Init(OffsetVector({0x33, BAD, BAD, 0x11, 0x44, BAD})); - - EXPECT_EQ(0x33U, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(1)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(2)); - EXPECT_EQ(0x11U, label_manager.OffsetOfIndex(3)); - EXPECT_EQ(0x44U, label_manager.OffsetOfIndex(4)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(5)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(6)); - - EXPECT_EQ(3U, label_manager.IndexOfOffset(0x11)); - EXPECT_EQ(0U, label_manager.IndexOfOffset(0x33)); - EXPECT_EQ(4U, label_manager.IndexOfOffset(0x44)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x00)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x66)); - - // Insert one offset, assumed to be new. - label_manager.InsertNewOffset(0x00); - EXPECT_EQ(0x33U, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(0x00U, label_manager.OffsetOfIndex(1)); - EXPECT_EQ(BAD, label_manager.OffsetOfIndex(2)); - EXPECT_EQ(0x11U, label_manager.OffsetOfIndex(3)); - EXPECT_EQ(0x44U, label_manager.OffsetOfIndex(4)); - - EXPECT_EQ(1U, label_manager.IndexOfOffset(0x00)); - EXPECT_EQ(3U, label_manager.IndexOfOffset(0x11)); - EXPECT_EQ(0U, label_manager.IndexOfOffset(0x33)); - EXPECT_EQ(4U, label_manager.IndexOfOffset(0x44)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x66)); - - // Insert few more offset, assumed to be new. - label_manager.InsertNewOffset(0x22); - label_manager.InsertNewOffset(0x77); - label_manager.InsertNewOffset(0x55); - - EXPECT_EQ(0x33U, label_manager.OffsetOfIndex(0)); - EXPECT_EQ(0x00U, label_manager.OffsetOfIndex(1)); - EXPECT_EQ(0x22U, label_manager.OffsetOfIndex(2)); - EXPECT_EQ(0x11U, label_manager.OffsetOfIndex(3)); - EXPECT_EQ(0x44U, label_manager.OffsetOfIndex(4)); - EXPECT_EQ(0x77U, label_manager.OffsetOfIndex(5)); - EXPECT_EQ(0x55U, label_manager.OffsetOfIndex(6)); - - EXPECT_EQ(1U, label_manager.IndexOfOffset(0x00)); - EXPECT_EQ(3U, label_manager.IndexOfOffset(0x11)); - EXPECT_EQ(2U, label_manager.IndexOfOffset(0x22)); - EXPECT_EQ(0U, label_manager.IndexOfOffset(0x33)); - EXPECT_EQ(4U, label_manager.IndexOfOffset(0x44)); - EXPECT_EQ(6U, label_manager.IndexOfOffset(0x55)); - EXPECT_EQ(BAD, label_manager.IndexOfOffset(0x66)); - EXPECT_EQ(5U, label_manager.IndexOfOffset(0x77)); -} - -} // namespace zucchini diff --git a/zucchini_gen.cc b/zucchini_gen.cc index 0758e5a..de0e7d9 100644 --- a/zucchini_gen.cc +++ b/zucchini_gen.cc @@ -21,7 +21,6 @@ #include "components/zucchini/equivalence_map.h" #include "components/zucchini/heuristic_ensemble_matcher.h" #include "components/zucchini/image_index.h" -#include "components/zucchini/label_manager.h" #include "components/zucchini/patch_writer.h" #include "components/zucchini/suffix_array.h" #include "components/zucchini/targets_affinity.h" diff --git a/zucchini_gen_unittest.cc b/zucchini_gen_unittest.cc index 29e84d6..fb16cdd 100644 --- a/zucchini_gen_unittest.cc +++ b/zucchini_gen_unittest.cc @@ -12,7 +12,6 @@ #include "components/zucchini/equivalence_map.h" #include "components/zucchini/image_index.h" #include "components/zucchini/image_utils.h" -#include "components/zucchini/label_manager.h" #include "components/zucchini/test_disassembler.h" #include "testing/gtest/include/gtest/gtest.h" |