author | Ryan VanderMeulen <ryanvm@gmail.com> |
Wed, 18 Jul 2012 22:33:41 -0400 | |
changeset 105210 | 2fcb28092c1378b97a36bbfa02103f2df965f563 |
parent 105209 | 675d4af07c28c76b45df169ebf9f1acc61ad7f85 |
child 105211 | bf48a6be16977315cb1b3dd202b44f32d6146d76 |
push id | 1490 |
push user | akeybl@mozilla.com |
push date | Mon, 08 Oct 2012 18:29:50 +0000 |
treeherder | mozilla-beta@f335e7dacdc1 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
bugs | 647367 |
milestone | 17.0a1 |
backs out | 61d052e202c8ca786b42f7f9116c2619d5a45fe6 |
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
|
--- a/js/jsd/Makefile.in +++ b/js/jsd/Makefile.in @@ -12,19 +12,17 @@ VPATH = @srcdir@ srcdir = @srcdir@ relativesrcdir = js/jsd include $(DEPTH)/config/autoconf.mk MODULE = jsdebug LIBRARY_NAME = jsd DIRS = idl -CPPSRCS = \ - jsd_xpc.cpp \ - jshash.cpp +CPPSRCS = jsd_xpc.cpp IS_COMPONENT = 1 LIBXUL_LIBRARY = 1 MODULE_NAME = JavaScript_Debugger EXPORT_LIBRARY = 1 XPCSHELL_TESTS = test
deleted file mode 100644 --- a/js/jsd/jshash.cpp +++ /dev/null @@ -1,444 +0,0 @@ -/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- - * - * This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -/* - * PR hash table package. - */ -#include <stdlib.h> -#include <string.h> -#include "jstypes.h" -#include "jsutil.h" -#include "jshash.h" - -using namespace js; - -/* Compute the number of buckets in ht */ -#define NBUCKETS(ht) JS_BIT(JS_HASH_BITS - (ht)->shift) - -/* The smallest table has 16 buckets */ -#define MINBUCKETSLOG2 4 -#define MINBUCKETS JS_BIT(MINBUCKETSLOG2) - -/* Compute the maximum entries given n buckets that we will tolerate, ~90% */ -#define OVERLOADED(n) ((n) - ((n) >> 3)) - -/* Compute the number of entries below which we shrink the table by half */ -#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0) - -/* -** Stubs for default hash allocator ops. -*/ -static void * -DefaultAllocTable(void *pool, size_t size) -{ - return OffTheBooks::malloc_(size); -} - -static void -DefaultFreeTable(void *pool, void *item, size_t size) -{ - UnwantedForeground::free_(item); -} - -static JSHashEntry * -DefaultAllocEntry(void *pool, const void *key) -{ - return (JSHashEntry*) OffTheBooks::malloc_(sizeof(JSHashEntry)); -} - -static void -DefaultFreeEntry(void *pool, JSHashEntry *he, unsigned flag) -{ - if (flag == HT_FREE_ENTRY) - UnwantedForeground::free_(he); -} - -static JSHashAllocOps defaultHashAllocOps = { - DefaultAllocTable, DefaultFreeTable, - DefaultAllocEntry, DefaultFreeEntry -}; - -JS_PUBLIC_API(JSHashTable *) -JS_NewHashTable(uint32_t n, JSHashFunction keyHash, - JSHashComparator keyCompare, JSHashComparator valueCompare, - JSHashAllocOps *allocOps, void *allocPriv) -{ - JSHashTable *ht; - size_t nb; - - if (n <= MINBUCKETS) { - n = MINBUCKETSLOG2; - } else { - n = JS_CEILING_LOG2W(n); - if (int32_t(n) < 0) - return NULL; - } - - if (!allocOps) allocOps = &defaultHashAllocOps; - - ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht); - if (!ht) - return NULL; - memset(ht, 0, sizeof *ht); - ht->shift = JS_HASH_BITS - n; - n = JS_BIT(n); - nb = n * sizeof(JSHashEntry *); - ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb); - if (!ht->buckets) { - allocOps->freeTable(allocPriv, ht, nb); - return NULL; - } - memset(ht->buckets, 0, nb); - - ht->keyHash = keyHash; - ht->keyCompare = keyCompare; - ht->valueCompare = valueCompare; - ht->allocOps = allocOps; - ht->allocPriv = allocPriv; - return ht; -} - -JS_PUBLIC_API(void) -JS_HashTableDestroy(JSHashTable *ht) -{ - uint32_t i, n; - JSHashEntry *he, **hep; - JSHashAllocOps *allocOps = ht->allocOps; - void *allocPriv = ht->allocPriv; - - n = NBUCKETS(ht); - for (i = 0; i < n; i++) { - hep = &ht->buckets[i]; - while ((he = *hep) != NULL) { - *hep = he->next; - allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY); - } - } -#ifdef DEBUG - memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]); -#endif - allocOps->freeTable(allocPriv, ht->buckets, n * sizeof ht->buckets[0]); -#ifdef DEBUG - memset(ht, 0xDB, sizeof *ht); -#endif - allocOps->freeTable(allocPriv, ht, sizeof *ht); -} - -/* - * Multiplicative hash, from Knuth 6.4. - */ -#define BUCKET_HEAD(ht, keyHash) \ - (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift]) - -JS_PUBLIC_API(JSHashEntry **) -JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key) -{ - JSHashEntry *he, **hep, **hep0; - -#ifdef JS_HASHMETER - ht->nlookups++; -#endif - hep = hep0 = BUCKET_HEAD(ht, keyHash); - while ((he = *hep) != NULL) { - if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) { - /* Move to front of chain if not already there */ - if (hep != hep0) { - *hep = he->next; - he->next = *hep0; - *hep0 = he; - } - return hep0; - } - hep = &he->next; -#ifdef JS_HASHMETER - ht->nsteps++; -#endif - } - return hep; -} - -static JSBool -Resize(JSHashTable *ht, uint32_t newshift) -{ - size_t nb, nentries, i; - JSHashEntry **oldbuckets, *he, *next, **hep; - size_t nold = NBUCKETS(ht); - - JS_ASSERT(newshift < JS_HASH_BITS); - - nb = (size_t)1 << (JS_HASH_BITS - newshift); - - /* Integer overflow protection. */ - if (nb > (size_t)-1 / sizeof(JSHashEntry*)) - return JS_FALSE; - nb *= sizeof(JSHashEntry*); - - oldbuckets = ht->buckets; - ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb); - if (!ht->buckets) { - ht->buckets = oldbuckets; - return JS_FALSE; - } - memset(ht->buckets, 0, nb); - - ht->shift = newshift; - nentries = ht->nentries; - - for (i = 0; nentries != 0; i++) { - for (he = oldbuckets[i]; he; he = next) { - JS_ASSERT(nentries != 0); - --nentries; - next = he->next; - hep = BUCKET_HEAD(ht, he->keyHash); - - /* - * We do not require unique entries, instead appending he to the - * chain starting at hep. - */ - while (*hep) - hep = &(*hep)->next; - he->next = NULL; - *hep = he; - } - } -#ifdef DEBUG - memset(oldbuckets, 0xDB, nold * sizeof oldbuckets[0]); -#endif - ht->allocOps->freeTable(ht->allocPriv, oldbuckets, - nold * sizeof oldbuckets[0]); - return JS_TRUE; -} - -JS_PUBLIC_API(JSHashEntry *) -JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, - JSHashNumber keyHash, const void *key, void *value) -{ - uint32_t n; - JSHashEntry *he; - - /* Grow the table if it is overloaded */ - n = NBUCKETS(ht); - if (ht->nentries >= OVERLOADED(n)) { - if (!Resize(ht, ht->shift - 1)) - return NULL; -#ifdef JS_HASHMETER - ht->ngrows++; -#endif - hep = JS_HashTableRawLookup(ht, keyHash, key); - } - - /* Make a new key value entry */ - he = ht->allocOps->allocEntry(ht->allocPriv, key); - if (!he) - return NULL; - he->keyHash = keyHash; - he->key = key; - he->value = value; - he->next = *hep; - *hep = he; - ht->nentries++; - return he; -} - -JS_PUBLIC_API(JSHashEntry *) -JS_HashTableAdd(JSHashTable *ht, const void *key, void *value) -{ - JSHashNumber keyHash; - JSHashEntry *he, **hep; - - keyHash = ht->keyHash(key); - hep = JS_HashTableRawLookup(ht, keyHash, key); - if ((he = *hep) != NULL) { - /* Hit; see if values match */ - if (ht->valueCompare(he->value, value)) { - /* key,value pair is already present in table */ - return he; - } - if (he->value) - ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE); - he->value = value; - return he; - } - return JS_HashTableRawAdd(ht, hep, keyHash, key, value); -} - -JS_PUBLIC_API(void) -JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he) -{ - uint32_t n; - - *hep = he->next; - ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY); - - /* Shrink table if it's underloaded */ - n = NBUCKETS(ht); - if (--ht->nentries < UNDERLOADED(n)) { - Resize(ht, ht->shift + 1); -#ifdef JS_HASHMETER - ht->nshrinks++; -#endif - } -} - -JS_PUBLIC_API(JSBool) -JS_HashTableRemove(JSHashTable *ht, const void *key) -{ - JSHashNumber keyHash; - JSHashEntry *he, **hep; - - keyHash = ht->keyHash(key); - hep = JS_HashTableRawLookup(ht, keyHash, key); - if ((he = *hep) == NULL) - return JS_FALSE; - - /* Hit; remove element */ - JS_HashTableRawRemove(ht, hep, he); - return JS_TRUE; -} - -JS_PUBLIC_API(void *) -JS_HashTableLookup(JSHashTable *ht, const void *key) -{ - JSHashNumber keyHash; - JSHashEntry *he, **hep; - - keyHash = ht->keyHash(key); - hep = JS_HashTableRawLookup(ht, keyHash, key); - if ((he = *hep) != NULL) { - return he->value; - } - return NULL; -} - -/* -** Iterate over the entries in the hash table calling func for each -** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP). -** Return a count of the number of elements scanned. -*/ -JS_PUBLIC_API(int) -JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg) -{ - JSHashEntry *he, **hep, **bucket; - uint32_t nlimit, n, nbuckets, newlog2; - int rv; - - nlimit = ht->nentries; - n = 0; - for (bucket = ht->buckets; n != nlimit; ++bucket) { - hep = bucket; - while ((he = *hep) != NULL) { - JS_ASSERT(n < nlimit); - rv = f(he, n, arg); - n++; - if (rv & HT_ENUMERATE_REMOVE) { - *hep = he->next; - ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY); - --ht->nentries; - } else { - hep = &he->next; - } - if (rv & HT_ENUMERATE_STOP) { - goto out; - } - } - } - -out: - /* Shrink table if removal of entries made it underloaded */ - if (ht->nentries != nlimit) { - JS_ASSERT(ht->nentries < nlimit); - nbuckets = NBUCKETS(ht); - if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) { - newlog2 = JS_CEILING_LOG2W(ht->nentries); - if (newlog2 < MINBUCKETSLOG2) - newlog2 = MINBUCKETSLOG2; - - /* Check that we really shrink the table. */ - JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2); - Resize(ht, JS_HASH_BITS - newlog2); - } - } - return (int)n; -} - -#ifdef JS_HASHMETER -#include <stdio.h> - -JS_PUBLIC_API(void) -JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) -{ - double sqsum, mean, sigma; - uint32_t nchains, nbuckets; - uint32_t i, n, maxChain, maxChainLen; - JSHashEntry *he; - - sqsum = 0; - nchains = 0; - maxChain = maxChainLen = 0; - nbuckets = NBUCKETS(ht); - for (i = 0; i < nbuckets; i++) { - he = ht->buckets[i]; - if (!he) - continue; - nchains++; - for (n = 0; he; he = he->next) - n++; - sqsum += n * n; - if (n > maxChainLen) { - maxChainLen = n; - maxChain = i; - } - } - - mean = JS_MeanAndStdDev(nchains, ht->nentries, sqsum, &sigma); - - fprintf(fp, "\nHash table statistics:\n"); - fprintf(fp, " number of lookups: %u\n", ht->nlookups); - fprintf(fp, " number of entries: %u\n", ht->nentries); - fprintf(fp, " number of grows: %u\n", ht->ngrows); - fprintf(fp, " number of shrinks: %u\n", ht->nshrinks); - fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps - / ht->nlookups); - fprintf(fp, "mean hash chain length: %g\n", mean); - fprintf(fp, " standard deviation: %g\n", sigma); - fprintf(fp, " max hash chain length: %u\n", maxChainLen); - fprintf(fp, " max hash chain: [%u]\n", maxChain); - - for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++) - if (dump(he, i, fp) != HT_ENUMERATE_NEXT) - break; -} -#endif /* JS_HASHMETER */ - -JS_PUBLIC_API(int) -JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) -{ - int count; - - count = JS_HashTableEnumerateEntries(ht, dump, fp); -#ifdef JS_HASHMETER - JS_HashTableDumpMeter(ht, dump, fp); -#endif - return count; -} - -JS_PUBLIC_API(JSHashNumber) -JS_HashString(const void *key) -{ - JSHashNumber h; - const unsigned char *s; - - h = 0; - for (s = (const unsigned char *)key; *s; s++) - h = JS_ROTATE_LEFT32(h, 4) ^ *s; - return h; -} - -JS_PUBLIC_API(int) -JS_CompareValues(const void *v1, const void *v2) -{ - return v1 == v2; -}
deleted file mode 100644 --- a/js/jsd/jshash.h +++ /dev/null @@ -1,120 +0,0 @@ -/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- - * - * This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ - -#ifndef jshash_h___ -#define jshash_h___ - -/* - * API to portable hash table code. - */ -#include <stddef.h> -#include <stdio.h> -#include "jstypes.h" - -JS_BEGIN_EXTERN_C - -typedef uint32_t JSHashNumber; -typedef struct JSHashEntry JSHashEntry; -typedef struct JSHashTable JSHashTable; - -#define JS_HASH_BITS 32 -#define JS_GOLDEN_RATIO 0x9E3779B9U - -typedef JSHashNumber (* JSHashFunction)(const void *key); -typedef int (* JSHashComparator)(const void *v1, const void *v2); -typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg); - -/* Flag bits in JSHashEnumerator's return value */ -#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ -#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ -#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ - -typedef struct JSHashAllocOps { - void * (*allocTable)(void *pool, size_t size); - void (*freeTable)(void *pool, void *item, size_t size); - JSHashEntry * (*allocEntry)(void *pool, const void *key); - void (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag); -} JSHashAllocOps; - -#define HT_FREE_VALUE 0 /* just free the entry's value */ -#define HT_FREE_ENTRY 1 /* free value and entire entry */ - -struct JSHashEntry { - JSHashEntry *next; /* hash chain linkage */ - JSHashNumber keyHash; /* key hash function result */ - const void *key; /* ptr to opaque key */ - void *value; /* ptr to opaque value */ -}; - -struct JSHashTable { - JSHashEntry **buckets; /* vector of hash buckets */ - uint32_t nentries; /* number of entries in table */ - uint32_t shift; /* multiplicative hash shift */ - JSHashFunction keyHash; /* key hash function */ - JSHashComparator keyCompare; /* key comparison function */ - JSHashComparator valueCompare; /* value comparison function */ - JSHashAllocOps *allocOps; /* allocation operations */ - void *allocPriv; /* allocation private data */ -#ifdef JS_HASHMETER - uint32_t nlookups; /* total number of lookups */ - uint32_t nsteps; /* number of hash chains traversed */ - uint32_t ngrows; /* number of table expansions */ - uint32_t nshrinks; /* number of table contractions */ -#endif -}; - -/* - * Create a new hash table. - * If allocOps is null, use default allocator ops built on top of malloc(). - */ -extern JS_PUBLIC_API(JSHashTable *) -JS_NewHashTable(uint32_t n, JSHashFunction keyHash, - JSHashComparator keyCompare, JSHashComparator valueCompare, - JSHashAllocOps *allocOps, void *allocPriv); - -extern JS_PUBLIC_API(void) -JS_HashTableDestroy(JSHashTable *ht); - -/* Low level access methods */ -extern JS_PUBLIC_API(JSHashEntry **) -JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key); - -#ifdef __cplusplus -extern JS_PUBLIC_API(JSHashEntry *) -JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash, - const void *key, void *value); -#endif - -extern JS_PUBLIC_API(void) -JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he); - -/* Higher level access methods */ -extern JS_PUBLIC_API(JSHashEntry *) -JS_HashTableAdd(JSHashTable *ht, const void *key, void *value); - -extern JS_PUBLIC_API(JSBool) -JS_HashTableRemove(JSHashTable *ht, const void *key); - -extern JS_PUBLIC_API(int) -JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg); - -extern JS_PUBLIC_API(void *) -JS_HashTableLookup(JSHashTable *ht, const void *key); - -extern JS_PUBLIC_API(int) -JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp); - -/* General-purpose C string hash function. */ -extern JS_PUBLIC_API(JSHashNumber) -JS_HashString(const void *key); - -/* Stub function just returns v1 == v2 */ -extern JS_PUBLIC_API(int) -JS_CompareValues(const void *v1, const void *v2); - -JS_END_EXTERN_C - -#endif /* jshash_h___ */
--- a/js/src/Makefile.in +++ b/js/src/Makefile.in @@ -77,16 +77,17 @@ CPPSRCS = \ jsdbgapi.cpp \ jsdhash.cpp \ jsdtoa.cpp \ jsexn.cpp \ jsfriendapi.cpp \ jsfun.cpp \ jsgc.cpp \ jscrashreport.cpp \ + jshash.cpp \ jsinfer.cpp \ jsinterp.cpp \ jsiter.cpp \ jslog2.cpp \ jsmath.cpp \ jsnativestack.cpp \ jsnum.cpp \ jsobj.cpp \ @@ -155,16 +156,17 @@ INSTALLED_HEADERS = \ jsatom.h \ jsatom.tbl \ jsclass.h \ jsclist.h \ jsdbgapi.h \ jsdhash.h \ jsfriendapi.h \ jsgc.h \ + jshash.h \ jslock.h \ json.h \ jsproxy.h \ jsprf.h \ jsproto.tbl \ jsprvtd.h \ jspubtd.h \ jstypes.h \
--- a/js/src/jsatom.cpp +++ b/js/src/jsatom.cpp @@ -10,16 +10,17 @@ #include <stdlib.h> #include <string.h> #include "mozilla/RangedPtr.h" #include "mozilla/Util.h" #include "jstypes.h" #include "jsutil.h" +#include "jshash.h" #include "jsprf.h" #include "jsapi.h" #include "jsatom.h" #include "jscntxt.h" #include "jsgc.h" #include "jslock.h" #include "jsnum.h" #include "jsstr.h" @@ -37,16 +38,22 @@ #include "vm/Xdr.h" using namespace mozilla; using namespace js; using namespace js::gc; const size_t JSAtomState::commonAtomsOffset = offsetof(JSAtomState, emptyAtom); +/* + * ATOM_HASH assumes that JSHashNumber is 32-bit even on 64-bit systems. + */ +JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4); +JS_STATIC_ASSERT(sizeof(JSAtom *) == JS_BYTES_PER_WORD); + const char * js_AtomToPrintableString(JSContext *cx, JSAtom *atom, JSAutoByteString *bytes) { return js_ValueToPrintable(cx, StringValue(atom), bytes); } #define JS_PROTO(name,code,init) const char js_##name##_str[] = #name; #include "jsproto.tbl"
--- a/js/src/jsatom.h +++ b/js/src/jsatom.h @@ -7,22 +7,22 @@ #ifndef jsatom_h___ #define jsatom_h___ #include <stddef.h> #include "jsversion.h" #include "jsalloc.h" #include "jsapi.h" #include "jsprvtd.h" +#include "jshash.h" #include "jspubtd.h" #include "jslock.h" #include "gc/Barrier.h" #include "js/HashTable.h" -#include "mozilla/HashFunctions.h" struct JSIdArray { int length; js::HeapId vector[1]; /* actually, length jsid words */ }; /* Engine-internal extensions of jsid */ @@ -78,25 +78,33 @@ JSID_IS_ATOM(jsid id, JSAtom *atom) } static JS_ALWAYS_INLINE JSAtom * JSID_TO_ATOM(jsid id) { return (JSAtom *)JSID_TO_STRING(id); } -JS_STATIC_ASSERT(sizeof(js::HashNumber) == 4); +JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4); JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTES_PER_WORD); namespace js { -static JS_ALWAYS_INLINE js::HashNumber +static JS_ALWAYS_INLINE JSHashNumber HashId(jsid id) { - return HashGeneric(JSID_BITS(id)); + JSHashNumber n = +#if JS_BYTES_PER_WORD == 4 + JSHashNumber(JSID_BITS(id)); +#elif JS_BYTES_PER_WORD == 8 + JSHashNumber(JSID_BITS(id)) ^ JSHashNumber(JSID_BITS(id) >> 32); +#else +# error "Unsupported configuration" +#endif + return n * JS_GOLDEN_RATIO; } static JS_ALWAYS_INLINE Value IdToValue(jsid id) { if (JSID_IS_STRING(id)) return StringValue(JSID_TO_STRING(id)); if (JS_LIKELY(JSID_IS_INT(id))) @@ -122,16 +130,25 @@ struct DefaultHasher<jsid> } static bool match(const jsid &id, const Lookup &l) { return id == l; } }; } +#if JS_BYTES_PER_WORD == 4 +# define ATOM_HASH(atom) ((JSHashNumber)(atom) >> 2) +#elif JS_BYTES_PER_WORD == 8 +# define ATOM_HASH(atom) (((JSHashNumber)(uintptr_t)(atom) >> 3) ^ \ + (JSHashNumber)((uintptr_t)(atom) >> 32)) +#else +# error "Unsupported configuration" +#endif + /* * Return a printable, lossless char[] representation of a string-type atom. * The lifetime of the result matches the lifetime of bytes. */ extern const char * js_AtomToPrintableString(JSContext *cx, JSAtom *atom, JSAutoByteString *bytes); namespace js {
--- a/js/src/jsgc.cpp +++ b/js/src/jsgc.cpp @@ -39,16 +39,17 @@ * barriers on them. */ #include <math.h> #include <string.h> /* for memset used when DEBUG */ #include "jstypes.h" #include "jsutil.h" +#include "jshash.h" #include "jsclist.h" #include "jsprf.h" #include "jsapi.h" #include "jsatom.h" #include "jscompartment.h" #include "jscrashreport.h" #include "jscrashformat.h" #include "jscntxt.h"
new file mode 100644 --- /dev/null +++ b/js/src/jshash.cpp @@ -0,0 +1,444 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * PR hash table package. + */ +#include <stdlib.h> +#include <string.h> +#include "jstypes.h" +#include "jsutil.h" +#include "jshash.h" + +using namespace js; + +/* Compute the number of buckets in ht */ +#define NBUCKETS(ht) JS_BIT(JS_HASH_BITS - (ht)->shift) + +/* The smallest table has 16 buckets */ +#define MINBUCKETSLOG2 4 +#define MINBUCKETS JS_BIT(MINBUCKETSLOG2) + +/* Compute the maximum entries given n buckets that we will tolerate, ~90% */ +#define OVERLOADED(n) ((n) - ((n) >> 3)) + +/* Compute the number of entries below which we shrink the table by half */ +#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0) + +/* +** Stubs for default hash allocator ops. +*/ +static void * +DefaultAllocTable(void *pool, size_t size) +{ + return OffTheBooks::malloc_(size); +} + +static void +DefaultFreeTable(void *pool, void *item, size_t size) +{ + UnwantedForeground::free_(item); +} + +static JSHashEntry * +DefaultAllocEntry(void *pool, const void *key) +{ + return (JSHashEntry*) OffTheBooks::malloc_(sizeof(JSHashEntry)); +} + +static void +DefaultFreeEntry(void *pool, JSHashEntry *he, unsigned flag) +{ + if (flag == HT_FREE_ENTRY) + UnwantedForeground::free_(he); +} + +static JSHashAllocOps defaultHashAllocOps = { + DefaultAllocTable, DefaultFreeTable, + DefaultAllocEntry, DefaultFreeEntry +}; + +JS_PUBLIC_API(JSHashTable *) +JS_NewHashTable(uint32_t n, JSHashFunction keyHash, + JSHashComparator keyCompare, JSHashComparator valueCompare, + JSHashAllocOps *allocOps, void *allocPriv) +{ + JSHashTable *ht; + size_t nb; + + if (n <= MINBUCKETS) { + n = MINBUCKETSLOG2; + } else { + n = JS_CEILING_LOG2W(n); + if (int32_t(n) < 0) + return NULL; + } + + if (!allocOps) allocOps = &defaultHashAllocOps; + + ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht); + if (!ht) + return NULL; + memset(ht, 0, sizeof *ht); + ht->shift = JS_HASH_BITS - n; + n = JS_BIT(n); + nb = n * sizeof(JSHashEntry *); + ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb); + if (!ht->buckets) { + allocOps->freeTable(allocPriv, ht, nb); + return NULL; + } + memset(ht->buckets, 0, nb); + + ht->keyHash = keyHash; + ht->keyCompare = keyCompare; + ht->valueCompare = valueCompare; + ht->allocOps = allocOps; + ht->allocPriv = allocPriv; + return ht; +} + +JS_PUBLIC_API(void) +JS_HashTableDestroy(JSHashTable *ht) +{ + uint32_t i, n; + JSHashEntry *he, **hep; + JSHashAllocOps *allocOps = ht->allocOps; + void *allocPriv = ht->allocPriv; + + n = NBUCKETS(ht); + for (i = 0; i < n; i++) { + hep = &ht->buckets[i]; + while ((he = *hep) != NULL) { + *hep = he->next; + allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY); + } + } +#ifdef DEBUG + memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]); +#endif + allocOps->freeTable(allocPriv, ht->buckets, n * sizeof ht->buckets[0]); +#ifdef DEBUG + memset(ht, 0xDB, sizeof *ht); +#endif + allocOps->freeTable(allocPriv, ht, sizeof *ht); +} + +/* + * Multiplicative hash, from Knuth 6.4. + */ +#define BUCKET_HEAD(ht, keyHash) \ + (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift]) + +JS_PUBLIC_API(JSHashEntry **) +JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key) +{ + JSHashEntry *he, **hep, **hep0; + +#ifdef JS_HASHMETER + ht->nlookups++; +#endif + hep = hep0 = BUCKET_HEAD(ht, keyHash); + while ((he = *hep) != NULL) { + if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) { + /* Move to front of chain if not already there */ + if (hep != hep0) { + *hep = he->next; + he->next = *hep0; + *hep0 = he; + } + return hep0; + } + hep = &he->next; +#ifdef JS_HASHMETER + ht->nsteps++; +#endif + } + return hep; +} + +static JSBool +Resize(JSHashTable *ht, uint32_t newshift) +{ + size_t nb, nentries, i; + JSHashEntry **oldbuckets, *he, *next, **hep; + size_t nold = NBUCKETS(ht); + + JS_ASSERT(newshift < JS_HASH_BITS); + + nb = (size_t)1 << (JS_HASH_BITS - newshift); + + /* Integer overflow protection. */ + if (nb > (size_t)-1 / sizeof(JSHashEntry*)) + return JS_FALSE; + nb *= sizeof(JSHashEntry*); + + oldbuckets = ht->buckets; + ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb); + if (!ht->buckets) { + ht->buckets = oldbuckets; + return JS_FALSE; + } + memset(ht->buckets, 0, nb); + + ht->shift = newshift; + nentries = ht->nentries; + + for (i = 0; nentries != 0; i++) { + for (he = oldbuckets[i]; he; he = next) { + JS_ASSERT(nentries != 0); + --nentries; + next = he->next; + hep = BUCKET_HEAD(ht, he->keyHash); + + /* + * We do not require unique entries, instead appending he to the + * chain starting at hep. + */ + while (*hep) + hep = &(*hep)->next; + he->next = NULL; + *hep = he; + } + } +#ifdef DEBUG + memset(oldbuckets, 0xDB, nold * sizeof oldbuckets[0]); +#endif + ht->allocOps->freeTable(ht->allocPriv, oldbuckets, + nold * sizeof oldbuckets[0]); + return JS_TRUE; +} + +JS_PUBLIC_API(JSHashEntry *) +JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, + JSHashNumber keyHash, const void *key, void *value) +{ + uint32_t n; + JSHashEntry *he; + + /* Grow the table if it is overloaded */ + n = NBUCKETS(ht); + if (ht->nentries >= OVERLOADED(n)) { + if (!Resize(ht, ht->shift - 1)) + return NULL; +#ifdef JS_HASHMETER + ht->ngrows++; +#endif + hep = JS_HashTableRawLookup(ht, keyHash, key); + } + + /* Make a new key value entry */ + he = ht->allocOps->allocEntry(ht->allocPriv, key); + if (!he) + return NULL; + he->keyHash = keyHash; + he->key = key; + he->value = value; + he->next = *hep; + *hep = he; + ht->nentries++; + return he; +} + +JS_PUBLIC_API(JSHashEntry *) +JS_HashTableAdd(JSHashTable *ht, const void *key, void *value) +{ + JSHashNumber keyHash; + JSHashEntry *he, **hep; + + keyHash = ht->keyHash(key); + hep = JS_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) != NULL) { + /* Hit; see if values match */ + if (ht->valueCompare(he->value, value)) { + /* key,value pair is already present in table */ + return he; + } + if (he->value) + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE); + he->value = value; + return he; + } + return JS_HashTableRawAdd(ht, hep, keyHash, key, value); +} + +JS_PUBLIC_API(void) +JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he) +{ + uint32_t n; + + *hep = he->next; + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY); + + /* Shrink table if it's underloaded */ + n = NBUCKETS(ht); + if (--ht->nentries < UNDERLOADED(n)) { + Resize(ht, ht->shift + 1); +#ifdef JS_HASHMETER + ht->nshrinks++; +#endif + } +} + +JS_PUBLIC_API(JSBool) +JS_HashTableRemove(JSHashTable *ht, const void *key) +{ + JSHashNumber keyHash; + JSHashEntry *he, **hep; + + keyHash = ht->keyHash(key); + hep = JS_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) == NULL) + return JS_FALSE; + + /* Hit; remove element */ + JS_HashTableRawRemove(ht, hep, he); + return JS_TRUE; +} + +JS_PUBLIC_API(void *) +JS_HashTableLookup(JSHashTable *ht, const void *key) +{ + JSHashNumber keyHash; + JSHashEntry *he, **hep; + + keyHash = ht->keyHash(key); + hep = JS_HashTableRawLookup(ht, keyHash, key); + if ((he = *hep) != NULL) { + return he->value; + } + return NULL; +} + +/* +** Iterate over the entries in the hash table calling func for each +** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP). +** Return a count of the number of elements scanned. +*/ +JS_PUBLIC_API(int) +JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg) +{ + JSHashEntry *he, **hep, **bucket; + uint32_t nlimit, n, nbuckets, newlog2; + int rv; + + nlimit = ht->nentries; + n = 0; + for (bucket = ht->buckets; n != nlimit; ++bucket) { + hep = bucket; + while ((he = *hep) != NULL) { + JS_ASSERT(n < nlimit); + rv = f(he, n, arg); + n++; + if (rv & HT_ENUMERATE_REMOVE) { + *hep = he->next; + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY); + --ht->nentries; + } else { + hep = &he->next; + } + if (rv & HT_ENUMERATE_STOP) { + goto out; + } + } + } + +out: + /* Shrink table if removal of entries made it underloaded */ + if (ht->nentries != nlimit) { + JS_ASSERT(ht->nentries < nlimit); + nbuckets = NBUCKETS(ht); + if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) { + newlog2 = JS_CEILING_LOG2W(ht->nentries); + if (newlog2 < MINBUCKETSLOG2) + newlog2 = MINBUCKETSLOG2; + + /* Check that we really shrink the table. */ + JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2); + Resize(ht, JS_HASH_BITS - newlog2); + } + } + return (int)n; +} + +#ifdef JS_HASHMETER +#include <stdio.h> + +JS_PUBLIC_API(void) +JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) +{ + double sqsum, mean, sigma; + uint32_t nchains, nbuckets; + uint32_t i, n, maxChain, maxChainLen; + JSHashEntry *he; + + sqsum = 0; + nchains = 0; + maxChain = maxChainLen = 0; + nbuckets = NBUCKETS(ht); + for (i = 0; i < nbuckets; i++) { + he = ht->buckets[i]; + if (!he) + continue; + nchains++; + for (n = 0; he; he = he->next) + n++; + sqsum += n * n; + if (n > maxChainLen) { + maxChainLen = n; + maxChain = i; + } + } + + mean = JS_MeanAndStdDev(nchains, ht->nentries, sqsum, &sigma); + + fprintf(fp, "\nHash table statistics:\n"); + fprintf(fp, " number of lookups: %u\n", ht->nlookups); + fprintf(fp, " number of entries: %u\n", ht->nentries); + fprintf(fp, " number of grows: %u\n", ht->ngrows); + fprintf(fp, " number of shrinks: %u\n", ht->nshrinks); + fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps + / ht->nlookups); + fprintf(fp, "mean hash chain length: %g\n", mean); + fprintf(fp, " standard deviation: %g\n", sigma); + fprintf(fp, " max hash chain length: %u\n", maxChainLen); + fprintf(fp, " max hash chain: [%u]\n", maxChain); + + for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++) + if (dump(he, i, fp) != HT_ENUMERATE_NEXT) + break; +} +#endif /* JS_HASHMETER */ + +JS_PUBLIC_API(int) +JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) +{ + int count; + + count = JS_HashTableEnumerateEntries(ht, dump, fp); +#ifdef JS_HASHMETER + JS_HashTableDumpMeter(ht, dump, fp); +#endif + return count; +} + +JS_PUBLIC_API(JSHashNumber) +JS_HashString(const void *key) +{ + JSHashNumber h; + const unsigned char *s; + + h = 0; + for (s = (const unsigned char *)key; *s; s++) + h = JS_ROTATE_LEFT32(h, 4) ^ *s; + return h; +} + +JS_PUBLIC_API(int) +JS_CompareValues(const void *v1, const void *v2) +{ + return v1 == v2; +}
new file mode 100644 --- /dev/null +++ b/js/src/jshash.h @@ -0,0 +1,120 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef jshash_h___ +#define jshash_h___ + +/* + * API to portable hash table code. + */ +#include <stddef.h> +#include <stdio.h> +#include "jstypes.h" + +JS_BEGIN_EXTERN_C + +typedef uint32_t JSHashNumber; +typedef struct JSHashEntry JSHashEntry; +typedef struct JSHashTable JSHashTable; + +#define JS_HASH_BITS 32 +#define JS_GOLDEN_RATIO 0x9E3779B9U + +typedef JSHashNumber (* JSHashFunction)(const void *key); +typedef int (* JSHashComparator)(const void *v1, const void *v2); +typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg); + +/* Flag bits in JSHashEnumerator's return value */ +#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */ +#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */ +#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */ + +typedef struct JSHashAllocOps { + void * (*allocTable)(void *pool, size_t size); + void (*freeTable)(void *pool, void *item, size_t size); + JSHashEntry * (*allocEntry)(void *pool, const void *key); + void (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag); +} JSHashAllocOps; + +#define HT_FREE_VALUE 0 /* just free the entry's value */ +#define HT_FREE_ENTRY 1 /* free value and entire entry */ + +struct JSHashEntry { + JSHashEntry *next; /* hash chain linkage */ + JSHashNumber keyHash; /* key hash function result */ + const void *key; /* ptr to opaque key */ + void *value; /* ptr to opaque value */ +}; + +struct JSHashTable { + JSHashEntry **buckets; /* vector of hash buckets */ + uint32_t nentries; /* number of entries in table */ + uint32_t shift; /* multiplicative hash shift */ + JSHashFunction keyHash; /* key hash function */ + JSHashComparator keyCompare; /* key comparison function */ + JSHashComparator valueCompare; /* value comparison function */ + JSHashAllocOps *allocOps; /* allocation operations */ + void *allocPriv; /* allocation private data */ +#ifdef JS_HASHMETER + uint32_t nlookups; /* total number of lookups */ + uint32_t nsteps; /* number of hash chains traversed */ + uint32_t ngrows; /* number of table expansions */ + uint32_t nshrinks; /* number of table contractions */ +#endif +}; + +/* + * Create a new hash table. + * If allocOps is null, use default allocator ops built on top of malloc(). + */ +extern JS_PUBLIC_API(JSHashTable *) +JS_NewHashTable(uint32_t n, JSHashFunction keyHash, + JSHashComparator keyCompare, JSHashComparator valueCompare, + JSHashAllocOps *allocOps, void *allocPriv); + +extern JS_PUBLIC_API(void) +JS_HashTableDestroy(JSHashTable *ht); + +/* Low level access methods */ +extern JS_PUBLIC_API(JSHashEntry **) +JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key); + +#ifdef __cplusplus +extern JS_PUBLIC_API(JSHashEntry *) +JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash, + const void *key, void *value); +#endif + +extern JS_PUBLIC_API(void) +JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he); + +/* Higher level access methods */ +extern JS_PUBLIC_API(JSHashEntry *) +JS_HashTableAdd(JSHashTable *ht, const void *key, void *value); + +extern JS_PUBLIC_API(JSBool) +JS_HashTableRemove(JSHashTable *ht, const void *key); + +extern JS_PUBLIC_API(int) +JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg); + +extern JS_PUBLIC_API(void *) +JS_HashTableLookup(JSHashTable *ht, const void *key); + +extern JS_PUBLIC_API(int) +JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp); + +/* General-purpose C string hash function. */ +extern JS_PUBLIC_API(JSHashNumber) +JS_HashString(const void *key); + +/* Stub function just returns v1 == v2 */ +extern JS_PUBLIC_API(int) +JS_CompareValues(const void *v1, const void *v2); + +JS_END_EXTERN_C + +#endif /* jshash_h___ */
--- a/js/src/jsobj.cpp +++ b/js/src/jsobj.cpp @@ -10,16 +10,17 @@ */ #include <stdlib.h> #include <string.h> #include "mozilla/Util.h" #include "jstypes.h" #include "jsutil.h" +#include "jshash.h" #include "jsprf.h" #include "jsapi.h" #include "jsarray.h" #include "jsatom.h" #include "jsbool.h" #include "jscntxt.h" #include "jsversion.h" #include "jsfun.h"
--- a/js/src/jsobj.h +++ b/js/src/jsobj.h @@ -16,16 +16,17 @@ * values, called slots. The map/slot pointer pair is GC'ed, while the map * is reference counted and the slot vector is malloc'ed. */ #include "jsapi.h" #include "jsatom.h" #include "jsclass.h" #include "jsfriendapi.h" #include "jsinfer.h" +#include "jshash.h" #include "jspubtd.h" #include "jsprvtd.h" #include "jslock.h" #include "gc/Barrier.h" #include "gc/Heap.h" #include "vm/ObjectImpl.h"
--- a/js/src/jsscope.cpp +++ b/js/src/jsscope.cpp @@ -19,17 +19,16 @@ #include "jscntxt.h" #include "jsdbgapi.h" #include "jslock.h" #include "jsnum.h" #include "jsobj.h" #include "jsscope.h" #include "jsstr.h" -#include "js/HashTable.h" #include "js/MemoryMetrics.h" #include "jsatominlines.h" #include "jscntxtinlines.h" #include "jsobjinlines.h" #include "jsscopeinlines.h" using namespace js; @@ -141,17 +140,17 @@ Shape::hashify(JSContext *cx) * size, so we simply make hash2 odd. */ #define HASH1(hash0,shift) ((hash0) >> (shift)) #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1) Shape ** ShapeTable::search(jsid id, bool adding) { - js::HashNumber hash0, hash1, hash2; + JSHashNumber hash0, hash1, hash2; int sizeLog2; Shape *stored, *shape, **spp, **firstRemoved; uint32_t sizeMask; JS_ASSERT(entries); JS_ASSERT(!JSID_IS_EMPTY(id)); /* Compute the primary hash address. */
--- a/js/src/jsscript.h +++ b/js/src/jsscript.h @@ -950,17 +950,17 @@ struct ScriptFilenameEntry static ScriptFilenameEntry *fromFilename(const char *filename) { return (ScriptFilenameEntry *)(filename - offsetof(ScriptFilenameEntry, filename)); } }; struct ScriptFilenameHasher { typedef const char *Lookup; - static HashNumber hash(const char *l) { return mozilla::HashString(l); } + static HashNumber hash(const char *l) { return JS_HashString(l); } static bool match(const ScriptFilenameEntry *e, const char *l) { return strcmp(e->filename, l) == 0; } }; typedef HashSet<ScriptFilenameEntry *, ScriptFilenameHasher, SystemAllocPolicy> ScriptFilenameTable;
--- a/js/src/jsstr.cpp +++ b/js/src/jsstr.cpp @@ -18,16 +18,17 @@ #include "mozilla/Attributes.h" #include "mozilla/FloatingPoint.h" #include <stdlib.h> #include <string.h> #include "jstypes.h" #include "jsutil.h" +#include "jshash.h" #include "jsprf.h" #include "jsapi.h" #include "jsarray.h" #include "jsatom.h" #include "jsbool.h" #include "jscntxt.h" #include "jsgc.h" #include "jsinterp.h" @@ -36,17 +37,16 @@ #include "jsobj.h" #include "jsopcode.h" #include "jsprobes.h" #include "jsscope.h" #include "jsstr.h" #include "jsversion.h" #include "builtin/RegExp.h" -#include "js/HashTable.h" #include "vm/GlobalObject.h" #include "vm/NumericConversions.h" #include "vm/RegExpObject.h" #include "vm/StringBuffer.h" #include "jsinferinlines.h" #include "jsobjinlines.h" #include "jsstrinlines.h"
--- a/js/src/jstypedarray.cpp +++ b/js/src/jstypedarray.cpp @@ -4,16 +4,17 @@ * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #include <string.h> #include "mozilla/FloatingPoint.h" #include "jstypes.h" #include "jsutil.h" +#include "jshash.h" #include "jsprf.h" #include "jsapi.h" #include "jsarray.h" #include "jsatom.h" #include "jsbool.h" #include "jscntxt.h" #include "jscpucfg.h" #include "jsversion.h"
--- a/js/xpconnect/src/XPCMaps.cpp +++ b/js/xpconnect/src/XPCMaps.cpp @@ -3,28 +3,28 @@ * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ /* Private maps (hashtables). */ #include "xpcprivate.h" -#include "js/HashTable.h" +#include "jshash.h" /***************************************************************************/ // static shared... // Note this is returning the bit pattern of the first part of the nsID, not // the pointer to the nsID. static JSDHashNumber HashIIDPtrKey(JSDHashTable *table, const void *key) { - return *((js::HashNumber*)key); + return *((JSHashNumber*)key); } static JSBool MatchIIDPtrKey(JSDHashTable *table, const JSDHashEntryHdr *entry, const void *key) { return ((const nsID*)key)-> @@ -51,31 +51,31 @@ HashNativeKey(JSDHashTable *table, const Addition = nsnull; Position = 0; } if (!Set) { NS_ASSERTION(Addition, "bad key"); // This would be an XOR like below. // But "0 ^ x == x". So it does not matter. - h = (js::HashNumber) NS_PTR_TO_INT32(Addition) >> 2; + h = (JSHashNumber) NS_PTR_TO_INT32(Addition) >> 2; } else { XPCNativeInterface** Current = Set->GetInterfaceArray(); PRUint16 count = Set->GetInterfaceCount(); if (Addition) { count++; for (PRUint16 i = 0; i < count; i++) { if (i == Position) - h ^= (js::HashNumber) NS_PTR_TO_INT32(Addition) >> 2; + h ^= (JSHashNumber) NS_PTR_TO_INT32(Addition) >> 2; else - h ^= (js::HashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2; + h ^= (JSHashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2; } } else { for (PRUint16 i = 0; i < count; i++) - h ^= (js::HashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2; + h ^= (JSHashNumber) NS_PTR_TO_INT32(*(Current++)) >> 2; } } return h; } /***************************************************************************/ // implement JSObject2WrappedJSMap...
--- a/mfbt/HashFunctions.h +++ b/mfbt/HashFunctions.h @@ -174,24 +174,16 @@ AddToHash(uint32_t hash, A* a) */ MOZ_STATIC_ASSERT(sizeof(a) == sizeof(uintptr_t), "Strange pointer!"); return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, uintptr_t(a)); } -template<> -MOZ_WARN_UNUSED_RESULT -inline uint32_t -AddToHash(uint32_t hash, uintptr_t a) -{ - return detail::AddUintptrToHash<sizeof(uintptr_t)>(hash, a); -} - template<typename A, typename B> MOZ_WARN_UNUSED_RESULT uint32_t AddToHash(uint32_t hash, A a, B b) { return AddToHash(AddToHash(hash, a), b); }