1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/jsd/jshash.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,453 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 + * PR hash table package.
1.12 + */
1.13 +
1.14 +#include "jshash.h"
1.15 +
1.16 +#include "mozilla/MathAlgorithms.h"
1.17 +
1.18 +#include <stdlib.h>
1.19 +#include <string.h>
1.20 +
1.21 +#include "jstypes.h"
1.22 +
1.23 +#include "js/Utility.h"
1.24 +
1.25 +using namespace js;
1.26 +
1.27 +using mozilla::CeilingLog2Size;
1.28 +using mozilla::RotateLeft;
1.29 +
1.30 +/* Compute the number of buckets in ht */
1.31 +#define NBUCKETS(ht) JS_BIT(JS_HASH_BITS - (ht)->shift)
1.32 +
1.33 +/* The smallest table has 16 buckets */
1.34 +#define MINBUCKETSLOG2 4
1.35 +#define MINBUCKETS JS_BIT(MINBUCKETSLOG2)
1.36 +
1.37 +/* Compute the maximum entries given n buckets that we will tolerate, ~90% */
1.38 +#define OVERLOADED(n) ((n) - ((n) >> 3))
1.39 +
1.40 +/* Compute the number of entries below which we shrink the table by half */
1.41 +#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
1.42 +
1.43 +/*
1.44 +** Stubs for default hash allocator ops.
1.45 +*/
1.46 +static void *
1.47 +DefaultAllocTable(void *pool, size_t size)
1.48 +{
1.49 + return js_malloc(size);
1.50 +}
1.51 +
1.52 +static void
1.53 +DefaultFreeTable(void *pool, void *item, size_t size)
1.54 +{
1.55 + js_free(item);
1.56 +}
1.57 +
1.58 +static JSHashEntry *
1.59 +DefaultAllocEntry(void *pool, const void *key)
1.60 +{
1.61 + return (JSHashEntry*) js_malloc(sizeof(JSHashEntry));
1.62 +}
1.63 +
1.64 +static void
1.65 +DefaultFreeEntry(void *pool, JSHashEntry *he, unsigned flag)
1.66 +{
1.67 + if (flag == HT_FREE_ENTRY)
1.68 + js_free(he);
1.69 +}
1.70 +
1.71 +static const JSHashAllocOps defaultHashAllocOps = {
1.72 + DefaultAllocTable, DefaultFreeTable,
1.73 + DefaultAllocEntry, DefaultFreeEntry
1.74 +};
1.75 +
1.76 +JSHashTable *
1.77 +JS_NewHashTable(uint32_t n, JSHashFunction keyHash,
1.78 + JSHashComparator keyCompare, JSHashComparator valueCompare,
1.79 + const JSHashAllocOps *allocOps, void *allocPriv)
1.80 +{
1.81 + JSHashTable *ht;
1.82 + size_t nb;
1.83 +
1.84 + if (n <= MINBUCKETS) {
1.85 + n = MINBUCKETSLOG2;
1.86 + } else {
1.87 + n = CeilingLog2Size(n);
1.88 + if (int32_t(n) < 0)
1.89 + return nullptr;
1.90 + }
1.91 +
1.92 + if (!allocOps) allocOps = &defaultHashAllocOps;
1.93 +
1.94 + ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht);
1.95 + if (!ht)
1.96 + return nullptr;
1.97 + memset(ht, 0, sizeof *ht);
1.98 + ht->shift = JS_HASH_BITS - n;
1.99 + n = JS_BIT(n);
1.100 + nb = n * sizeof(JSHashEntry *);
1.101 + ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb);
1.102 + if (!ht->buckets) {
1.103 + allocOps->freeTable(allocPriv, ht, nb);
1.104 + return nullptr;
1.105 + }
1.106 + memset(ht->buckets, 0, nb);
1.107 +
1.108 + ht->keyHash = keyHash;
1.109 + ht->keyCompare = keyCompare;
1.110 + ht->valueCompare = valueCompare;
1.111 + ht->allocOps = allocOps;
1.112 + ht->allocPriv = allocPriv;
1.113 + return ht;
1.114 +}
1.115 +
1.116 +void
1.117 +JS_HashTableDestroy(JSHashTable *ht)
1.118 +{
1.119 + uint32_t i, n;
1.120 + JSHashEntry *he, **hep;
1.121 + const JSHashAllocOps *allocOps = ht->allocOps;
1.122 + void *allocPriv = ht->allocPriv;
1.123 +
1.124 + n = NBUCKETS(ht);
1.125 + for (i = 0; i < n; i++) {
1.126 + hep = &ht->buckets[i];
1.127 + while ((he = *hep) != nullptr) {
1.128 + *hep = he->next;
1.129 + allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY);
1.130 + }
1.131 + }
1.132 +#ifdef DEBUG
1.133 + memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
1.134 +#endif
1.135 + allocOps->freeTable(allocPriv, ht->buckets, n * sizeof ht->buckets[0]);
1.136 +#ifdef DEBUG
1.137 + memset(ht, 0xDB, sizeof *ht);
1.138 +#endif
1.139 + allocOps->freeTable(allocPriv, ht, sizeof *ht);
1.140 +}
1.141 +
1.142 +/*
1.143 + * Multiplicative hash, from Knuth 6.4.
1.144 + */
1.145 +#define BUCKET_HEAD(ht, keyHash) \
1.146 + (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift])
1.147 +
1.148 +JSHashEntry **
1.149 +JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
1.150 +{
1.151 + JSHashEntry *he, **hep, **hep0;
1.152 +
1.153 +#ifdef JS_HASHMETER
1.154 + ht->nlookups++;
1.155 +#endif
1.156 + hep = hep0 = BUCKET_HEAD(ht, keyHash);
1.157 + while ((he = *hep) != nullptr) {
1.158 + if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) {
1.159 + /* Move to front of chain if not already there */
1.160 + if (hep != hep0) {
1.161 + *hep = he->next;
1.162 + he->next = *hep0;
1.163 + *hep0 = he;
1.164 + }
1.165 + return hep0;
1.166 + }
1.167 + hep = &he->next;
1.168 +#ifdef JS_HASHMETER
1.169 + ht->nsteps++;
1.170 +#endif
1.171 + }
1.172 + return hep;
1.173 +}
1.174 +
1.175 +static bool
1.176 +Resize(JSHashTable *ht, uint32_t newshift)
1.177 +{
1.178 + size_t nb, nentries, i;
1.179 + JSHashEntry **oldbuckets, *he, *next, **hep;
1.180 + size_t nold = NBUCKETS(ht);
1.181 +
1.182 + MOZ_ASSERT(newshift < JS_HASH_BITS);
1.183 +
1.184 + nb = (size_t)1 << (JS_HASH_BITS - newshift);
1.185 +
1.186 + /* Integer overflow protection. */
1.187 + if (nb > (size_t)-1 / sizeof(JSHashEntry*))
1.188 + return false;
1.189 + nb *= sizeof(JSHashEntry*);
1.190 +
1.191 + oldbuckets = ht->buckets;
1.192 + ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb);
1.193 + if (!ht->buckets) {
1.194 + ht->buckets = oldbuckets;
1.195 + return false;
1.196 + }
1.197 + memset(ht->buckets, 0, nb);
1.198 +
1.199 + ht->shift = newshift;
1.200 + nentries = ht->nentries;
1.201 +
1.202 + for (i = 0; nentries != 0; i++) {
1.203 + for (he = oldbuckets[i]; he; he = next) {
1.204 + MOZ_ASSERT(nentries != 0);
1.205 + --nentries;
1.206 + next = he->next;
1.207 + hep = BUCKET_HEAD(ht, he->keyHash);
1.208 +
1.209 + /*
1.210 + * We do not require unique entries, instead appending he to the
1.211 + * chain starting at hep.
1.212 + */
1.213 + while (*hep)
1.214 + hep = &(*hep)->next;
1.215 + he->next = nullptr;
1.216 + *hep = he;
1.217 + }
1.218 + }
1.219 +#ifdef DEBUG
1.220 + memset(oldbuckets, 0xDB, nold * sizeof oldbuckets[0]);
1.221 +#endif
1.222 + ht->allocOps->freeTable(ht->allocPriv, oldbuckets,
1.223 + nold * sizeof oldbuckets[0]);
1.224 + return true;
1.225 +}
1.226 +
1.227 +JSHashEntry *
1.228 +JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep,
1.229 + JSHashNumber keyHash, const void *key, void *value)
1.230 +{
1.231 + uint32_t n;
1.232 + JSHashEntry *he;
1.233 +
1.234 + /* Grow the table if it is overloaded */
1.235 + n = NBUCKETS(ht);
1.236 + if (ht->nentries >= OVERLOADED(n)) {
1.237 + if (!Resize(ht, ht->shift - 1))
1.238 + return nullptr;
1.239 +#ifdef JS_HASHMETER
1.240 + ht->ngrows++;
1.241 +#endif
1.242 + hep = JS_HashTableRawLookup(ht, keyHash, key);
1.243 + }
1.244 +
1.245 + /* Make a new key value entry */
1.246 + he = ht->allocOps->allocEntry(ht->allocPriv, key);
1.247 + if (!he)
1.248 + return nullptr;
1.249 + he->keyHash = keyHash;
1.250 + he->key = key;
1.251 + he->value = value;
1.252 + he->next = *hep;
1.253 + *hep = he;
1.254 + ht->nentries++;
1.255 + return he;
1.256 +}
1.257 +
1.258 +JSHashEntry *
1.259 +JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
1.260 +{
1.261 + JSHashNumber keyHash;
1.262 + JSHashEntry *he, **hep;
1.263 +
1.264 + keyHash = ht->keyHash(key);
1.265 + hep = JS_HashTableRawLookup(ht, keyHash, key);
1.266 + if ((he = *hep) != nullptr) {
1.267 + /* Hit; see if values match */
1.268 + if (ht->valueCompare(he->value, value)) {
1.269 + /* key,value pair is already present in table */
1.270 + return he;
1.271 + }
1.272 + if (he->value)
1.273 + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
1.274 + he->value = value;
1.275 + return he;
1.276 + }
1.277 + return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
1.278 +}
1.279 +
1.280 +void
1.281 +JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
1.282 +{
1.283 + uint32_t n;
1.284 +
1.285 + *hep = he->next;
1.286 + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
1.287 +
1.288 + /* Shrink table if it's underloaded */
1.289 + n = NBUCKETS(ht);
1.290 + if (--ht->nentries < UNDERLOADED(n)) {
1.291 + Resize(ht, ht->shift + 1);
1.292 +#ifdef JS_HASHMETER
1.293 + ht->nshrinks++;
1.294 +#endif
1.295 + }
1.296 +}
1.297 +
1.298 +bool
1.299 +JS_HashTableRemove(JSHashTable *ht, const void *key)
1.300 +{
1.301 + JSHashNumber keyHash;
1.302 + JSHashEntry *he, **hep;
1.303 +
1.304 + keyHash = ht->keyHash(key);
1.305 + hep = JS_HashTableRawLookup(ht, keyHash, key);
1.306 + if ((he = *hep) == nullptr)
1.307 + return false;
1.308 +
1.309 + /* Hit; remove element */
1.310 + JS_HashTableRawRemove(ht, hep, he);
1.311 + return true;
1.312 +}
1.313 +
1.314 +void *
1.315 +JS_HashTableLookup(JSHashTable *ht, const void *key)
1.316 +{
1.317 + JSHashNumber keyHash;
1.318 + JSHashEntry *he, **hep;
1.319 +
1.320 + keyHash = ht->keyHash(key);
1.321 + hep = JS_HashTableRawLookup(ht, keyHash, key);
1.322 + if ((he = *hep) != nullptr) {
1.323 + return he->value;
1.324 + }
1.325 + return nullptr;
1.326 +}
1.327 +
1.328 +/*
1.329 +** Iterate over the entries in the hash table calling func for each
1.330 +** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
1.331 +** Return a count of the number of elements scanned.
1.332 +*/
1.333 +int
1.334 +JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
1.335 +{
1.336 + JSHashEntry *he, **hep, **bucket;
1.337 + uint32_t nlimit, n, nbuckets, newlog2;
1.338 + int rv;
1.339 +
1.340 + nlimit = ht->nentries;
1.341 + n = 0;
1.342 + for (bucket = ht->buckets; n != nlimit; ++bucket) {
1.343 + hep = bucket;
1.344 + while ((he = *hep) != nullptr) {
1.345 + MOZ_ASSERT(n < nlimit);
1.346 + rv = f(he, n, arg);
1.347 + n++;
1.348 + if (rv & HT_ENUMERATE_REMOVE) {
1.349 + *hep = he->next;
1.350 + ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
1.351 + --ht->nentries;
1.352 + } else {
1.353 + hep = &he->next;
1.354 + }
1.355 + if (rv & HT_ENUMERATE_STOP) {
1.356 + goto out;
1.357 + }
1.358 + }
1.359 + }
1.360 +
1.361 +out:
1.362 + /* Shrink table if removal of entries made it underloaded */
1.363 + if (ht->nentries != nlimit) {
1.364 + MOZ_ASSERT(ht->nentries < nlimit);
1.365 + nbuckets = NBUCKETS(ht);
1.366 + if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) {
1.367 + newlog2 = CeilingLog2Size(ht->nentries);
1.368 + if (newlog2 < MINBUCKETSLOG2)
1.369 + newlog2 = MINBUCKETSLOG2;
1.370 +
1.371 + /* Check that we really shrink the table. */
1.372 + MOZ_ASSERT(JS_HASH_BITS - ht->shift > newlog2);
1.373 + Resize(ht, JS_HASH_BITS - newlog2);
1.374 + }
1.375 + }
1.376 + return (int)n;
1.377 +}
1.378 +
1.379 +#ifdef JS_HASHMETER
1.380 +#include <stdio.h>
1.381 +
1.382 +void
1.383 +JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
1.384 +{
1.385 + double sqsum, mean, sigma;
1.386 + uint32_t nchains, nbuckets;
1.387 + uint32_t i, n, maxChain, maxChainLen;
1.388 + JSHashEntry *he;
1.389 +
1.390 + sqsum = 0;
1.391 + nchains = 0;
1.392 + maxChain = maxChainLen = 0;
1.393 + nbuckets = NBUCKETS(ht);
1.394 + for (i = 0; i < nbuckets; i++) {
1.395 + he = ht->buckets[i];
1.396 + if (!he)
1.397 + continue;
1.398 + nchains++;
1.399 + for (n = 0; he; he = he->next)
1.400 + n++;
1.401 + sqsum += n * n;
1.402 + if (n > maxChainLen) {
1.403 + maxChainLen = n;
1.404 + maxChain = i;
1.405 + }
1.406 + }
1.407 +
1.408 + mean = JS_MeanAndStdDev(nchains, ht->nentries, sqsum, &sigma);
1.409 +
1.410 + fprintf(fp, "\nHash table statistics:\n");
1.411 + fprintf(fp, " number of lookups: %u\n", ht->nlookups);
1.412 + fprintf(fp, " number of entries: %u\n", ht->nentries);
1.413 + fprintf(fp, " number of grows: %u\n", ht->ngrows);
1.414 + fprintf(fp, " number of shrinks: %u\n", ht->nshrinks);
1.415 + fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps
1.416 + / ht->nlookups);
1.417 + fprintf(fp, "mean hash chain length: %g\n", mean);
1.418 + fprintf(fp, " standard deviation: %g\n", sigma);
1.419 + fprintf(fp, " max hash chain length: %u\n", maxChainLen);
1.420 + fprintf(fp, " max hash chain: [%u]\n", maxChain);
1.421 +
1.422 + for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
1.423 + if (dump(he, i, fp) != HT_ENUMERATE_NEXT)
1.424 + break;
1.425 +}
1.426 +#endif /* JS_HASHMETER */
1.427 +
1.428 +int
1.429 +JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
1.430 +{
1.431 + int count;
1.432 +
1.433 + count = JS_HashTableEnumerateEntries(ht, dump, fp);
1.434 +#ifdef JS_HASHMETER
1.435 + JS_HashTableDumpMeter(ht, dump, fp);
1.436 +#endif
1.437 + return count;
1.438 +}
1.439 +
1.440 +JSHashNumber
1.441 +JS_HashString(const void *key)
1.442 +{
1.443 + JSHashNumber h;
1.444 + const unsigned char *s;
1.445 +
1.446 + h = 0;
1.447 + for (s = (const unsigned char *)key; *s; s++)
1.448 + h = RotateLeft(h, 4) ^ *s;
1.449 + return h;
1.450 +}
1.451 +
1.452 +int
1.453 +JS_CompareValues(const void *v1, const void *v2)
1.454 +{
1.455 + return v1 == v2;
1.456 +}
