← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mozjs17/trusty

« back to all changes in this revision

Viewing changes to js/src/jsdhash.cpp

  • Committer: Package Import Robot
  • Author(s): Rico Tzschichholz
  • Date: 2013-05-25 12:24:23 UTC
  • Revision ID: package-import@ubuntu.com-20130525122423-zmxucrhtensw90xy
Tags: upstream-17.0.0
Import upstream version 17.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
js/src/jsdhash.cpp
 
1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
 
2
/* This Source Code Form is subject to the terms of the Mozilla Public
 
3
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 
4
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
5
 
 
6
/*
 
7
 * Double hashing implementation.
 
8
 *
 
9
 * Try to keep this file in sync with xpcom/glue/pldhash.cpp.
 
10
 */
 
11
#include <stdio.h>
 
12
#include <stdlib.h>
 
13
#include <string.h>
 
14
#include "jsdhash.h"
 
15
#include "jsutil.h"
 
16
 
 
17
using namespace js;
 
18
 
 
19
#ifdef JS_DHASHMETER
 
20
# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
 
21
#  include "nsTraceMalloc.h"
 
22
# endif
 
23
# define METER(x)       x
 
24
#else
 
25
# define METER(x)       /* nothing */
 
26
#endif
 
27
 
 
28
/*
 
29
 * The following DEBUG-only code is used to assert that calls to one of
 
30
 * table->ops or to an enumerator do not cause re-entry into a call that
 
31
 * can mutate the table.  The recursion level is stored in additional
 
32
 * space allocated at the end of the entry store to avoid changing
 
33
 * JSDHashTable, which could cause issues when mixing DEBUG and
 
34
 * non-DEBUG components.
 
35
 */
 
36
#ifdef DEBUG
 
37
 
 
38
#define JSDHASH_ONELINE_ASSERT JS_ASSERT
 
39
#define RECURSION_LEVEL(table_) (*(uint32_t*)(table_->entryStore +            \
 
40
                                              JS_DHASH_TABLE_SIZE(table_) *   \
 
41
                                              table_->entrySize))
 
42
/*
 
43
 * Most callers that assert about the recursion level don't care about
 
44
 * this magical value because they are asserting that mutation is
 
45
 * allowed (and therefore the level is 0 or 1, depending on whether they
 
46
 * incremented it).
 
47
 *
 
48
 * Only PL_DHashTableFinish needs to allow this special value.
 
49
 */
 
50
#define IMMUTABLE_RECURSION_LEVEL UINT32_MAX
 
51
 
 
52
#define RECURSION_LEVEL_SAFE_TO_FINISH(table_)                                \
 
53
    (RECURSION_LEVEL(table_) == 0 ||                                          \
 
54
     RECURSION_LEVEL(table_) == IMMUTABLE_RECURSION_LEVEL)
 
55
 
 
56
#define ENTRY_STORE_EXTRA                   sizeof(uint32_t)
 
57
#define INCREMENT_RECURSION_LEVEL(table_)                                     \
 
58
    JS_BEGIN_MACRO                                                            \
 
59
        if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL)             \
 
60
            ++RECURSION_LEVEL(table_);                                        \
 
61
    JS_END_MACRO
 
62
#define DECREMENT_RECURSION_LEVEL(table_)                                     \
 
63
    JS_BEGIN_MACRO                                                            \
 
64
        if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) {           \
 
65
            JS_ASSERT(RECURSION_LEVEL(table_) > 0);                           \
 
66
            --RECURSION_LEVEL(table_);                                        \
 
67
        }                                                                     \
 
68
    JS_END_MACRO
 
69
 
 
70
#else
 
71
 
 
72
#define ENTRY_STORE_EXTRA 0
 
73
#define INCREMENT_RECURSION_LEVEL(table_)   JS_BEGIN_MACRO JS_END_MACRO
 
74
#define DECREMENT_RECURSION_LEVEL(table_)   JS_BEGIN_MACRO JS_END_MACRO
 
75
 
 
76
#endif /* defined(DEBUG) */
 
77
 
 
78
JS_PUBLIC_API(void *)
 
79
JS_DHashAllocTable(JSDHashTable *table, uint32_t nbytes)
 
80
{
 
81
    return OffTheBooks::malloc_(nbytes);
 
82
}
 
83
 
 
84
JS_PUBLIC_API(void)
 
85
JS_DHashFreeTable(JSDHashTable *table, void *ptr)
 
86
{
 
87
    UnwantedForeground::free_(ptr);
 
88
}
 
89
 
 
90
JS_PUBLIC_API(JSDHashNumber)
 
91
JS_DHashStringKey(JSDHashTable *table, const void *key)
 
92
{
 
93
    JSDHashNumber h;
 
94
    const unsigned char *s;
 
95
 
 
96
    h = 0;
 
97
    for (s = (const unsigned char *) key; *s != '\0'; s++)
 
98
        h = JS_ROTATE_LEFT32(h, 4) ^ *s;
 
99
    return h;
 
100
}
 
