root/core/MultinameHashtable.cpp

/* [<][>][^][v][top][bottom][index][help] */
/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is [Open Source Virtual Machine.].
 *
 * The Initial Developer of the Original Code is
 * Adobe System Incorporated.
 * Portions created by the Initial Developer are Copyright (C) 2004-2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Adobe AS3 Team
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

#include "avmplus.h"

using namespace MMgc;

namespace avmplus
{
        void MultinameHashtable::grow()
        {
                // double our table
                int capacity = numQuads*2;
                MMgc::GC* gc = MMgc::GC::GetGC(this);
                MMGC_MEM_TYPE(this);
                Quad* newAtoms = (Quad *) gc->Calloc(capacity, sizeof(Quad), GC::kContainsPointers|GC::kZero);
                rehash(m_quads, numQuads, newAtoms, capacity);
                gc->Free(m_quads);
                WB(gc, this, &m_quads, newAtoms);
                numQuads = capacity;
        }

        Binding MultinameHashtable::getMulti(const Multiname* mname) const
        {
                // multiname must not be an attr name, have wildcards, or have runtime parts.
                AvmAssert(mname->isBinding() && !mname->isAnyName());

                if (!mname->isNsset())
                        return get(mname->getName(), mname->getNamespace());
                else
                        return get(mname->getName(), mname->getNsset());
        }

        // return the NS that unambigously matches in "match" (or null for none/ambiguous)
        Binding MultinameHashtable::getMulti(const Multiname& mname, Namespacep& match) const
        {
                // multiname must not be an attr name, have wildcards, or have runtime parts.
                AvmAssert(mname.isBinding() && !mname.isAnyName());

                if (!mname.isNsset())
                {
                        Binding b = get(mname.getName(), mname.getNamespace());
                        match = (b != BIND_NONE) ? mname.getNamespace() : NULL;
                        return b;
                }
                else
                {
                        const Quad* q = getNSSet(mname.getName(), mname.getNsset()); 
                        match = q->ns; 
                        return q->value; 
                }
        }

        void MultinameHashtable::add(Stringp name, Namespacep ns, Binding value)
        {
                if (isFull())
                {
                        grow();
                }
                put(name, ns, value);
        }

        MultinameHashtable::MultinameHashtable(int capacity) : 
                m_quads(NULL),
                size(0),
                numQuads(0)
        {
                Init(capacity);
        }

        void MultinameHashtable::Init(int capacity)
        {
                if (capacity)
                {
                        numQuads = MathUtils::nextPowerOfTwo(capacity);

                        MMgc::GC* gc = MMgc::GC::GetGC(this);

                        AvmAssert(numQuads > 0);
                        MMGC_MEM_TYPE(this);
                        Quad* newAtoms = (Quad *) gc->Alloc (sizeof(Quad) * numQuads, GC::kContainsPointers|GC::kZero);
                        WB(gc, this, &m_quads, newAtoms);
                }
        }

        MultinameHashtable::~MultinameHashtable()
        {
                GC *gc = GC::GetGC(this);
                gc->Free(m_quads);
        }

        bool MultinameHashtable::isFull() const
        { 
                // 0.80 load factor
                return 5*(size+1) >= numQuads*4; 
        }

        int MultinameHashtable::find(Stringp name, Namespacep ns, const Quad* t, unsigned m)
        {
                AvmAssert(ns->getURI()->isInterned());
                AvmAssert(name != NULL && ns != NULL);
                AvmAssert(name->isInterned());

                // this is a quadratic probe but we only hit every third slot since those hold keys.
                int n = 7;

                int bitmask = (m - 1);

                // Note: Mask off MSB to avoid negative indices.  Mask off bottom
                // 3 bits because it doesn't contribute to hash.  Quad it
                // because names, namespaces, and values are stored adjacently.
                unsigned i = ((0x7FFFFFF8 & (uintptr)name) >> 3) & bitmask;

                Stringp k;
                while (((k=t[i].name) != name || !(t[i].ns == ns || matchNS(t[i].ns->m_uri, t[i].apis, ns))) && k != NULL)
                {
                        i = (i + (n++)) & bitmask;                      // quadratic probe
                }
                return i;
        }

