The Mozilla
Organization
Our Mission
Who We Are
Getting Involved
Community
Editorials
What's New
Development
Roadmap
Module Owners
Blue Sky
Projects
Status
Tools
Products
Source Code
Binaries
Documentation
License Terms
Bug Reports
Search
Feedback


Hash Tables

This chapter describes the hash table functions in the plds (portable library -- data structures) library of NSPR. The hash table library functions are declared in the header file plhash.h.

Warning: The NSPR hash table library functions are not thread safe.

A hash table lookup may change the internal organization of the hash table (to speed up future lookups).

Hash Table Types and Constants

PLHashEntry

Syntax
typedef struct PLHashEntry PLHashEntry;
Description
PLHashEntry is a structure that represents an entry in the hash table. An entry has a key and a value, represented by the following fields in the PLHashEntry structure. 
    const void *key;
    void *value;
The key field is a pointer to an opaque key. The value field is a pointer to an opaque value. If the key of an entry is an integral value that can fit into a void * pointer, you can just cast the key itself to void * and store it in the key field. Similarly, if the value of an entry is an integral value that can fit into a void * pointer, you can cast the value itself to void * and store it in the value field..

Warning: There are other fields in the PLHashEntry structure besides key and value. These fields are for use by the hash table library functions and the user should not tamper with them.

PLHashTable

Syntax
typedef struct PLHashTable PLHashTable;
Description
The opaque PLHashTable structure represents a hash table. Entries in the table have the type PLHashEntry and are organized into buckets. The number of buckets in a hash table may be changed by the library functions during the lifetime of the table to optimize speed and space.

A new hash table is created by the PL_NewHashTable function, and destroyed by the PL_HashTableDestroy function.

PLHashNumber

Syntax
typedef PRUint32 PLHashNumber;

#define PL_HASH_BITS 32

Description
PLHashNumber is an unsigned 32-bit integer. PLHashNumber is the data type of the return value of a hash function. A hash function maps a key to a hash number, which is then used to compute the index of the bucket.

The macro PL_HASH_BITS is the size (in bits) of the PLHashNumber datatype and has the value of 32.

See Also
PLHashFunction.

PLHashFunction

Syntax
typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key);
Description
PLHashNumber is a function type that maps the key of a hash table entry to a hash number.
See Also
PL_HashString.

PLHashComparator

Syntax
typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2);
Description
PLHashComparator is a function type that compares two values of an unspecified type. It returns a nonzero value if the two values are equal, and 0 if the two values are not equal. PLHashComparator defines the meaning of equality for the unspecified type.

For convenience, two comparator functions are provided. PL_CompareStrings compare two character strings using strcmp. PL_CompareValues compares the values of the arguments v1 and v2 numerically.

Remark
The return value of PLHashComparator functions should be of type PRBool.
See Also
PL_CompareStrings, PL_CompareValues.

PLHashEnumerator

Syntax
typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn index, void *arg);

/* Return value */
#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 */
Description
PLHashEnumerator is a function type used in the enumerating a hash table. When all the table entries are enumerated, each entry is passed to a user-specified function of type PLHashEnumerator with the hash table entry, an integer index, and an arbitrary piece of user data as argument.
Remark
It is not clear what the meaning of HT_ENUMERATE_UNHASH is. In the current implementation, it will leave the hash table in an inconsistent state (the entries are unlinked from the table, they are not freed, but the entry count (the nentries field of the PLHashTable structure) is not decremented).
See Also
PL_HashTableEnumerateEntries.

PLHashAllocOps

Syntax
typedef struct PLHashAllocOps {
    void *(PR_CALLBACK *allocTable)(void *pool, PRSize size);
    void (PR_CALLBACK *freeTable)(void *pool, void *item);
    PLHashEntry *(PR_CALLBACK *allocEntry)(void *pool, const void *key);
    void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag);
} PLHashAllocOps;

#define HT_FREE_VALUE 0 /* just free the entry's value */
#define HT_FREE_ENTRY 1 /* free value and entire entry */
Description
A user of the hash table functions can provide his own memory allocation functions. A pair of functions is used to allocate and tree the table, and another pair of functions is used to allocate and free the table entries.

The first argument, pool, for all four functions is a void * pointer that is a piece of data for the memory allocator. Typically pool points to a memory pool used by the memory allocator.

The freeEntry function does not need to free the value of the entry. If flag is HT_FREE_ENTRY, the
function frees the entry.

Remark
The key argument for the allocEntry function does not seem to be useful. It is unused in the default allocEntry function.

Hash Table Functions

PL_NewHashTable

