blob: d74d01de4dcbd739e8fd839658f046e18034b219 [file] [log] [blame]
* 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
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* See the License for the specific language governing permissions and
* limitations under the License.
#include "dex_file.h"
#include "leb128.h"
#include "utf.h"
namespace art {
* TypeLookupTable used to find class_def_idx by class descriptor quickly.
* Implementation of TypeLookupTable is based on hash table.
* This class instantiated at compile time by calling Create() method and written into OAT file.
* At runtime, the raw data is read from memory-mapped file by calling Open() method. The table
* memory remains clean.
class TypeLookupTable {
// Return the number of buckets in the lookup table.
uint32_t Size() const {
return mask_ + 1;
// Method search class_def_idx by class descriptor and it's hash.
// If no data found then the method returns DexFile::kDexNoIndex
ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const {
uint32_t pos = hash & GetSizeMask();
// Thanks to special insertion algorithm, the element at position pos can be empty or start of
// bucket.
const Entry* entry = &entries_[pos];
while (!entry->IsEmpty()) {
if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) {
return GetClassDefIdx(entry->data);
if (entry->IsLast()) {
return DexFile::kDexNoIndex;
pos = (pos + entry->next_pos_delta) & GetSizeMask();
entry = &entries_[pos];
return DexFile::kDexNoIndex;
// Method creates lookup table for dex file
static TypeLookupTable* Create(const DexFile& dex_file, uint8_t* storage = nullptr);
// Method opens lookup table from binary data. Lookup table does not owns binary data.
static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file);
// Method returns pointer to binary data of lookup table. Used by the oat writer.
const uint8_t* RawData() const {
return reinterpret_cast<const uint8_t*>(entries_.get());
// Method returns length of binary data. Used by the oat writer.
uint32_t RawDataLength() const;
// Method returns length of binary data for the specified dex file.
static uint32_t RawDataLength(const DexFile& dex_file);
// Method returns length of binary data for the specified number of class definitions.
static uint32_t RawDataLength(uint32_t num_class_defs);
* To find element we need to compare strings.
* It is faster to compare first hashes and then strings itself.
* But we have no full hash of element of table. But we can use 2 ideas.
* 1. All minor bits of hash inside one bucket are equals.
* 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n)
* then 16-n bits are free. So we can encode part of element's hash into these bits.
* So hash of element can be divided on three parts:
* Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) -
* n bits
* Y - a part of hash that we can write into free 16-n bits (because only n bits used to store
* class_def_idx)
* X - a part of has that we can't use without increasing increase
* So the data element of Entry used to store class_def_idx and part of hash of the entry.
struct Entry {
uint32_t str_offset;
uint16_t data;
uint16_t next_pos_delta;
Entry() : str_offset(0), data(0), next_pos_delta(0) {}
bool IsEmpty() const {
return str_offset == 0;
bool IsLast() const {
return next_pos_delta == 0;
static uint32_t CalculateMask(uint32_t num_class_defs);
static bool SupportedSize(uint32_t num_class_defs);
// Construct from a dex file.
explicit TypeLookupTable(const DexFile& dex_file, uint8_t* storage);
// Construct from a dex file with existing data.
TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file);
bool IsStringsEquals(const char* str, uint32_t str_offset) const {
const uint8_t* ptr = dex_file_.Begin() + str_offset;
// Skip string length.
return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(
str, reinterpret_cast<const char*>(ptr)) == 0;
// Method extracts hash bits from element's data and compare them with
// the corresponding bits of the specified hash
bool CmpHashBits(uint32_t data, uint32_t hash) const {
uint32_t mask = static_cast<uint16_t>(~GetSizeMask());
return (hash & mask) == (data & mask);
uint32_t GetClassDefIdx(uint32_t data) const {
return data & mask_;
uint32_t GetSizeMask() const {
return mask_;
// Attempt to set an entry on it's hash' slot. If there is alrady something there, return false.
// Otherwise return true.
bool SetOnInitialPos(const Entry& entry, uint32_t hash);
// Insert an entry, probes until there is an empty slot.
void Insert(const Entry& entry, uint32_t hash);
// Find the last entry in a chain.
uint32_t FindLastEntryInBucket(uint32_t cur_pos) const;
const DexFile& dex_file_;
const uint32_t mask_;
std::unique_ptr<Entry[]> entries_;
// owns_entries_ specifies if the lookup table owns the entries_ array.
const bool owns_entries_;
} // namespace art