        /**
         * since identifiers are always interned strings, they can't be 0,
         * so we can use 0 as the empty value.
         */
        static const Stringp EMPTY = NULL;

        const MultinameHashtable::Quad* MultinameHashtable::getNSSet(Stringp mnameName, NamespaceSetp nsset) const
        {
        #ifdef AVMPLUS_64BIT
                static const Quad kBindNone = { NULL, NULL, BIND_NONE, 0, 0 };
                static const Quad kBindAmbiguous = { NULL, NULL, BIND_AMBIGUOUS, 0, 0 };
        #else
                static const Quad kBindNone = { NULL, NULL, BIND_NONE, 0, 0 };
                static const Quad kBindAmbiguous = { NULL, NULL, BIND_AMBIGUOUS, 0, 0 };
        #endif
        
                int nsCount = nsset->count();
                int j;

                const Quad* match = &kBindNone;
                Binding matchValue = match->value;

                // this is a quadratic probe but we only hit every third slot since those hold keys.
                int n = 7;
                int bitMask = numQuads - 1;

                // Note: Mask off MSB to avoid negative indices.  Mask off bottom
                // 3 bits because it doesn't contribute to hash.  Quad it
                // because names, namespaces, and values are stored adjacently.
                unsigned i = ((0x7FFFFFF8 & (uintptr)mnameName)>>3) & bitMask;
                Stringp atomName;

                const Quad* t = m_quads;
                while ((atomName = t[i].name) != EMPTY)
                {
                        if (atomName == mnameName)
                        {
                                Namespacep probeNS = t[i].ns;
                                AvmAssert(probeNS->getURI()->isInterned());
                                API probeAPIs = t[i].apis;
                                uintptr probeURI = probeNS ? probeNS->m_uri : 0;
                                for (j=0; j < nsCount; j++)
                                {
                                        Namespacep ns = nsset->nsAt(j);
                                        AvmAssert(ns->getURI()->isInterned());
                                        if (probeNS==ns || (probeURI == ns->m_uri && (probeAPIs & ns->m_api)))
                                        {
                                                match = &t[i];
                                                matchValue = match->value;
                                                goto found1;
                                        }
                                }
                        }

                        i = (i + (n++)) & bitMask;                      // quadratic probe
                }

                return &kBindNone;

found1:
                if (t[i].multiNS)
                {
                        int k = (i + (n++)) & bitMask;                  // quadratic probe
                        while ((atomName = t[k].name) != EMPTY)
                        {
                                if (atomName == mnameName)
                                {
                                        Namespacep probeNS = t[k].ns;
                                        AvmAssert(probeNS->getURI()->isInterned());
                                        API probeAPIs = t[k].apis;
                                        uintptr probeURI = t[k].ns->m_uri;
                                        for (j=0; j < nsCount; j++)
                                        {
                                                Namespacep ns = nsset->nsAt(j);
                                                if ((probeNS==ns || matchNS(probeURI, probeAPIs, ns)) && matchValue != t[k].value)
                                                {
                                                        return &kBindAmbiguous;

                                                }
                                        }
                                }
                                k = (k + (n++)) & bitMask;                      // quadratic probe
                        }
                }
                return match;
        }


