Back to index

lightning-sunbird  0.9+nobinonly
Defines | Functions | Variables
pldhash.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "prbit.h"
#include "pldhash.h"
#include "nsDebug.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   ((PLDHashNumber) 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)   PL_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)   ((PLDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))

Functions

voidPL_DHashAllocTable (PLDHashTable *table, PRUint32 nbytes)
void PL_DHashFreeTable (PLDHashTable *table, void *ptr)
PLDHashNumber PL_DHashStringKey (PLDHashTable *table, const void *key)
const voidPL_DHashGetKeyStub (PLDHashTable *table, PLDHashEntryHdr *entry)
PLDHashNumber PL_DHashVoidPtrKeyStub (PLDHashTable *table, const void *key)
PRBool PL_DHashMatchEntryStub (PLDHashTable *table, const PLDHashEntryHdr *entry, const void *key)
PRBool PL_DHashMatchStringKey (PLDHashTable *table, const PLDHashEntryHdr *entry, const void *key)
void PL_DHashMoveEntryStub (PLDHashTable *table, const PLDHashEntryHdr *from, PLDHashEntryHdr *to)
void PL_DHashClearEntryStub (PLDHashTable *table, PLDHashEntryHdr *entry)
void PL_DHashFreeStringKey (PLDHashTable *table, PLDHashEntryHdr *entry)
void PL_DHashFinalizeStub (PLDHashTable *table)
const PLDHashTableOpsPL_DHashGetStubOps (void)
PLDHashTablePL_NewDHashTable (const PLDHashTableOps *ops, void *data, PRUint32 entrySize, PRUint32 capacity)
void PL_DHashTableDestroy (PLDHashTable *table)
PRBool PL_DHashTableInit (PLDHashTable *table, const PLDHashTableOps *ops, void *data, PRUint32 entrySize, PRUint32 capacity)
void PL_DHashTableSetAlphaBounds (PLDHashTable *table, float maxAlpha, float minAlpha)
void PL_DHashTableFinish (PLDHashTable *table)
static PLDHashEntryHdr
*PL_DHASH_FASTCALL 
SearchTable (PLDHashTable *table, const void *key, PLDHashNumber keyHash, PLDHashOperator op)
static PRBool ChangeTable (PLDHashTable *table, int deltaLog2)
PLDHashEntryHdr *PL_DHASH_FASTCALL PL_DHashTableOperate (PLDHashTable *table, const void *key, PLDHashOperator op)
void PL_DHashTableRawRemove (PLDHashTable *table, PLDHashEntryHdr *entry)
PRUint32 PL_DHashTableEnumerate (PLDHashTable *table, PLDHashEnumerator etor, void *arg)

Variables

static const PLDHashTableOps stub_ops

Define Documentation

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

Definition at line 346 of file pldhash.c.

Definition at line 334 of file pldhash.c.

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

Definition at line 82 of file pldhash.c.

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

Definition at line 339 of file pldhash.c.

Definition at line 338 of file pldhash.c.

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

Definition at line 337 of file pldhash.c.

Definition at line 80 of file pldhash.c.

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

Definition at line 319 of file pldhash.c.

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

Definition at line 320 of file pldhash.c.

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

Definition at line 81 of file pldhash.c.

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

Definition at line 335 of file pldhash.c.

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

Definition at line 336 of file pldhash.c.

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

Definition at line 342 of file pldhash.c.

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

Definition at line 267 of file pldhash.c.

#define METER (   x)    /* nothing */

Definition at line 57 of file pldhash.c.

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

Definition at line 268 of file pldhash.c.


Function Documentation

static PRBool ChangeTable ( PLDHashTable table,
int  deltaLog2 
) [static]

Definition at line 471 of file pldhash.c.

{
    int oldLog2, newLog2;
    PRUint32 oldCapacity, newCapacity;
    char *newEntryStore, *oldEntryStore, *oldEntryAddr;
    PRUint32 entrySize, i, nbytes;
    PLDHashEntryHdr *oldEntry, *newEntry;
    PLDHashGetKey getKey;
    PLDHashMoveEntry moveEntry;
#ifdef DEBUG
    PRUint32 recursionLevel;
#endif

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

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

    /* We can't fail from here on, so update table parameters. */
#ifdef DEBUG
    recursionLevel = RECURSION_LEVEL(table);
#endif
    table->hashShift = PL_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 = (PLDHashEntryHdr *)oldEntryAddr;
        if (ENTRY_IS_LIVE(oldEntry)) {
            oldEntry->keyHash &= ~COLLISION_FLAG;
            newEntry = SearchTable(table, getKey(table, oldEntry),
                                   oldEntry->keyHash, PL_DHASH_ADD);
            NS_ASSERTION(PL_DHASH_ENTRY_IS_FREE(newEntry),
                         "PL_DHASH_ENTRY_IS_FREE(newEntry)");
            moveEntry(table, oldEntry, newEntry);
            newEntry->keyHash = oldEntry->keyHash;
        }
        oldEntryAddr += entrySize;
    }

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