101
 
 
102
JS_PUBLIC_API(JSDHashNumber)
 
103
JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
 
104
{
 
105
    return (JSDHashNumber)(uintptr_t)key >> 2;
 
106
}
 
107
 
 
108
JS_PUBLIC_API(JSBool)
 
109
JS_DHashMatchEntryStub(JSDHashTable *table,
 
110
                       const JSDHashEntryHdr *entry,
 
111
                       const void *key)
 
112
{
 
113
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 
114
 
 
115
    return stub->key == key;
 
116
}
 
117
 
 
118
JS_PUBLIC_API(JSBool)
 
119
JS_DHashMatchStringKey(JSDHashTable *table,
 
120
                       const JSDHashEntryHdr *entry,
 
121
                       const void *key)
 
122
{
 
123
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 
124
 
 
125
    /* XXX tolerate null keys on account of sloppy Mozilla callers. */
 
126
    return stub->key == key ||
 
127
           (stub->key && key &&
 
128
            strcmp((const char *) stub->key, (const char *) key) == 0);
 
129
}
 
130
 
 
131
JS_PUBLIC_API(void)
 
132
JS_DHashMoveEntryStub(JSDHashTable *table,
 
133
                      const JSDHashEntryHdr *from,
 
134
                      JSDHashEntryHdr *to)
 
135
{
 
136
    js_memcpy(to, from, table->entrySize);
 
137
}
 
138
 
 
139
JS_PUBLIC_API(void)
 
140
JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
 
141
{
 
142
    memset(entry, 0, table->entrySize);
 
143
}
 
144
 
 
145
JS_PUBLIC_API(void)
 
146
JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
 
147
{
 
148
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 
149
 
 
150
    UnwantedForeground::free_((void *) stub->key);
 
151
    memset(entry, 0, table->entrySize);
 
152
}
 
153
 
 
154
JS_PUBLIC_API(void)
 
155
JS_DHashFinalizeStub(JSDHashTable *table)
 
156
{
 
157
}
 
158
 
 
159
static const JSDHashTableOps stub_ops = {
 
160
    JS_DHashAllocTable,
 
161
    JS_DHashFreeTable,
 
162
    JS_DHashVoidPtrKeyStub,
 
163
    JS_DHashMatchEntryStub,
 
164
    JS_DHashMoveEntryStub,
 
165
    JS_DHashClearEntryStub,
 
166
    JS_DHashFinalizeStub,
 
167
    NULL
 
168
};
 
169
 
 
170
JS_PUBLIC_API(const JSDHashTableOps *)
 
171
JS_DHashGetStubOps(void)
 
172
{
 
173
    return &stub_ops;
 
174
}
 
175
 
 
176
JS_PUBLIC_API(JSDHashTable *)
 
177
JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32_t entrySize,
 
178
                 uint32_t capacity)
 
179
{
 
180
    JSDHashTable *table;
 
181
 
 
182
    table = (JSDHashTable *) OffTheBooks::malloc_(sizeof *table);
 
183
    if (!table)
 
184
        return NULL;
 
185
    if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
 
186
        Foreground::free_(table);
 
187
        return NULL;
 
188
    }
 
189
    return table;
 
190
}
 
191
 
 
192
JS_PUBLIC_API(void)
 
193
JS_DHashTableDestroy(JSDHashTable *table)
 
194
{
 
195
    JS_DHashTableFinish(table);
 
196
    UnwantedForeground::free_(table);
 
197
}
 
198
 
 
199
JS_PUBLIC_API(JSBool)
 
200
JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
 
201
                  uint32_t entrySize, uint32_t capacity)
 