        void MultinameHashtable::put(Stringp name, Namespacep ns, Binding value)
        {
                AvmAssert(!isFull());
                AvmAssert(name->isInterned());
                AvmAssert(ns->getURI()->isInterned());

                GC* gc = GC::GetGC(m_quads);

                uint32_t multiNS = 0;
                
                // inlined version of find(), so that we can sniff for the multiNS
                // case (and update as necessary) in a single pass (rather than the 
                // two extra passes we used to do)... this relies on the fact that
                // the quadratic probe will walk thru every existing entry with the same
                // same name in order to find an empty slot, thus if there are any existing
                // entries with a different ns than what we are adding, all of those name
                // entries should be marked as multiNS.
                Quad* cur;
                Quad* const quadbase = m_quads;
                {
                        int n = 7;
                        int const bitmask = (numQuads - 1);
                        unsigned i = ((0x7FFFFFF8 & (uintptr)name) >> 3) & bitmask;
                        cur = quadbase + i;
                        for (;;)
                        {
                                Stringp probeName = cur->name;
                                if (!probeName)
                                {
                                        // found the hole.
                                        break;
                                }

                                if (probeName == name)
                                {
                                        // there's at least one existing entry with this name in the MNHT.
                                        if (cur->ns == ns || matchNS(cur->ns->m_uri, cur->apis, ns))
                                        {
                                                // it's the one we're looking for, just update the value.
                                                goto write_value;
                                        }

                                        // it's not the one we're looking for, thus we are now multiNS on this name.
                                        if (cur->ns->m_uri != ns->m_uri) {
                                                cur->multiNS = multiNS = 1;
                                        }
                                }

                                i = (i + (n++)) & bitmask;                      // quadratic probe
                                cur = quadbase + i;
                        }
                }
                
                AvmAssert(cur->name == NULL);

                // New table entry for this <name,ns> pair
                size++;
                //quads[i].name = name;
                WBRC(gc, quadbase, &cur->name, name);
                //quads[i].ns = ns;
                WBRC(gc, quadbase, &cur->ns, ns);
                cur->multiNS = multiNS;

write_value:
                //quads[i].value = value;
                WB(gc, quadbase, &cur->value, value);
                cur->apis |= ns->getAPI();
        }

        Binding MultinameHashtable::get(Stringp name, Namespacep ns) const
        {
                AvmAssert(ns->getURI()->isInterned());
                const Quad* t = m_quads;
                int i = find(name, ns, t, numQuads);
                if (t[i].name == name)
                {
                        const Quad& tf = t[i];
                        AvmAssert(tf.ns==ns || matchNS(tf.ns->m_uri, tf.apis, ns));
                        return tf.value;
                }
                return BIND_NONE;
        }

        Binding MultinameHashtable::getName(Stringp name) const
        {
                const Quad* t = m_quads;
                for (int i=0, n=numQuads; i < n; i++)
                {
                        if (t[i].name == name)
                        {
                                const Quad& tf = t[i];

                                return tf.value;
                        }
                }
                return BIND_NONE;
        }

        void MultinameHashtable::rehash(const Quad* oldAtoms, int oldTriplet, Quad* newAtoms, int newTriplet)
        {
                for (int i=0, n=oldTriplet; i < n; i++)
                {
                        Stringp oldName;
                        if ((oldName=oldAtoms[i].name) != EMPTY)
                        {
                                // inlined & simplified version of put()
                                int j = find(oldName, oldAtoms[i].ns, newAtoms, newTriplet);
                                // don't need WBRC/WB here because we are just moving pointers
                                newAtoms[j].name = oldName;
                                newAtoms[j].ns = oldAtoms[i].ns;
                                newAtoms[j].value = oldAtoms[i].value;
                                newAtoms[j].multiNS = oldAtoms[i].multiNS;
                                newAtoms[j].apis = oldAtoms[i].apis;
                        }
                }
        }

        // call this method using the previous value returned
        // by this method starting with 0, until 0 is returned.
        int FASTCALL MultinameHashtable::next(int index) const
        {
                // Advance to first non-empty slot.
                const Quad* t = m_quads;
                while (index < numQuads) {
                        if (t[index++].name != NULL) {
                                return index;
                        }
                }
                return 0;
        }       
}


/* [<][>][^][v][top][bottom][index][help] */