Back to index

lightning-sunbird  0.9+nobinonly
Defines | Functions | Variables
jsdhash.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "jsbit.h"
#include "jsdhash.h"
#include "jsutil.h"

Go to the source code of this file.

Defines

#define METER(x)   /* nothing */
#define ENTRY_STORE_EXTRA   0
#define INCREMENT_RECURSION_LEVEL(table_)   ((void)1)
#define DECREMENT_RECURSION_LEVEL(table_)   ((void)0)
#define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
#define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
#define HASH1(hash0, shift)   ((hash0) >> (shift))
#define HASH2(hash0, log2, shift)   ((((hash0) << (log2)) >> (shift)) | 1)
#define COLLISION_FLAG   ((JSDHashNumber) 1)
#define MARK_ENTRY_FREE(entry)   ((entry)->keyHash = 0)
#define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
#define ENTRY_IS_REMOVED(entry)   ((entry)->keyHash == 1)
#define ENTRY_IS_LIVE(entry)   JS_DHASH_ENTRY_IS_LIVE(entry)
#define ENSURE_LIVE_KEYHASH(hash0)   if (hash0 < 2) hash0 -= 2; else (void)0
#define MATCH_ENTRY_KEYHASH(entry, hash0)   (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
#define ADDRESS_ENTRY(table, index)   ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))

Functions

 JS_DHashAllocTable (JSDHashTable *table, uint32 nbytes)
 JS_DHashFreeTable (JSDHashTable *table, void *ptr)
 JS_DHashStringKey (JSDHashTable *table, const void *key)
 JS_DHashGetKeyStub (JSDHashTable *table, JSDHashEntryHdr *entry)
 JS_DHashVoidPtrKeyStub (JSDHashTable *table, const void *key)
 JS_DHashMatchEntryStub (JSDHashTable *table, const JSDHashEntryHdr *entry, const void *key)
 JS_DHashMatchStringKey (JSDHashTable *table, const JSDHashEntryHdr *entry, const void *key)
 JS_DHashMoveEntryStub (JSDHashTable *table, const JSDHashEntryHdr *from, JSDHashEntryHdr *to)
 JS_DHashClearEntryStub (JSDHashTable *table, JSDHashEntryHdr *entry)
 JS_DHashFreeStringKey (JSDHashTable *table, JSDHashEntryHdr *entry)
 JS_DHashFinalizeStub (JSDHashTable *table)
 JS_DHashGetStubOps (void)
 JS_NewDHashTable (const JSDHashTableOps *ops, void *data, uint32 entrySize, uint32 capacity)
 JS_DHashTableDestroy (JSDHashTable *table)
 JS_DHashTableInit (JSDHashTable *table, const JSDHashTableOps *ops, void *data, uint32 entrySize, uint32 capacity)
 JS_DHashTableSetAlphaBounds (JSDHashTable *table, float maxAlpha, float minAlpha)
 JS_DHashTableFinish (JSDHashTable *table)
static JSDHashEntryHdr
*JS_DHASH_FASTCALL 
SearchTable (JSDHashTable *table, const void *key, JSDHashNumber keyHash, JSDHashOperator op)
static JSBool ChangeTable (JSDHashTable *table, int deltaLog2)
 JS_PUBLIC_API (JSDHashEntryHdr *)
 JS_DHashTableRawRemove (JSDHashTable *table, JSDHashEntryHdr *entry)
 JS_DHashTableEnumerate (JSDHashTable *table, JSDHashEnumerator etor, void *arg)

Variables

static const JSDHashTableOps stub_ops

Define Documentation

#define ADDRESS_ENTRY (   table,
  index 
)    ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))

Definition at line 342 of file jsdhash.c.

Definition at line 330 of file jsdhash.c.

#define DECREMENT_RECURSION_LEVEL (   table_)    ((void)0)

Definition at line 81 of file jsdhash.c.

#define ENSURE_LIVE_KEYHASH (   hash0)    if (hash0 < 2) hash0 -= 2; else (void)0

