1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/nsprpub/lib/ds/plhash.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,126 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef plhash_h___
1.10 +#define plhash_h___
1.11 +/*
1.12 + * API to portable hash table code.
1.13 + */
1.14 +#include <stdio.h>
1.15 +#include "prtypes.h"
1.16 +
1.17 +PR_BEGIN_EXTERN_C
1.18 +
1.19 +typedef struct PLHashEntry PLHashEntry;
1.20 +typedef struct PLHashTable PLHashTable;
1.21 +typedef PRUint32 PLHashNumber;
1.22 +#define PL_HASH_BITS 32 /* Number of bits in PLHashNumber */
1.23 +typedef PLHashNumber (PR_CALLBACK *PLHashFunction)(const void *key);
1.24 +typedef PRIntn (PR_CALLBACK *PLHashComparator)(const void *v1, const void *v2);
1.25 +
1.26 +typedef PRIntn (PR_CALLBACK *PLHashEnumerator)(PLHashEntry *he, PRIntn i, void *arg);
1.27 +
1.28 +/* Flag bits in PLHashEnumerator's return value */
1.29 +#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */
1.30 +#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */
1.31 +#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */
1.32 +#define HT_ENUMERATE_UNHASH 4 /* just unhash the current entry */
1.33 +
1.34 +typedef struct PLHashAllocOps {
1.35 + void * (PR_CALLBACK *allocTable)(void *pool, PRSize size);
1.36 + void (PR_CALLBACK *freeTable)(void *pool, void *item);
1.37 + PLHashEntry * (PR_CALLBACK *allocEntry)(void *pool, const void *key);
1.38 + void (PR_CALLBACK *freeEntry)(void *pool, PLHashEntry *he, PRUintn flag);
1.39 +} PLHashAllocOps;
1.40 +
1.41 +#define HT_FREE_VALUE 0 /* just free the entry's value */
1.42 +#define HT_FREE_ENTRY 1 /* free value and entire entry */
1.43 +
1.44 +struct PLHashEntry {
1.45 + PLHashEntry *next; /* hash chain linkage */
1.46 + PLHashNumber keyHash; /* key hash function result */
1.47 + const void *key; /* ptr to opaque key */
1.48 + void *value; /* ptr to opaque value */
1.49 +};
1.50 +
1.51 +struct PLHashTable {
1.52 + PLHashEntry **buckets; /* vector of hash buckets */
1.53 + PRUint32 nentries; /* number of entries in table */
1.54 + PRUint32 shift; /* multiplicative hash shift */
1.55 + PLHashFunction keyHash; /* key hash function */
1.56 + PLHashComparator keyCompare; /* key comparison function */
1.57 + PLHashComparator valueCompare; /* value comparison function */
1.58 + const PLHashAllocOps *allocOps; /* allocation operations */
1.59 + void *allocPriv; /* allocation private data */
1.60 +#ifdef HASHMETER
1.61 + PRUint32 nlookups; /* total number of lookups */
1.62 + PRUint32 nsteps; /* number of hash chains traversed */
1.63 + PRUint32 ngrows; /* number of table expansions */
1.64 + PRUint32 nshrinks; /* number of table contractions */
1.65 +#endif
1.66 +};
1.67 +
1.68 +/*
1.69 + * Create a new hash table.
1.70 + * If allocOps is null, use default allocator ops built on top of malloc().
1.71 + */
1.72 +PR_EXTERN(PLHashTable *)
1.73 +PL_NewHashTable(PRUint32 numBuckets, PLHashFunction keyHash,
1.74 + PLHashComparator keyCompare, PLHashComparator valueCompare,
1.75 + const PLHashAllocOps *allocOps, void *allocPriv);
1.76 +
1.77 +PR_EXTERN(void)
1.78 +PL_HashTableDestroy(PLHashTable *ht);
1.79 +
1.80 +/* Higher level access methods */
1.81 +PR_EXTERN(PLHashEntry *)
1.82 +PL_HashTableAdd(PLHashTable *ht, const void *key, void *value);
1.83 +
1.84 +PR_EXTERN(PRBool)
1.85 +PL_HashTableRemove(PLHashTable *ht, const void *key);
1.86 +
1.87 +PR_EXTERN(void *)
1.88 +PL_HashTableLookup(PLHashTable *ht, const void *key);
1.89 +
1.90 +PR_EXTERN(void *)
1.91 +PL_HashTableLookupConst(PLHashTable *ht, const void *key);
1.92 +
1.93 +PR_EXTERN(PRIntn)
1.94 +PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg);
1.95 +
1.96 +/* General-purpose C string hash function. */
1.97 +PR_EXTERN(PLHashNumber)
1.98 +PL_HashString(const void *key);
1.99 +
1.100 +/* Compare strings using strcmp(), return true if equal. */
1.101 +PR_EXTERN(PRIntn)
1.102 +PL_CompareStrings(const void *v1, const void *v2);
1.103 +
1.104 +/* Stub function just returns v1 == v2 */
1.105 +PR_EXTERN(PRIntn)
1.106 +PL_CompareValues(const void *v1, const void *v2);
1.107 +
1.108 +/* Low level access methods */
1.109 +PR_EXTERN(PLHashEntry **)
1.110 +PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key);
1.111 +
1.112 +PR_EXTERN(PLHashEntry **)
1.113 +PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash,
1.114 + const void *key);
1.115 +
1.116 +PR_EXTERN(PLHashEntry *)
1.117 +PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, PLHashNumber keyHash,
1.118 + const void *key, void *value);
1.119 +
1.120 +PR_EXTERN(void)
1.121 +PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he);
1.122 +
1.123 +/* This can be trivially implemented using PL_HashTableEnumerateEntries. */
1.124 +PR_EXTERN(PRIntn)
1.125 +PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp);
1.126 +
1.127 +PR_END_EXTERN_C
1.128 +
1.129 +#endif /* plhash_h___ */
