• file
• revisions
• annotate
• diff
• comparison
• raw

nsprpub/lib/ds/plhash.h@7e26c7da4463 (annotated)

nsprpub/lib/ds/plhash.h

Wed, 31 Dec 2014 06:55:50 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Wed, 31 Dec 2014 06:55:50 +0100

changeset 2

7e26c7da4463

permissions

-rw-r--r--

Added tag UPSTREAM_283F7C6 for changeset ca08bd8f51b2

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