1 //===-- HashedNameToDIE.cpp -------------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "HashedNameToDIE.h"
11 #include "lldb/Core/ConstString.h"
12 #include "lldb/Core/DataExtractor.h"
13 #include "lldb/Core/Stream.h"
14 #include "lldb/Core/StreamString.h"
15 #include "lldb/Core/RegularExpression.h"
16 #include "lldb/Symbol/ObjectFile.h"
17 
18 #include "DWARFCompileUnit.h"
19 #include "DWARFDebugInfo.h"
20 #include "DWARFDebugInfoEntry.h"
21 #include "SymbolFileDWARF.h"
22 using namespace lldb;
23 using namespace lldb_private;
24 
25 static uint32_t
26 dl_new_hash (const char *s)
27 {
28     uint32_t h = 5381;
29 
30     for (unsigned char c = *s; c; c = *++s)
31         h = ((h << 5) + h) + c;
32 
33     return h;
34 }
35 
36 HashedNameToDIE::HashedNameToDIE (SymbolFileDWARF *dwarf, const DataExtractor &data) :
37     m_dwarf (dwarf),
38     m_data (data),
39     m_header  ()
40 {
41 }
42 
43 void
44 HashedNameToDIE::Initialize()
45 {
46     uint32_t offset = 0;
47     m_header.version = m_data.GetU16(&offset);
48     if (m_header.version)
49     {
50         m_header.hash_type = m_data.GetU8(&offset);
51         m_header.hash_index_bitsize = m_data.GetU8(&offset);
52         m_header.num_buckets = m_data.GetU32(&offset);
53         m_header.num_hashes = m_data.GetU32(&offset);
54         m_header.die_offset_base = m_data.GetU32(&offset);
55     }
56 }
57 
58 size_t
59 HashedNameToDIE::Find (const ConstString &name, DIEArray &die_ofsets) const
60 {
61     const size_t initial_size = die_ofsets.size();
62     const char *name_cstr = name.GetCString();
63     if (name_cstr && name_cstr[0])
64     {
65         // Hash the C string
66         const uint32_t name_hash = dl_new_hash (name_cstr);
67 
68         // Find the correct bucket for the using the hash value
69         const uint32_t bucket_idx = name_hash % m_header.num_buckets;
70 
71         // Calculate the offset for the bucket entry for the bucket index
72         uint32_t offset = GetOffsetOfBucketEntry (bucket_idx);
73 
74         // Extract the bucket entry.
75         const uint32_t bucket_entry = m_data.GetU32 (&offset);
76         if (bucket_entry)
77         {
78             // The bucket entry is non-zero which means it isn't empty.
79             // The bucket entry is made up of a hash index whose bit width
80             // is m_header.hash_index_bitsize, and a hash count whose value
81             // is the remaining bits in the 32 bit value. Below we extract
82             // the hash index and the hash count
83             const uint32_t hash_idx = bucket_entry & GetHashIndexMask();
84             const uint32_t hash_count = bucket_entry >> m_header.hash_index_bitsize;
85             const uint32_t hash_end_idx = hash_idx + hash_count;
86             // Figure out the offset to the hash value by index
87             uint32_t hash_offset = GetOffsetOfHashValue (hash_idx);
88             for (uint32_t idx = hash_idx; idx < hash_end_idx; ++idx)
89             {
90                 // Extract the hash value and see if it matches our string
91                 const uint32_t hash = m_data.GetU32 (&hash_offset);
92                 if (hash == name_hash)
93                 {
94                     // The hash matches, but we still need to verify that the
95                     // C string matches in case we have a hash collision. Figure
96                     // out the offset for the data associated with this hash entry
97                     offset = GetOffsetOfHashDataOffset (idx);
98                     // Extract the first 32 bit value which is the .debug_str offset
99                     // of the string we need
100                     uint32_t hash_data_offset = m_data.GetU32 (&offset);
101                     const uint32_t str_offset = m_data.GetU32 (&hash_data_offset);
102                     // Extract the C string and comapare it
103                     const char *cstr_name = m_dwarf->get_debug_str_data().PeekCStr(str_offset);
104                     if (cstr_name)
105                     {
106                         if (strcmp(name_cstr, cstr_name) == 0)
107                         {
108                             // We have a match, now extract the DIE count
109                             const uint32_t die_count = m_data.GetU32 (&hash_data_offset);
110                             // Now extract "die_count" DIE offsets and put them into the
111                             // results
112                             for (uint32_t die_idx = 0; die_idx < die_count; ++die_idx)
113                                 die_ofsets.push_back(m_data.GetU32 (&hash_data_offset));
114                         }
115                     }
116                 }
117             }
118         }
119     }
120     return die_ofsets.size() - initial_size;
121 }
122 
123 size_t
124 HashedNameToDIE::Find (const RegularExpression& regex, DIEArray &die_ofsets) const
125 {
126 //    const size_t initial_info_array_size = info_array.size();
127 //    collection::const_iterator pos, end = m_collection.end();
128 //    for (pos = m_collection.begin(); pos != end; ++pos)
129 //    {
130 //        if (regex.Execute(pos->first))
131 //            info_array.push_back (pos->second);
132 //    }
133 //    return info_array.size() - initial_info_array_size;
134     return 0;
135 }
136 
137 void
138 HashedNameToDIE::Dump (Stream *s)
139 {
140 //    collection::const_iterator pos, end = m_collection.end();
141 //    for (pos = m_collection.begin(); pos != end; ++pos)
142 //    {
143 //        s->Printf("%p: 0x%8.8x 0x%8.8x \"%s\"\n", pos->first, pos->second.cu_idx, pos->second.die_idx, pos->first);
144 //    }
145 }
146 
147 
148