Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Enumerations | Functions
pldhash.h File Reference
#include "nscore.h"

Go to the source code of this file.

Classes

struct  PLDHashEntryHdr
struct  PLDHashTable
struct  PLDHashTableOps
struct  PLDHashEntryStub

Defines

#define PL_DHASH_FASTCALL
#define PL_DHASH_SIZE_LIMIT   PR_BIT(24)
#define PL_DHASH_MIN_SIZE   16
#define PL_DHASH_BITS   32
#define PL_DHASH_GOLDEN_RATIO   0x9E3779B9U
#define PL_DHASH_ENTRY_IS_FREE(entry)   ((entry)->keyHash == 0)
#define PL_DHASH_ENTRY_IS_BUSY(entry)   (!PL_DHASH_ENTRY_IS_FREE(entry))
#define PL_DHASH_ENTRY_IS_LIVE(entry)   ((entry)->keyHash >= 2)
#define PL_DHASH_TABLE_SIZE(table)   PR_BIT(PL_DHASH_BITS - (table)->hashShift)
#define PL_DHASH_MIN_ALPHA(table, k)

Typedefs

typedef PRUint32 PLDHashNumber
typedef struct PLDHashEntryHdr
typedef struct PLDHashEntryStub
typedef struct PLDHashTable
typedef struct PLDHashTableOps
typedef void *(* PR_CALLBACK )(PLDHashTable *table, PRUint32 nbytes)
typedef enum PLDHashOperator PLDHashOperator

Enumerations

enum  PLDHashOperator {
  PL_DHASH_LOOKUP = 0, PL_DHASH_ADD = 1, PL_DHASH_REMOVE = 2, PL_DHASH_NEXT = 0,
  PL_DHASH_STOP = 1
}

Functions

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

Class Documentation

struct PLDHashTableOps

Definition at line 337 of file pldhash.h.

Class Members
PLDHashAllocTable allocTable
PLDHashClearEntry clearEntry
PLDHashFinalize finalize
PLDHashFreeTable freeTable
PLDHashGetKey getKey
PLDHashHashKey hashKey
PLDHashInitEntry initEntry
PLDHashMatchEntry matchEntry
PLDHashMoveEntry moveEntry
struct PLDHashEntryStub

Definition at line 365 of file pldhash.h.

Class Members
PLDHashEntryHdr hdr
const void * key

Define Documentation

Definition at line 74 of file pldhash.h.

Definition at line 117 of file pldhash.h.

Definition at line 116 of file pldhash.h.

Definition at line 118 of file pldhash.h.

Definition at line 52 of file pldhash.h.

#define PL_DHASH_GOLDEN_RATIO   0x9E3779B9U

Definition at line 75 of file pldhash.h.

#define PL_DHASH_MIN_ALPHA (   table,
 
)
Value:
((float)((table)->entrySize / sizeof(void *) - 1)                         \
     / ((table)->entrySize / sizeof(void *) + (k)))

Definition at line 453 of file pldhash.h.

Definition at line 65 of file pldhash.h.

Definition at line 61 of file pldhash.h.

#define PL_DHASH_TABLE_SIZE (   table)    PR_BIT(PL_DHASH_BITS - (table)->hashShift)

Definition at line 231 of file pldhash.h.


Typedef Documentation

typedef struct PLDHashEntryHdr

Definition at line 79 of file pldhash.h.

typedef struct PLDHashEntryStub

Definition at line 80 of file pldhash.h.

Definition at line 78 of file pldhash.h.

typedef struct PLDHashTable

Definition at line 81 of file pldhash.h.

static struct PLDHashTableOps

Definition at line 239 of file pldhash.h.


Enumeration Type Documentation

Enumerator:
PL_DHASH_LOOKUP 
PL_DHASH_ADD 
PL_DHASH_REMOVE 
PL_DHASH_NEXT 
PL_DHASH_STOP 

Definition at line 472 of file pldhash.h.

                             {
    PL_DHASH_LOOKUP = 0,        /* lookup entry */
    PL_DHASH_ADD = 1,           /* add entry */
    PL_DHASH_REMOVE = 2,        /* remove entry, or enumerator says remove */
    PL_DHASH_NEXT = 0,          /* enumerator says continue */
    PL_DHASH_STOP = 1           /* enumerator says stop */
} PLDHashOperator;

Function Documentation

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:

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:

NS_COM_GLUE 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:

NS_COM_GLUE 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:

NS_COM_GLUE 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:

NS_COM_GLUE 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: