1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
9 * API to portable hash table code.
16 typedef struct PLHashEntry PLHashEntry
;
17 typedef struct PLHashTable PLHashTable
;
18 typedef PRUint32 PLHashNumber
;
19 #define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */
20 typedef PLHashNumber (PR_CALLBACK
*PLHashFunction
)(const void *key
);
21 typedef PRIntn (PR_CALLBACK
*PLHashComparator
)(const void *v1
, const void *v2
);
23 typedef PRIntn (PR_CALLBACK
*PLHashEnumerator
)(PLHashEntry
*he
, PRIntn i
, void *arg
);
25 /* Flag bits in PLHashEnumerator's return value */
26 #define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */
27 #define HT_ENUMERATE_STOP 1 /* stop enumerating entries */
28 #define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */
29 #define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */
31 typedef struct PLHashAllocOps
{
32 void * (PR_CALLBACK
*allocTable
)(void *pool
, PRSize size
);
33 void (PR_CALLBACK
*freeTable
)(void *pool
, void *item
);
34 PLHashEntry
* (PR_CALLBACK
*allocEntry
)(void *pool
, const void *key
);
35 void (PR_CALLBACK
*freeEntry
)(void *pool
, PLHashEntry
*he
, PRUintn flag
);
38 #define HT_FREE_VALUE 0 /* just free the entry's value */
39 #define HT_FREE_ENTRY 1 /* free value and entire entry */
42 PLHashEntry
*next
; /* hash chain linkage */
43 PLHashNumber keyHash
; /* key hash function result */
44 const void *key
; /* ptr to opaque key */
45 void *value
; /* ptr to opaque value */
49 PLHashEntry
**buckets
; /* vector of hash buckets */
50 PRUint32 nentries
; /* number of entries in table */
51 PRUint32 shift
; /* multiplicative hash shift */
52 PLHashFunction keyHash
; /* key hash function */
53 PLHashComparator keyCompare
; /* key comparison function */
54 PLHashComparator valueCompare
; /* value comparison function */
55 const PLHashAllocOps
*allocOps
; /* allocation operations */
56 void *allocPriv
; /* allocation private data */
58 PRUint32 nlookups
; /* total number of lookups */
59 PRUint32 nsteps
; /* number of hash chains traversed */
60 PRUint32 ngrows
; /* number of table expansions */
61 PRUint32 nshrinks
; /* number of table contractions */
66 * Create a new hash table.
67 * If allocOps is null, use default allocator ops built on top of malloc().
69 PR_EXTERN(PLHashTable
*)
70 PL_NewHashTable(PRUint32 numBuckets
, PLHashFunction keyHash
,
71 PLHashComparator keyCompare
, PLHashComparator valueCompare
,
72 const PLHashAllocOps
*allocOps
, void *allocPriv
);
75 PL_HashTableDestroy(PLHashTable
*ht
);
77 /* Higher level access methods */
78 PR_EXTERN(PLHashEntry
*)
79 PL_HashTableAdd(PLHashTable
*ht
, const void *key
, void *value
);
82 PL_HashTableRemove(PLHashTable
*ht
, const void *key
);
85 PL_HashTableLookup(PLHashTable
*ht
, const void *key
);
88 PL_HashTableLookupConst(PLHashTable
*ht
, const void *key
);
91 PL_HashTableEnumerateEntries(PLHashTable
*ht
, PLHashEnumerator f
, void *arg
);
93 /* General-purpose C string hash function. */
94 PR_EXTERN(PLHashNumber
)
95 PL_HashString(const void *key
);
97 /* Compare strings using strcmp(), return true if equal. */
99 PL_CompareStrings(const void *v1
, const void *v2
);
101 /* Stub function just returns v1 == v2 */
103 PL_CompareValues(const void *v1
, const void *v2
);
105 /* Low level access methods */
106 PR_EXTERN(PLHashEntry
**)
107 PL_HashTableRawLookup(PLHashTable
*ht
, PLHashNumber keyHash
, const void *key
);
109 PR_EXTERN(PLHashEntry
**)
110 PL_HashTableRawLookupConst(PLHashTable
*ht
, PLHashNumber keyHash
,
113 PR_EXTERN(PLHashEntry
*)
114 PL_HashTableRawAdd(PLHashTable
*ht
, PLHashEntry
**hep
, PLHashNumber keyHash
,
115 const void *key
, void *value
);
118 PL_HashTableRawRemove(PLHashTable
*ht
, PLHashEntry
**hep
, PLHashEntry
*he
);
120 /* This can be trivially implemented using PL_HashTableEnumerateEntries. */
122 PL_HashTableDump(PLHashTable
*ht
, PLHashEnumerator dump
, FILE *fp
);
126 #endif /* plhash_h___ */