Here is the call graph for this function:

Here is the caller graph for this function:

void* PL_DHashAllocTable ( PLDHashTable table,
PRUint32  nbytes 
)

Definition at line 87 of file pldhash.c.

{
    return malloc(nbytes);
}

Here is the caller graph for this function:

Definition at line 155 of file pldhash.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 170 of file pldhash.c.

{
}

Here is the caller graph for this function:

Definition at line 161 of file pldhash.c.

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

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

Here is the call graph for this function:

void PL_DHashFreeTable ( PLDHashTable table,
void ptr 
)

Definition at line 93 of file pldhash.c.

{
    free(ptr);
}

Here is the caller graph for this function:

Definition at line 111 of file pldhash.c.

{
    PLDHashEntryStub *stub = (PLDHashEntryStub *)entry;

    return stub->key;
}

Here is the caller graph for this function:

Definition at line 187 of file pldhash.c.

{
    return &stub_ops;
}

Here is the caller graph for this function:

Definition at line 125 of file pldhash.c.

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

    return stub->key == key;
}

Here is the caller graph for this function:

Definition at line 135 of file pldhash.c.

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

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

Here is the caller graph for this function:

Definition at line 147 of file pldhash.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 99 of file pldhash.c.

{
    PLDHashNumber h;
    const unsigned char *s;

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

Here is the caller graph for this function:

Definition at line 209 of file pldhash.c.

{
    PL_DHashTableFinish(table);
    free(table);
}

Here is the call graph for this function:

Here is the caller graph for this function:

PRUint32 PL_DHashTableEnumerate ( PLDHashTable table,
PLDHashEnumerator  etor,
void arg 
)

Definition at line 664 of file pldhash.c.

{
    char *entryAddr, *entryLimit;
    PRUint32 i, capacity, entrySize, ceiling;
    PRBool didRemove;
    PLDHashEntryHdr *entry;
    PLDHashOperator op;

    INCREMENT_RECURSION_LEVEL(table);

    entryAddr = table->entryStore;
    entrySize = table->entrySize;
    capacity = PL_DHASH_TABLE_SIZE(table);
    entryLimit = entryAddr + capacity * entrySize;
    i = 0;
    didRemove = PR_FALSE;
    while (entryAddr < entryLimit) {
        entry = (PLDHashEntryHdr *)entryAddr;
        if (ENTRY_IS_LIVE(entry)) {
            op = etor(table, entry, i++, arg);
            if (op & PL_DHASH_REMOVE) {
                METER(table->stats.removeEnums++);
                PL_DHashTableRawRemove(table, entry);
                didRemove = PR_TRUE;
            }
            if (op & PL_DHASH_STOP)
                break;
        }
        entryAddr += entrySize;
    }

    NS_ASSERTION(!didRemove || RECURSION_LEVEL(table) == 1,
                 "!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 > PL_DHASH_MIN_SIZE &&
          table->entryCount <= MIN_LOAD(table, capacity)))) {
        METER(table->stats.enumShrinks++);
        capacity = table->entryCount;
        capacity += capacity >> 1;
        if (capacity < PL_DHASH_MIN_SIZE)
            capacity = PL_DHASH_MIN_SIZE;

        PR_CEILING_LOG2(ceiling, capacity);
        ceiling -= PL_DHASH_BITS - table->hashShift;

        (void) ChangeTable(table, ceiling);
    }

    DECREMENT_RECURSION_LEVEL(table);

    return i;
}

Here is the call graph for this function:

Definition at line 350 of file pldhash.c.