Definition at line 335 of file jsdhash.c.

Definition at line 334 of file jsdhash.c.

#define ENTRY_IS_REMOVED (   entry)    ((entry)->keyHash == 1)

Definition at line 333 of file jsdhash.c.

Definition at line 79 of file jsdhash.c.

#define HASH1 (   hash0,
  shift 
)    ((hash0) >> (shift))

Definition at line 315 of file jsdhash.c.

#define HASH2 (   hash0,
  log2,
  shift 
)    ((((hash0) << (log2)) >> (shift)) | 1)

Definition at line 316 of file jsdhash.c.

#define INCREMENT_RECURSION_LEVEL (   table_)    ((void)1)

Definition at line 80 of file jsdhash.c.

#define MARK_ENTRY_FREE (   entry)    ((entry)->keyHash = 0)

Definition at line 331 of file jsdhash.c.

#define MARK_ENTRY_REMOVED (   entry)    ((entry)->keyHash = 1)

Definition at line 332 of file jsdhash.c.

#define MATCH_ENTRY_KEYHASH (   entry,
  hash0 
)    (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))

Definition at line 338 of file jsdhash.c.

#define MAX_LOAD (   table,
  size 
)    (((table)->maxAlphaFrac * (size)) >> 8)

Definition at line 266 of file jsdhash.c.

#define METER (   x)    /* nothing */

Definition at line 56 of file jsdhash.c.

#define MIN_LOAD (   table,
  size 
)    (((table)->minAlphaFrac * (size)) >> 8)

Definition at line 267 of file jsdhash.c.


Function Documentation

static JSBool ChangeTable ( JSDHashTable table,
int  deltaLog2 
) [static]

Definition at line 465 of file jsdhash.c.