202
{
 
203
    int log2;
 
204
    uint32_t nbytes;
 
205
 
 
206
#ifdef DEBUG
 
207
    if (entrySize > 10 * sizeof(void *)) {
 
208
        fprintf(stderr,
 
209
                "jsdhash: for the table at address %p, the given entrySize"
 
210
                " of %lu %s favors chaining over double hashing.\n",
 
211
                (void *) table,
 
212
                (unsigned long) entrySize,
 
213
                (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
 
214
    }
 
215
#endif
 
216
 
 
217
    table->ops = ops;
 
218
    table->data = data;
 
219
    if (capacity < JS_DHASH_MIN_SIZE)
 
220
        capacity = JS_DHASH_MIN_SIZE;
 
221
 
 
222
    JS_CEILING_LOG2(log2, capacity);
 
223
 
 
224
    capacity = JS_BIT(log2);
 
225
    if (capacity >= JS_DHASH_SIZE_LIMIT)
 
226
        return JS_FALSE;
 
227
    table->hashShift = JS_DHASH_BITS - log2;
 
228
    table->maxAlphaFrac = (uint8_t)(0x100 * JS_DHASH_DEFAULT_MAX_ALPHA);
 
229
    table->minAlphaFrac = (uint8_t)(0x100 * JS_DHASH_DEFAULT_MIN_ALPHA);
 
230
    table->entrySize = entrySize;
 
231
    table->entryCount = table->removedCount = 0;
 
232
    table->generation = 0;
 
233
    nbytes = capacity * entrySize;
 
234
 
 
235
    table->entryStore = (char *) ops->allocTable(table,
 
236
                                                 nbytes + ENTRY_STORE_EXTRA);
 
237
    if (!table->entryStore)
 
238
        return JS_FALSE;
 
239
    memset(table->entryStore, 0, nbytes);
 
240
    METER(memset(&table->stats, 0, sizeof table->stats));
 
241
 
 
242
#ifdef DEBUG
 
243
    RECURSION_LEVEL(table) = 0;
 
244
#endif
 
245
 
 
246
    return JS_TRUE;
 
247
}
 
248
 
 
249
/*
 
250
 * Compute max and min load numbers (entry counts) from table params.
 
251
 */
 
252
#define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
 
253
#define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
 
254
 
 
255
JS_PUBLIC_API(void)
 
256
JS_DHashTableSetAlphaBounds(JSDHashTable *table,
 
257
                            float maxAlpha,
 
258
                            float minAlpha)
 
259
{
 
260
    uint32_t size;
 
261
 
 
262
    /*
 
263
     * Reject obviously insane bounds, rather than trying to guess what the
 
264
     * buggy caller intended.
 
265
     */
 
266
    JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
 
267
    if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
 
268
        return;
 
269
 
 
270
    /*
 
271
     * Ensure that at least one entry will always be free.  If maxAlpha at
 
272
     * minimum size leaves no entries free, reduce maxAlpha based on minimum
 
273
     * size and the precision limit of maxAlphaFrac's fixed point format.
 
274
     */
 
275
    JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
 
276
    if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
 
277
        maxAlpha = (float)
 
278
                   (JS_DHASH_MIN_SIZE - Max(JS_DHASH_MIN_SIZE / 256, 1))
 
279
                   / JS_DHASH_MIN_SIZE;
 
280
    }
 
281
 
 
282
    /*
 
283
     * Ensure that minAlpha is strictly less than half maxAlpha.  Take care
 
284
     * not to truncate an entry's worth of alpha when storing in minAlphaFrac
 
285
     * (8-bit fixed point format).
 
286
     */
 
287
    JS_ASSERT(minAlpha < maxAlpha / 2);
 
288
    if (minAlpha >= maxAlpha / 2) {
 
289
        size = JS_DHASH_TABLE_SIZE(table);
 
290
        minAlpha = (size * maxAlpha - Max(size / 256, 1U)) / (2 * size);
 
291
    }
 
292
 
 
293
    table->maxAlphaFrac = (uint8_t)(maxAlpha * 256);
 
294
    table->minAlphaFrac = (uint8_t)(minAlpha * 256);
 
295
}
 
296
 
 
297
/*
 
298
 * Double hashing needs the second hash code to be relatively prime to table
 
299
 * size, so we simply make hash2 odd.
 
300
 */
 
301
#define HASH1(hash0, shift)         ((hash0) >> (shift))
 
302
#define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
 
303
 
 
304
/*
 
305
 * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
 
306
 * that a removed-entry sentinel need be stored only if the removed entry had
 
307
 * a colliding entry added after it.  Therefore we can use 1 as the collision
 
308
 * flag in addition to the removed-entry sentinel value.  Multiplicative hash
 
309
 * uses the high order bits of keyHash, so this least-significant reservation
 
310
 * should not hurt the hash function's effectiveness much.
 
311
 *
 
312
 * If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
 
313
 * in jsdhash.h.  It used to be private to jsdhash.c, but then became public to
 
314
 * assist iterator writers who inspect table->entryStore directly.
 
315
 */
 
316
#define COLLISION_FLAG              ((JSDHashNumber) 1)
 
317
#define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
 
318
#define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
 
319
#define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
 
320
#define ENTRY_IS_LIVE(entry)        JS_DHASH_ENTRY_IS_LIVE(entry)
 
321
#define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
 
322
 
 
323
/* Match an entry's keyHash against an unstored one computed from a key. */
 
324
#define MATCH_ENTRY_KEYHASH(entry,hash0) \
 
325
    (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
 
326
 
 
327
/* Compute the address of the indexed entry in table. */
 
328
#define ADDRESS_ENTRY(table, index) \
 
329
    ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
 
330
 
 
331
JS_PUBLIC_API(void)
 
332
JS_DHashTableFinish(JSDHashTable *table)
 
333
{
 
334
    char *entryAddr, *entryLimit;
 
335
    uint32_t entrySize;
 
336
    JSDHashEntryHdr *entry;
 
337
 
 
338
#ifdef DEBUG_XXXbrendan
 
339
    static FILE *dumpfp = NULL;
 
340
    if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
 
341
    if (dumpfp) {
 
342
#ifdef MOZILLA_CLIENT
 
343
        NS_TraceStack(1, dumpfp);
 
344
#endif
 
345
        JS_DHashTableDumpMeter(table, NULL, dumpfp);
 
346
        fputc('\n', dumpfp);
 
347
    }
 
348
#endif
 
349
 
 
350
    INCREMENT_RECURSION_LEVEL(table);
 
351
 
 
352
    /* Call finalize before clearing entries, so it can enumerate them. */
 
353
    table->ops->finalize(table);
 
354
 
 
355
    /* Clear any remaining live entries. */
 
356
    entryAddr = table->entryStore;
 
357
    entrySize = table->entrySize;
 
358
    entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
 
359
    while (entryAddr < entryLimit) {
 
360
        entry = (JSDHashEntryHdr *)entryAddr;
 
361
        if (ENTRY_IS_LIVE(entry)) {
 
362
            METER(table->stats.removeEnums++);
 
363
            table->ops->clearEntry(table, entry);
 
364
        }
 
365
        entryAddr += entrySize;
 
366
    }
 
367
 
 
368
    DECREMENT_RECURSION_LEVEL(table);
 
369
    JS_ASSERT(RECURSION_LEVEL_SAFE_TO_FINISH(table));
 
370
 
 
371
    /* Free entry storage last. */
 
372
    table->ops->freeTable(table, table->entryStore);
 
373
}
 
374
 
 
375
static JSDHashEntryHdr * JS_DHASH_FASTCALL
 
376
SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
 
377
            JSDHashOperator op)
 
378
{
 
379
    JSDHashNumber hash1, hash2;
 
380
    int hashShift, sizeLog2;
 
381
    JSDHashEntryHdr *entry, *firstRemoved;
 
382
    JSDHashMatchEntry matchEntry;
 
383
    uint32_t sizeMask;
 
384
 
 
385
    METER(table->stats.searches++);
 
386
    JS_ASSERT(!(keyHash & COLLISION_FLAG));
 
387
 
 
388
    /* Compute the primary hash address. */
 
389
    hashShift = table->hashShift;
 
390
    hash1 = HASH1(keyHash, hashShift);
 
391
    entry = ADDRESS_ENTRY(table, hash1);
 
392
 
 
393
    /* Miss: return space for a new entry. */
 
394
    if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 
395
        METER(table->stats.misses++);
 
396
        return entry;
 
397
    }
 
398
 
 
399
    /* Hit: return entry. */
 
400
    matchEntry = table->ops->matchEntry;
 
401
    if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
 
402
        METER(table->stats.hits++);
 
403
        return entry;
 
404
    }
 
