Populate the name-to-pseudo map lazily

Source/core/css/CSSSelector.cpp

Index: Source/core/css/CSSSelector.cpp
diff --git a/Source/core/css/CSSSelector.cpp b/Source/core/css/CSSSelector.cpp
index 94238d4c17481b5b12a844c5c404e252577c8dc6..dbea5fa34a4478c1d7dff469c46ae8f9a530d174 100644
--- a/Source/core/css/CSSSelector.cpp
+++ b/Source/core/css/CSSSelector.cpp
@@ -33,8 +33,8 @@
 #include "wtf/Assertions.h"
 #include "wtf/HashMap.h"
 #include "wtf/StdLibExtras.h"
+#include "wtf/text/AtomicStringHash.h"
 #include "wtf/text/StringBuilder.h"
-#include "wtf/text/StringHash.h"
 
 #ifndef NDEBUG
 #include <stdio.h>
@@ -274,108 +274,112 @@ PseudoId CSSSelector::pseudoId(PseudoType type)
 struct NameToPseudoStruct {
     const char* string;
     unsigned type:8;
+
+    bool operator<(const NameToPseudoStruct& b) const { return strcmp(string, b.string) < 0; }
 };
 
+// This table should be kept sorted.
 const static NameToPseudoStruct pseudoTypeMap[] = {
-{"active",                        CSSSelector::PseudoActive},
-{"after",                         CSSSelector::PseudoAfter},
 {"-webkit-any(",                  CSSSelector::PseudoAny},
 {"-webkit-any-link",              CSSSelector::PseudoAnyLink},
 {"-webkit-autofill",              CSSSelector::PseudoAutofill},
+{"-webkit-drag",                  CSSSelector::PseudoDrag},
+{"-webkit-full-page-media",       CSSSelector::PseudoFullPageMedia},
+{"-webkit-full-screen",           CSSSelector::PseudoFullScreen},
+{"-webkit-full-screen-ancestor",  CSSSelector::PseudoFullScreenAncestor},
+{"-webkit-full-screen-document",  CSSSelector::PseudoFullScreenDocument},
+{"-webkit-resizer",               CSSSelector::PseudoResizer},
+{"-webkit-scrollbar",             CSSSelector::PseudoScrollbar},
+{"-webkit-scrollbar-button",      CSSSelector::PseudoScrollbarButton},
+{"-webkit-scrollbar-corner",      CSSSelector::PseudoScrollbarCorner},
+{"-webkit-scrollbar-thumb",       CSSSelector::PseudoScrollbarThumb},
+{"-webkit-scrollbar-track",       CSSSelector::PseudoScrollbarTrack},
+{"-webkit-scrollbar-track-piece", CSSSelector::PseudoScrollbarTrackPiece},
+{"active",                        CSSSelector::PseudoActive},
+{"after",                         CSSSelector::PseudoAfter},
 {"backdrop",                      CSSSelector::PseudoBackdrop},
 {"before",                        CSSSelector::PseudoBefore},
 {"checked",                       CSSSelector::PseudoChecked},
+{"content",                       CSSSelector::PseudoContent},
+{"corner-present",                CSSSelector::PseudoCornerPresent},
+{"cue",                           CSSSelector::PseudoWebKitCustomElement},
+{"cue(",                          CSSSelector::PseudoCue},
+{"decrement",                     CSSSelector::PseudoDecrement},
 {"default",                       CSSSelector::PseudoDefault},
 {"disabled",                      CSSSelector::PseudoDisabled},
-{"read-only",                     CSSSelector::PseudoReadOnly},
-{"read-write",                    CSSSelector::PseudoReadWrite},
-{"valid",                         CSSSelector::PseudoValid},
-{"invalid",                       CSSSelector::PseudoInvalid},
-{"-webkit-drag",                  CSSSelector::PseudoDrag},
+{"double-button",                 CSSSelector::PseudoDoubleButton},
 {"empty",                         CSSSelector::PseudoEmpty},
 {"enabled",                       CSSSelector::PseudoEnabled},
+{"end",                           CSSSelector::PseudoEnd},
+{"first",                         CSSSelector::PseudoFirstPage},
 {"first-child",                   CSSSelector::PseudoFirstChild},
 {"first-letter",                  CSSSelector::PseudoFirstLetter},
 {"first-line",                    CSSSelector::PseudoFirstLine},
 {"first-of-type",                 CSSSelector::PseudoFirstOfType},
-{"-webkit-full-page-media",       CSSSelector::PseudoFullPageMedia},
-{"nth-child(",                    CSSSelector::PseudoNthChild},
-{"nth-of-type(",                  CSSSelector::PseudoNthOfType},
-{"nth-last-child(",               CSSSelector::PseudoNthLastChild},
-{"nth-last-of-type(",             CSSSelector::PseudoNthLastOfType},
 {"focus",                         CSSSelector::PseudoFocus},
+{"future",                        CSSSelector::PseudoFutureCue},
+{"horizontal",                    CSSSelector::PseudoHorizontal},
+{"host",                          CSSSelector::PseudoHost},
+{"host(",                         CSSSelector::PseudoHost},
+{"host-context(",                 CSSSelector::PseudoHostContext},
 {"hover",                         CSSSelector::PseudoHover},
+{"in-range",                      CSSSelector::PseudoInRange},
+{"increment",                     CSSSelector::PseudoIncrement},
 {"indeterminate",                 CSSSelector::PseudoIndeterminate},
+{"invalid",                       CSSSelector::PseudoInvalid},
+{"lang(",                         CSSSelector::PseudoLang},
 {"last-child",                    CSSSelector::PseudoLastChild},
 {"last-of-type",                  CSSSelector::PseudoLastOfType},
+{"left",                          CSSSelector::PseudoLeftPage},
 {"link",                          CSSSelector::PseudoLink},
-{"lang(",                         CSSSelector::PseudoLang},
+{"no-button",                     CSSSelector::PseudoNoButton},
 {"not(",                          CSSSelector::PseudoNot},
+{"nth-child(",                    CSSSelector::PseudoNthChild},
+{"nth-last-child(",               CSSSelector::PseudoNthLastChild},
+{"nth-last-of-type(",             CSSSelector::PseudoNthLastOfType},
+{"nth-of-type(",                  CSSSelector::PseudoNthOfType},
 {"only-child",                    CSSSelector::PseudoOnlyChild},
 {"only-of-type",                  CSSSelector::PseudoOnlyOfType},
 {"optional",                      CSSSelector::PseudoOptional},
+{"out-of-range",                  CSSSelector::PseudoOutOfRange},
+{"past",                          CSSSelector::PseudoPastCue},
+{"read-only",                     CSSSelector::PseudoReadOnly},
+{"read-write",                    CSSSelector::PseudoReadWrite},
 {"required",                      CSSSelector::PseudoRequired},
-{"-webkit-resizer",               CSSSelector::PseudoResizer},
+{"right",                         CSSSelector::PseudoRightPage},
 {"root",                          CSSSelector::PseudoRoot},
-{"-webkit-scrollbar",             CSSSelector::PseudoScrollbar},
-{"-webkit-scrollbar-button",      CSSSelector::PseudoScrollbarButton},
-{"-webkit-scrollbar-corner",      CSSSelector::PseudoScrollbarCorner},
-{"-webkit-scrollbar-thumb",       CSSSelector::PseudoScrollbarThumb},
-{"-webkit-scrollbar-track",       CSSSelector::PseudoScrollbarTrack},
-{"-webkit-scrollbar-track-piece", CSSSelector::PseudoScrollbarTrackPiece},
+{"scope",                         CSSSelector::PseudoScope},
 {"selection",                     CSSSelector::PseudoSelection},
+{"shadow",                        CSSSelector::PseudoShadow},
+{"single-button",                 CSSSelector::PseudoSingleButton},
+{"start",                         CSSSelector::PseudoStart},
 {"target",                        CSSSelector::PseudoTarget},
+{"unresolved",                    CSSSelector::PseudoUnresolved},
+{"valid",                         CSSSelector::PseudoValid},
+{"vertical",                      CSSSelector::PseudoVertical},
 {"visited",                       CSSSelector::PseudoVisited},
 {"window-inactive",               CSSSelector::PseudoWindowInactive},
-{"decrement",                     CSSSelector::PseudoDecrement},
-{"increment",                     CSSSelector::PseudoIncrement},
-{"start",                         CSSSelector::PseudoStart},
-{"end",                           CSSSelector::PseudoEnd},
-{"horizontal",                    CSSSelector::PseudoHorizontal},
-{"vertical",                      CSSSelector::PseudoVertical},
-{"double-button",                 CSSSelector::PseudoDoubleButton},
-{"single-button",                 CSSSelector::PseudoSingleButton},
-{"no-button",                     CSSSelector::PseudoNoButton},
-{"corner-present",                CSSSelector::PseudoCornerPresent},
-{"first",                         CSSSelector::PseudoFirstPage},
-{"left",                          CSSSelector::PseudoLeftPage},
-{"right",                         CSSSelector::PseudoRightPage},
-{"-webkit-full-screen",           CSSSelector::PseudoFullScreen},
-{"-webkit-full-screen-document",  CSSSelector::PseudoFullScreenDocument},
-{"-webkit-full-screen-ancestor",  CSSSelector::PseudoFullScreenAncestor},
-{"cue(",                          CSSSelector::PseudoCue},
-{"cue",                           CSSSelector::PseudoWebKitCustomElement},
-{"future",                        CSSSelector::PseudoFutureCue},
-{"past",                          CSSSelector::PseudoPastCue},
-{"in-range",                      CSSSelector::PseudoInRange},
-{"out-of-range",                  CSSSelector::PseudoOutOfRange},
-{"scope",                         CSSSelector::PseudoScope},
-{"unresolved",                    CSSSelector::PseudoUnresolved},
-{"host",                          CSSSelector::PseudoHost},
-{"host(",                         CSSSelector::PseudoHost},
-{"host-context(",                 CSSSelector::PseudoHostContext},
-{"content",                       CSSSelector::PseudoContent},
-{"shadow",                        CSSSelector::PseudoShadow},
 };
 
