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

js/jsd/jshash.h@a63d609f5ebe (annotated)

js/jsd/jshash.h

Thu, 15 Jan 2015 15:55:04 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Thu, 15 Jan 2015 15:55:04 +0100

branch

TOR_BUG_9701

changeset 9

a63d609f5ebe

permissions

-rw-r--r--

Back out 97036ab72558 which inappropriately compared turds to third parties.

michael@0	1	/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0	2	* vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0	3	* This Source Code Form is subject to the terms of the Mozilla Public
michael@0	4	* License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0	5	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0	6
michael@0	7	#ifndef jshash_h___
michael@0	8	#define jshash_h___
michael@0	9
michael@0	10	/*
michael@0	11	* API to portable hash table code.
michael@0	12	*/
michael@0	13	#include <stddef.h>
michael@0	14	#include <stdint.h>
michael@0	15	#include <stdio.h>
michael@0	16
michael@0	17	extern "C" {
michael@0	18
michael@0	19	typedef uint32_t JSHashNumber;
michael@0	20	typedef struct JSHashEntry JSHashEntry;
michael@0	21	typedef struct JSHashTable JSHashTable;
michael@0	22
michael@0	23	#define JS_HASH_BITS 32
michael@0	24	#define JS_GOLDEN_RATIO 0x9E3779B9U
michael@0	25
michael@0	26	typedef JSHashNumber (* JSHashFunction)(const void *key);
michael@0	27	typedef int (* JSHashComparator)(const void *v1, const void *v2);
michael@0	28	typedef int (* JSHashEnumerator)(JSHashEntry *he, int i, void *arg);
michael@0	29
michael@0	30	/* Flag bits in JSHashEnumerator's return value */
michael@0	31	#define HT_ENUMERATE_NEXT 0 /* continue enumerating entries */
michael@0	32	#define HT_ENUMERATE_STOP 1 /* stop enumerating entries */
michael@0	33	#define HT_ENUMERATE_REMOVE 2 /* remove and free the current entry */
michael@0	34
michael@0	35	typedef struct JSHashAllocOps {
michael@0	36	void * (*allocTable)(void *pool, size_t size);
michael@0	37	void (*freeTable)(void *pool, void *item, size_t size);
michael@0	38	JSHashEntry * (*allocEntry)(void *pool, const void *key);
michael@0	39	void (*freeEntry)(void *pool, JSHashEntry *he, unsigned flag);
michael@0	40	} JSHashAllocOps;
michael@0	41
michael@0	42	#define HT_FREE_VALUE 0 /* just free the entry's value */
michael@0	43	#define HT_FREE_ENTRY 1 /* free value and entire entry */
michael@0	44
michael@0	45	struct JSHashEntry {
michael@0	46	JSHashEntry *next; /* hash chain linkage */
michael@0	47	JSHashNumber keyHash; /* key hash function result */
michael@0	48	const void *key; /* ptr to opaque key */
michael@0	49	void *value; /* ptr to opaque value */
michael@0	50	};
michael@0	51
michael@0	52	struct JSHashTable {
michael@0	53	JSHashEntry **buckets; /* vector of hash buckets */
michael@0	54	uint32_t nentries; /* number of entries in table */
michael@0	55	uint32_t shift; /* multiplicative hash shift */
michael@0	56	JSHashFunction keyHash; /* key hash function */
michael@0	57	JSHashComparator keyCompare; /* key comparison function */
michael@0	58	JSHashComparator valueCompare; /* value comparison function */
michael@0	59	const JSHashAllocOps *allocOps; /* allocation operations */
michael@0	60	void *allocPriv; /* allocation private data */
michael@0	61	#ifdef JS_HASHMETER
michael@0	62	uint32_t nlookups; /* total number of lookups */
michael@0	63	uint32_t nsteps; /* number of hash chains traversed */
michael@0	64	uint32_t ngrows; /* number of table expansions */
michael@0	65	uint32_t nshrinks; /* number of table contractions */
michael@0	66	#endif
michael@0	67	};
michael@0	68
michael@0	69	/*
michael@0	70	* Create a new hash table.
michael@0	71	* If allocOps is null, use default allocator ops built on top of malloc().
michael@0	72	*/
michael@0	73	extern JSHashTable *
michael@0	74	JS_NewHashTable(uint32_t n, JSHashFunction keyHash,
michael@0	75	JSHashComparator keyCompare, JSHashComparator valueCompare,
michael@0	76	const JSHashAllocOps *allocOps, void *allocPriv);
michael@0	77
michael@0	78	extern void
michael@0	79	JS_HashTableDestroy(JSHashTable *ht);
michael@0	80
michael@0	81	/* Low level access methods */
michael@0	82	extern JSHashEntry **
michael@0	83	JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key);
michael@0	84
michael@0	85	extern JSHashEntry *
michael@0	86	JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep, JSHashNumber keyHash,
michael@0	87	const void *key, void *value);
michael@0	88
michael@0	89	extern void
michael@0	90	JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he);
michael@0	91
michael@0	92	/* Higher level access methods */
michael@0	93	extern JSHashEntry *
michael@0	94	JS_HashTableAdd(JSHashTable *ht, const void *key, void *value);
michael@0	95
michael@0	96	extern bool
michael@0	97	JS_HashTableRemove(JSHashTable *ht, const void *key);
michael@0	98
michael@0	99	extern int
michael@0	100	JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg);
michael@0	101
michael@0	102	extern void *
michael@0	103	JS_HashTableLookup(JSHashTable *ht, const void *key);
michael@0	104
michael@0	105	extern int
michael@0	106	JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp);
michael@0	107
michael@0	108	/* General-purpose C string hash function. */
michael@0	109	extern JSHashNumber
michael@0	110	JS_HashString(const void *key);
michael@0	111
michael@0	112	/* Stub function just returns v1 == v2 */
michael@0	113	extern int
michael@0	114	JS_CompareValues(const void *v1, const void *v2);
michael@0	115
michael@0	116	} // extern "C"
michael@0	117
michael@0	118	#endif /* jshash_h___ */