405
 
 
406
    /* Collision: double hash. */
 
407
    sizeLog2 = JS_DHASH_BITS - table->hashShift;
 
408
    hash2 = HASH2(keyHash, sizeLog2, hashShift);
 
409
    sizeMask = JS_BITMASK(sizeLog2);
 
410
 
 
411
    /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
 
412
    firstRemoved = NULL;
 
413
 
 
414
    for (;;) {
 
415
        if (JS_UNLIKELY(ENTRY_IS_REMOVED(entry))) {
 
416
            if (!firstRemoved)
 
417
                firstRemoved = entry;
 
418
        } else {
 
419
            if (op == JS_DHASH_ADD)
 
420
                entry->keyHash |= COLLISION_FLAG;
 
421
        }
 
422
 
 
423
        METER(table->stats.steps++);
 
424
        hash1 -= hash2;
 
425
        hash1 &= sizeMask;
 
426
 
 
427
        entry = ADDRESS_ENTRY(table, hash1);
 
428
        if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 
429
            METER(table->stats.misses++);
 
430
            return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
 
431
        }
 
432
 
 
433
        if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
 
434
            matchEntry(table, entry, key)) {
 
435
            METER(table->stats.hits++);
 
436
            return entry;
 
437
        }
 
438
    }
 
439
 
 
440
    /* NOTREACHED */
 
441
    return NULL;
 
442
}
 
443
 
 
444
/*
 
445
 * This is a copy of SearchTable, used by ChangeTable, hardcoded to
 
446
 *   1. assume |op == PL_DHASH_ADD|,
 
447
 *   2. assume that |key| will never match an existing entry, and
 
448
 *   3. assume that no entries have been removed from the current table
 
449
 *      structure.
 
450
 * Avoiding the need for |key| means we can avoid needing a way to map
 
451
 * entries to keys, which means callers can use complex key types more
 
452
 * easily.
 
453
 */
 
454
static JSDHashEntryHdr * JS_DHASH_FASTCALL
 
455
FindFreeEntry(JSDHashTable *table, JSDHashNumber keyHash)
 
