Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Functions
plhash.h File Reference
#include <stdio.h>
#include "prtypes.h"

Go to the source code of this file.

Classes

struct  PLHashAllocOps
struct  PLHashEntry
struct  PLHashTable

Defines

#define PL_HASH_BITS   32 /* Number of bits in PLHashNumber */
#define HT_ENUMERATE_NEXT   0 /* continue enumerating entries */
#define HT_ENUMERATE_STOP   1 /* stop enumerating entries */
#define HT_ENUMERATE_REMOVE   2 /* remove and free the current entry */
#define HT_ENUMERATE_UNHASH   4 /* just unhash the current entry */
#define HT_FREE_VALUE   0 /* just free the entry's value */
#define HT_FREE_ENTRY   1 /* free value and entire entry */

Typedefs

typedef
typedefPR_BEGIN_EXTERN_C
struct 
PLHashEntry
typedef struct PLHashTable
typedef PRUint32 PLHashNumber
typedef PLHashNumber(PR_CALLBACKPLHashFunction )(const void *key)
typedef PRIntn(PR_CALLBACKPLHashComparator )(const void *v1, const void *v2)
typedef PRIntn(PR_CALLBACKPLHashEnumerator )(PLHashEntry *he, PRIntn i, void *arg)
typedef struct PLHashAllocOps PLHashAllocOps

Functions

 PL_NewHashTable (PRUint32 numBuckets, PLHashFunction keyHash, PLHashComparator keyCompare, PLHashComparator valueCompare, const PLHashAllocOps *allocOps, void *allocPriv)
 PL_HashTableDestroy (PLHashTable *ht)
 PL_HashTableAdd (PLHashTable *ht, const void *key, void *value)
 PL_HashTableRemove (PLHashTable *ht, const void *key)
 PL_HashTableLookup (PLHashTable *ht, const void *key)
 PL_HashTableLookupConst (PLHashTable *ht, const void *key)
 PL_HashTableEnumerateEntries (PLHashTable *ht, PLHashEnumerator f, void *arg)
 PL_HashString (const void *key)
 PL_CompareStrings (const void *v1, const void *v2)
 PL_CompareValues (const void *v1, const void *v2)
 PL_HashTableRawLookup (PLHashTable *ht, PLHashNumber keyHash, const void *key)
 PL_HashTableRawLookupConst (PLHashTable *ht, PLHashNumber keyHash, const void *key)
 PL_HashTableRawAdd (PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash, const void *key, void *value)
 PL_HashTableRawRemove (PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he)
 PL_HashTableDump (PLHashTable *ht, PLHashEnumerator dump, FILE *fp)

Class Documentation

struct PLHashTable

Definition at line 87 of file plhash.h.

Collaboration diagram for PLHashTable:
Class Members
const PLHashAllocOps * allocOps
void * allocPriv
PLHashEntry ** buckets
PLHashComparator keyCompare
PLHashFunction keyHash
PRUint32 nentries
PRUint32 shift
PLHashComparator valueCompare

Define Documentation

#define HT_ENUMERATE_NEXT   0 /* continue enumerating entries */

Definition at line 65 of file plhash.h.

Definition at line 67 of file plhash.h.

#define HT_ENUMERATE_STOP   1 /* stop enumerating entries */

Definition at line 66 of file plhash.h.

#define HT_ENUMERATE_UNHASH   4 /* just unhash the current entry */

Definition at line 68 of file plhash.h.

#define HT_FREE_ENTRY   1 /* free value and entire entry */

Definition at line 78 of file plhash.h.

#define HT_FREE_VALUE   0 /* just free the entry's value */

Definition at line 77 of file plhash.h.

#define PL_HASH_BITS   32 /* Number of bits in PLHashNumber */

Definition at line 51 of file plhash.h.


Typedef Documentation

Definition at line 53 of file plhash.h.

typedef typedefPR_BEGIN_EXTERN_C struct PLHashEntry

Definition at line 48 of file plhash.h.

typedef PRIntn(PR_CALLBACK * PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg)

Definition at line 58 of file plhash.h.

Definition at line 52 of file plhash.h.

Definition at line 50 of file plhash.h.

typedef struct PLHashTable

Definition at line 49 of file plhash.h.


Function Documentation

PL_CompareStrings ( const void v1,
const void v2 
)

Definition at line 532 of file plhash.c.

{
    return strcmp((const char*)v1, (const char*)v2) == 0;
}

Here is the caller graph for this function:

PL_CompareValues ( const void v1,
const void v2 
)

Definition at line 538 of file plhash.c.

{
    return v1 == v2;
}

Here is the caller graph for this function:

PL_HashString ( const void key)

Definition at line 520 of file plhash.c.

{
    PLHashNumber h;
    const PRUint8 *s;

    h = 0;
    for (s = (const PRUint8*)key; *s; s++)
        h = (h >> 28) ^ (h << 4) ^ *s;
    return h;
}