{
    char *entryAddr, *entryLimit;
    PRUint32 entrySize;
    PLDHashEntryHdr *entry;

#ifdef DEBUG_XXXbrendan
    static FILE *dumpfp = NULL;
    if (!dumpfp) dumpfp = fopen("/tmp/pldhash.bigdump", "w");
    if (dumpfp) {
#ifdef MOZILLA_CLIENT
        NS_TraceStack(1, dumpfp);
#endif
        PL_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 + PL_DHASH_TABLE_SIZE(table) * entrySize;
    while (entryAddr < entryLimit) {
        entry = (PLDHashEntryHdr *)entryAddr;
        if (ENTRY_IS_LIVE(entry)) {
            METER(table->stats.removeEnums++);
            table->ops->clearEntry(table, entry);
        }
        entryAddr += entrySize;
    }

    DECREMENT_RECURSION_LEVEL(table);
    NS_ASSERTION(RECURSION_LEVEL(table) == 0,
                 "RECURSION_LEVEL(table) == 0");

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

Here is the call graph for this function:

PRBool PL_DHashTableInit ( PLDHashTable table,
const PLDHashTableOps ops,
void data,
PRUint32  entrySize,
PRUint32  capacity 
)

Definition at line 216 of file pldhash.c.

{
    int log2;
    PRUint32 nbytes;

#ifdef DEBUG
    if (entrySize > 10 * sizeof(void *)) {
        fprintf(stderr,
                "pldhash: 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 < PL_DHASH_MIN_SIZE)
        capacity = PL_DHASH_MIN_SIZE;

    PR_CEILING_LOG2(log2, capacity);

    capacity = PR_BIT(log2);
    if (capacity >= PL_DHASH_SIZE_LIMIT)
        return PR_FALSE;
    table->hashShift = PL_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 PR_FALSE;
    memset(table->entryStore, 0, nbytes);
    METER(memset(&table->stats, 0, sizeof table->stats));

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

    return PR_TRUE;
}

Here is the call graph for this function:

Definition at line 536 of file pldhash.c.

{
    PLDHashNumber keyHash;
    PLDHashEntryHdr *entry;
    PRUint32 size;
    int deltaLog2;

    NS_ASSERTION(op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0,
                 "op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0");
    INCREMENT_RECURSION_LEVEL(table);

    keyHash = table->ops->hashKey(table, key);
    keyHash *= PL_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 PL_DHASH_LOOKUP:
        METER(table->stats.lookups++);
        entry = SearchTable(table, key, keyHash, op);
        break;

      case PL_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 = PL_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 PL_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++);
            PL_DHashTableRawRemove(table, entry);

            /* Shrink if alpha is <= .25 and table isn't too small already. */
            size = PL_DHASH_TABLE_SIZE(table);
            if (size > PL_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:
        NS_NOTREACHED("0");
        entry = NULL;
    }

    DECREMENT_RECURSION_LEVEL(table);

    return entry;
}

Here is the call graph for this function:

Definition at line 645 of file pldhash.c.

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

    NS_ASSERTION(PL_DHASH_ENTRY_IS_LIVE(entry),
                 "PL_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:

void PL_DHashTableSetAlphaBounds ( PLDHashTable table,
float  maxAlpha,
float  minAlpha 
)

Definition at line 271 of file pldhash.c.

{
    PRUint32 size;

    /*
     * Reject obviously insane bounds, rather than trying to guess what the
     * buggy caller intended.
     */
    NS_ASSERTION(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha,
                 "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.
     */
    NS_ASSERTION(PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1,
                 "PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1");
    if (PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) < 1) {
        maxAlpha = (float)
                   (PL_DHASH_MIN_SIZE - PR_MAX(PL_DHASH_MIN_SIZE / 256, 1))
                   / PL_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).
     */
    NS_ASSERTION(minAlpha < maxAlpha / 2,
                 "minAlpha < maxAlpha / 2");
    if (minAlpha >= maxAlpha / 2) {
        size = PL_DHASH_TABLE_SIZE(table);
        minAlpha = (size * maxAlpha - PR_MAX(size / 256, 1)) / (2 * size);
    }

    table->maxAlphaFrac = (uint8)(maxAlpha * 256);
    table->minAlphaFrac = (uint8)(minAlpha * 256);
}

Here is the caller graph for this function:

Definition at line 119 of file pldhash.c.

{
    return (PLDHashNumber)(unsigned long)key >> 2;
}

Here is the caller graph for this function:

PLDHashTable* PL_NewDHashTable ( const PLDHashTableOps ops,
void data,
PRUint32  entrySize,
PRUint32  capacity 
)

Definition at line 193 of file pldhash.c.

{
    PLDHashTable *table;

    table = (PLDHashTable *) malloc(sizeof *table);
    if (!table)
        return NULL;
    if (!PL_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:

static PLDHashEntryHdr* PL_DHASH_FASTCALL SearchTable ( PLDHashTable table,
const void key,
PLDHashNumber  keyHash,
PLDHashOperator  op 
) [static]

Definition at line 395 of file pldhash.c.

{
    PLDHashNumber hash1, hash2;
    int hashShift, sizeLog2;
    PLDHashEntryHdr *entry, *firstRemoved;
    PLDHashMatchEntry matchEntry;
    PRUint32 sizeMask;

    METER(table->stats.searches++);
    NS_ASSERTION(!(keyHash & COLLISION_FLAG),
                 "!(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 (PL_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 = PL_DHASH_BITS - table->hashShift;
    hash2 = HASH2(keyHash, sizeLog2, hashShift);
    sizeMask = PR_BITMASK(sizeLog2);

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

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

        entry = ADDRESS_ENTRY(table, hash1);
        if (PL_DHASH_ENTRY_IS_FREE(entry)) {
            METER(table->stats.misses++);
            return (firstRemoved && op == PL_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 == PL_DHASH_ADD)
                entry->keyHash |= COLLISION_FLAG;
        }
    }

    /* NOTREACHED */
    return NULL;
}

Here is the caller graph for this function:


Variable Documentation