|
Hash TablesWarning: 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 ConstantsPLHashEntrySyntaxtypedef struct PLHashEntry PLHashEntry;DescriptionPLHashEntry 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. PLHashTableSyntaxtypedef struct PLHashTable PLHashTable;DescriptionThe 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. PLHashNumberSyntaxtypedef PRUint32 PLHashNumber;#define PL_HASH_BITS 32 DescriptionPLHashNumber 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 AlsoPLHashFunction.PLHashFunctionSyntaxtypedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key);DescriptionPLHashNumber is a function type that maps the key of a hash table entry to a hash number.See AlsoPL_HashString.PLHashComparatorSyntaxtypedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2);DescriptionPLHashComparator 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. RemarkThe return value of PLHashComparator functions should be of type PRBool.See AlsoPL_CompareStrings, PL_CompareValues.PLHashEnumeratorSyntaxtypedef 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 */ DescriptionPLHashEnumerator 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.RemarkIt 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 AlsoPL_HashTableEnumerateEntries.PLHashAllocOpsSyntax
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 */
DescriptionA 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
RemarkThe key argument for the allocEntry function does not seem to be useful. It is unused in the default allocEntry function.Hash Table FunctionsPL_NewHashTableCreate a new hash table.Syntax
PLHashTable *PL_NewHashTable(
PRUint32 numBuckets,
PLHashFunction keyHash,
PLHashComparator keyCompare,
PLHashComparator valueCompare,
const PLHashAllocOps *allocOps,
void *allocPriv
);
DescriptionPL_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_HashTableDestroyFree the table and all the entries.Syntaxvoid PL_HashTableDestroy(PLHashTable *ht);DescriptionPL_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_HashTableAddAdd a new entry with the specified key and value to the hash table.SyntaxPLHashEntry *PL_HashTableAdd(PLHashTable *ht, const void *key, void *value); DescriptionAdd 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_HashTableRemoveRemove the entry with the specified key from the hash table.SyntaxPRBool PL_HashTableRemove(PLHashTable *ht, const void *key);DescriptionPL_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. RemarkThis function should return PRStatus.PL_HashTableLookupLook up the entry with the specified key and return its value.Syntaxvoid *PL_HashTableLookup(PLHashTable *ht, const void *key);DescriptionPL_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_HashTableEnumerateEntriesEnumerate all the entries in the hash table, invoking the specified function on each entry.SyntaxPRIntn PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg);DescriptionThe 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_HashStringA general-purpose hash function for character strings.SyntaxPLHashNumber PL_HashString(const void *key);DescriptionPL_HashString can be used as the key hash function for a hash table if the key is a character string.PL_CompareStringsCompare two character strings.SyntaxPRIntn PL_CompareStrings(const void *v1, const void *v2);DescriptionPL_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_CompareValuesCompare two void * values numerically.SyntaxPRIntn PL_CompareValues(const void *v1, const void *v2);DescriptionPL_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-2000 The Mozilla Organization.
Last modified July 17, 1998. |
|