Bug 729952 - Part 2: Use a better hash function in nsCRT, nsTHashtable, and pldhash. r=bz
authorJustin Lebar <justin.lebar@gmail.com>
Fri, 02 Mar 2012 17:20:44 -0500
changeset 88176 73831fbed59f5e31cc325cf5c1f8b49866d5f5bd
parent 88175 69e8dd5e9201e4608a0d603ae9c9287bf8687d7d
child 88177 7fa4f6cd52f54cf4221dce371381c489be8e23d0
push id22173
push userbmo@edmorley.co.uk
push dateSat, 03 Mar 2012 13:14:42 +0000
treeherdermozilla-central@ed57abebd328 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz
bugs729952
milestone13.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 729952 - Part 2: Use a better hash function in nsCRT, nsTHashtable, and pldhash. r=bz
xpcom/ds/nsCRT.cpp
xpcom/glue/nsTHashtable.cpp
xpcom/glue/pldhash.cpp
--- a/xpcom/ds/nsCRT.cpp
+++ b/xpcom/ds/nsCRT.cpp
@@ -49,21 +49,20 @@
  * In general, if you pass a null into any of these string compare
  * routines, we simply return 0.
  */
 
 
 #include "nsCRT.h"
 #include "nsIServiceManager.h"
 #include "nsCharTraits.h"
-#include "prbit.h"
 #include "nsUTF8Utils.h"
+#include "mozilla/HashFunctions.h"
 
-#define ADD_TO_HASHVAL(hashval, c) \
-    hashval = PR_ROTATE_LEFT32(hashval, 4) ^ (c);
+using namespace mozilla;
 
 //----------------------------------------------------------------------
 
 
 ////////////////////////////////////////////////////////////////////////////////
 // My lovely strtok routine
 
 #define IS_DELIM(m, c)          ((m)[(c) >> 3] & (1 << ((c) & 7)))