-static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoTypeMap()
+static CSSSelector::PseudoType nameToPseudoType(const AtomicString& name)
 {
-    static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = 0;
-    if (!nameToPseudoType) {
-        nameToPseudoType = new HashMap<StringImpl*, CSSSelector::PseudoType>;
-
-        size_t pseudoCount = WTF_ARRAY_LENGTH(pseudoTypeMap);
-        for (size_t i = 0; i < pseudoCount; i++) {
-            const char* str = pseudoTypeMap[i].string;
-            CSSSelector::PseudoType type;
-            type = static_cast<CSSSelector::PseudoType>(pseudoTypeMap[i].type);
-            // This is a one-time leak.
-            AtomicString* name = new AtomicString(str, strlen(str), AtomicString::ConstructFromLiteral);
-            nameToPseudoType->set(name->impl(), type);
-        }
-    }
+    typedef HashMap<AtomicString, CSSSelector::PseudoType> NameToPseudoTypeMap;
+    DEFINE_STATIC_LOCAL(NameToPseudoTypeMap, nameToPseudoTypeMap, ());
+
+    NameToPseudoTypeMap::iterator slot = nameToPseudoTypeMap.find(name);

[esprehn, 2014/04/25 09:08:03]

You might even be able to always binary search and get rid of the hash table
entirely.

[fs, 2014/04/25 11:23:33]

Yepp, that's doable, but I figured it'd be too gnarly... Anyway, uploaded now,
and probably warrants a new look.

+    if (slot != nameToPseudoTypeMap.end())
+        return slot->value;
+
+    const NameToPseudoStruct* pseudoTypeMapEnd = pseudoTypeMap + WTF_ARRAY_LENGTH(pseudoTypeMap);
+    CString cstrName = name.utf8();

[apavlov, 2014/04/24 15:19:18]

This could as well be inlined

[fs, 2014/04/24 16:01:53]

Assuming you by that mean:

... key = { name.utf8().data(), ... };

then, no, I don't think so, since the lifetime of the CString would then not
last to the next line. Unfortunately.

[apavlov, 2014/04/24 16:53:06]

Ahh, correct. There's a newly constructed object in flight there...

+    NameToPseudoStruct key = { cstrName.data(), CSSSelector::PseudoUnknown };
+    const NameToPseudoStruct* match = std::lower_bound(pseudoTypeMap, pseudoTypeMapEnd, key);
+    if (match == pseudoTypeMapEnd || strcmp(match->string, key.string))
+        return CSSSelector::PseudoUnknown;
 
-    return nameToPseudoType;
+    CSSSelector::PseudoType pseudoType = static_cast<CSSSelector::PseudoType>(match->type);
+    nameToPseudoTypeMap.set(name, pseudoType);
+    return pseudoType;
 }
 
 #ifndef NDEBUG
@@ -414,11 +418,10 @@ CSSSelector::PseudoType CSSSelector::parsePseudoType(const AtomicString& name)
 {
     if (name.isNull())
         return PseudoUnknown;
-    HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = nameToPseudoTypeMap();
-    HashMap<StringImpl*, CSSSelector::PseudoType>::iterator slot = nameToPseudoType->find(name.impl());
 
-    if (slot != nameToPseudoType->end())
-        return slot->value;
+    CSSSelector::PseudoType pseudoType = nameToPseudoType(name);
+    if (pseudoType != PseudoUnknown)
+        return pseudoType;
 
     if (name.startsWith("-webkit-"))
         return PseudoWebKitCustomElement;