Replace std::map, std::set by WTF::HashMap and WTF::HashSet....

webkit/port/bindings/v8/npruntime.cpp

 /*
  * Copyright (C) 2004, 2006 Apple Computer, Inc.  All rights reserved.
  * Copyright (C) 2007-2009 Google, Inc.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 
-#include <map>
-#include <set>
-#include <string>
-#include <v8.h>
-
-#include "bindings/npruntime.h"
 #include "NPV8Object.h"
 #include "npruntime_priv.h"
 #include "V8NPObject.h"
 
+#include <wtf/HashMap.h>
+#include <wtf/HashSet.h>
 #include <wtf/Assertions.h>
 
-using namespace v8;
-
-
 // FIXME: Consider removing locks if we're singlethreaded already.
 // The static initializer here should work okay, but we want to avoid
 // static initialization in general.
 //
 // Commenting out the locks to avoid dependencies on chrome for now.
 // Need a platform abstraction which we can use.
 // static Lock StringIdentifierMapLock;
 
 namespace {
 
 // We use StringKey here as the key-type to avoid a string copy to
 // construct the map key and for faster comparisons than strcmp.
-struct StringKey {
-    StringKey(const char* str) : string(str), length(strlen(str)) {}
-    const char* string;
-    const size_t length;
+class StringKey {
+  public:
+    StringKey(const char* str) : _string(str), _length(strlen(str)) {}

[Mike Belshe, 2009/04/30 21:37:52]

style wise, these should be m_string and m_length?  (for webkit style)

+    StringKey() : _string(0), _length(0) {}
+    StringKey(WTF::HashTableDeletedValueType)
+        : _string(hashTableDeletedValue()), _length(0) { }
+
+    StringKey& operator=(const StringKey& other) {
+        this->_string = other._string;
+        this->_length = other._length;
+        return *this;
+    }
+
+    bool isHashTableDeletedValue() const {
+        return _string == hashTableDeletedValue();
+    }
+
+    const char* _string;
+    size_t _length;
+  private:
+    const char* hashTableDeletedValue() const {
+        return reinterpret_cast<const char*>(-1);
+    }
 };
 
-inline bool operator<(const StringKey& x, const StringKey& y) {
-    // Shorter strings are less than longer strings, memcmp breaks ties.
-    if (x.length < y.length)
+inline bool operator==(const StringKey& x, const StringKey& y) {
+    if (x._length != y._length) {
+        return false;
+    } else if (x._string == y._string) {
         return true;
-    else if (x.length > y.length)
-        return false;
-    else
-        return memcmp(x.string, y.string, y.length) < 0;
+    } else {
+        ASSERT(!x.isHashTableDeletedValue() && !y.isHashTableDeletedValue());
+        return memcmp(x._string, y._string, y._length) == 0;
+    }
 }
 
+// Implement WTF::DefaultHash<StringKey>::Hash interface.
+struct StringKeyHash {
+    static unsigned hash(const StringKey& key) {
+        // Use the same string hash function as in V8.

[Mike Belshe, 2009/04/30 21:37:52]

This comment might make the reader think this needs to match the v8 algorithm,
but I don't think it does?

+        unsigned hash = 0;
+        size_t len = key._length;
+        const char* str = key._string;
+        for (size_t i = 0; i < len; i++) {
+            char c = str[i];
+            hash += c;
+            hash += (hash << 10);
+            hash ^= (hash >> 6);
+        }
+        hash += (hash << 3);
+        hash ^= (hash >> 11);
+        hash += (hash << 15);
+        if (hash == 0) {
+            hash = 27;
+        }
+        return hash;
+    }
+
+    static bool equal(const StringKey& x, const StringKey& y) {
+        return x == y;
+    }
+
+    static const bool safeToCompareToEmptyOrDeleted = true;
+};
+
 }  // namespace
 
-typedef std::map<const StringKey, PrivateIdentifier*> StringIdentifierMap;
+// Implement HashTraits<StringKey>
+struct StringKeyHashTraits : WTF::GenericHashTraits<StringKey> {
+    static void constructDeletedValue(StringKey& slot) {
+        new (&slot) StringKey(WTF::HashTableDeletedValue);
+    }
+    static bool isDeletedValue(const StringKey& value) {
+        return value.isHashTableDeletedValue();
+    }
+};
+
+typedef WTF::HashMap<StringKey, PrivateIdentifier*, \
+        StringKeyHash, StringKeyHashTraits> StringIdentifierMap;
 
 static StringIdentifierMap* getStringIdentifierMap() {
     static StringIdentifierMap* stringIdentifierMap = 0;
     if (!stringIdentifierMap)
         stringIdentifierMap = new StringIdentifierMap();
     return stringIdentifierMap;
 }
 
 // FIXME: Consider removing locks if we're singlethreaded already.
 // static Lock IntIdentifierMapLock;
 
-typedef std::map<int, PrivateIdentifier*> IntIdentifierMap;
+typedef WTF::HashMap<int, PrivateIdentifier*> IntIdentifierMap;
 
 static IntIdentifierMap* getIntIdentifierMap() {
     static IntIdentifierMap* intIdentifierMap = 0;
     if (!intIdentifierMap)
         intIdentifierMap = new IntIdentifierMap();
     return intIdentifierMap;
 }
 
 extern "C" {
 
 NPIdentifier NPN_GetStringIdentifier(const NPUTF8* name) {
     ASSERT(name);
 
     if (name) {
         // AutoLock safeLock(StringIdentifierMapLock);
 
         StringKey key(name);
         StringIdentifierMap* identMap = getStringIdentifierMap();
         StringIdentifierMap::iterator iter = identMap->find(key);
         if (iter != identMap->end())
             return static_cast<NPIdentifier>(iter->second);
 
-        size_t nameLen = key.length;
+        size_t nameLen = key._length;
 
         // We never release identifiers, so this dictionary will grow.
         PrivateIdentifier* identifier = static_cast<PrivateIdentifier*>(
             malloc(sizeof(PrivateIdentifier) + nameLen + 1));
         char* nameStorage = reinterpret_cast<char*>(identifier + 1);
         memcpy(nameStorage, name, nameLen + 1);
         identifier->isString = true;
         identifier->value.string = reinterpret_cast<NPUTF8*>(nameStorage);
-        key.string = nameStorage;
-        (*identMap)[key] = identifier;
+        key._string = nameStorage;
+        identMap->set(key, identifier);
         return (NPIdentifier)identifier;
     }
 
     return 0;
 }
 
 void NPN_GetStringIdentifiers(const NPUTF8** names, int32_t nameCount,
                               NPIdentifier* identifiers) {
     ASSERT(names);
     ASSERT(identifiers);
 
     if (names && identifiers)
         for (int i = 0; i < nameCount; i++)
             identifiers[i] = NPN_GetStringIdentifier(names[i]);
 }
 
 NPIdentifier NPN_GetIntIdentifier(int32_t intid) {
     // AutoLock safeLock(IntIdentifierMapLock);
 
     IntIdentifierMap* identMap = getIntIdentifierMap();
     IntIdentifierMap::iterator iter = identMap->find(intid);
     if (iter != identMap->end())
         return static_cast<NPIdentifier>(iter->second);
 
     // We never release identifiers, so this dictionary will grow.
     PrivateIdentifier* identifier = reinterpret_cast<PrivateIdentifier*>(
         malloc(sizeof(PrivateIdentifier)));
     identifier->isString = false;
     identifier->value.number = intid;
-    (*identMap)[intid] = identifier;
+    identMap->set(intid, identifier);
     return (NPIdentifier)identifier;
 }
 
 bool NPN_IdentifierIsString(NPIdentifier identifier) {
     PrivateIdentifier* i = reinterpret_cast<PrivateIdentifier*>(identifier);
     return i->isString;
 }
 
 NPUTF8 *NPN_UTF8FromIdentifier(NPIdentifier identifier) {
     PrivateIdentifier* i = reinterpret_cast<PrivateIdentifier*>(identifier);
@@ skipping 109 matching lines @@
 // The g_live_objects is a hash table of all live objects to their owner
 // objects.  Presence in this table is used primarily to determine if
 // objects are live or not.
 //
 // The g_root_objects is a hash table of root objects to a set of
 // objects that should be deactivated in sync with the root.  A
 // root is defined as a top-level owner object.  This is used on
 // Frame teardown to deactivate all objects associated
 // with a particular plugin.
 
-typedef std::set<NPObject*> NPObjectSet;
-typedef std::map<NPObject*, NPObject*> NPObjectMap;
-typedef std::map<NPObject*, NPObjectSet*> NPRootObjectMap;
+typedef WTF::HashSet<NPObject*> NPObjectSet;
+typedef WTF::HashMap<NPObject*, NPObject*> NPObjectMap;
+typedef WTF::HashMap<NPObject*, NPObjectSet*> NPRootObjectMap;
 
 // A map of live NPObjects with pointers to their Roots.
 NPObjectMap g_live_objects;
 
 // A map of the root objects and the list of NPObjects
 // associated with that object.
 NPRootObjectMap g_root_objects;
 
 void _NPN_RegisterObject(NPObject* obj, NPObject* owner) {
     ASSERT(obj);
 
     // Check if already registered.
     if (g_live_objects.find(obj) != g_live_objects.end()) {
       return;
     }
 
     if (!owner) {
       // Registering a new owner object.
       ASSERT(g_root_objects.find(obj) == g_root_objects.end());
-      g_root_objects[obj] = new NPObjectSet();
+      g_root_objects.set(obj, new NPObjectSet());
     } else {
       // Always associate this object with it's top-most parent.
       // Since we always flatten, we only have to look up one level.
       NPObjectMap::iterator owner_entry = g_live_objects.find(owner);
       NPObject* parent = NULL;
       if (g_live_objects.end() != owner_entry)
           parent = owner_entry->second;
 
       if (parent) {
-        owner = parent;
+          owner = parent;
       }
       ASSERT(g_root_objects.find(obj) == g_root_objects.end());
       if (g_root_objects.find(owner) != g_root_objects.end())
-        (g_root_objects[owner])->insert(obj);
+          g_root_objects.get(owner)->add(obj);
     }
 
     ASSERT(g_live_objects.find(obj) == g_live_objects.end());
-    g_live_objects[obj] = owner;
+    g_live_objects.set(obj, owner);
 }
 
 void _NPN_UnregisterObject(NPObject* obj) {
     ASSERT(obj);
     ASSERT(g_live_objects.find(obj) != g_live_objects.end());
 
     NPObject* owner = NULL;
     if (g_live_objects.find(obj) != g_live_objects.end())
       owner = g_live_objects.find(obj)->second;
 
     if (owner == NULL) {
         // Unregistering a owner object; also unregister it's descendants.
         ASSERT(g_root_objects.find(obj) != g_root_objects.end());
-        NPObjectSet* set = g_root_objects[obj];
+        NPObjectSet* set = g_root_objects.get(obj);
         while (set->size() > 0) {
 #ifndef NDEBUG
-            size_t size = set->size();
+            int size = set->size();
 #endif
             NPObject* sub_object = *(set->begin());
             // The sub-object should not be a owner!
             ASSERT(g_root_objects.find(sub_object) == g_root_objects.end());
 
             // First, unregister the object.
-            set->erase(sub_object);
-            g_live_objects.erase(sub_object);
+            set->remove(sub_object);
+            g_live_objects.remove(sub_object);
 
             // Remove the JS references to the object.
             ForgetV8ObjectForNPObject(sub_object);
 
             ASSERT(set->size() < size);
         }
         delete set;
-        g_root_objects.erase(obj);
+        g_root_objects.remove(obj);
     } else {
         NPRootObjectMap::iterator owner_entry = g_root_objects.find(owner);
         if (owner_entry != g_root_objects.end()) {
           NPObjectSet* list = owner_entry->second;
           ASSERT(list->find(obj) != list->end());
-          list->erase(obj);
+          list->remove(obj);
         }
     }
     ForgetV8ObjectForNPObject(obj);
 
-    g_live_objects.erase(obj);
+    g_live_objects.remove(obj);
 }
 
 bool _NPN_IsAlive(NPObject* obj) {
     return g_live_objects.find(obj) != g_live_objects.end();
 }
 
 }  // extern "C"