Iterating a HashMap<String, X> involves a string equality comparison to check for the empty value
https://bugs.webkit.org/show_bug.cgi?id=84524
Reviewed by Antti Koivisto.
Added a new algorithm for checking for empty buckets that can be specialized.
Specialized it for String. We may later want to do the same thing for KURL.
It's not important to do it for AtomicString, since AtomicString's == function
is already a simple pointer equality compare.
* wtf/HashTable.h:
(WTF::HashTable::isEmptyBucket): Call the new isHashTraitsEmptyValue function, which
will do something more efficient for String.
* wtf/HashTraits.h: Added hasIsEmptyValueFunction to hash traits, with a default value
of false. This allows us to continue to get automatic comparison with the appropriate
emptyValue result for all existing traits, but supply a custom isEmptyValue function
for HashTraits<String>. Putting an isEmptyValue function into the traits would require
overriding it in every class that has a custom value for emptyValue. Specialized
HashTraits for String to add hasIsEmptyValueFunction and declare, but not define, the
isEmptyValue function.
(WTF::isHashTraitsEmptyValue): Added a function that uses the HashTraitsEmptyValueChecker
struct to use either == combined with the emptyValue function or the isEmptyValue function.
(PairHashTraits): Define hasIsEmptyValueFunction and isEmptyValue.
* wtf/text/StringHash.h: Removed unneeded includes and sorted the using statements at
the bottom of the file.
(WTF::HashTraits<String>::isEmptyValue): Define this function here, since here we have
included the WTFString.h header; the HashTraits.h header compiles without WTFString.h.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@114914 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
index 4b4c1a8..2b9b6b9 100644
--- a/Source/WTF/ChangeLog
+++ b/Source/WTF/ChangeLog
@@ -1,3 +1,35 @@
+2012-04-23 Darin Adler <darin@apple.com>
+
+ Iterating a HashMap<String, X> involves a string equality comparison to check for the empty value
+ https://bugs.webkit.org/show_bug.cgi?id=84524
+
+ Reviewed by Antti Koivisto.
+
+ Added a new algorithm for checking for empty buckets that can be specialized.
+ Specialized it for String. We may later want to do the same thing for KURL.
+ It's not important to do it for AtomicString, since AtomicString's == function
+ is already a simple pointer equality compare.
+
+ * wtf/HashTable.h:
+ (WTF::HashTable::isEmptyBucket): Call the new isHashTraitsEmptyValue function, which
+ will do something more efficient for String.
+
+ * wtf/HashTraits.h: Added hasIsEmptyValueFunction to hash traits, with a default value
+ of false. This allows us to continue to get automatic comparison with the appropriate
+ emptyValue result for all existing traits, but supply a custom isEmptyValue function
+ for HashTraits<String>. Putting an isEmptyValue function into the traits would require
+ overriding it in every class that has a custom value for emptyValue. Specialized
+ HashTraits for String to add hasIsEmptyValueFunction and declare, but not define, the
+ isEmptyValue function.
+ (WTF::isHashTraitsEmptyValue): Added a function that uses the HashTraitsEmptyValueChecker
+ struct to use either == combined with the emptyValue function or the isEmptyValue function.
+ (PairHashTraits): Define hasIsEmptyValueFunction and isEmptyValue.
+
+ * wtf/text/StringHash.h: Removed unneeded includes and sorted the using statements at
+ the bottom of the file.
+ (WTF::HashTraits<String>::isEmptyValue): Define this function here, since here we have
+ included the WTFString.h header; the HashTraits.h header compiles without WTFString.h.
+
2012-04-18 Myles Maxfield <mmaxfield@google.com>
Somehow, there's an errant backslash in my last WTF patch
diff --git a/Source/WTF/wtf/HashTable.h b/Source/WTF/wtf/HashTable.h
index 9bd5482..06feed6 100644
--- a/Source/WTF/wtf/HashTable.h
+++ b/Source/WTF/wtf/HashTable.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
* Copyright (C) 2008 David Levin <levin@chromium.org>
*
* This library is free software; you can redistribute it and/or
@@ -359,7 +359,7 @@
void removeWithoutEntryConsistencyCheck(const_iterator);
void clear();
- static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
+ static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
diff --git a/Source/WTF/wtf/HashTraits.h b/Source/WTF/wtf/HashTraits.h
index 10f14d1..92306e0 100644
--- a/Source/WTF/wtf/HashTraits.h
+++ b/Source/WTF/wtf/HashTraits.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
@@ -42,8 +42,17 @@
template<bool isInteger, typename T> struct GenericHashTraitsBase;
template<typename T> struct GenericHashTraitsBase<false, T> {
+ // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
static const bool emptyValueIsZero = false;
+
+ // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
+ // for the empty value when it can be done with the equality operator, but allows custom functions
+ // for cases like String that need them.
+ static const bool hasIsEmptyValueFunction = false;
+
+ // The needsDestruction flag is used to optimize destruction and rehashing.
static const bool needsDestruction = true;
+
static const int minimumTableSize = 64;
};
@@ -138,7 +147,24 @@
// but then callers won't need to call get; doing so will require updating many call sites.
};
- template<> struct HashTraits<String> : SimpleClassHashTraits<String> { };
+ template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
+ static const bool hasIsEmptyValueFunction = true;
+ static bool isEmptyValue(const String&);
+ };
+
+ // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
+ // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
+ template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
+ template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
+ template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
+ };
+ template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
+ template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
+ };
+ template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
+ {
+ return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
+ }
// special traits for pairs, helpful for their use in HashMap implementation
@@ -152,6 +178,10 @@
static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
static EmptyValueType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
+ static const bool hasIsEmptyValueFunction = true;
+ static bool isEmptyValue(const TraitType& value)
+ { return isHashTraitsEmptyValue<FirstTraits>(value.first) && isHashTraitsEmptyValue<SecondTraits>(value.second); }
+
static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
static const int minimumTableSize = FirstTraits::minimumTableSize;
diff --git a/Source/WTF/wtf/text/StringHash.h b/Source/WTF/wtf/text/StringHash.h
index acc97b9..2d34d2c 100644
--- a/Source/WTF/wtf/text/StringHash.h
+++ b/Source/WTF/wtf/text/StringHash.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2006, 2007, 2008 Apple Inc. All rights reserved
+ * Copyright (C) 2006, 2007, 2008, 2012 Apple Inc. All rights reserved
* Copyright (C) Research In Motion Limited 2009. All rights reserved.
*
* This library is free software; you can redistribute it and/or
@@ -23,14 +23,16 @@
#define StringHash_h
#include <wtf/text/AtomicString.h>
-#include <wtf/text/WTFString.h>
-#include <wtf/Forward.h>
#include <wtf/HashTraits.h>
#include <wtf/StringHasher.h>
-#include <wtf/unicode/Unicode.h>
namespace WTF {
+ inline bool HashTraits<String>::isEmptyValue(const String& value)
+ {
+ return value.isNull();
+ }
+
// The hash() functions on StringHash and CaseFoldingHash do not support
// null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
// cause a null-pointer dereference when passed null strings.
@@ -179,8 +181,8 @@
}
-using WTF::StringHash;
-using WTF::CaseFoldingHash;
using WTF::AlreadyHashed;
+using WTF::CaseFoldingHash;
+using WTF::StringHash;
#endif
