You are currently viewing a snapshot of www.mozilla.org taken on April 21, 2008. Most of this content is highly out of date (some pages haven't been updated since the project began in 1998) and exists for historical purposes only. If there are any pages on this archive site that you think should be added back to www.mozilla.org, please file a bug.



NSPR Reference

Hash Tables (Chapter 33)

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
#include <plhash.h>

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
#include <plhash.h>

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
#include <plhash.h>

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 data type and has the value of 32.

See Also

PLHashFunction.

PLHashFunction

Syntax
#include <plhash.h>

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
#include <plhash.h>

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.

PLHashEnumerator

Syntax
#include <plhash.h>

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

The meaning of HT_ENUMERATE_UNHASH is not clear. 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.

PLHashAllocOps

Syntax
#include <plhash.h>

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

Users of the hash table functions can provide their 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
#include <plhash.h>

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

The function has the following parameters:

numBuckets
The number of buckets in the hash table.
keyHash
Hash function.
keyCompare
Function used to compare keys of entries.
valueCompare
Function used to compare keys of entries.
allocOps
A pointer to a PLHashAllocOps structure that must exist throughout the lifetime of the new hash table.
allocPriv
Passed as the first argument (pool).
Returns

The new hash table.

Description

PL_NewHashTable creates a new 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 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

Frees the table and all the entries.

Syntax
#include <plhash.h>

void PL_HashTableDestroy(PLHashTable *ht);
Parameters

The function has the following parameters:

ht
A pointer to the hash table to be destroyed.
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
#include <plhash.h>

PLHashEntry *PL_HashTableAdd(
   PLHashTable *ht, 
   const void *key, 
   void *value);
Parameters

The function has the following parameters:

ht
A pointer to the the hash table to which to add the entry.
key
A pointer to the key for the entry to be added.
value
A pointer to the value for the entry to be added.
Returns

A pointer to the new entry.

Description

Add a new entry with the specified key and value to the hash table.

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

Removes the entry with the specified key from the hash table.

Syntax
#include <plhash.h>

PRBool PL_HashTableRemove(
   PLHashTable *ht, 
   const void *key);
Parameters

The function has the following parameters:

ht
A pointer to the hash table from which to remove the entry.
key
A pointer to the key for the entry to be removed.
Description

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

Looks up the entry with the specified key and return its value.

Syntax
#include <plhash.h>

void *PL_HashTableLookup(
   PLHashTable *ht, 
   const void *key);
Parameters

The function has the following parameters:

ht
A pointer to the hash table in which to look up the entry specified by key.
key
A pointer to the key for the entry to look up.
Returns

The value of the entry with the specified key, or NULL if there is no such entry.

Description

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

Enumerates all the entries in the hash table, invoking a specified function on each entry.

Syntax
#include <plhash.h>

PRIntn PL_HashTableEnumerateEntries(
   PLHashTable *ht, 
   PLHashEnumerator f, 
   void *arg);
Parameters

The function has the following parameters:

ht
A pointer to the hash table whose entries are to be enumerated.
f
Function to be applied to each entry..
arg
Argument for function f.
Returns

The number of entries enumerated.

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
#include <plhash.h>

PLHashNumber PL_HashString(const void *key);
Parameters

The function has the following parameters:

key
A pointer to a character string.
Returns

The hash number for the specified 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

Compares two character strings.

Syntax
#include <plhash.h>

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

Compares two void * values numerically.

Syntax
#include <plhash.h>

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.