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
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.
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__
47 template <class VALUE_TYPE
, class VALUE_WRITER
>
48 bool MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::gcTrace(MMgc::GC
*gc
, size_t cursor
)
51 gc
->TraceLocation(&m_quads
);
55 template <class VALUE_TYPE
, class VALUE_WRITER
>
56 void MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::grow()
59 int capacity
= numQuads
*2;
60 MMgc::GC
* gc
= MMgc::GC::GetGC(this);
62 QuadContainer
<VALUE_TYPE
>* newAtoms
= QuadContainer
<VALUE_TYPE
>::create(gc
, capacity
);
63 rehash(m_quads
->quads
, numQuads
, newAtoms
->quads
, capacity
);
65 WB(gc
, this, &m_quads
, newAtoms
);
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());
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());
90 VALUE_TYPE b
= get(mname
.getName(), mname
.getNamespace());
91 match
= (b
!= NULL
) ? mname
.getNamespace() : NULL
;
96 const Quad
<VALUE_TYPE
>* q
= getNSSet(mname
.getName(), mname
.getNsset());
102 template <class VALUE_TYPE
, class VALUE_WRITER
>
103 MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::MultinameHashtable(int capacity
) :
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);
117 template <class VALUE_TYPE
, class VALUE_WRITER
>
118 void MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::Init(int capacity
)
122 numQuads
= MathUtils::nextPowerOfTwo(capacity
);
124 MMgc::GC
* gc
= MMgc::GC::GetGC(this);
126 AvmAssert(numQuads
> 0);
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
147 template <class VALUE_TYPE
, class VALUE_WRITER
>
148 bool MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::isFull() const
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.
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
;
172 while (((k
=t
[i
].name
) != name
|| !t
[i
].matchNS(ns
)) && k
!= NULL
)
174 i
= (i
+ (n
++)) & bitmask
; // quadratic probe
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
)
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
);
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();
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.
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
;
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
))
238 matchValue
= match
->value
;
244 i
= (i
+ (n
++)) & bitMask
; // quadratic probe
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
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
));
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
];
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
++)
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
) {
342 template <class VALUE_TYPE
, class VALUE_WRITER
>
343 void MultinameHashtable
<VALUE_TYPE
, VALUE_WRITER
>::add(Stringp name
, Namespacep ns
, VALUE_TYPE value
)
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
;
374 int const bitmask
= (numQuads
- 1);
375 unsigned i
= ((0x7FFFFFF8 & (uintptr_t)name
) >> 3) & bitmask
;
379 Stringp probeName
= cur
->name
;
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.
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;
402 i
= (i
+ (n
++)) & bitmask
; // quadratic probe
407 AvmAssert(cur
->name
== NULL
);
408 AvmAssert(cur
->ns
== NULL
);
410 // New table entry for this <name,ns> pair
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
;
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__ */