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
|
/*
* Copyright (C) 2015 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_COMPILER_DWARF_DEDUP_VECTOR_H_
#define ART_COMPILER_DWARF_DEDUP_VECTOR_H_
#include <vector>
#include <unordered_map>
namespace art {
namespace dwarf {
class DedupVector {
public:
// Returns an offset to previously inserted identical block of data,
// or appends the data at the end of the vector and returns offset to it.
size_t Insert(const uint8_t* ptr, size_t num_bytes) {
// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
uint32_t hash = 2166136261u;
for (size_t i = 0; i < num_bytes; i++) {
hash = (hash ^ ptr[i]) * 16777619u;
}
// Try to find existing copy of the data.
const auto& range = hash_to_offset_.equal_range(hash);
for (auto it = range.first; it != range.second; ++it) {
const size_t offset = it->second;
if (offset + num_bytes <= vector_.size() &&
memcmp(vector_.data() + offset, ptr, num_bytes) == 0) {
return offset;
}
}
// Append the data at the end of the vector.
const size_t new_offset = vector_.size();
hash_to_offset_.emplace(hash, new_offset);
vector_.insert(vector_.end(), ptr, ptr + num_bytes);
return new_offset;
}
const std::vector<uint8_t>& Data() const { return vector_; }
private:
struct IdentityHash {
size_t operator()(uint32_t v) const { return v; }
};
// We store the full hash as the key to simplify growing of the table.
// It avoids storing or referencing the actual data in the hash-table.
std::unordered_multimap<uint32_t, size_t, IdentityHash> hash_to_offset_;
std::vector<uint8_t> vector_;
};
} // namespace dwarf
} // namespace art
#endif // ART_COMPILER_DWARF_DEDUP_VECTOR_H_
|