456
{
 
457
    JSDHashNumber hash1, hash2;
 
458
    int hashShift, sizeLog2;
 
459
    JSDHashEntryHdr *entry;
 
460
    uint32_t sizeMask;
 
461
 
 
462
    METER(table->stats.searches++);
 
463
    JS_ASSERT(!(keyHash & COLLISION_FLAG));
 
464
 
 
465
    /* Compute the primary hash address. */
 
466
    hashShift = table->hashShift;
 
467
    hash1 = HASH1(keyHash, hashShift);
 
468
    entry = ADDRESS_ENTRY(table, hash1);
 
469
 
 
470
    /* Miss: return space for a new entry. */
 
471
    if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 
472
        METER(table->stats.misses++);
 
473
        return entry;
 
474
    }
 
475
 
 
476
    /* Collision: double hash. */
 
477
    sizeLog2 = JS_DHASH_BITS - table->hashShift;
 
478
    hash2 = HASH2(keyHash, sizeLog2, hashShift);
 
479
    sizeMask = JS_BITMASK(sizeLog2);
 
480
 
 
481
    for (;;) {
 
482
        JS_ASSERT(!ENTRY_IS_REMOVED(entry));
 
483
        entry->keyHash |= COLLISION_FLAG;
 
484
 
 
485
        METER(table->stats.steps++);
 
486
        hash1 -= hash2;
 
487
        hash1 &= sizeMask;
 
488
 
 
489
        entry = ADDRESS_ENTRY(table, hash1);
 
490
        if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 
491
            METER(table->stats.misses++);
 
492
            return entry;
 
493
        }
 
494
    }
 
495
 
 
496
    /* NOTREACHED */
 
497
    return NULL;
 
498
}
 
499
 
 
500
static JSBool
 
501
ChangeTable(JSDHashTable *table, int deltaLog2)
 
502
{
 
503
    int oldLog2, newLog2;
 
504
    uint32_t oldCapacity, newCapacity;
 
505
    char *newEntryStore, *oldEntryStore, *oldEntryAddr;
 
506
    uint32_t entrySize, i, nbytes;
 
507
    JSDHashEntryHdr *oldEntry, *newEntry;
 
508
    JSDHashMoveEntry moveEntry;
 
509
#ifdef DEBUG
 
510
    uint32_t recursionLevel;
 
511
#endif
 
512
 
 
513
    /* Look, but don't touch, until we succeed in getting new entry store. */
 
514
    oldLog2 = JS_DHASH_BITS - table->hashShift;
 
515
    newLog2 = oldLog2 + deltaLog2;
 
516
    oldCapacity = JS_BIT(oldLog2);
 
517
    newCapacity = JS_BIT(newLog2);
 
518
    if (newCapacity >= JS_DHASH_SIZE_LIMIT)
 
519
        return JS_FALSE;
 
520
    entrySize = table->entrySize;
 
521
    nbytes = newCapacity * entrySize;
 
522
 
 
523
    newEntryStore = (char *) table->ops->allocTable(table,
 
524
                                                    nbytes + ENTRY_STORE_EXTRA);
 
525
    if (!newEntryStore)
 
526
        return JS_FALSE;
 
527
 
 
528
    /* We can't fail from here on, so update table parameters. */
 
529
#ifdef DEBUG
 
530
    recursionLevel = RECURSION_LEVEL(table);
 
531
#endif
 
532
    table->hashShift = JS_DHASH_BITS - newLog2;
 
533
    table->removedCount = 0;
 
534
    table->generation++;
 
535
 
 
536
    /* Assign the new entry store to table. */
 
537
    memset(newEntryStore, 0, nbytes);
 
538
    oldEntryAddr = oldEntryStore = table->entryStore;
 
539
    table->entryStore = newEntryStore;
 
540
    moveEntry = table->ops->moveEntry;
 
541
#ifdef DEBUG
 
542
    RECURSION_LEVEL(table) = recursionLevel;
 
543
#endif
 
544
 
 
545
    /* Copy only live entries, leaving removed ones behind. */
 
546
    for (i = 0; i < oldCapacity; i++) {
 
547
        oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
 
548
        if (ENTRY_IS_LIVE(oldEntry)) {
 
549
            oldEntry->keyHash &= ~COLLISION_FLAG;
 
550
            newEntry = FindFreeEntry(table, oldEntry->keyHash);
 
551
            JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
 
552
            moveEntry(table, oldEntry, newEntry);
 
553
            newEntry->keyHash = oldEntry->keyHash;
 
554
        }
 
555
        oldEntryAddr += entrySize;
 
556
    }
 
557
 
 
558
    table->ops->freeTable(table, oldEntryStore);
 
559
    return JS_TRUE;
 
560
}
 
561
 
 
562
JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
 
563
JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
 
