1ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// 2ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// MappedHash.h 3ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// 4ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 5ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#ifndef liblldb_MappedHash_h_ 6ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#define liblldb_MappedHash_h_ 7ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 8ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#include <assert.h> 9ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#include <stdint.h> 1049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 1149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton#include <map> 1249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton#include <vector> 1349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 14ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#include "lldb/Core/DataExtractor.h" 15ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton#include "lldb/Core/Stream.h" 16ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 17ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Claytonclass MappedHash 18ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton{ 19ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Claytonpublic: 20ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 21ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton enum HashFunctionType 22ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 23f09a857961404d937463e9419dc3a8d019cae5f6Daniel Dunbar eHashFunctionDJB = 0u // Daniel J Bernstein hash function that is also used by the ELF GNU_HASH sections 24ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton }; 25ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 26ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 27ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton static uint32_t 28ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton HashStringUsingDJB (const char *s) 29ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 30ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t h = 5381; 31ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 32ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton for (unsigned char c = *s; c; c = *++s) 33ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton h = ((h << 5) + h) + c; 34ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 35ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return h; 36ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 37ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 38ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton static uint32_t 3936da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton HashString (uint32_t hash_function, const char *s) 40ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 41ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton switch (hash_function) 42ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 43ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case MappedHash::eHashFunctionDJB: 44ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return HashStringUsingDJB (s); 45ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 46ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton default: 47ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton break; 48ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 49ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton assert (!"Invalid hash function index"); 50ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return 0; 51ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 52ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 53ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 54ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton static const uint32_t HASH_MAGIC = 0x48415348u; 55ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton static const uint32_t HASH_CIGAM = 0x48534148u; 56ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 57ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton template <typename T> 58ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton struct Header 59ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 60ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton typedef T HeaderData; 61ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 6249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton uint32_t magic; // HASH_MAGIC or HASH_CIGAM magic value to allow endian detection 63ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint16_t version; // Version number 64bbe39167c881ac025cdc4f383ee8895cfd5b1148Greg Clayton uint16_t hash_function; // The hash function enumeration that was used 65ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t bucket_count; // The number of buckets in this hash table 66ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t hashes_count; // The total number of unique hash values and hash data offsets in this table 67ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t header_data_len; // The size in bytes of the "header_data" template member below 68ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton HeaderData header_data; // 69ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 70ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton Header () : 7149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton magic (HASH_MAGIC), 72ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton version (1), 73ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton hash_function (eHashFunctionDJB), 74ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton bucket_count (0), 75ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton hashes_count (0), 76ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton header_data_len (sizeof(T)), 77ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton header_data () 78ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 79ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 80ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 81ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton virtual 82ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton ~Header() 83ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 84ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 85ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 86ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton size_t 87ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetByteSize() const 88ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 89ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return sizeof(magic) + 90ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton sizeof(version) + 91ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton sizeof(hash_function) + 92ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton sizeof(bucket_count) + 93ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton sizeof(hashes_count) + 94ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton sizeof(header_data_len) + 95ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton header_data_len; 96ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 97ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 98ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton virtual size_t 99ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetByteSize (const HeaderData &header_data) = 0; 100ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 101ce04560e6affff2342d931cab4e904605119c742Greg Clayton void 102ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton SetHeaderDataByteSize (uint32_t header_data_byte_size) 103ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 104ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton header_data_len = header_data_byte_size; 105ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 106ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 107ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton void 108ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton Dump (lldb_private::Stream &s) 109ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 110ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton s.Printf ("header.magic = 0x%8.8x\n", magic); 111ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton s.Printf ("header.version = 0x%4.4x\n", version); 112bbe39167c881ac025cdc4f383ee8895cfd5b1148Greg Clayton s.Printf ("header.hash_function = 0x%4.4x\n", hash_function); 113ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton s.Printf ("header.bucket_count = 0x%8.8x %u\n", bucket_count, bucket_count); 114ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton s.Printf ("header.hashes_count = 0x%8.8x %u\n", hashes_count, hashes_count); 115ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton s.Printf ("header.header_data_len = 0x%8.8x %u\n", header_data_len, header_data_len); 116ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 117ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 11836da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton virtual lldb::offset_t 11936da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton Read (lldb_private::DataExtractor &data, lldb::offset_t offset) 120ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 121ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (data.ValidOffsetForDataOfSize (offset, 12249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (magic) + 12349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (version) + 12449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (hash_function) + 12549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (bucket_count) + 12649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (hashes_count) + 12749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton sizeof (header_data_len))) 128ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 129ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton magic = data.GetU32 (&offset); 130ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (magic != HASH_MAGIC) 131ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 132ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (magic == HASH_CIGAM) 133ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 134ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton switch (data.GetByteOrder()) 135ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 136ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case lldb::eByteOrderBig: 137ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton data.SetByteOrder(lldb::eByteOrderLittle); 138ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton break; 139ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case lldb::eByteOrderLittle: 140ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton data.SetByteOrder(lldb::eByteOrderBig); 141ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton break; 142ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton default: 14336da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton return LLDB_INVALID_OFFSET; 144ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 145ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 146ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton else 147ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 148ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // Magic bytes didn't match 149ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton version = 0; 15036da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton return LLDB_INVALID_OFFSET; 151ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 152ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 153ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 154ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton version = data.GetU16 (&offset); 155ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (version != 1) 156ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 157ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // Unsupported version 15836da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton return LLDB_INVALID_OFFSET; 159ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 160bbe39167c881ac025cdc4f383ee8895cfd5b1148Greg Clayton hash_function = data.GetU16 (&offset); 161bbe39167c881ac025cdc4f383ee8895cfd5b1148Greg Clayton if (hash_function == 4) 162bbe39167c881ac025cdc4f383ee8895cfd5b1148Greg Clayton hash_function = 0; // Deal with pre-release version of this table... 163ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton bucket_count = data.GetU32 (&offset); 164ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton hashes_count = data.GetU32 (&offset); 165ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton header_data_len = data.GetU32 (&offset); 166ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return offset; 167ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 16836da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton return LLDB_INVALID_OFFSET; 169ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 170ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// 171ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// // Returns a buffer that contains a serialized version of this table 172ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// // that must be freed with free(). 173ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// virtual void * 174ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton// Write (int fd); 175ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton }; 176ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 17749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton template <typename __KeyType, class __HeaderDataType, class __ValueType> 17849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton class ExportTable 17949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 18049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton public: 18149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef __HeaderDataType HeaderDataType; 18249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef Header<HeaderDataType> HeaderType; 18349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef __KeyType KeyType; 18449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef __ValueType ValueType; 18549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 18649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton struct Entry 18749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 18849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton uint32_t hash; 18949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton KeyType key; 19049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ValueType value; 19149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton }; 19249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 19349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef std::vector<ValueType> ValueArrayType; 19449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 19549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef std::map<KeyType, ValueArrayType> HashData; 19649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Map a name hash to one or more name infos 19749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef std::map<uint32_t, HashData> HashToHashData; 19849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 19949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton virtual KeyType 20049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton GetKeyForStringType (const char *cstr) const = 0; 20149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 20249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton virtual size_t 20349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton GetByteSize (const HashData &key_to_key_values) = 0; 20449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 20549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton virtual bool 20649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton WriteHashData (const HashData &hash_data, 20749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton lldb_private::Stream &ostrm) = 0; 20849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton// 20949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton void 21049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton AddEntry (const char *cstr, const ValueType &value) 21149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 21249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton Entry entry; 21349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton entry.hash = MappedHash::HashString (eHashFunctionDJB, cstr); 21449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton entry.key = GetKeyForStringType (cstr); 21549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton entry.value = value; 21649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton m_entries.push_back (entry); 21749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 21849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 21949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton void 22049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton Save (const HeaderDataType &header_data, 22149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton lldb_private::Stream &ostrm) 22249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 22349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton if (m_entries.empty()) 22449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton return; 22549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 22649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const uint32_t num_entries = m_entries.size(); 22749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton uint32_t i = 0; 22849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 22949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton HeaderType header; 23049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 23149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.magic = HASH_MAGIC; 23249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.version = 1; 23349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.hash_function = eHashFunctionDJB; 23449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.bucket_count = 0; 23549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.hashes_count = 0; 23649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.prologue_length = header_data.GetByteSize(); 23749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 23849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // We need to figure out the number of unique hashes first before we can 23949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // calculate the number of buckets we want to use. 24049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef std::vector<uint32_t> hash_coll; 24149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_coll unique_hashes; 24249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton unique_hashes.resize (num_entries); 24349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<num_entries; ++i) 24449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton unique_hashes[i] = m_entries[i].hash; 24549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton std::sort (unique_hashes.begin(), unique_hashes.end()); 24649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_coll::iterator pos = std::unique (unique_hashes.begin(), unique_hashes.end()); 24749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const size_t num_unique_hashes = std::distance (unique_hashes.begin(), pos); 24849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 24949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton if (num_unique_hashes > 1024) 25049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.bucket_count = num_unique_hashes/4; 25149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton else if (num_unique_hashes > 16) 25249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.bucket_count = num_unique_hashes/2; 25349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton else 25449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.bucket_count = num_unique_hashes; 25549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton if (header.bucket_count == 0) 25649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.bucket_count = 1; 25749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 25849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 25949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton std::vector<HashToHashData> hash_buckets; 26049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton std::vector<uint32_t> hash_indexes (header.bucket_count, 0); 26149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton std::vector<uint32_t> hash_values; 26249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton std::vector<uint32_t> hash_offsets; 26349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_buckets.resize (header.bucket_count); 26449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton uint32_t bucket_entry_empties = 0; 26549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton //StreamString hash_file_data(Stream::eBinary, dwarf->GetObjectFile()->GetAddressByteSize(), dwarf->GetObjectFile()->GetByteSize()); 26649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 26749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Push all of the hashes into their buckets and create all bucket 26849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // entries all populated with data. 26949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<num_entries; ++i) 27049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 27149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const uint32_t hash = m_entries[i].hash; 27249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const uint32_t bucket_idx = hash % header.bucket_count; 27349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const uint32_t strp_offset = m_entries[i].str_offset; 274ce490e3161b17c3f2904d6e797bb5e5517d651c2Greg Clayton const uint32_t die_offset = m_entries[i].die_offset; 27549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_buckets[bucket_idx][hash][strp_offset].push_back(die_offset); 27649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 27749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 27849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Now for each bucket we write the bucket value which is the 27949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // number of hashes and the hash index encoded into a single 28049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // 32 bit unsigned integer. 28149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<header.bucket_count; ++i) 28249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 28349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton HashToHashData &bucket_entry = hash_buckets[i]; 28449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 28549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton if (bucket_entry.empty()) 28649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 28749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Empty bucket 28849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ++bucket_entry_empties; 28949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_indexes[i] = UINT32_MAX; 29049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 29149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton else 29249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 29349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton const uint32_t hash_value_index = hash_values.size(); 29449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton uint32_t hash_count = 0; 29549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typename HashToHashData::const_iterator pos, end = bucket_entry.end(); 29649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (pos = bucket_entry.begin(); pos != end; ++pos) 29749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 29849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_values.push_back (pos->first); 29949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_offsets.push_back (GetByteSize (pos->second)); 30049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ++hash_count; 30149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 30249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 30349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton hash_indexes[i] = hash_value_index; 30449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 30549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 30649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.hashes_count = hash_values.size(); 30749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 30849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Write the header out now that we have the hash_count 30949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton header.Write (ostrm); 31049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 31149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Now for each bucket we write the start index of the hashes 31249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // for the current bucket, or UINT32_MAX if the bucket is empty 31349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<header.bucket_count; ++i) 31449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 31549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ostrm.PutHex32(hash_indexes[i]); 31649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 31749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 31849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Now we need to write out all of the hash values 31949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<header.hashes_count; ++i) 32049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 32149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ostrm.PutHex32(hash_values[i]); 32249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 32349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 32449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Now we need to write out all of the hash data offsets, 32549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // there is an offset for each hash in the hashes array 32649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // that was written out above 32749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<header.hashes_count; ++i) 32849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 32949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton ostrm.PutHex32(hash_offsets[i]); 33049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 33149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 33249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // Now we write the data for each hash and verify we got the offset 33349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton // correct above... 33449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (i=0; i<header.bucket_count; ++i) 33549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 33649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton HashToHashData &bucket_entry = hash_buckets[i]; 33749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton 33849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typename HashToHashData::const_iterator pos, end = bucket_entry.end(); 33949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton for (pos = bucket_entry.begin(); pos != end; ++pos) 34049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 34149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton if (!bucket_entry.empty()) 34249e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton { 34349e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton WriteHashData (pos->second); 34449e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 34549e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 34649e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 34749e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton } 34849e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton protected: 34949e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton typedef std::vector<Entry> collection; 35049e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton collection m_entries; 35149e08e3b6ffa42a0148bad845c34da2c4fe603deGreg Clayton }; 352ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // A class for reading and using a saved hash table from a block of data 353ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // in memory 354ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton template <typename __KeyType, class __HeaderType, class __HashData> 355ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton class MemoryTable 356ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 357ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton public: 358ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton typedef __HeaderType HeaderType; 359ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton typedef __KeyType KeyType; 360ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton typedef __HashData HashData; 361ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 362ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton enum Result 363ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 364ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton eResultKeyMatch = 0u, // The entry was found, key matched and "pair" was filled in successfully 365ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton eResultKeyMismatch = 1u, // Bucket hash data collision, but key didn't match 366ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton eResultEndOfHashData = 2u, // The chain of items for this hash data in this bucket is terminated, search no more 367ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton eResultError = 3u // Error parsing the hash data, abort 368ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton }; 369ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 370ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton struct Pair 371ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 372ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton KeyType key; 373ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton HashData value; 374ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton }; 375ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 376ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton MemoryTable (lldb_private::DataExtractor &data) : 377ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_header (), 378ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_indexes (NULL), 379ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_values (NULL), 380ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_offsets (NULL) 381ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 38236da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton lldb::offset_t offset = m_header.Read (data, 0); 38336da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton if (offset != LLDB_INVALID_OFFSET && IsValid ()) 384ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 385ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_indexes = (uint32_t *)data.GetData (&offset, m_header.bucket_count * sizeof(uint32_t)); 386ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_values = (uint32_t *)data.GetData (&offset, m_header.hashes_count * sizeof(uint32_t)); 387ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton m_hash_offsets = (uint32_t *)data.GetData (&offset, m_header.hashes_count * sizeof(uint32_t)); 388ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 389ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 390ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 391ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton virtual 392ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton ~MemoryTable () 393ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 394ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 395ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 396ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton bool 397ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton IsValid () const 398ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 39922a3afd927a97026bd22b6023162439c59e6166dGreg Clayton return m_header.version == 1 && 40022a3afd927a97026bd22b6023162439c59e6166dGreg Clayton m_header.hash_function == eHashFunctionDJB && 40122a3afd927a97026bd22b6023162439c59e6166dGreg Clayton m_header.bucket_count > 0 && 40222a3afd927a97026bd22b6023162439c59e6166dGreg Clayton m_header.hashes_count > 0; 403ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 404ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 405ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t 406ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetHashIndex (uint32_t bucket_idx) const 407ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 408ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (m_hash_indexes && bucket_idx < m_header.bucket_count) 409ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return m_hash_indexes[bucket_idx]; 410ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return UINT32_MAX; 411ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 412ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 413ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t 414ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetHashValue (uint32_t hash_idx) const 415ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 416ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (m_hash_values && hash_idx < m_header.hashes_count) 417ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return m_hash_values[hash_idx]; 418ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return UINT32_MAX; 419ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 420ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 421ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t 422ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetHashDataOffset (uint32_t hash_idx) const 423ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 424ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (m_hash_offsets && hash_idx < m_header.hashes_count) 425ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return m_hash_offsets[hash_idx]; 426ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return UINT32_MAX; 427ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 428ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 429ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton bool 430ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton Find (const char *name, Pair &pair) const 431ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 432ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (IsValid ()) 433ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 434ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton const uint32_t bucket_count = m_header.bucket_count; 435ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton const uint32_t hash_count = m_header.hashes_count; 436ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton const uint32_t hash_value = MappedHash::HashString (m_header.hash_function, name); 437ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton const uint32_t bucket_idx = hash_value % bucket_count; 438ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t hash_idx = GetHashIndex (bucket_idx); 439ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (hash_idx < hash_count) 440ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 441ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton for (; hash_idx < hash_count; ++hash_idx) 442ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 443ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton const uint32_t curr_hash_value = GetHashValue (hash_idx); 444ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (curr_hash_value == hash_value) 445ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 44636da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton lldb::offset_t hash_data_offset = GetHashDataOffset (hash_idx); 447ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton while (hash_data_offset != UINT32_MAX) 448ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 44936da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton const lldb::offset_t prev_hash_data_offset = hash_data_offset; 450ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton Result hash_result = GetHashDataForName (name, &hash_data_offset, pair); 451ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // Check the result of getting our hash data 452ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton switch (hash_result) 453ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton { 454ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case eResultKeyMatch: 455ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return true; 456ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 457ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case eResultKeyMismatch: 458ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if (prev_hash_data_offset == hash_data_offset) 459ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return false; 460ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton break; 461ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 462ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case eResultEndOfHashData: 463ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // The last HashData for this key has been reached, stop searching 464ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return false; 465ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton case eResultError: 466ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // Error parsing the hash data, abort 467ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return false; 468ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 469ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 470ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 471ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton if ((curr_hash_value % bucket_count) != bucket_idx) 472ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton break; 473ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 474ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 475ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 476ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton return false; 477ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton } 478ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 479ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // This method must be implemented in any subclasses. 480ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // The KeyType is user specified and must somehow result in a string 481ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // value. For example, the KeyType might be a string offset in a string 482ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // table and subclasses can store their string table as a member of the 483ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // subclass and return a valie "const char *" given a "key". The value 484ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // could also be a C string pointer, in which case just returning "key" 485ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // will suffice. 486ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 487ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton virtual const char * 488ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetStringForKeyType (KeyType key) const = 0; 489a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton 490a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton virtual bool 491a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton ReadHashData (uint32_t hash_data_offset, 492a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton HashData &hash_data) const = 0; 493ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 494ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // This method must be implemented in any subclasses and it must try to 495ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // read one "Pair" at the offset pointed to by the "hash_data_offset_ptr" 496ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // parameter. This offset should be updated as bytes are consumed and 497ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // a value "Result" enum should be returned. If the "name" matches the 498ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // full name for the "pair.key" (which must be filled in by this call), 499ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // then the HashData in the pair ("pair.value") should be extracted and 500ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // filled in and "eResultKeyMatch" should be returned. If "name" doesn't 501ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // match this string for the key, then "eResultKeyMismatch" should be 502ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // returned and all data for the current HashData must be consumed or 503ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // skipped and the "hash_data_offset_ptr" offset needs to be updated to 504ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // point to the next HashData. If the end of the HashData objects for 505ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // a given hash value have been reached, then "eResultEndOfHashData" 506ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // should be returned. If anything else goes wrong during parsing, 507ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // return "eResultError" and the corresponding "Find()" function will 508ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // be canceled and return false. 509ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 510ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton virtual Result 511ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton GetHashDataForName (const char *name, 51236da2aa6dc5ad9994b638ed09eb81c44cc05540bGreg Clayton lldb::offset_t* hash_data_offset_ptr, 513ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton Pair &pair) const = 0; 514ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 51537bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton const HeaderType & 51637bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton GetHeader() 51737bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton { 51837bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton return m_header; 51937bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton } 52037bb8ddd443da172f42bb8657f15ec856a525c84Greg Clayton 521a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton 522a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton void 523a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton ForEach (std::function <bool(const HashData &hash_data)> const &callback) const 524a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton { 525a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton const size_t num_hash_offsets = m_header.hashes_count; 526a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton for (size_t i=0; i<num_hash_offsets; ++i) 527a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton { 528a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton uint32_t hash_data_offset = GetHashDataOffset (i); 529a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton if (hash_data_offset != UINT32_MAX) 530a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton { 531a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton HashData hash_data; 532a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton if (ReadHashData (hash_data_offset, hash_data)) 533a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton { 534a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton // If the callback returns false, then we are done and should stop 535a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton if (callback(hash_data) == false) 536a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton return; 537a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton } 538a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton } 539a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton } 540a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton } 541a8b56238ce138e70433a0ce0b4218c9257beae38Greg Clayton 542ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton protected: 543ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton // Implementation agnostic information 544ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton HeaderType m_header; 545ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t *m_hash_indexes; 546ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t *m_hash_values; 547ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton uint32_t *m_hash_offsets; 548ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton }; 549ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 550ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton}; 551ff9a7e065cb72e24dc3629725ae7d1100b29acd4Greg Clayton 552141f8d98cb74262914d66a7af4732e8cb2d8699fGreg Clayton#endif // #ifndef liblldb_MappedHash_h_ 553