Artem Udovichenko | d9786b0 | 2015-10-14 16:36:55 +0300 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2015 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "type_lookup_table.h" |
| 18 | |
| 19 | #include "dex_file-inl.h" |
| 20 | #include "utf-inl.h" |
| 21 | #include "utils.h" |
| 22 | |
| 23 | #include <memory> |
| 24 | #include <cstring> |
| 25 | |
| 26 | namespace art { |
| 27 | |
| 28 | static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) { |
| 29 | uint16_t hash_mask = static_cast<uint16_t>(~mask); |
| 30 | return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx; |
| 31 | } |
| 32 | |
| 33 | TypeLookupTable::~TypeLookupTable() { |
| 34 | if (!owns_entries_) { |
| 35 | // We don't actually own the entries, don't let the unique_ptr release them. |
| 36 | entries_.release(); |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | uint32_t TypeLookupTable::RawDataLength() const { |
| 41 | return RawDataLength(dex_file_); |
| 42 | } |
| 43 | |
| 44 | uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) { |
| 45 | return RoundUpToPowerOfTwo(dex_file.NumClassDefs()) * sizeof(Entry); |
| 46 | } |
| 47 | |
| 48 | TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file) { |
| 49 | const uint32_t num_class_defs = dex_file.NumClassDefs(); |
| 50 | return (num_class_defs == 0 || num_class_defs > std::numeric_limits<uint16_t>::max()) |
| 51 | ? nullptr |
| 52 | : new TypeLookupTable(dex_file); |
| 53 | } |
| 54 | |
| 55 | TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) { |
| 56 | return new TypeLookupTable(raw_data, dex_file); |
| 57 | } |
| 58 | |
| 59 | TypeLookupTable::TypeLookupTable(const DexFile& dex_file) |
| 60 | : dex_file_(dex_file), |
| 61 | mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1), |
| 62 | entries_(new Entry[mask_ + 1]), |
| 63 | owns_entries_(true) { |
| 64 | std::vector<uint16_t> conflict_class_defs; |
| 65 | // The first stage. Put elements on their initial positions. If an initial position is already |
| 66 | // occupied then delay the insertion of the element to the second stage to reduce probing |
| 67 | // distance. |
| 68 | for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) { |
| 69 | const DexFile::ClassDef& class_def = dex_file.GetClassDef(i); |
| 70 | const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); |
| 71 | const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); |
| 72 | const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); |
| 73 | Entry entry; |
| 74 | entry.str_offset = str_id.string_data_off_; |
| 75 | entry.data = MakeData(i, hash, GetSizeMask()); |
| 76 | if (!SetOnInitialPos(entry, hash)) { |
| 77 | conflict_class_defs.push_back(i); |
| 78 | } |
| 79 | } |
| 80 | // The second stage. The initial position of these elements had a collision. Put these elements |
| 81 | // into the nearest free cells and link them together by updating next_pos_delta. |
| 82 | for (uint16_t class_def_idx : conflict_class_defs) { |
| 83 | const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx); |
| 84 | const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); |
| 85 | const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); |
| 86 | const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); |
| 87 | Entry entry; |
| 88 | entry.str_offset = str_id.string_data_off_; |
| 89 | entry.data = MakeData(class_def_idx, hash, GetSizeMask()); |
| 90 | Insert(entry, hash); |
| 91 | } |
| 92 | } |
| 93 | |
| 94 | TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file) |
| 95 | : dex_file_(dex_file), |
| 96 | mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1), |
| 97 | entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))), |
| 98 | owns_entries_(false) {} |
| 99 | |
| 100 | bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) { |
| 101 | const uint32_t pos = hash & GetSizeMask(); |
| 102 | if (!entries_[pos].IsEmpty()) { |
| 103 | return false; |
| 104 | } |
| 105 | entries_[pos] = entry; |
| 106 | entries_[pos].next_pos_delta = 0; |
| 107 | return true; |
| 108 | } |
| 109 | |
| 110 | void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) { |
| 111 | uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask()); |
| 112 | uint32_t next_pos = (pos + 1) & GetSizeMask(); |
| 113 | while (!entries_[next_pos].IsEmpty()) { |
| 114 | next_pos = (next_pos + 1) & GetSizeMask(); |
| 115 | } |
| 116 | const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos); |
| 117 | entries_[pos].next_pos_delta = delta; |
| 118 | entries_[next_pos] = entry; |
| 119 | entries_[next_pos].next_pos_delta = 0; |
| 120 | } |
| 121 | |
| 122 | uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const { |
| 123 | const Entry* entry = &entries_[pos]; |
| 124 | while (!entry->IsLast()) { |
| 125 | pos = (pos + entry->next_pos_delta) & GetSizeMask(); |
| 126 | entry = &entries_[pos]; |
| 127 | } |
| 128 | return pos; |
| 129 | } |
| 130 | |
| 131 | } // namespace art |