564
{
 
565
    JSDHashNumber keyHash;
 
566
    JSDHashEntryHdr *entry;
 
567
    uint32_t size;
 
568
    int deltaLog2;
 
569
 
 
570
    JS_ASSERT(op == JS_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0);
 
571
    INCREMENT_RECURSION_LEVEL(table);
 
572
 
 
573
    keyHash = table->ops->hashKey(table, key);
 
574
    keyHash *= JS_DHASH_GOLDEN_RATIO;
 
575
 
 
576
    /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
 
577
    ENSURE_LIVE_KEYHASH(keyHash);
 
578
    keyHash &= ~COLLISION_FLAG;
 
579
 
 
580
    switch (op) {
 
581
      case JS_DHASH_LOOKUP:
 
582
        METER(table->stats.lookups++);
 
583
        entry = SearchTable(table, key, keyHash, op);
 
584
        break;
 
585
 
 
586
      case JS_DHASH_ADD:
 
587
        /*
 
588
         * If alpha is >= .75, grow or compress the table.  If key is already
 
589
         * in the table, we may grow once more than necessary, but only if we
 
590
         * are on the edge of being overloaded.
 
591
         */
 
592
        size = JS_DHASH_TABLE_SIZE(table);
 
593
        if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
 
594
            /* Compress if a quarter or more of all entries are removed. */
 
595
            if (table->removedCount >= size >> 2) {
 
596
                METER(table->stats.compresses++);
 
597
                deltaLog2 = 0;
 
598
            } else {
 
599
                METER(table->stats.grows++);
 
600
                deltaLog2 = 1;
 
601
            }
 
602
 
 
603
            /*
 
604
             * Grow or compress table, returning null if ChangeTable fails and
 
605
             * falling through might claim the last free entry.
 
606
             */
 
607
            if (!ChangeTable(table, deltaLog2) &&
 
608
                table->entryCount + table->removedCount == size - 1) {
 
609
                METER(table->stats.addFailures++);
 
610
                entry = NULL;
 
611
                break;
 
612
            }
 
613
        }
 
614
 
 
615
        /*
 
616
         * Look for entry after possibly growing, so we don't have to add it,
 
617
         * then skip it while growing the table and re-add it after.
 
618
         */
 
619
        entry = SearchTable(table, key, keyHash, op);
 
620
        if (!ENTRY_IS_LIVE(entry)) {
 
621
            /* Initialize the entry, indicating that it's no longer free. */
 
622
            METER(table->stats.addMisses++);
 
623
            if (ENTRY_IS_REMOVED(entry)) {
 
624
                METER(table->stats.addOverRemoved++);
 
625
                table->removedCount--;
 
626
                keyHash |= COLLISION_FLAG;
 
627
            }
 
628
            if (table->ops->initEntry &&
 
629
                !table->ops->initEntry(table, entry, key)) {
 
630
                /* We haven't claimed entry yet; fail with null return. */
 
631
                memset(entry + 1, 0, table->entrySize - sizeof *entry);
 
632
                entry = NULL;
 
633
                break;
 
634
            }
 
635
            entry->keyHash = keyHash;
 
636
            table->entryCount++;
 
637
        }
 
638
        METER(else table->stats.addHits++);
 
639
        break;
 
640
 
 
641
      case JS_DHASH_REMOVE:
 
642
        entry = SearchTable(table, key, keyHash, op);
 
643
        if (ENTRY_IS_LIVE(entry)) {
 
644
            /* Clear this entry and mark it as "removed". */
 
645
            METER(table->stats.removeHits++);
 
646
            JS_DHashTableRawRemove(table, entry);
 
647
 
 
648
            /* Shrink if alpha is <= .25 and table isn't too small already. */
 
649
            size = JS_DHASH_TABLE_SIZE(table);
 
650
            if (size > JS_DHASH_MIN_SIZE &&
 
651
                table->entryCount <= MIN_LOAD(table, size)) {
 
652
                METER(table->stats.shrinks++);
 
653
                (void) ChangeTable(table, -1);
 
654
            }
 
655
        }
 
656
        METER(else table->stats.removeMisses++);
 
657
        entry = NULL;
 
658
        break;
 
659
 
 
660
      default:
 
661
        JS_ASSERT(0);
 
662
        entry = NULL;
 
663
    }
 
664
 
 
665
    DECREMENT_RECURSION_LEVEL(table);
 
666
 
 
667
    return entry;
 
668
}
 
669
 
 
670
JS_PUBLIC_API(void)
 
671
JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
 
672
{
 
673
    JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */
 
674
 
 
675
    JS_ASSERT(RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL);
 
676
 
 
677
    JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
 
678
    keyHash = entry->keyHash;
 
679
    table->ops->clearEntry(table, entry);
 
680
    if (keyHash & COLLISION_FLAG) {
 
681
        MARK_ENTRY_REMOVED(entry);
 
682
        table->removedCount++;
 
683
    } else {
 
684
        METER(table->stats.removeFrees++);
 
685
        MARK_ENTRY_FREE(entry);
 
686
    }
 
687
    table->entryCount--;
 
688
}
 
689
 
 
690
JS_PUBLIC_API(uint32_t)
 
691
JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
 
