1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4//*****************************************************************************
5// MetaDataHash.h -- Meta data hash data structures.
6//
7
8//
9// Used by Emitters and by E&C.
10//
11//*****************************************************************************
12#ifndef _MetaDataHash_h_
13#define _MetaDataHash_h_
14
15#if _MSC_VER >= 1100
16 # pragma once
17#endif
18
19#include "utilcode.h"
20
21
22#define REHASH_THREADSHOLD 3
23
24
25//*****************************************************************************
26// A hash entry list item.
27//*****************************************************************************
28struct TOKENHASHENTRY
29{
30 mdToken tok;
31 ULONG ulHash;
32 ULONG iNext;
33};
34
35//*****************************************************************************
36// The following is a hash class definition used for hashing MemberDef. The difference
37// from the hash table above is because it is expansive to retrieve the parent for MemberDef.
38//
39//*****************************************************************************
40struct MEMBERDEFHASHENTRY
41{
42 mdToken tok;
43 mdToken tkParent;
44 ULONG ulHash;
45 ULONG iNext;
46};
47
48
49//*****************************************************************************
50// This class is used to create transient indexes for meta data structures.
51// This class is generic; one must override it to provide hashing and
52// accessor methods for your specific record type. It can start out on top
53// of malloc with a small memory footprint, and as you get larger, it must
54// be capable of rehashing.
55//*****************************************************************************
56template <class Entry> class CMetaDataHashTemplate
57{
58public:
59 CMetaDataHashTemplate()
60 {
61 m_rgBuckets = 0;
62 m_cItems = 0;
63 m_iBuckets = 0;
64 }
65
66 ~CMetaDataHashTemplate()
67 {
68 // Free the bucket list.
69 if (m_rgBuckets)
70 {
71 delete [] m_rgBuckets;
72 m_rgBuckets = 0;
73 m_cItems = 0;
74 m_iBuckets = 0;
75 }
76 }
77
78//*****************************************************************************
79// Called to allocate the hash table entries so that new data may be added.
80//*****************************************************************************
81 HRESULT NewInit( // Return status.
82 int iBuckets=17) // How many buckets you want.
83 {
84 m_rgBuckets = new (nothrow) int[iBuckets];
85 if (!m_rgBuckets)
86 return (OutOfMemory());
87 m_iBuckets = iBuckets;
88 memset(m_rgBuckets, ~0, sizeof(int) * iBuckets);
89 return (S_OK);
90 }
91
92//*****************************************************************************
93// Add new items to the hash list.
94//*****************************************************************************
95 Entry *Add( // Pointer to element to write to.
96 ULONG iHash) // Hash value of entry to add.
97 {
98 Entry *p = 0;
99 HRESULT hr;
100
101 int iBucket = iHash % m_iBuckets;
102
103 if (m_cItems > REHASH_THREADSHOLD * m_iBuckets)
104 {
105 hr = ReHash();
106 if (FAILED(hr))
107 return (0);
108 iBucket = iHash % m_iBuckets;
109 }
110
111 // Add a new item pointer.
112 p = m_Heap.Append();
113 if (!p)
114 return (0);
115
116 // Chain the new item to the front of the heap.
117 p->iNext = m_rgBuckets[iBucket];
118 p->ulHash = iHash;
119 m_cItems++;
120 m_rgBuckets[iBucket] = m_Heap.ItemIndex(p);
121 return (p);
122 }
123
124
125//*****************************************************************************
126// Grow the hash table
127//*****************************************************************************
128 HRESULT ReHash()
129 {
130 int *rgBuckets;
131 int iBuckets;
132 int iBucket;
133 int index;
134 int iCount;
135 Entry *p = 0;
136
137 iBuckets = m_iBuckets*2 -1;
138 rgBuckets = new (nothrow) int[iBuckets];
139 if (!rgBuckets)
140 return (OutOfMemory());
141 memset(rgBuckets, ~0, sizeof(int) * iBuckets);
142
143 // loop through each of data and rehash them
144 iCount = m_Heap.Count();
145 for (index = 0; index < iCount; index++)
146 {
147 // get the hash value of the entry
148 p = m_Heap.Get(index);
149
150 // rehash the entry
151 iBucket = p->ulHash % iBuckets;
152
153 // Chain the item to the front of the new heap.
154 p->iNext = rgBuckets[iBucket];
155 rgBuckets[iBucket] = index;
156 }
157
158 // swap the hash table
159 delete [] m_rgBuckets;
160 m_rgBuckets = rgBuckets;
161 m_iBuckets = iBuckets;
162 return NOERROR;
163
164 }
165
166//*****************************************************************************
167// Find first/find next node for a chain given the hash.
168//*****************************************************************************
169 Entry *FindFirst( // Return entry.
170 ULONG iHash, // The hash value for the entry.
171 int &POS) // Current position.
172 {
173 int iBucket = iHash % m_iBuckets;
174 POS = m_rgBuckets[iBucket];
175 return (FindNext(POS));
176 }
177
178 Entry *FindNext( // Return entry or 0.
179 int &POS) // Current location.
180 {
181 Entry *p;
182
183 if (POS == ~0)
184 return (0);
185
186 p = m_Heap.Get(POS);
187 POS = p->iNext;
188 return (p);
189 }
190
191private:
192 CDynArray<Entry> m_Heap; // First heap in the list.
193 int *m_rgBuckets; // Bucket list.
194 int m_iBuckets; // How many buckets.
195 int m_cItems; // Number of items in the hash
196};
197
198
199class CMetaDataHashBase : public CMetaDataHashTemplate<TOKENHASHENTRY>
200{
201};
202
203class CMemberDefHash : public CMetaDataHashTemplate<MEMBERDEFHASHENTRY>
204{
205};
206
207#endif // _MetaDataHash_h_
208