{
    int oldLog2, newLog2;
    uint32 oldCapacity, newCapacity;
    char *newEntryStore, *oldEntryStore, *oldEntryAddr;
    uint32 entrySize, i, nbytes;
    JSDHashEntryHdr *oldEntry, *newEntry;
    JSDHashGetKey getKey;
    JSDHashMoveEntry moveEntry;
#ifdef DEBUG
    uint32 recursionLevel;
#endif

    /* Look, but don't touch, until we succeed in getting new entry store. */
    oldLog2 = JS_DHASH_BITS - table->hashShift;
    newLog2 = oldLog2 + deltaLog2;
    oldCapacity = JS_BIT(oldLog2);
    newCapacity = JS_BIT(newLog2);
    if (newCapacity >= JS_DHASH_SIZE_LIMIT)
        return JS_FALSE;
    entrySize = table->entrySize;
    nbytes = newCapacity * entrySize;

    newEntryStore = table->ops->allocTable(table, nbytes + ENTRY_STORE_EXTRA);
    if (!newEntryStore)
        return JS_FALSE;

    /* We can't fail from here on, so update table parameters. */
#ifdef DEBUG
    recursionLevel = RECURSION_LEVEL(table);
#endif
    table->hashShift = JS_DHASH_BITS - newLog2;
    table->removedCount = 0;
    table->generation++;

    /* Assign the new entry store to table. */
    memset(newEntryStore, 0, nbytes);
    oldEntryAddr = oldEntryStore = table->entryStore;
    table->entryStore = newEntryStore;
    getKey = table->ops->getKey;
    moveEntry = table->ops->moveEntry;
#ifdef DEBUG
    RECURSION_LEVEL(table) = recursionLevel;
#endif

    /* Copy only live entries, leaving removed ones behind. */
    for (i = 0; i < oldCapacity; i++) {
        oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
        if (ENTRY_IS_LIVE(oldEntry)) {
            oldEntry->keyHash &= ~COLLISION_FLAG;
            newEntry = SearchTable(table, getKey(table, oldEntry),
                                   oldEntry->keyHash, JS_DHASH_ADD);
            JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
            moveEntry(table, oldEntry, newEntry);
            newEntry->keyHash = oldEntry->keyHash;
        }
        oldEntryAddr += entrySize;
    }

    table->ops->freeTable(table, oldEntryStore);
    return JS_TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

JS_DHashAllocTable ( JSDHashTable table,
uint32  nbytes 
)

Definition at line 86 of file jsdhash.c.

{
    return malloc(nbytes);
}

Definition at line 154 of file jsdhash.c.

{
    memset(entry, 0, table->entrySize);
}

Here is the call graph for this function:

Definition at line 169 of file jsdhash.c.

{
}

Definition at line 160 of file jsdhash.c.

{
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;

    free((void *) stub->key);
    memset(entry, 0, table->entrySize);
}

Here is the call graph for this function:

JS_DHashFreeTable ( JSDHashTable table,
void ptr 
)

Definition at line 92 of file jsdhash.c.

{
    free(ptr);
}
JS_DHashGetKeyStub ( JSDHashTable table,
JSDHashEntryHdr entry 
)

Definition at line 110 of file jsdhash.c.

{
    JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;

    return stub->key;
}

Definition at line 186 of file jsdhash.c.

{
    return &stub_ops;
}

Here is the caller graph for this function:

JS_DHashMatchEntryStub ( JSDHashTable table,
const JSDHashEntryHdr entry,
const void key 
)

Definition at line 124 of file jsdhash.c.

{
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;

    return stub->key == key;
}
JS_DHashMatchStringKey ( JSDHashTable table,
const JSDHashEntryHdr entry,
const void key 
)

Definition at line 134 of file jsdhash.c.

{
    const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;

    /* XXX tolerate null keys on account of sloppy Mozilla callers. */
    return stub->key == key ||
           (stub->key && key && strcmp(stub->key, key) == 0);
}

Definition at line 146 of file jsdhash.c.

{
    memcpy(to, from, table->entrySize);
}

Here is the call graph for this function:

JS_DHashStringKey ( JSDHashTable table,
const void key 
)

Definition at line 98 of file jsdhash.c.

{
    JSDHashNumber h;
    const unsigned char *s;

    h = 0;
    for (s = key; *s != '\0'; s++)
        h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
    return h;
}

Definition at line 208 of file jsdhash.c.

{
    JS_DHashTableFinish(table);
    free(table);
}

Here is the call graph for this function:

Here is the caller graph for this function:

JS_DHashTableEnumerate ( JSDHashTable table,
JSDHashEnumerator  etor,
void arg 
)

Definition at line 655 of file jsdhash.c.

{
    char *entryAddr, *entryLimit;
    uint32 i, capacity, entrySize, ceiling;
    JSBool didRemove;
    JSDHashEntryHdr *entry;
    JSDHashOperator op;

    INCREMENT_RECURSION_LEVEL(table);

    entryAddr = table->entryStore;
    entrySize = table->entrySize;
    capacity = JS_DHASH_TABLE_SIZE(table);
    entryLimit = entryAddr + capacity * entrySize;
    i = 0;
    didRemove = JS_FALSE;
    while (entryAddr < entryLimit) {
        entry = (JSDHashEntryHdr *)entryAddr;
        if (ENTRY_IS_LIVE(entry)) {
            op = etor(table, entry, i++, arg);
            if (op & JS_DHASH_REMOVE) {
                METER(table->stats.removeEnums++);
                JS_DHashTableRawRemove(table, entry);
                didRemove = JS_TRUE;
            }
            if (op & JS_DHASH_STOP)
                break;
        }
        entryAddr += entrySize;
    }

    JS_ASSERT(!didRemove || RECURSION_LEVEL(table) == 1);

    /*
     * Shrink or compress if a quarter or more of all entries are removed, or
     * if the table is underloaded according to the configured minimum alpha,
     * and is not minimal-size already.  Do this only if we removed above, so
     * non-removing enumerations can count on stable table->entryStore until
     * the next non-lookup-Operate or removing-Enumerate.
     */
    if (didRemove &&
        (table->removedCount >= capacity >> 2 ||
         (capacity > JS_DHASH_MIN_SIZE &&
          table->entryCount <= MIN_LOAD(table, capacity)))) {
        METER(table->stats.enumShrinks++);
        capacity = table->entryCount;
        capacity += capacity >> 1;
        if (capacity < JS_DHASH_MIN_SIZE)
            capacity = JS_DHASH_MIN_SIZE;

        JS_CEILING_LOG2(ceiling, capacity);
        ceiling -= JS_DHASH_BITS - table->hashShift;

        (void) ChangeTable(table, ceiling);
    }

    DECREMENT_RECURSION_LEVEL(table);

    return i;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 346 of file jsdhash.c.

{
    char *entryAddr, *entryLimit;
    uint32 entrySize;
    JSDHashEntryHdr *entry;

#ifdef DEBUG_XXXbrendan
    static FILE *dumpfp = NULL;
    if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
    if (dumpfp) {
#ifdef MOZILLA_CLIENT
        NS_TraceStack(1, dumpfp);
#endif
        JS_DHashTableDumpMeter(table, NULL, dumpfp);
        fputc('\n', dumpfp);
    }
#endif

    INCREMENT_RECURSION_LEVEL(table);

    /* Call finalize before clearing entries, so it can enumerate them. */
    table->ops->finalize(table);

    /* Clear any remaining live entries. */
    entryAddr = table->entryStore;
    entrySize = table->entrySize;
    entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
    while (entryAddr < entryLimit) {
        entry = (JSDHashEntryHdr *)entryAddr;
        if (ENTRY_IS_LIVE(entry)) {
            METER(table->stats.removeEnums++);
            table->ops->clearEntry(table, entry);
        }
        entryAddr += entrySize;
    }

    DECREMENT_RECURSION_LEVEL(table);
    JS_ASSERT(RECURSION_LEVEL(table) == 0);

    /* Free entry storage last. */
    table->ops->freeTable(table, table->entryStore);
}

Here is the call graph for this function:

Here is the caller graph for this function:

JS_DHashTableInit ( JSDHashTable table,
const JSDHashTableOps ops,
void data,
uint32  entrySize,
uint32  capacity 
)

Definition at line 215 of file jsdhash.c.

{
    int log2;
    uint32 nbytes;

#ifdef DEBUG
    if (entrySize > 10 * sizeof(void *)) {
        fprintf(stderr,
                "jsdhash: for the table at address %p, the given entrySize"
                " of %lu %s favors chaining over double hashing.\n",
                (void *)table,
                (unsigned long) entrySize,
                (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
    }
#endif

    table->ops = ops;
    table->data = data;
    if (capacity < JS_DHASH_MIN_SIZE)
        capacity = JS_DHASH_MIN_SIZE;

    JS_CEILING_LOG2(log2, capacity);

    capacity = JS_BIT(log2);
    if (capacity >= JS_DHASH_SIZE_LIMIT)
        return JS_FALSE;
    table->hashShift = JS_DHASH_BITS - log2;
    table->maxAlphaFrac = 0xC0;                 /* .75 */
    table->minAlphaFrac = 0x40;                 /* .25 */
    table->entrySize = entrySize;
    table->entryCount = table->removedCount = 0;
    table->generation = 0;
    nbytes = capacity * entrySize;

    table->entryStore = ops->allocTable(table, nbytes + ENTRY_STORE_EXTRA);
    if (!table->entryStore)
        return JS_FALSE;
    memset(table->entryStore, 0, nbytes);
    METER(memset(&table->stats, 0, sizeof table->stats));

#ifdef DEBUG
    RECURSION_LEVEL(table) = 0;
#endif

    return JS_TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 637 of file jsdhash.c.

{
    JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */

    JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
    keyHash = entry->keyHash;
    table->ops->clearEntry(table, entry);
    if (keyHash & COLLISION_FLAG) {
        MARK_ENTRY_REMOVED(entry);
        table->removedCount++;
    } else {
        METER(table->stats.removeFrees++);
        MARK_ENTRY_FREE(entry);
    }
    table->entryCount--;
}

Here is the caller graph for this function:

JS_DHashTableSetAlphaBounds ( JSDHashTable table,
float  maxAlpha,
float  minAlpha 
)

Definition at line 270 of file jsdhash.c.

{
    uint32 size;

    /*
     * Reject obviously insane bounds, rather than trying to guess what the
     * buggy caller intended.
     */
    JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
    if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
        return;

    /*
     * Ensure that at least one entry will always be free.  If maxAlpha at
     * minimum size leaves no entries free, reduce maxAlpha based on minimum
     * size and the precision limit of maxAlphaFrac's fixed point format.
     */
    JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
    if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
        maxAlpha = (float)
                   (JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
                   / JS_DHASH_MIN_SIZE;
    }

    /*
     * Ensure that minAlpha is strictly less than half maxAlpha.  Take care
     * not to truncate an entry's worth of alpha when storing in minAlphaFrac
     * (8-bit fixed point format).
     */
    JS_ASSERT(minAlpha < maxAlpha / 2);
    if (minAlpha >= maxAlpha / 2) {
        size = JS_DHASH_TABLE_SIZE(table);
        minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
    }

    table->maxAlphaFrac = (uint8)(maxAlpha * 256);
    table->minAlphaFrac = (uint8)(minAlpha * 256);
}
JS_DHashVoidPtrKeyStub ( JSDHashTable table,
const void key 
)

Definition at line 118 of file jsdhash.c.

{
    return (JSDHashNumber)(unsigned long)key >> 2;
}
JS_NewDHashTable ( const JSDHashTableOps ops,
void data,
uint32  entrySize,
uint32  capacity 
)

Definition at line 192 of file jsdhash.c.

{
    JSDHashTable *table;

    table = (JSDHashTable *) malloc(sizeof *table);
    if (!table)
        return NULL;
    if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
        free(table);
        return NULL;
    }
    return table;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 528 of file jsdhash.c.

{
    JSDHashNumber keyHash;
    JSDHashEntryHdr *entry;
    uint32 size;
    int deltaLog2;

    JS_ASSERT(op == JS_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0);
    INCREMENT_RECURSION_LEVEL(table);

    keyHash = table->ops->hashKey(table, key);
    keyHash *= JS_DHASH_GOLDEN_RATIO;

    /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
    ENSURE_LIVE_KEYHASH(keyHash);
    keyHash &= ~COLLISION_FLAG;

    switch (op) {
      case JS_DHASH_LOOKUP:
        METER(table->stats.lookups++);
        entry = SearchTable(table, key, keyHash, op);
        break;

      case JS_DHASH_ADD:
        /*
         * If alpha is >= .75, grow or compress the table.  If key is already
         * in the table, we may grow once more than necessary, but only if we
         * are on the edge of being overloaded.
         */
        size = JS_DHASH_TABLE_SIZE(table);
        if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
            /* Compress if a quarter or more of all entries are removed. */
            if (table->removedCount >= size >> 2) {
                METER(table->stats.compresses++);
                deltaLog2 = 0;
            } else {
                METER(table->stats.grows++);
                deltaLog2 = 1;
            }

            /*
             * Grow or compress table, returning null if ChangeTable fails and
             * falling through might claim the last free entry.
             */
            if (!ChangeTable(table, deltaLog2) &&
                table->entryCount + table->removedCount == size - 1) {
                METER(table->stats.addFailures++);
                entry = NULL;
                break;
            }
        }

        /*
         * Look for entry after possibly growing, so we don't have to add it,
         * then skip it while growing the table and re-add it after.
         */
        entry = SearchTable(table, key, keyHash, op);
        if (!ENTRY_IS_LIVE(entry)) {
            /* Initialize the entry, indicating that it's no longer free. */
            METER(table->stats.addMisses++);
            if (ENTRY_IS_REMOVED(entry)) {
                METER(table->stats.addOverRemoved++);
                table->removedCount--;
                keyHash |= COLLISION_FLAG;
            }
            if (table->ops->initEntry &&
                !table->ops->initEntry(table, entry, key)) {
                /* We haven't claimed entry yet; fail with null return. */
                memset(entry + 1, 0, table->entrySize - sizeof *entry);
                entry = NULL;
                break;
            }
            entry->keyHash = keyHash;
            table->entryCount++;
        }
        METER(else table->stats.addHits++);
        break;

      case JS_DHASH_REMOVE:
        entry = SearchTable(table, key, keyHash, op);
        if (ENTRY_IS_LIVE(entry)) {
            /* Clear this entry and mark it as "removed". */
            METER(table->stats.removeHits++);
            JS_DHashTableRawRemove(table, entry);

            /* Shrink if alpha is <= .25 and table isn't too small already. */
            size = JS_DHASH_TABLE_SIZE(table);
            if (size > JS_DHASH_MIN_SIZE &&
                table->entryCount <= MIN_LOAD(table, size)) {
                METER(table->stats.shrinks++);
                (void) ChangeTable(table, -1);
            }
        }
        METER(else table->stats.removeMisses++);
        entry = NULL;
        break;

      default:
        JS_ASSERT(0);
        entry = NULL;
    }

    DECREMENT_RECURSION_LEVEL(table);

    return entry;
}

Here is the call graph for this function:

static JSDHashEntryHdr* JS_DHASH_FASTCALL SearchTable ( JSDHashTable table,
const void key,
JSDHashNumber  keyHash,
JSDHashOperator  op 
) [static]

Definition at line 390 of file jsdhash.c.

{
    JSDHashNumber hash1, hash2;
    int hashShift, sizeLog2;
    JSDHashEntryHdr *entry, *firstRemoved;
    JSDHashMatchEntry matchEntry;
    uint32 sizeMask;

    METER(table->stats.searches++);
    JS_ASSERT(!(keyHash & COLLISION_FLAG));

    /* Compute the primary hash address. */
    hashShift = table->hashShift;
    hash1 = HASH1(keyHash, hashShift);
    entry = ADDRESS_ENTRY(table, hash1);

    /* Miss: return space for a new entry. */
    if (JS_DHASH_ENTRY_IS_FREE(entry)) {
        METER(table->stats.misses++);
        return entry;
    }

    /* Hit: return entry. */
    matchEntry = table->ops->matchEntry;
    if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
        METER(table->stats.hits++);
        return entry;
    }

    /* Collision: double hash. */
    sizeLog2 = JS_DHASH_BITS - table->hashShift;
    hash2 = HASH2(keyHash, sizeLog2, hashShift);
    sizeMask = JS_BITMASK(sizeLog2);

    /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
    if (ENTRY_IS_REMOVED(entry)) {
        firstRemoved = entry;
    } else {
        firstRemoved = NULL;
        if (op == JS_DHASH_ADD)
            entry->keyHash |= COLLISION_FLAG;
    }

    for (;;) {
        METER(table->stats.steps++);
        hash1 -= hash2;
        hash1 &= sizeMask;

        entry = ADDRESS_ENTRY(table, hash1);
        if (JS_DHASH_ENTRY_IS_FREE(entry)) {
            METER(table->stats.misses++);
            return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
        }

        if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
            matchEntry(table, entry, key)) {
            METER(table->stats.hits++);
            return entry;
        }

        if (ENTRY_IS_REMOVED(entry)) {
            if (!firstRemoved)
                firstRemoved = entry;
        } else {
            if (op == JS_DHASH_ADD)
                entry->keyHash |= COLLISION_FLAG;
        }
    }

    /* NOTREACHED */
    return NULL;
}

Here is the caller graph for this function:


Variable Documentation