692
{
 
693
    char *entryAddr, *entryLimit;
 
694
    uint32_t i, capacity, entrySize, ceiling;
 
695
    JSBool didRemove;
 
696
    JSDHashEntryHdr *entry;
 
697
    JSDHashOperator op;
 
698
 
 
699
    INCREMENT_RECURSION_LEVEL(table);
 
700
 
 
701
    entryAddr = table->entryStore;
 
702
    entrySize = table->entrySize;
 
703
    capacity = JS_DHASH_TABLE_SIZE(table);
 
704
    entryLimit = entryAddr + capacity * entrySize;
 
705
    i = 0;
 
706
    didRemove = JS_FALSE;
 
707
    while (entryAddr < entryLimit) {
 
708
        entry = (JSDHashEntryHdr *)entryAddr;
 
709
        if (ENTRY_IS_LIVE(entry)) {
 
710
            op = etor(table, entry, i++, arg);
 
711
            if (op & JS_DHASH_REMOVE) {
 
712
                METER(table->stats.removeEnums++);
 
713
                JS_DHashTableRawRemove(table, entry);
 
714
                didRemove = JS_TRUE;
 
715
            }
 
716
            if (op & JS_DHASH_STOP)
 
717
                break;
 
718
        }
 
719
        entryAddr += entrySize;
 
720
    }
 
721
 
 
722
    JS_ASSERT(!didRemove || RECURSION_LEVEL(table) == 1);
 
723
 
 
724
    /*
 
725
     * Shrink or compress if a quarter or more of all entries are removed, or
 
726
     * if the table is underloaded according to the configured minimum alpha,
 
727
     * and is not minimal-size already.  Do this only if we removed above, so
 
728
     * non-removing enumerations can count on stable table->entryStore until
 
729
     * the next non-lookup-Operate or removing-Enumerate.
 
730
     */
 
731
    if (didRemove &&
 
732
        (table->removedCount >= capacity >> 2 ||
 
733
         (capacity > JS_DHASH_MIN_SIZE &&
 
734
          table->entryCount <= MIN_LOAD(table, capacity)))) {
 
735
        METER(table->stats.enumShrinks++);
 
736
        capacity = table->entryCount;
 
737
        capacity += capacity >> 1;
 
738
        if (capacity < JS_DHASH_MIN_SIZE)
 
739
            capacity = JS_DHASH_MIN_SIZE;
 
740
 
 
741
        JS_CEILING_LOG2(ceiling, capacity);
 
742
        ceiling -= JS_DHASH_BITS - table->hashShift;
 
743
 
 
744
        (void) ChangeTable(table, ceiling);
 
745
    }
 
746
 
 
747
    DECREMENT_RECURSION_LEVEL(table);
 
748
 
 
749
    return i;
 
750
}
 
751
 
 
752
struct SizeOfEntryExcludingThisArg
 
753
{
 
754
    size_t total;
 
755
    JSDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis;
 
756
    JSMallocSizeOfFun mallocSizeOf;
 
757
    void *arg;      // the arg passed by the user
 
758
};
 
759
 
 
760
static JSDHashOperator
 
761
SizeOfEntryExcludingThisEnumerator(JSDHashTable *table, JSDHashEntryHdr *hdr,
 
762
                                   uint32_t number, void *arg)
 
763
{
 
764
    SizeOfEntryExcludingThisArg *e = (SizeOfEntryExcludingThisArg *)arg;
 
765
    e->total += e->sizeOfEntryExcludingThis(hdr, e->mallocSizeOf, e->arg);
 
766
    return JS_DHASH_NEXT;
 
767
}
 
768
 
 
769
extern JS_PUBLIC_API(size_t)
 
770
JS_DHashTableSizeOfExcludingThis(const JSDHashTable *table,
 
771
                                 JSDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
 
772
                                 JSMallocSizeOfFun mallocSizeOf,
 
773
                                 void *arg /* = NULL */)
 
774
{
 
775
    size_t n = 0;
 
776
    n += mallocSizeOf(table->entryStore);
 
777
    if (sizeOfEntryExcludingThis) {
 
778
        SizeOfEntryExcludingThisArg arg2 = { 0, sizeOfEntryExcludingThis, mallocSizeOf, arg };
 
779
        JS_DHashTableEnumerate(const_cast<JSDHashTable *>(table),
 
780
                               SizeOfEntryExcludingThisEnumerator, &arg2);
 
781
        n += arg2.total;
 
782
    }
 
783
    return n;
 
784
}
 
785
 
 
786
extern JS_PUBLIC_API(size_t)
 
787
JS_DHashTableSizeOfIncludingThis(const JSDHashTable *table,
 
788
                                 JSDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
 
789
                                 JSMallocSizeOfFun mallocSizeOf,
 
790
                                 void *arg /* = NULL */)
 
791
{
 
792
    return mallocSizeOf(table) +
 
793
           JS_DHashTableSizeOfExcludingThis(table, sizeOfEntryExcludingThis,
 
794
                                            mallocSizeOf, arg);
 
795
}
 