@@ -216,65 +215,68 @@ PRUnichar* nsCRT::strndup(const PRUnicha
 PRUint32 nsCRT::HashCode(const char* str, PRUint32* resultingStrLen)
 {
   PRUint32 h = 0;
   const char* s = str;
 
   if (!str) return h;
 
   unsigned char c;
-  while ( (c = *s++) )
-    ADD_TO_HASHVAL(h, c);
+  while ( (c = *s++) ) {
+    h = AddToHash(h, c);
+  }
 
   if ( resultingStrLen )
     *resultingStrLen = (s-str)-1;
+
   return h;
 }
 
 PRUint32 nsCRT::HashCode(const char* start, PRUint32 length)
 {
   PRUint32 h = 0;
   const char* s = start;
   const char* end = start + length;
 
   unsigned char c;
   while ( s < end ) {
     c = *s++;
-    ADD_TO_HASHVAL(h, c);
+    h = AddToHash(h, c);
   }
 
   return h;
 }
 
 PRUint32 nsCRT::HashCode(const PRUnichar* str, PRUint32* resultingStrLen)
 {
   PRUint32 h = 0;
   const PRUnichar* s = str;
 
   if (!str) return h;
 
   PRUnichar c;
   while ( (c = *s++) )
-    ADD_TO_HASHVAL(h, c);
+    h = AddToHash(h, c);
 
   if ( resultingStrLen )
     *resultingStrLen = (s-str)-1;
+
   return h;
 }
 
 PRUint32 nsCRT::HashCode(const PRUnichar* start, PRUint32 length)
 {
   PRUint32 h = 0;
   const PRUnichar* s = start;
   const PRUnichar* end = start + length;
 
   PRUnichar c;
   while ( s < end ) {
     c = *s++;
-    ADD_TO_HASHVAL(h, c);
+    h = AddToHash(h, c);
   }
 
   return h;
 }
 
 PRUint32 nsCRT::HashCodeAsUTF16(const char* start, PRUint32 length,
                                 bool* err)
 {
@@ -287,21 +289,20 @@ PRUint32 nsCRT::HashCodeAsUTF16(const ch
   while ( s < end )
     {
       PRUint32 ucs4 = UTF8CharEnumerator::NextChar(&s, end, err);
       if (*err) {
 	return 0;
       }
 
       if (ucs4 < PLANE1_BASE) {
-        ADD_TO_HASHVAL(h, ucs4);
+        h = AddToHash(h, ucs4);
       }
       else {
-        ADD_TO_HASHVAL(h, H_SURROGATE(ucs4));
-        ADD_TO_HASHVAL(h, L_SURROGATE(ucs4));
+        h = AddToHash(h, H_SURROGATE(ucs4), L_SURROGATE(ucs4));
       }
     }
 
   return h;
 }
 
 // This should use NSPR but NSPR isn't exporting its PR_strtoll function
 // Until then...
--- a/xpcom/glue/nsTHashtable.cpp
+++ b/xpcom/glue/nsTHashtable.cpp
@@ -33,16 +33,19 @@
  * 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 "nsTHashtable.h"
 #include "nsHashKeys.h"
 #include "prbit.h"
+#include "mozilla/HashFunctions.h"
+
+using namespace mozilla;
 
 PRUint32
 HashString( const nsAString& aStr )
 {
   PRUint32 code = 0;
 
 #ifdef MOZILLA_INTERNAL_API
   nsAString::const_iterator begin, end;
@@ -50,17 +53,17 @@ HashString( const nsAString& aStr )
   aStr.EndReading(end);
 #else
   const PRUnichar *begin, *end;
   PRUint32 len = NS_StringGetData(aStr, &begin);
   end = begin + len;
 #endif
 
   while (begin != end) {
-    code = PR_ROTATE_LEFT32(code, 4) ^ PRUint32(*begin);
+    code = AddToHash(code, *begin);
     ++begin;
   }
 
   return code;
 }
 
 PRUint32
 HashString( const nsACString& aStr )
@@ -73,43 +76,45 @@ HashString( const nsACString& aStr )
   aStr.EndReading(end);
 #else
   const char *begin, *end;
   PRUint32 len = NS_CStringGetData(aStr, &begin);
   end = begin + len;
 #endif
 
   while (begin != end) {
-    code = PR_ROTATE_LEFT32(code, 4) ^ PRUint32(*begin);
+    code = AddToHash(code, *begin);
     ++begin;
   }
 
   return code;
 }
 
 PRUint32
 HashString(const char *str)
 {
   PRUint32 code = 0;
+  const char *origStr = str;
 
   while (*str) {
-    code = PR_ROTATE_LEFT32(code, 4) ^ PRUint32(*str);
+    code = AddToHash(code, *str);
     ++str;
   }
 
   return code;
 }
 
 PRUint32
 HashString(const PRUnichar *str)
 {
   PRUint32 code = 0;
+  const PRUnichar *origStr = str;
 
   while (*str) {
-    code = PR_ROTATE_LEFT32(code, 4) ^ PRUint32(*str);
+    code = AddToHash(code, *str);
     ++str;
   }
 
   return code;
 }
 
 PLDHashOperator
 PL_DHashStubEnumRemove(PLDHashTable    *table,
--- a/xpcom/glue/pldhash.cpp
+++ b/xpcom/glue/pldhash.cpp
@@ -43,16 +43,17 @@
  *
  * Try to keep this file in sync with js/src/jsdhash.cpp.
  */
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "prbit.h"
 #include "pldhash.h"
+#include "mozilla/HashFunctions.h"
 #include "nsDebug.h"     /* for PR_ASSERT */
 
 #ifdef PL_DHASHMETER
 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
 #  include "nsTraceMalloc.h"
 # endif
 # define METER(x)       x
 #else
@@ -103,16 +104,18 @@
 #else
 
 #define ENTRY_STORE_EXTRA 0
 #define INCREMENT_RECURSION_LEVEL(table_)   PR_BEGIN_MACRO PR_END_MACRO
 #define DECREMENT_RECURSION_LEVEL(table_)   PR_BEGIN_MACRO PR_END_MACRO
 
 #endif /* defined(DEBUG) */
 
+using namespace mozilla;
+
 void *
 PL_DHashAllocTable(PLDHashTable *table, PRUint32 nbytes)
 {
     return malloc(nbytes);
 }
 
 void
 PL_DHashFreeTable(PLDHashTable *table, void *ptr)
@@ -123,17 +126,17 @@ PL_DHashFreeTable(PLDHashTable *table, v
 PLDHashNumber
 PL_DHashStringKey(PLDHashTable *table, const void *key)
 {
     PLDHashNumber h;
     const unsigned char *s;
 
     h = 0;
     for (s = (const unsigned char *) key; *s != '\0'; s++)
-        h = PR_ROTATE_LEFT32(h, 4) ^ *s;
+        h = AddToHash(h, *s);
     return h;
 }
 
 PLDHashNumber
 PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key)
 {
     return (PLDHashNumber)(PRPtrdiff)key >> 2;
 }