Create a new hash table.
Syntax
PLHashTable *PL_NewHashTable(
    PRUint32 numBuckets,
    PLHashFunction keyHash,
    PLHashComparator keyCompare,
    PLHashComparator valueCompare,
    const PLHashAllocOps *allocOps,
    void *allocPriv
);
Description
PL_NewHashTable creates a new hash table. The argument numBuckets is the number of buckets in the hash table. The table has at least 16 buckets. You can pass a value of 0 as numBuckets to create the default number of buckets in the new table. The argument keyHash is a hash function pointer of type PLHashFunction. The arguments keyCompare and valueCompare are functions of type PLHashComparator that the hash table library functions use to compare the keys and the values of entries.

The argument allocOps points to a PLHashAllocOps structure that must exist throughout the lifetime of the new hash table. The hash table library functions do not make a copy of this structure. When the allocation functions in allocOps are invoked, the allocation private data allocPriv is passed as the first argument (pool). You can specify a NULL value for allocOps to use the default allocation functions. If allocOps is NULL, allocPriv is ignored. Note that the default freeEntry function does not free the value of the entry.

PL_HashTableDestroy

Free the table and all the entries.
Syntax
void PL_HashTableDestroy(PLHashTable *ht);
Description
PL_HashTableDestroy frees all the entries in the table and the table itself. The entries are freed by the freeEntry function (with the HT_FREE_ENTRY flag) in the allocOps structure supplied when the table was created.

PL_HashTableAdd

Add a new entry with the specified key and value to the hash table.
Syntax
PLHashEntry *PL_HashTableAdd(PLHashTable *ht, const void *key, void *value);
Description
Add a new entry with the specified key and value to the hash table. A pointer to the new entry is returned.

If an entry with the same key already exists in the table, the freeEntry function is invoked with the HT_FREE_VALUE flag. You can write your freeEntry function to free the value of the specified entry if the old value should be freed. The default freeEntry function does not free the value of the entry.

PL_HashTableAdd returns NULL if there is not enough memory to create a new entry.

It doubles the number of buckets if the table is overloaded.

PL_HashTableRemove

Remove the entry with the specified key from the hash table.
Syntax
PRBool PL_HashTableRemove(PLHashTable *ht, const void *key);
Description
PL_HashTableRemove removes the entry with the specified key from the hash table. If there is no entry in the table with the specified key, PL_HashTableRemove returns PR_FALSE. If the entry exists, PL_HashTableRemove removes the entry from the table, invokes freeEntry with the HT_FREE_ENTRY flag to frees the entry, and returns PR_TRUE.

If the table is underloaded, PL_HashTableRemove also shrinks the number of buckets by half.

Remark
This function should return PRStatus.

PL_HashTableLookup

Look up the entry with the specified key and return its value.
Syntax
void *PL_HashTableLookup(PLHashTable *ht, const void *key);
Description
PL_HashTableLookup looks up the entry with the specified key in the hash table and returns its value. If there is no entry with the specified key, PL_HashTableLookup returns NULL. This means that one cannot tell whether a NULL return value means the entry does not exist or the value of the entry is NULL. Keep this ambiguity in mind if you want to store NULL values in a hash table.

PL_HashTableEnumerateEntries

Enumerate all the entries in the hash table, invoking the specified function on each entry.
Syntax
PRIntn PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg);
Description
The entries are enumerated in an unspecified order. For each entry, the enumerator function is invoked with the entry, the index (in the sequence of enumeration, starting from 0) of the entry, and arg as arguments.

PL_HashString

A general-purpose hash function for character strings.
Syntax
PLHashNumber PL_HashString(const void *key);
Description
PL_HashString can be used as the key hash function for a hash table if the key is a character string.

PL_CompareStrings

Compare two character strings.
Syntax
PRIntn PL_CompareStrings(const void *v1, const void *v2);
Description
PL_CompareStrings compares v1 and v2 as character strings using strcmp. If the two strings are equal, it returns 1. If the two strings are not equal, it returns 0.

PL_CompareStrings can be used as the comparator function for string-valued key or entry value.

PL_CompareValues

Compare two void * values numerically.
Syntax
PRIntn PL_CompareValues(const void *v1, const void *v2);
Description
PL_CompareValues compares the two void * values v1 and v2 numerically, i.e., it returns the value of the expression v1 == v2.

PL_CompareValues can be used as the comparator function for integer or pointer-valued key or entry value.

Last updated: Wed Jul 15 11:41:15 PDT 1998
Copyright © 1998 Netscape Communications Corporation

Copyright © 1998 The Mozilla Organization.