796
 
 
797
#ifdef DEBUG
 
798
JS_PUBLIC_API(void)
 
799
JS_DHashMarkTableImmutable(JSDHashTable *table)
 
800
{
 
801
    RECURSION_LEVEL(table) = IMMUTABLE_RECURSION_LEVEL;
 
802
}
 
803
#endif
 
804
 
 
805
#ifdef JS_DHASHMETER
 
806
#include <math.h>
 
807
 
 
808
JS_PUBLIC_API(void)
 
809
JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
 
810
{
 
811
    char *entryAddr;
 
812
    uint32_t entrySize, entryCount;
 
813
    int hashShift, sizeLog2;
 
814
    uint32_t i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
 
815
    JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
 
816
    double sqsum, mean, variance, sigma;
 
817
    JSDHashEntryHdr *entry, *probe;
 
818
 
 
819
    entryAddr = table->entryStore;
 
820
    entrySize = table->entrySize;
 
821
    hashShift = table->hashShift;
 
822
    sizeLog2 = JS_DHASH_BITS - hashShift;
 
823
    tableSize = JS_DHASH_TABLE_SIZE(table);
 
824
    sizeMask = JS_BITMASK(sizeLog2);
 
825
    chainCount = maxChainLen = 0;
 
826
    hash2 = 0;
 
827
    sqsum = 0;
 
828
 
 
829
    for (i = 0; i < tableSize; i++) {
 
830
        entry = (JSDHashEntryHdr *)entryAddr;
 
831
        entryAddr += entrySize;
 
832
        if (!ENTRY_IS_LIVE(entry))
 
833
            continue;
 
834
        hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
 
835
        saveHash1 = hash1;
 
836
        probe = ADDRESS_ENTRY(table, hash1);
 
837
        chainLen = 1;
 
838
        if (probe == entry) {
 
839
            /* Start of a (possibly unit-length) chain. */
 
840
            chainCount++;
 
841
        } else {
 
842
            hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
 
843
                          hashShift);
 
844
            do {
 
845
                chainLen++;
 
846
                hash1 -= hash2;
 
847
                hash1 &= sizeMask;
 
848
                probe = ADDRESS_ENTRY(table, hash1);
 
849
            } while (probe != entry);
 
850
        }
 
851
        sqsum += chainLen * chainLen;
 
852
        if (chainLen > maxChainLen) {
 
853
            maxChainLen = chainLen;
 
854
            maxChainHash1 = saveHash1;
 
855
            maxChainHash2 = hash2;
 
856
        }
 
857
    }
 
858
 
 
859
    entryCount = table->entryCount;
 
860
    if (entryCount && chainCount) {
 
861
        mean = (double)entryCount / chainCount;
 
862
        variance = chainCount * sqsum - entryCount * entryCount;
 
863
        if (variance < 0 || chainCount == 1)
 
864
            variance = 0;
 
865
        else
 
866
            variance /= chainCount * (chainCount - 1);
 
867
        sigma = sqrt(variance);
 
868
    } else {
 
869
        mean = sigma = 0;
 
870
    }
 
871
 
 
872
    fprintf(fp, "Double hashing statistics:\n");
 
873
    fprintf(fp, "    table size (in entries): %u\n", tableSize);
 
874
    fprintf(fp, "          number of entries: %u\n", table->entryCount);
 
875
    fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
 
876
    fprintf(fp, "         number of searches: %u\n", table->stats.searches);
 
877
    fprintf(fp, "             number of hits: %u\n", table->stats.hits);
 
878
    fprintf(fp, "           number of misses: %u\n", table->stats.misses);
 
879
    fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
 
880
                                                     (double)table->stats.steps
 
881
                                                     / table->stats.searches :
 
882
                                                     0.);
 
883
    fprintf(fp, "     mean hash chain length: %g\n", mean);
 
884
    fprintf(fp, "         standard deviation: %g\n", sigma);
 
885
    fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
 
886
    fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
 
887
    fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
 
888
    fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
 
889
    fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
 
890
    fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
 
891
    fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
 
892
    fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
 
893
    fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
 
894
    fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
 
895
    fprintf(fp, "            number of grows: %u\n", table->stats.grows);
 
896
    fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
 
897
    fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
 
898
    fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
 
899
 
 
900
    if (dump && maxChainLen && hash2) {
 
901
        fputs("Maximum hash chain:\n", fp);
 
902
        hash1 = maxChainHash1;
 
903
        hash2 = maxChainHash2;
 
904
        entry = ADDRESS_ENTRY(table, hash1);
 
905
        i = 0;
 
906
        do {
 
907
            if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
 
908
                break;
 
909
            hash1 -= hash2;
 
910
            hash1 &= sizeMask;
 
911
            entry = ADDRESS_ENTRY(table, hash1);
 
912
        } while (JS_DHASH_ENTRY_IS_BUSY(entry));
 
913
    }
 
914
}
 
915
#endif /* JS_DHASHMETER */