Merge remote-tracking branch 'redux/master' into sh4-pool
[tamarin-stm.git] / core / MultinameHashtable-impl.h
blob276084f4ce6ade70ba6f8a60c2c08cf819eb7d1e
1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
3 /* ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
16 * The Original Code is [Open Source Virtual Machine.].
18 * The Initial Developer of the Original Code is
19 * Adobe System Incorporated.
20 * Portions created by the Initial Developer are Copyright (C) 2004-2006
21 * the Initial Developer. All Rights Reserved.
23 * Contributor(s):
24 * Adobe AS3 Team
26 * Alternatively, the contents of this file may be used under the terms of
27 * either the GNU General Public License Version 2 or later (the "GPL"), or
28 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
38 * ***** END LICENSE BLOCK ***** */
40 #ifndef __avmplus_MultinameHashtable_impl__
41 #define __avmplus_MultinameHashtable_impl__
43 using namespace MMgc;
45 namespace avmplus
47 template <class VALUE_TYPE, class VALUE_WRITER>
48 bool MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::gcTrace(MMgc::GC *gc, size_t cursor)
50 (void)cursor;
51 gc->TraceLocation(&m_quads);
52 return false;
55 template <class VALUE_TYPE, class VALUE_WRITER>
56 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::grow()
58 // double our table
59 int capacity = numQuads*2;
60 MMgc::GC* gc = MMgc::GC::GetGC(this);
61 MMGC_MEM_TYPE(this);
62 QuadContainer<VALUE_TYPE>* newAtoms = QuadContainer<VALUE_TYPE>::create(gc, capacity);
63 rehash(m_quads->quads, numQuads, newAtoms->quads, capacity);
64 freeQuads(gc);
65 WB(gc, this, &m_quads, newAtoms);
66 numQuads = capacity;
69 template <class VALUE_TYPE, class VALUE_WRITER>
70 VALUE_TYPE MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::getMulti(const Multiname* mname) const
72 // multiname must not be an attr name, have wildcards, or have runtime parts.
73 AvmAssert(mname->isBinding() && !mname->isAnyName());
75 if (!mname->isNsset())
76 return get(mname->getName(), mname->getNamespace());
77 else
78 return get(mname->getName(), mname->getNsset());
81 // return the NS that unambigously matches in "match" (or null for none/ambiguous)
82 template <class VALUE_TYPE, class VALUE_WRITER>
83 VALUE_TYPE MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::getMulti(const Multiname& mname, Namespacep& match) const
85 // multiname must not be an attr name, have wildcards, or have runtime parts.
86 AvmAssert(mname.isBinding() && !mname.isAnyName());
88 if (!mname.isNsset())
90 VALUE_TYPE b = get(mname.getName(), mname.getNamespace());
91 match = (b != NULL) ? mname.getNamespace() : NULL;
92 return b;
94 else
96 const Quad<VALUE_TYPE>* q = getNSSet(mname.getName(), mname.getNsset());
97 match = q->ns;
98 return q->value;
102 template <class VALUE_TYPE, class VALUE_WRITER>
103 MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::MultinameHashtable(int capacity) :
104 m_quads(NULL),
105 size(0),
106 numQuads(0)
108 // We really want alignment and size of the Quad to be tightly controlled.
109 MMGC_STATIC_ASSERT(sizeof(Quad<VALUE_TYPE>) == 4*sizeof(uintptr_t));
111 // Code near the end of MultinameHashtable::put assumes that API will fit into 31 bits
112 MMGC_STATIC_ASSERT(kApiVersion_count <= 0x7fffffff);
114 Init(capacity);
117 template <class VALUE_TYPE, class VALUE_WRITER>
118 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::Init(int capacity)
120 if (capacity)
122 numQuads = MathUtils::nextPowerOfTwo(capacity);
124 MMgc::GC* gc = MMgc::GC::GetGC(this);
126 AvmAssert(numQuads > 0);
127 MMGC_MEM_TYPE(this);
128 QuadContainer<VALUE_TYPE>* newAtoms = QuadContainer<VALUE_TYPE>::create(gc, numQuads);
129 WB(gc, this, &m_quads, newAtoms);
133 template <class VALUE_TYPE, class VALUE_WRITER>
134 MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::~MultinameHashtable()
136 freeQuads(GC::GetGC(this));
139 template <class VALUE_TYPE, class VALUE_WRITER>
140 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::freeQuads(MMgc::GC* gc)
142 QuadContainer<VALUE_TYPE>* quads = m_quads;
143 m_quads = NULL; // Avoid dangling m_quad
144 gc->Free(quads);
147 template <class VALUE_TYPE, class VALUE_WRITER>
148 bool MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::isFull() const
150 // 0.80 load factor
151 return 5*(size+1) >= numQuads*4;
154 template <class VALUE_TYPE, class VALUE_WRITER>
155 int MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::find(Stringp name, Namespacep ns, const Quad<VALUE_TYPE>* t, unsigned m)
157 AvmAssert(ns->getURI()->isInterned());
158 AvmAssert(name != NULL && ns != NULL);
159 AvmAssert(name->isInterned());
161 // this is a quadratic probe but we only hit every third slot since those hold keys.
162 int n = 7;
164 int bitmask = (m - 1);
166 // Note: Mask off MSB to avoid negative indices. Mask off bottom
167 // 3 bits because it doesn't contribute to hash. Quad it
168 // because names, namespaces, and values are stored adjacently.
169 unsigned i = ((0x7FFFFFF8 & (uintptr_t)name) >> 3) & bitmask;
171 Stringp k;
172 while (((k=t[i].name) != name || !t[i].matchNS(ns)) && k != NULL)
174 i = (i + (n++)) & bitmask; // quadratic probe
176 return i;
179 template <class VALUE_TYPE>
180 REALLY_INLINE QuadContainer<VALUE_TYPE>* QuadContainer<VALUE_TYPE>::create(MMgc::GC* gc, uint32_t capacity)
182 return new (gc, MMgc::kExact, sizeof(Quad<VALUE_TYPE>) * (capacity-1)) QuadContainer(capacity);
185 template <class VALUE_TYPE>
186 bool QuadContainer<VALUE_TYPE>::gcTrace(MMgc::GC* gc, size_t cursor)
188 (void)cursor;
189 for ( uint32_t i=0 ; i < capacity ; i++ ) {
190 Quad<VALUE_TYPE>& q = quads[i];
191 gc->TraceLocation(&q.name);
192 gc->TraceLocation(&q.ns);
193 gc->TraceConservativeLocation((uintptr_t*)&q.value);
195 return false;
199 * since identifiers are always interned strings, they can't be 0,
200 * so we can use 0 as the empty value.
202 static const Stringp EMPTY = NULL;
204 template <class VALUE_TYPE, class VALUE_WRITER>
205 const Quad<VALUE_TYPE>* MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::getNSSet(Stringp mnameName, NamespaceSetp nsset) const
207 static const Quad<VALUE_TYPE> kBindNone = { NULL, NULL, NULL, 0 };
208 static const Quad<VALUE_TYPE> kBindAmbiguous = { NULL, NULL, (VALUE_TYPE)-1, 0 };
210 int nsCount = nsset->count();
211 int j;
213 const Quad<VALUE_TYPE>* match = &kBindNone;
214 VALUE_TYPE matchValue = match->value;
216 // this is a quadratic probe but we only hit every third slot since those hold keys.
217 int n = 7;
218 int bitMask = numQuads - 1;
220 // Note: Mask off MSB to avoid negative indices. Mask off bottom
221 // 3 bits because it doesn't contribute to hash. Quad it
222 // because names, namespaces, and values are stored adjacently.
223 unsigned i = ((0x7FFFFFF8 & (uintptr_t)mnameName)>>3) & bitMask;
224 Stringp atomName;
226 const Quad<VALUE_TYPE>* t = m_quads->quads;
227 while ((atomName = t[i].name) != EMPTY)
229 if (atomName == mnameName)
231 for (j=0; j < nsCount; j++)
233 Namespacep ns = nsset->nsAt(j);
234 AvmAssert(ns->getURI()->isInterned());
235 if (t[i].matchNS(ns))
237 match = &t[i];
238 matchValue = match->value;
239 goto found1;
244 i = (i + (n++)) & bitMask; // quadratic probe
247 return &kBindNone;
249 found1:
250 if (t[i].multiNS())
252 int k = (i + (n++)) & bitMask; // quadratic probe
253 while ((atomName = t[k].name) != EMPTY)
255 if (atomName == mnameName)
257 AvmAssert(t[k].ns->getURI()->isInterned());
258 for (j=0; j < nsCount; j++)
260 Namespacep ns = nsset->nsAt(j);
261 if (t[k].matchNS(ns) && matchValue != t[k].value)
263 return &kBindAmbiguous;
268 k = (k + (n++)) & bitMask; // quadratic probe
271 return match;
274 template <class VALUE_TYPE, class VALUE_WRITER>
275 VALUE_TYPE MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::get(Stringp name, Namespacep ns) const
277 AvmAssert(ns->getURI()->isInterned());
278 const Quad<VALUE_TYPE>* t = m_quads->quads;
279 int i = find(name, ns, t, numQuads);
280 if (t[i].name == name)
282 const Quad<VALUE_TYPE>& tf = t[i];
283 AvmAssert(tf.matchNS(ns));
284 return tf.value;
286 return (VALUE_TYPE)NULL;
289 template <class VALUE_TYPE, class VALUE_WRITER>
290 VALUE_TYPE MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::getName(Stringp name, Namespacep* nsFoundOut) const
292 const Quad<VALUE_TYPE>* t = m_quads->quads;
293 for (int i=0, n=numQuads; i < n; i++)
295 if (t[i].name == name)
297 const Quad<VALUE_TYPE>& tf = t[i];
298 if (nsFoundOut)
299 *nsFoundOut = tf.ns;
300 return tf.value;
303 if (nsFoundOut)
304 *nsFoundOut = NULL;
305 return (VALUE_TYPE)NULL;
308 template <class VALUE_TYPE, class VALUE_WRITER>
309 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::rehash(const Quad<VALUE_TYPE>* oldAtoms, int oldTriplet, Quad<VALUE_TYPE>* newAtoms, int newTriplet)
311 for (int i=0, n=oldTriplet; i < n; i++)
313 Stringp oldName;
314 if ((oldName=oldAtoms[i].name) != EMPTY)
316 // inlined & simplified version of put()
317 int j = find(oldName, oldAtoms[i].ns, newAtoms, newTriplet);
318 // don't need WBRC/WB here because we are just moving pointers
319 newAtoms[j].name = oldName;
320 newAtoms[j].ns = oldAtoms[i].ns;
321 newAtoms[j].value = oldAtoms[i].value;
322 newAtoms[j].apiAndMultiNS = oldAtoms[i].apiAndMultiNS;
327 // call this method using the previous value returned
328 // by this method starting with 0, until 0 is returned.
329 template <class VALUE_TYPE, class VALUE_WRITER>
330 int FASTCALL MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::next(int index) const
332 // Advance to first non-empty slot.
333 const Quad<VALUE_TYPE>* t = m_quads->quads;
334 while (index < numQuads) {
335 if (t[index++].name != NULL) {
336 return index;
339 return 0;
342 template <class VALUE_TYPE, class VALUE_WRITER>
343 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::add(Stringp name, Namespacep ns, VALUE_TYPE value)
345 if (isFull())
347 grow();
349 put(name, ns, value);
352 template <class VALUE_TYPE, class VALUE_WRITER>
353 void MultinameHashtable<VALUE_TYPE, VALUE_WRITER>::put(Stringp name, Namespacep ns, VALUE_TYPE value)
355 AvmAssert(!isFull());
356 AvmAssert(name->isInterned());
357 AvmAssert(ns->getURI()->isInterned());
359 MMgc::GC* gc = MMgc::GC::GetGC(m_quads);
361 uint32_t multiNS = 0;
363 // inlined version of find(), so that we can sniff for the multiNS
364 // case (and update as necessary) in a single pass (rather than the
365 // two extra passes we used to do)... this relies on the fact that
366 // the quadratic probe will walk thru every existing entry with the same
367 // name in order to find an empty slot, thus if there are any existing
368 // entries with a different ns than what we are adding, all of those name
369 // entries should be marked as multiNS.
370 Quad<VALUE_TYPE>* cur;
371 Quad<VALUE_TYPE>* const quadbase = m_quads->quads;
373 int n = 7;
374 int const bitmask = (numQuads - 1);
375 unsigned i = ((0x7FFFFFF8 & (uintptr_t)name) >> 3) & bitmask;
376 cur = quadbase + i;
377 for (;;)
379 Stringp probeName = cur->name;
380 if (!probeName)
382 // found the hole.
383 break;
386 if (probeName == name)
388 // there's at least one existing entry with this name in the MNHT.
389 if (cur->matchNS(ns))
391 // it's the one we're looking for, just update the value.
392 goto write_value;
395 // it's not the one we're looking for, thus we are now multiNS on this name.
396 if (cur->ns->m_uriAndType != ns->m_uriAndType) {
397 cur->apiAndMultiNS |= 1;
398 multiNS = 1;
402 i = (i + (n++)) & bitmask; // quadratic probe
403 cur = quadbase + i;
407 AvmAssert(cur->name == NULL);
408 AvmAssert(cur->ns == NULL);
410 // New table entry for this <name,ns> pair
411 size++;
412 // OPTIMIZEME: we know the entries are zero, so we could use WriteBarrierRC_ctor here...
413 // except that it will call GetGC() on the address, which will be wrong for > 4k.
414 // Need a version of WriteBarrierRC_ctor that takes explicit GC*.
415 WBRC(gc, m_quads, &cur->name, name);
416 WBRC(gc, m_quads, &cur->ns, ns);
417 // Set the "ApiVersion" section to an impossibly large value, so that we always
418 // set it to the proper value the first time through.
419 AvmAssert(cur->apiAndMultiNS == 0);
420 cur->apiAndMultiNS = (kApiVersion_count << 1) | multiNS;
422 write_value:
423 VALUE_WRITER::store(gc, m_quads, (void**)&cur->value, (void*)value);
424 uintptr_t const v = (uintptr_t)ns->getApiVersion() << 1;
425 if (v < (cur->apiAndMultiNS & ~1))
427 // Note that this assumes that both ApiVersions are in the same series;
428 // this should always be the case as we build them that way, but let's double-check.
429 cur->apiAndMultiNS = v | (cur->apiAndMultiNS & 1);
430 AvmAssert((kApiVersionSeriesMembership[ns->getApiVersion()] & kApiVersionSeriesMembership[cur->apiVersion()]) != 0);
435 #endif /*__avmplus_MultinameHashtable_impl__ */