diff options
Diffstat (limited to 'include/lldb/Core/MappedHash.h')
| -rw-r--r-- | include/lldb/Core/MappedHash.h | 933 |
1 files changed, 429 insertions, 504 deletions
diff --git a/include/lldb/Core/MappedHash.h b/include/lldb/Core/MappedHash.h index b7cf3b02e01e..44fe63216165 100644 --- a/include/lldb/Core/MappedHash.h +++ b/include/lldb/Core/MappedHash.h @@ -25,535 +25,460 @@ #include "lldb/Core/DataExtractor.h" #include "lldb/Core/Stream.h" -class MappedHash -{ +class MappedHash { public: - enum HashFunctionType - { - eHashFunctionDJB = 0u // Daniel J Bernstein hash function that is also used by the ELF GNU_HASH sections - }; + enum HashFunctionType { + eHashFunctionDJB = 0u // Daniel J Bernstein hash function that is also used + // by the ELF GNU_HASH sections + }; + + static uint32_t HashStringUsingDJB(const char *s) { + uint32_t h = 5381; + + for (unsigned char c = *s; c; c = *++s) + h = ((h << 5) + h) + c; + + return h; + } - static uint32_t - HashStringUsingDJB (const char *s) - { - uint32_t h = 5381; - - for (unsigned char c = *s; c; c = *++s) - h = ((h << 5) + h) + c; - - return h; + static uint32_t HashString(uint32_t hash_function, const char *s) { + if (!s) + return 0; + + switch (hash_function) { + case MappedHash::eHashFunctionDJB: + return HashStringUsingDJB(s); + + default: + break; } - - static uint32_t - HashString (uint32_t hash_function, const char *s) - { - if (!s) - return 0; - - switch (hash_function) - { - case MappedHash::eHashFunctionDJB: - return HashStringUsingDJB (s); - - default: - break; - } - assert (!"Invalid hash function index"); - return 0; + assert(!"Invalid hash function index"); + return 0; + } + + static const uint32_t HASH_MAGIC = 0x48415348u; + static const uint32_t HASH_CIGAM = 0x48534148u; + + template <typename T> struct Header { + typedef T HeaderData; + + uint32_t + magic; // HASH_MAGIC or HASH_CIGAM magic value to allow endian detection + uint16_t version; // Version number + uint16_t hash_function; // The hash function enumeration that was used + uint32_t bucket_count; // The number of buckets in this hash table + uint32_t hashes_count; // The total number of unique hash values and hash + // data offsets in this table + uint32_t header_data_len; // The size in bytes of the "header_data" template + // member below + HeaderData header_data; // + + Header() + : magic(HASH_MAGIC), version(1), hash_function(eHashFunctionDJB), + bucket_count(0), hashes_count(0), header_data_len(sizeof(T)), + header_data() {} + + virtual ~Header() = default; + + size_t GetByteSize() const { + return sizeof(magic) + sizeof(version) + sizeof(hash_function) + + sizeof(bucket_count) + sizeof(hashes_count) + + sizeof(header_data_len) + header_data_len; } - static const uint32_t HASH_MAGIC = 0x48415348u; - static const uint32_t HASH_CIGAM = 0x48534148u; - - template <typename T> - struct Header - { - typedef T HeaderData; - - uint32_t magic; // HASH_MAGIC or HASH_CIGAM magic value to allow endian detection - uint16_t version; // Version number - uint16_t hash_function; // The hash function enumeration that was used - uint32_t bucket_count; // The number of buckets in this hash table - uint32_t hashes_count; // The total number of unique hash values and hash data offsets in this table - uint32_t header_data_len; // The size in bytes of the "header_data" template member below - HeaderData header_data; // - - Header () : - magic (HASH_MAGIC), - version (1), - hash_function (eHashFunctionDJB), - bucket_count (0), - hashes_count (0), - header_data_len (sizeof(T)), - header_data () - { - } - - virtual - ~Header() = default; - - size_t - GetByteSize() const - { - return sizeof(magic) + - sizeof(version) + - sizeof(hash_function) + - sizeof(bucket_count) + - sizeof(hashes_count) + - sizeof(header_data_len) + - header_data_len; - } - - virtual size_t - GetByteSize (const HeaderData &header_data) = 0; - - void - SetHeaderDataByteSize (uint32_t header_data_byte_size) - { - header_data_len = header_data_byte_size; - } + virtual size_t GetByteSize(const HeaderData &header_data) = 0; - void - Dump (lldb_private::Stream &s) - { - s.Printf ("header.magic = 0x%8.8x\n", magic); - s.Printf ("header.version = 0x%4.4x\n", version); - s.Printf ("header.hash_function = 0x%4.4x\n", hash_function); - s.Printf ("header.bucket_count = 0x%8.8x %u\n", bucket_count, bucket_count); - s.Printf ("header.hashes_count = 0x%8.8x %u\n", hashes_count, hashes_count); - s.Printf ("header.header_data_len = 0x%8.8x %u\n", header_data_len, header_data_len); - } - - virtual lldb::offset_t - Read (lldb_private::DataExtractor &data, lldb::offset_t offset) - { - if (data.ValidOffsetForDataOfSize (offset, - sizeof (magic) + - sizeof (version) + - sizeof (hash_function) + - sizeof (bucket_count) + - sizeof (hashes_count) + - sizeof (header_data_len))) - { - magic = data.GetU32 (&offset); - if (magic != HASH_MAGIC) - { - if (magic == HASH_CIGAM) - { - switch (data.GetByteOrder()) - { - case lldb::eByteOrderBig: - data.SetByteOrder(lldb::eByteOrderLittle); - break; - case lldb::eByteOrderLittle: - data.SetByteOrder(lldb::eByteOrderBig); - break; - default: - return LLDB_INVALID_OFFSET; - } - } - else - { - // Magic bytes didn't match - version = 0; - return LLDB_INVALID_OFFSET; - } - } - - version = data.GetU16 (&offset); - if (version != 1) - { - // Unsupported version - return LLDB_INVALID_OFFSET; - } - hash_function = data.GetU16 (&offset); - if (hash_function == 4) - hash_function = 0; // Deal with pre-release version of this table... - bucket_count = data.GetU32 (&offset); - hashes_count = data.GetU32 (&offset); - header_data_len = data.GetU32 (&offset); - return offset; + void SetHeaderDataByteSize(uint32_t header_data_byte_size) { + header_data_len = header_data_byte_size; + } + + void Dump(lldb_private::Stream &s) { + s.Printf("header.magic = 0x%8.8x\n", magic); + s.Printf("header.version = 0x%4.4x\n", version); + s.Printf("header.hash_function = 0x%4.4x\n", hash_function); + s.Printf("header.bucket_count = 0x%8.8x %u\n", bucket_count, + bucket_count); + s.Printf("header.hashes_count = 0x%8.8x %u\n", hashes_count, + hashes_count); + s.Printf("header.header_data_len = 0x%8.8x %u\n", header_data_len, + header_data_len); + } + + virtual lldb::offset_t Read(lldb_private::DataExtractor &data, + lldb::offset_t offset) { + if (data.ValidOffsetForDataOfSize( + offset, sizeof(magic) + sizeof(version) + sizeof(hash_function) + + sizeof(bucket_count) + sizeof(hashes_count) + + sizeof(header_data_len))) { + magic = data.GetU32(&offset); + if (magic != HASH_MAGIC) { + if (magic == HASH_CIGAM) { + switch (data.GetByteOrder()) { + case lldb::eByteOrderBig: + data.SetByteOrder(lldb::eByteOrderLittle); + break; + case lldb::eByteOrderLittle: + data.SetByteOrder(lldb::eByteOrderBig); + break; + default: + return LLDB_INVALID_OFFSET; } + } else { + // Magic bytes didn't match + version = 0; return LLDB_INVALID_OFFSET; + } } -// -// // Returns a buffer that contains a serialized version of this table -// // that must be freed with free(). -// virtual void * -// Write (int fd); - }; - - template <typename __KeyType, class __HeaderDataType, class __ValueType> - class ExportTable - { - public: - typedef __HeaderDataType HeaderDataType; - typedef Header<HeaderDataType> HeaderType; - typedef __KeyType KeyType; - typedef __ValueType ValueType; - - struct Entry - { - uint32_t hash; - KeyType key; - ValueType value; - }; - - typedef std::vector<ValueType> ValueArrayType; - - typedef std::map<KeyType, ValueArrayType> HashData; - // Map a name hash to one or more name infos - typedef std::map<uint32_t, HashData> HashToHashData; - - virtual KeyType - GetKeyForStringType (const char *cstr) const = 0; - - virtual size_t - GetByteSize (const HashData &key_to_key_values) = 0; - - virtual bool - WriteHashData (const HashData &hash_data, - lldb_private::Stream &ostrm) = 0; -// - void - AddEntry (const char *cstr, const ValueType &value) - { - Entry entry; - entry.hash = MappedHash::HashString (eHashFunctionDJB, cstr); - entry.key = GetKeyForStringType (cstr); - entry.value = value; - m_entries.push_back (entry); + + version = data.GetU16(&offset); + if (version != 1) { + // Unsupported version + return LLDB_INVALID_OFFSET; } + hash_function = data.GetU16(&offset); + if (hash_function == 4) + hash_function = 0; // Deal with pre-release version of this table... + bucket_count = data.GetU32(&offset); + hashes_count = data.GetU32(&offset); + header_data_len = data.GetU32(&offset); + return offset; + } + return LLDB_INVALID_OFFSET; + } + // + // // Returns a buffer that contains a serialized version of this + // table + // // that must be freed with free(). + // virtual void * + // Write (int fd); + }; + + template <typename __KeyType, class __HeaderDataType, class __ValueType> + class ExportTable { + public: + typedef __HeaderDataType HeaderDataType; + typedef Header<HeaderDataType> HeaderType; + typedef __KeyType KeyType; + typedef __ValueType ValueType; + + struct Entry { + uint32_t hash; + KeyType key; + ValueType value; + }; - void - Save (const HeaderDataType &header_data, - lldb_private::Stream &ostrm) - { - if (m_entries.empty()) - return; - - const uint32_t num_entries = m_entries.size(); - uint32_t i = 0; - - HeaderType header; - - header.magic = HASH_MAGIC; - header.version = 1; - header.hash_function = eHashFunctionDJB; - header.bucket_count = 0; - header.hashes_count = 0; - header.prologue_length = header_data.GetByteSize(); - - // We need to figure out the number of unique hashes first before we can - // calculate the number of buckets we want to use. - typedef std::vector<uint32_t> hash_coll; - hash_coll unique_hashes; - unique_hashes.resize (num_entries); - for (i=0; i<num_entries; ++i) - unique_hashes[i] = m_entries[i].hash; - std::sort (unique_hashes.begin(), unique_hashes.end()); - hash_coll::iterator pos = std::unique (unique_hashes.begin(), unique_hashes.end()); - const size_t num_unique_hashes = std::distance (unique_hashes.begin(), pos); - - if (num_unique_hashes > 1024) - header.bucket_count = num_unique_hashes/4; - else if (num_unique_hashes > 16) - header.bucket_count = num_unique_hashes/2; - else - header.bucket_count = num_unique_hashes; - if (header.bucket_count == 0) - header.bucket_count = 1; - - std::vector<HashToHashData> hash_buckets; - std::vector<uint32_t> hash_indexes (header.bucket_count, 0); - std::vector<uint32_t> hash_values; - std::vector<uint32_t> hash_offsets; - hash_buckets.resize (header.bucket_count); - uint32_t bucket_entry_empties = 0; - //StreamString hash_file_data(Stream::eBinary, dwarf->GetObjectFile()->GetAddressByteSize(), dwarf->GetObjectFile()->GetByteSize()); - - // Push all of the hashes into their buckets and create all bucket - // entries all populated with data. - for (i=0; i<num_entries; ++i) - { - const uint32_t hash = m_entries[i].hash; - const uint32_t bucket_idx = hash % header.bucket_count; - const uint32_t strp_offset = m_entries[i].str_offset; - const uint32_t die_offset = m_entries[i].die_offset; - hash_buckets[bucket_idx][hash][strp_offset].push_back(die_offset); - } - - // Now for each bucket we write the bucket value which is the - // number of hashes and the hash index encoded into a single - // 32 bit unsigned integer. - for (i=0; i<header.bucket_count; ++i) - { - HashToHashData &bucket_entry = hash_buckets[i]; - - if (bucket_entry.empty()) - { - // Empty bucket - ++bucket_entry_empties; - hash_indexes[i] = UINT32_MAX; - } - else - { - const uint32_t hash_value_index = hash_values.size(); - uint32_t hash_count = 0; - typename HashToHashData::const_iterator pos, end = bucket_entry.end(); - for (pos = bucket_entry.begin(); pos != end; ++pos) - { - hash_values.push_back (pos->first); - hash_offsets.push_back (GetByteSize (pos->second)); - ++hash_count; - } - - hash_indexes[i] = hash_value_index; - } - } - header.hashes_count = hash_values.size(); - - // Write the header out now that we have the hash_count - header.Write (ostrm); - - // Now for each bucket we write the start index of the hashes - // for the current bucket, or UINT32_MAX if the bucket is empty - for (i=0; i<header.bucket_count; ++i) - { - ostrm.PutHex32(hash_indexes[i]); - } - - // Now we need to write out all of the hash values - for (i=0; i<header.hashes_count; ++i) - { - ostrm.PutHex32(hash_values[i]); - } + typedef std::vector<ValueType> ValueArrayType; - // Now we need to write out all of the hash data offsets, - // there is an offset for each hash in the hashes array - // that was written out above - for (i=0; i<header.hashes_count; ++i) - { - ostrm.PutHex32(hash_offsets[i]); - } + typedef std::map<KeyType, ValueArrayType> HashData; + // Map a name hash to one or more name infos + typedef std::map<uint32_t, HashData> HashToHashData; - // Now we write the data for each hash and verify we got the offset - // correct above... - for (i=0; i<header.bucket_count; ++i) - { - HashToHashData &bucket_entry = hash_buckets[i]; - - typename HashToHashData::const_iterator pos, end = bucket_entry.end(); - for (pos = bucket_entry.begin(); pos != end; ++pos) - { - if (!bucket_entry.empty()) - { - WriteHashData (pos->second); - } - } - } + virtual KeyType GetKeyForStringType(const char *cstr) const = 0; + + virtual size_t GetByteSize(const HashData &key_to_key_values) = 0; + + virtual bool WriteHashData(const HashData &hash_data, + lldb_private::Stream &ostrm) = 0; + // + void AddEntry(const char *cstr, const ValueType &value) { + Entry entry; + entry.hash = MappedHash::HashString(eHashFunctionDJB, cstr); + entry.key = GetKeyForStringType(cstr); + entry.value = value; + m_entries.push_back(entry); + } + + void Save(const HeaderDataType &header_data, lldb_private::Stream &ostrm) { + if (m_entries.empty()) + return; + + const uint32_t num_entries = m_entries.size(); + uint32_t i = 0; + + HeaderType header; + + header.magic = HASH_MAGIC; + header.version = 1; + header.hash_function = eHashFunctionDJB; + header.bucket_count = 0; + header.hashes_count = 0; + header.prologue_length = header_data.GetByteSize(); + + // We need to figure out the number of unique hashes first before we can + // calculate the number of buckets we want to use. + typedef std::vector<uint32_t> hash_coll; + hash_coll unique_hashes; + unique_hashes.resize(num_entries); + for (i = 0; i < num_entries; ++i) + unique_hashes[i] = m_entries[i].hash; + std::sort(unique_hashes.begin(), unique_hashes.end()); + hash_coll::iterator pos = + std::unique(unique_hashes.begin(), unique_hashes.end()); + const size_t num_unique_hashes = + std::distance(unique_hashes.begin(), pos); + + if (num_unique_hashes > 1024) + header.bucket_count = num_unique_hashes / 4; + else if (num_unique_hashes > 16) + header.bucket_count = num_unique_hashes / 2; + else + header.bucket_count = num_unique_hashes; + if (header.bucket_count == 0) + header.bucket_count = 1; + + std::vector<HashToHashData> hash_buckets; + std::vector<uint32_t> hash_indexes(header.bucket_count, 0); + std::vector<uint32_t> hash_values; + std::vector<uint32_t> hash_offsets; + hash_buckets.resize(header.bucket_count); + uint32_t bucket_entry_empties = 0; + // StreamString hash_file_data(Stream::eBinary, + // dwarf->GetObjectFile()->GetAddressByteSize(), + // dwarf->GetObjectFile()->GetByteSize()); + + // Push all of the hashes into their buckets and create all bucket + // entries all populated with data. + for (i = 0; i < num_entries; ++i) { + const uint32_t hash = m_entries[i].hash; + const uint32_t bucket_idx = hash % header.bucket_count; + const uint32_t strp_offset = m_entries[i].str_offset; + const uint32_t die_offset = m_entries[i].die_offset; + hash_buckets[bucket_idx][hash][strp_offset].push_back(die_offset); + } + + // Now for each bucket we write the bucket value which is the + // number of hashes and the hash index encoded into a single + // 32 bit unsigned integer. + for (i = 0; i < header.bucket_count; ++i) { + HashToHashData &bucket_entry = hash_buckets[i]; + + if (bucket_entry.empty()) { + // Empty bucket + ++bucket_entry_empties; + hash_indexes[i] = UINT32_MAX; + } else { + const uint32_t hash_value_index = hash_values.size(); + uint32_t hash_count = 0; + typename HashToHashData::const_iterator pos, end = bucket_entry.end(); + for (pos = bucket_entry.begin(); pos != end; ++pos) { + hash_values.push_back(pos->first); + hash_offsets.push_back(GetByteSize(pos->second)); + ++hash_count; + } + + hash_indexes[i] = hash_value_index; } + } + header.hashes_count = hash_values.size(); + + // Write the header out now that we have the hash_count + header.Write(ostrm); + + // Now for each bucket we write the start index of the hashes + // for the current bucket, or UINT32_MAX if the bucket is empty + for (i = 0; i < header.bucket_count; ++i) { + ostrm.PutHex32(hash_indexes[i]); + } + + // Now we need to write out all of the hash values + for (i = 0; i < header.hashes_count; ++i) { + ostrm.PutHex32(hash_values[i]); + } + + // Now we need to write out all of the hash data offsets, + // there is an offset for each hash in the hashes array + // that was written out above + for (i = 0; i < header.hashes_count; ++i) { + ostrm.PutHex32(hash_offsets[i]); + } + + // Now we write the data for each hash and verify we got the offset + // correct above... + for (i = 0; i < header.bucket_count; ++i) { + HashToHashData &bucket_entry = hash_buckets[i]; + + typename HashToHashData::const_iterator pos, end = bucket_entry.end(); + for (pos = bucket_entry.begin(); pos != end; ++pos) { + if (!bucket_entry.empty()) { + WriteHashData(pos->second); + } + } + } + } - protected: - typedef std::vector<Entry> collection; - collection m_entries; + protected: + typedef std::vector<Entry> collection; + collection m_entries; + }; + + // A class for reading and using a saved hash table from a block of data + // in memory + template <typename __KeyType, class __HeaderType, class __HashData> + class MemoryTable { + public: + typedef __HeaderType HeaderType; + typedef __KeyType KeyType; + typedef __HashData HashData; + + enum Result { + eResultKeyMatch = 0u, // The entry was found, key matched and "pair" was + // filled in successfully + eResultKeyMismatch = + 1u, // Bucket hash data collision, but key didn't match + eResultEndOfHashData = 2u, // The chain of items for this hash data in + // this bucket is terminated, search no more + eResultError = 3u // Error parsing the hash data, abort }; - // A class for reading and using a saved hash table from a block of data - // in memory - template <typename __KeyType, class __HeaderType, class __HashData> - class MemoryTable - { - public: - typedef __HeaderType HeaderType; - typedef __KeyType KeyType; - typedef __HashData HashData; - - enum Result - { - eResultKeyMatch = 0u, // The entry was found, key matched and "pair" was filled in successfully - eResultKeyMismatch = 1u, // Bucket hash data collision, but key didn't match - eResultEndOfHashData = 2u, // The chain of items for this hash data in this bucket is terminated, search no more - eResultError = 3u // Error parsing the hash data, abort - }; - - struct Pair - { - KeyType key; - HashData value; - }; - - MemoryTable (lldb_private::DataExtractor &data) : - m_header (), - m_hash_indexes (nullptr), - m_hash_values (nullptr), - m_hash_offsets (nullptr) - { - lldb::offset_t offset = m_header.Read (data, 0); - if (offset != LLDB_INVALID_OFFSET && IsValid ()) - { - m_hash_indexes = (const uint32_t *)data.GetData (&offset, m_header.bucket_count * sizeof(uint32_t)); - m_hash_values = (const uint32_t *)data.GetData (&offset, m_header.hashes_count * sizeof(uint32_t)); - m_hash_offsets = (const uint32_t *)data.GetData (&offset, m_header.hashes_count * sizeof(uint32_t)); - } - } + struct Pair { + KeyType key; + HashData value; + }; - virtual - ~MemoryTable() = default; + MemoryTable(lldb_private::DataExtractor &data) + : m_header(), m_hash_indexes(nullptr), m_hash_values(nullptr), + m_hash_offsets(nullptr) { + lldb::offset_t offset = m_header.Read(data, 0); + if (offset != LLDB_INVALID_OFFSET && IsValid()) { + m_hash_indexes = (const uint32_t *)data.GetData( + &offset, m_header.bucket_count * sizeof(uint32_t)); + m_hash_values = (const uint32_t *)data.GetData( + &offset, m_header.hashes_count * sizeof(uint32_t)); + m_hash_offsets = (const uint32_t *)data.GetData( + &offset, m_header.hashes_count * sizeof(uint32_t)); + } + } - bool - IsValid () const - { - return m_header.version == 1 && - m_header.hash_function == eHashFunctionDJB && - m_header.bucket_count > 0 && - m_header.hashes_count > 0; - } - - uint32_t - GetHashIndex (uint32_t bucket_idx) const - { - if (m_hash_indexes && bucket_idx < m_header.bucket_count) - return m_hash_indexes[bucket_idx]; - return UINT32_MAX; - } - - uint32_t - GetHashValue (uint32_t hash_idx) const - { - if (m_hash_values && hash_idx < m_header.hashes_count) - return m_hash_values[hash_idx]; - return UINT32_MAX; - } - - uint32_t - GetHashDataOffset (uint32_t hash_idx) const - { - if (m_hash_offsets && hash_idx < m_header.hashes_count) - return m_hash_offsets[hash_idx]; - return UINT32_MAX; - } - - bool - Find (const char *name, Pair &pair) const - { - if (!name || !name[0]) - return false; - - if (IsValid ()) - { - const uint32_t bucket_count = m_header.bucket_count; - const uint32_t hash_count = m_header.hashes_count; - const uint32_t hash_value = MappedHash::HashString (m_header.hash_function, name); - const uint32_t bucket_idx = hash_value % bucket_count; - uint32_t hash_idx = GetHashIndex (bucket_idx); - if (hash_idx < hash_count) - { - for (; hash_idx < hash_count; ++hash_idx) - { - const uint32_t curr_hash_value = GetHashValue (hash_idx); - if (curr_hash_value == hash_value) - { - lldb::offset_t hash_data_offset = GetHashDataOffset (hash_idx); - while (hash_data_offset != UINT32_MAX) - { - const lldb::offset_t prev_hash_data_offset = hash_data_offset; - Result hash_result = GetHashDataForName (name, &hash_data_offset, pair); - // Check the result of getting our hash data - switch (hash_result) - { - case eResultKeyMatch: - return true; - - case eResultKeyMismatch: - if (prev_hash_data_offset == hash_data_offset) - return false; - break; - - case eResultEndOfHashData: - // The last HashData for this key has been reached, stop searching - return false; - case eResultError: - // Error parsing the hash data, abort - return false; - } - } - } - if ((curr_hash_value % bucket_count) != bucket_idx) - break; - } - } - } - return false; - } + virtual ~MemoryTable() = default; - // This method must be implemented in any subclasses. - // The KeyType is user specified and must somehow result in a string - // value. For example, the KeyType might be a string offset in a string - // table and subclasses can store their string table as a member of the - // subclass and return a valie "const char *" given a "key". The value - // could also be a C string pointer, in which case just returning "key" - // will suffice. - virtual const char * - GetStringForKeyType (KeyType key) const = 0; - - virtual bool - ReadHashData (uint32_t hash_data_offset, - HashData &hash_data) const = 0; - - // This method must be implemented in any subclasses and it must try to - // read one "Pair" at the offset pointed to by the "hash_data_offset_ptr" - // parameter. This offset should be updated as bytes are consumed and - // a value "Result" enum should be returned. If the "name" matches the - // full name for the "pair.key" (which must be filled in by this call), - // then the HashData in the pair ("pair.value") should be extracted and - // filled in and "eResultKeyMatch" should be returned. If "name" doesn't - // match this string for the key, then "eResultKeyMismatch" should be - // returned and all data for the current HashData must be consumed or - // skipped and the "hash_data_offset_ptr" offset needs to be updated to - // point to the next HashData. If the end of the HashData objects for - // a given hash value have been reached, then "eResultEndOfHashData" - // should be returned. If anything else goes wrong during parsing, - // return "eResultError" and the corresponding "Find()" function will - // be canceled and return false. - virtual Result - GetHashDataForName (const char *name, - lldb::offset_t* hash_data_offset_ptr, - Pair &pair) const = 0; - - const HeaderType & - GetHeader() - { - return m_header; - } + bool IsValid() const { + return m_header.version == 1 && + m_header.hash_function == eHashFunctionDJB && + m_header.bucket_count > 0 && m_header.hashes_count > 0; + } + + uint32_t GetHashIndex(uint32_t bucket_idx) const { + if (m_hash_indexes && bucket_idx < m_header.bucket_count) + return m_hash_indexes[bucket_idx]; + return UINT32_MAX; + } + + uint32_t GetHashValue(uint32_t hash_idx) const { + if (m_hash_values && hash_idx < m_header.hashes_count) + return m_hash_values[hash_idx]; + return UINT32_MAX; + } - void - ForEach (std::function <bool(const HashData &hash_data)> const &callback) const - { - const size_t num_hash_offsets = m_header.hashes_count; - for (size_t i=0; i<num_hash_offsets; ++i) - { - uint32_t hash_data_offset = GetHashDataOffset (i); - if (hash_data_offset != UINT32_MAX) - { - HashData hash_data; - if (ReadHashData (hash_data_offset, hash_data)) - { - // If the callback returns false, then we are done and should stop - if (callback(hash_data) == false) - return; - } + uint32_t GetHashDataOffset(uint32_t hash_idx) const { + if (m_hash_offsets && hash_idx < m_header.hashes_count) + return m_hash_offsets[hash_idx]; + return UINT32_MAX; + } + + bool Find(const char *name, Pair &pair) const { + if (!name || !name[0]) + return false; + + if (IsValid()) { + const uint32_t bucket_count = m_header.bucket_count; + const uint32_t hash_count = m_header.hashes_count; + const uint32_t hash_value = + MappedHash::HashString(m_header.hash_function, name); + const uint32_t bucket_idx = hash_value % bucket_count; + uint32_t hash_idx = GetHashIndex(bucket_idx); + if (hash_idx < hash_count) { + for (; hash_idx < hash_count; ++hash_idx) { + const uint32_t curr_hash_value = GetHashValue(hash_idx); + if (curr_hash_value == hash_value) { + lldb::offset_t hash_data_offset = GetHashDataOffset(hash_idx); + while (hash_data_offset != UINT32_MAX) { + const lldb::offset_t prev_hash_data_offset = hash_data_offset; + Result hash_result = + GetHashDataForName(name, &hash_data_offset, pair); + // Check the result of getting our hash data + switch (hash_result) { + case eResultKeyMatch: + return true; + + case eResultKeyMismatch: + if (prev_hash_data_offset == hash_data_offset) + return false; + break; + + case eResultEndOfHashData: + // The last HashData for this key has been reached, stop + // searching + return false; + case eResultError: + // Error parsing the hash data, abort + return false; } + } } + if ((curr_hash_value % bucket_count) != bucket_idx) + break; + } } + } + return false; + } - protected: - // Implementation agnostic information - HeaderType m_header; - const uint32_t *m_hash_indexes; - const uint32_t *m_hash_values; - const uint32_t *m_hash_offsets; - }; + // This method must be implemented in any subclasses. + // The KeyType is user specified and must somehow result in a string + // value. For example, the KeyType might be a string offset in a string + // table and subclasses can store their string table as a member of the + // subclass and return a valie "const char *" given a "key". The value + // could also be a C string pointer, in which case just returning "key" + // will suffice. + virtual const char *GetStringForKeyType(KeyType key) const = 0; + + virtual bool ReadHashData(uint32_t hash_data_offset, + HashData &hash_data) const = 0; + + // This method must be implemented in any subclasses and it must try to + // read one "Pair" at the offset pointed to by the "hash_data_offset_ptr" + // parameter. This offset should be updated as bytes are consumed and + // a value "Result" enum should be returned. If the "name" matches the + // full name for the "pair.key" (which must be filled in by this call), + // then the HashData in the pair ("pair.value") should be extracted and + // filled in and "eResultKeyMatch" should be returned. If "name" doesn't + // match this string for the key, then "eResultKeyMismatch" should be + // returned and all data for the current HashData must be consumed or + // skipped and the "hash_data_offset_ptr" offset needs to be updated to + // point to the next HashData. If the end of the HashData objects for + // a given hash value have been reached, then "eResultEndOfHashData" + // should be returned. If anything else goes wrong during parsing, + // return "eResultError" and the corresponding "Find()" function will + // be canceled and return false. + virtual Result GetHashDataForName(const char *name, + lldb::offset_t *hash_data_offset_ptr, + Pair &pair) const = 0; + + const HeaderType &GetHeader() { return m_header; } + + void ForEach( + std::function<bool(const HashData &hash_data)> const &callback) const { + const size_t num_hash_offsets = m_header.hashes_count; + for (size_t i = 0; i < num_hash_offsets; ++i) { + uint32_t hash_data_offset = GetHashDataOffset(i); + if (hash_data_offset != UINT32_MAX) { + HashData hash_data; + if (ReadHashData(hash_data_offset, hash_data)) { + // If the callback returns false, then we are done and should stop + if (callback(hash_data) == false) + return; + } + } + } + } + + protected: + // Implementation agnostic information + HeaderType m_header; + const uint32_t *m_hash_indexes; + const uint32_t *m_hash_values; + const uint32_t *m_hash_offsets; + }; }; #endif // liblldb_MappedHash_h_ |