Here is the caller graph for this function:

PL_HashTableAdd ( PLHashTable ht,
const void key,
void value 
)

Definition at line 304 of file plhash.c.

{
    PLHashNumber keyHash;
    PLHashEntry *he, **hep;

    keyHash = (*ht->keyHash)(key);
    hep = PL_HashTableRawLookup(ht, keyHash, key);
    if ((he = *hep) != 0) {
        /* Hit; see if values match */
        if ((*ht->valueCompare)(he->value, value)) {
            /* key,value pair is already present in table */
            return he;
        }
        if (he->value)
            (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
        he->value = value;
        return he;
    }
    return PL_HashTableRawAdd(ht, hep, keyHash, key, value);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 158 of file plhash.c.

{
    PRUint32 i, n;
    PLHashEntry *he, *next;
    const PLHashAllocOps *allocOps = ht->allocOps;
    void *allocPriv = ht->allocPriv;

    n = NBUCKETS(ht);
    for (i = 0; i < n; i++) {
        for (he = ht->buckets[i]; he; he = next) {
            next = he->next;
            (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
        }
    }
#ifdef DEBUG
    memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
#endif
    (*allocOps->freeTable)(allocPriv, ht->buckets);
#ifdef DEBUG
    memset(ht, 0xDB, sizeof *ht);
#endif
    (*allocOps->freeTable)(allocPriv, ht);
}

Here is the call graph for this function:

PL_HashTableDump ( PLHashTable ht,
PLHashEnumerator  dump,
FILE fp 
)

Definition at line 508 of file plhash.c.

{
    int count;

    count = PL_HashTableEnumerateEntries(ht, dump, fp);
#ifdef HASHMETER
    PL_HashTableDumpMeter(ht, dump, fp);
#endif
    return count;
}

Here is the call graph for this function:

Definition at line 421 of file plhash.c.

{
    PLHashEntry *he, **hep;
    PRUint32 i, nbuckets;
    int rv, n = 0;
    PLHashEntry *todo = 0;

    nbuckets = NBUCKETS(ht);
    for (i = 0; i < nbuckets; i++) {
        hep = &ht->buckets[i];
        while ((he = *hep) != 0) {
            rv = (*f)(he, n, arg);
            n++;
            if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
                *hep = he->next;
                if (rv & HT_ENUMERATE_REMOVE) {
                    he->next = todo;
                    todo = he;
                }
            } else {
                hep = &he->next;
            }
            if (rv & HT_ENUMERATE_STOP) {
                goto out;
            }
        }
    }

out:
    hep = &todo;
    while ((he = *hep) != 0) {
        PL_HashTableRawRemove(ht, hep, he);
    }
    return n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PL_HashTableLookup ( PLHashTable ht,
const void key 
)

Definition at line 385 of file plhash.c.

{
    PLHashNumber keyHash;
    PLHashEntry *he, **hep;

    keyHash = (*ht->keyHash)(key);
    hep = PL_HashTableRawLookup(ht, keyHash, key);
    if ((he = *hep) != 0) {
        return he->value;
    }
    return 0;
}

Here is the call graph for this function:

Definition at line 402 of file plhash.c.

{
    PLHashNumber keyHash;
    PLHashEntry *he, **hep;

    keyHash = (*ht->keyHash)(key);
    hep = PL_HashTableRawLookupConst(ht, keyHash, key);
    if ((he = *hep) != 0) {
        return he->value;
    }
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PL_HashTableRawAdd ( PLHashTable ht,
PLHashEntry **  hep,
PLHashNumber  keyHash,
const void key,
void value 
)

Definition at line 246 of file plhash.c.

{
    PRUint32 i, n;
    PLHashEntry *he, *next, **oldbuckets;
    PRSize nb;

    /* Grow the table if it is overloaded */
    n = NBUCKETS(ht);
    if (ht->nentries >= OVERLOADED(n)) {
        oldbuckets = ht->buckets;
#if defined(WIN16)
        if (2 * n > 16000)
            return 0;
#endif  /* WIN16 */
        nb = 2 * n * sizeof(PLHashEntry *);
        ht->buckets = (PLHashEntry**)
            ((*ht->allocOps->allocTable)(ht->allocPriv, nb));
        if (!ht->buckets) {
            ht->buckets = oldbuckets;
            return 0;
        }
        memset(ht->buckets, 0, nb);
#ifdef HASHMETER
        ht->ngrows++;
#endif
        ht->shift--;

        for (i = 0; i < n; i++) {
            for (he = oldbuckets[i]; he; he = next) {
                next = he->next;
                hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
                PR_ASSERT(*hep == 0);
                he->next = 0;
                *hep = he;
            }
        }
#ifdef DEBUG
        memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
#endif
        (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
        hep = PL_HashTableRawLookup(ht, keyHash, key);
    }

    /* Make a new key value entry */
    he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
    if (!he)
       return 0;
    he->keyHash = keyHash;
    he->key = key;
    he->value = value;
    he->next = *hep;
    *hep = he;
    ht->nentries++;
    return he;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PL_HashTableRawLookup ( PLHashTable ht,
PLHashNumber  keyHash,
const void key 
)

Definition at line 188 of file plhash.c.

{
    PLHashEntry *he, **hep, **hep0;
    PLHashNumber h;

#ifdef HASHMETER
    ht->nlookups++;
#endif
    h = keyHash * GOLDEN_RATIO;
    h >>= ht->shift;
    hep = hep0 = &ht->buckets[h];
    while ((he = *hep) != 0) {
        if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
            /* Move to front of chain if not already there */
            if (hep != hep0) {
                *hep = he->next;
                he->next = *hep0;
                *hep0 = he;
            }
            return hep0;
        }
        hep = &he->next;
#ifdef HASHMETER
        ht->nsteps++;
#endif
    }
    return hep;
}

Here is the caller graph for this function:

PL_HashTableRawLookupConst ( PLHashTable ht,
PLHashNumber  keyHash,
const void key 
)

Definition at line 221 of file plhash.c.

{
    PLHashEntry *he, **hep;
    PLHashNumber h;

#ifdef HASHMETER
    ht->nlookups++;
#endif
    h = keyHash * GOLDEN_RATIO;
    h >>= ht->shift;
    hep = &ht->buckets[h];
    while ((he = *hep) != 0) {
        if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
            break;
        }
        hep = &he->next;
#ifdef HASHMETER
        ht->nsteps++;
#endif
    }
    return hep;
}

Here is the caller graph for this function:

PL_HashTableRawRemove ( PLHashTable ht,
PLHashEntry **  hep,
PLHashEntry he 
)

Definition at line 326 of file plhash.c.

{
    PRUint32 i, n;
    PLHashEntry *next, **oldbuckets;
    PRSize nb;

    *hep = he->next;
    (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);

    /* Shrink table if it's underloaded */
    n = NBUCKETS(ht);
    if (--ht->nentries < UNDERLOADED(n)) {
        oldbuckets = ht->buckets;
        nb = n * sizeof(PLHashEntry*) / 2;
        ht->buckets = (PLHashEntry**)(
            (*ht->allocOps->allocTable)(ht->allocPriv, nb));
        if (!ht->buckets) {
            ht->buckets = oldbuckets;
            return;
        }
        memset(ht->buckets, 0, nb);
#ifdef HASHMETER
        ht->nshrinks++;
#endif
        ht->shift++;

        for (i = 0; i < n; i++) {
            for (he = oldbuckets[i]; he; he = next) {
                next = he->next;
                hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
                PR_ASSERT(*hep == 0);
                he->next = 0;
                *hep = he;
            }
        }
#ifdef DEBUG
        memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
#endif
        (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

PL_HashTableRemove ( PLHashTable ht,
const void key 
)

Definition at line 369 of file plhash.c.

{
    PLHashNumber keyHash;
    PLHashEntry *he, **hep;

    keyHash = (*ht->keyHash)(key);
    hep = PL_HashTableRawLookup(ht, keyHash, key);
    if ((he = *hep) == 0)
        return PR_FALSE;

    /* Hit; remove element */
    PL_HashTableRawRemove(ht, hep, he);
    return PR_TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PL_NewHashTable ( PRUint32  numBuckets,
PLHashFunction  keyHash,
PLHashComparator  keyCompare,
PLHashComparator  valueCompare,
const PLHashAllocOps allocOps,
void allocPriv 
)

Definition at line 112 of file plhash.c.

{
    PLHashTable *ht;
    PRSize nb;

    if (n <= MINBUCKETS) {
        n = MINBUCKETSLOG2;
    } else {
        n = PR_CeilingLog2(n);
        if ((PRInt32)n < 0)
            return 0;
    }

    if (!allocOps) allocOps = &defaultHashAllocOps;

    ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));
    if (!ht)
       return 0;
    memset(ht, 0, sizeof *ht);
    ht->shift = PL_HASH_BITS - n;
    n = 1 << n;
#if defined(WIN16)
    if (n > 16000) {
        (*allocOps->freeTable)(allocPriv, ht);
        return 0;
    }
#endif  /* WIN16 */
    nb = n * sizeof(PLHashEntry *);
    ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));
    if (!ht->buckets) {
        (*allocOps->freeTable)(allocPriv, ht);
        return 0;
    }
    memset(ht->buckets, 0, nb);

    ht->keyHash = keyHash;
    ht->keyCompare = keyCompare;
    ht->valueCompare = valueCompare;
    ht->allocOps = allocOps;
    ht->allocPriv = allocPriv;
    return ht;
}

Here is the call graph for this function:

Here is the caller graph for this function: