blob: 4b74d8bd027ad63e0987e630d842966f768cd2d5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
// 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
|
