1		/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2		*
3		* ***** BEGIN LICENSE BLOCK *****
4		* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5		*
6		* The contents of this file are subject to the Mozilla Public License Version
7		* 1.1 (the "License"); you may not use this file except in compliance with
8		* the License. You may obtain a copy of the License at
9		* http://www.mozilla.org/MPL/
10		*
11		* Software distributed under the License is distributed on an "AS IS" basis,
12		* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13		* for the specific language governing rights and limitations under the
14		* License.
15		*
16		* The Original Code is Mozilla Communicator client code, released
17		* March 31, 1998.
18		*
19		* The Initial Developer of the Original Code is
20		* Netscape Communications Corporation.
21		* Portions created by the Initial Developer are Copyright (C) 1998
22		* the Initial Developer. All Rights Reserved.
23		*
24		* Contributor(s):
25		*
26		* Alternatively, the contents of this file may be used under the terms of
27		* either of the GNU General Public License Version 2 or later (the "GPL"),
28		* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29		* in which case the provisions of the GPL or the LGPL are applicable instead
30		* of those above. If you wish to allow use of your version of this file only
31		* under the terms of either the GPL or the LGPL, and not to allow others to
32		* use your version of this file under the terms of the MPL, indicate your
33		* decision by deleting the provisions above and replace them with the notice
34		* and other provisions required by the GPL or the LGPL. If you do not delete
35		* the provisions above, a recipient may use your version of this file under
36		* the terms of any one of the MPL, the GPL or the LGPL.
37		*
38		* ***** END LICENSE BLOCK ***** */
39
40		/*
41		* PR hash table package.
42		*/
43		#include "jsstddef.h"
44		#include <stdlib.h>
45		#include <string.h>
46		#include "jstypes.h"
47		#include "jsbit.h"
48		#include "jsutil.h" /* Added by JSIFY */
49		#include "jshash.h" /* Added by JSIFY */
50
51		/* Compute the number of buckets in ht */
52		#define NBUCKETS(ht)    JS_BIT(JS_HASH_BITS - (ht)->shift)
53
54		/* The smallest table has 16 buckets */
55		#define MINBUCKETSLOG2  4
56		#define MINBUCKETS      JS_BIT(MINBUCKETSLOG2)
57
58		/* Compute the maximum entries given n buckets that we will tolerate, ~90% */
59		#define OVERLOADED(n)   ((n) - ((n) >> 3))
60
61		/* Compute the number of entries below which we shrink the table by half */
62		#define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
63
64		/*
65		** Stubs for default hash allocator ops.
66		*/
67		static void *
68		DefaultAllocTable(void *pool, size_t size)
69	300	{
70	300	return malloc(size);
71		}
72
73		static void
74		DefaultFreeTable(void *pool, void *item)
75	266	{
76	266	free(item);
77		}
78
79		static JSHashEntry *
80		DefaultAllocEntry(void *pool, const void *key)
81	41113	{
82	41113	return (JSHashEntry*) malloc(sizeof(JSHashEntry));
83		}
84
85		static void
86		DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag)
87	41113	{
88	41113	if (flag == HT_FREE_ENTRY)
89	41113	free(he);
90		}
91
92		static JSHashAllocOps defaultHashAllocOps = {
93		DefaultAllocTable, DefaultFreeTable,
94		DefaultAllocEntry, DefaultFreeEntry
95		};
96
97		JS_PUBLIC_API(JSHashTable *)
98		JS_NewHashTable(uint32 n, JSHashFunction keyHash,
99		JSHashComparator keyCompare, JSHashComparator valueCompare,
100		JSHashAllocOps *allocOps, void *allocPriv)
101	2979	{
102	2979	JSHashTable *ht;
103	2979	size_t nb;
104
105	2979	if (n <= MINBUCKETS) {
106	2962	n = MINBUCKETSLOG2;
107		} else {
108	17	n = JS_CeilingLog2(n);
109	17	if ((int32)n < 0)
110	0	return NULL;
111		}
112
113	2979	if (!allocOps) allocOps = &defaultHashAllocOps;
114
115	2979	ht = (JSHashTable*) (*allocOps->allocTable)(allocPriv, sizeof *ht);
116	2979	if (!ht)
117	0	return NULL;
118	2979	memset(ht, 0, sizeof *ht);
119	2979	ht->shift = JS_HASH_BITS - n;
120	2979	n = JS_BIT(n);
121		#if defined _MSC_VER && _MSC_VER <= 800
122		if (n > 16000) {
123		(*allocOps->freeTable)(allocPriv, ht);
124		return NULL;
125		}
126		#endif  /* WIN16 */
127	2979	nb = n * sizeof(JSHashEntry *);
128	2979	ht->buckets = (JSHashEntry**) (*allocOps->allocTable)(allocPriv, nb);
129	2979	if (!ht->buckets) {
130	0	(*allocOps->freeTable)(allocPriv, ht);
131	0	return NULL;
132		}
133	2979	memset(ht->buckets, 0, nb);
134
135	2979	ht->keyHash = keyHash;
136	2979	ht->keyCompare = keyCompare;
137	2979	ht->valueCompare = valueCompare;
138	2979	ht->allocOps = allocOps;
139	2979	ht->allocPriv = allocPriv;
140	2979	return ht;
141		}
142
143		JS_PUBLIC_API(void)
144		JS_HashTableDestroy(JSHashTable *ht)
145	34	{
146	34	uint32 i, n;
147	34	JSHashEntry *he, **hep;
148	34	JSHashAllocOps *allocOps = ht->allocOps;
149	34	void *allocPriv = ht->allocPriv;
150
151	34	n = NBUCKETS(ht);
152	23346	for (i = 0; i < n; i++) {
153	23312	hep = &ht->buckets[i];
154	31164	while ((he = *hep) != NULL) {
155	7852	*hep = he->next;
156	7852	(*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
157		}
158		}
159		#ifdef DEBUG
160		memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
161		#endif
162	34	(*allocOps->freeTable)(allocPriv, ht->buckets);
163		#ifdef DEBUG
164		memset(ht, 0xDB, sizeof *ht);
165		#endif
166	34	(*allocOps->freeTable)(allocPriv, ht);
167		}
168
169		/*
170		** Multiplicative hash, from Knuth 6.4.
171		*/
172		JS_PUBLIC_API(JSHashEntry **)
173		JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
174	3738785	{
175	3738785	JSHashEntry *he, **hep, **hep0;
176	3738785	JSHashNumber h;
177
178		#ifdef HASHMETER
179		ht->nlookups++;
180		#endif
181	3738785	h = keyHash * JS_GOLDEN_RATIO;
182	3738785	h >>= ht->shift;
183	3738785	hep = hep0 = &ht->buckets[h];
184	4034058	while ((he = *hep) != NULL) {
185	3315316	if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
186		/* Move to front of chain if not already there */
187	3020043	if (hep != hep0) {
188	75778	*hep = he->next;
189	75778	he->next = *hep0;
190	75778	*hep0 = he;
191		}
192	3020043	return hep0;
193		}
194	295273	hep = &he->next;
195		#ifdef HASHMETER
196		ht->nsteps++;
197		#endif
198		}
199	718742	return hep;
200		}
201
202		JS_PUBLIC_API(JSHashEntry *)
203		JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep,
204		JSHashNumber keyHash, const void *key, void *value)
205	223046	{
206	223046	uint32 i, n;
207	223046	JSHashEntry *he, *next, **oldbuckets;
208	223046	size_t nb;
209
210		/* Grow the table if it is overloaded */
211	223046	n = NBUCKETS(ht);
212	223046	if (ht->nentries >= OVERLOADED(n)) {
213	3883	oldbuckets = ht->buckets;
214		#if defined _MSC_VER && _MSC_VER <= 800
215		if (2 * n > 16000)
216		return NULL;
217		#endif  /* WIN16 */
218	3883	nb = 2 * n * sizeof(JSHashEntry *);
219	3883	ht->buckets = (JSHashEntry**) (*ht->allocOps->allocTable)(ht->allocPriv, nb);
220	3883	if (!ht->buckets) {
221	0	ht->buckets = oldbuckets;
222	0	return NULL;
223		}
224	3883	memset(ht->buckets, 0, nb);
225		#ifdef HASHMETER
226		ht->ngrows++;
227		#endif
228	3883	ht->shift--;
229
230	337931	for (i = 0; i < n; i++) {
231	663460	for (he = oldbuckets[i]; he; he = next) {
232	329412	next = he->next;
233	329412	hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
234	329412	JS_ASSERT(*hep == NULL);
235	329412	he->next = NULL;
236	329412	*hep = he;
237		}
238		}
239		#ifdef DEBUG
240		memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
241		#endif
242	3883	(*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
243	3883	hep = JS_HashTableRawLookup(ht, keyHash, key);
244		}
245
246		/* Make a new key value entry */
247	223046	he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
248	223046	if (!he)
249	0	return NULL;
250	223046	he->keyHash = keyHash;
251	223046	he->key = key;
252	223046	he->value = value;
253	223046	he->next = *hep;
254	223046	*hep = he;
255	223046	ht->nentries++;
256	223046	return he;
257		}
258
259		JS_PUBLIC_API(JSHashEntry *)
260		JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
261	0	{
262	0	JSHashNumber keyHash;
263	0	JSHashEntry *he, **hep;
264
265	0	keyHash = (*ht->keyHash)(key);
266	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
267	0	if ((he = *hep) != NULL) {
268		/* Hit; see if values match */
269	0	if ((*ht->valueCompare)(he->value, value)) {
270		/* key,value pair is already present in table */
271	0	return he;
272		}
273	0	if (he->value)
274	0	(*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
275	0	he->value = value;
276	0	return he;
277		}
278	0	return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
279		}
280
281		JS_PUBLIC_API(void)
282		JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
283	80210	{
284	80210	uint32 i, n;
285	80210	JSHashEntry *next, **oldbuckets;
286	80210	size_t nb;
287
288	80210	*hep = he->next;
289	80210	(*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
290
291		/* Shrink table if it's underloaded */
292	80210	n = NBUCKETS(ht);
293	80210	if (--ht->nentries < UNDERLOADED(n)) {
294	171	oldbuckets = ht->buckets;
295	171	nb = n * sizeof(JSHashEntry*) / 2;
296	171	ht->buckets = (JSHashEntry**) (*ht->allocOps->allocTable)(ht->allocPriv, nb);
297	171	if (!ht->buckets) {
298	0	ht->buckets = oldbuckets;
299	0	return;
300		}
301	171	memset(ht->buckets, 0, nb);
302		#ifdef HASHMETER
303		ht->nshrinks++;
304		#endif
305	171	ht->shift++;
306
307	226091	for (i = 0; i < n; i++) {
308	272597	for (he = oldbuckets[i]; he; he = next) {
309	46677	next = he->next;
310	46677	hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
311	46677	JS_ASSERT(*hep == NULL);
312	46677	he->next = NULL;
313	46677	*hep = he;
314		}
315		}
316		#ifdef DEBUG
317		memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
318		#endif
319	171	(*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
320		}
321		}
322
323		JS_PUBLIC_API(JSBool)
324		JS_HashTableRemove(JSHashTable *ht, const void *key)
325	0	{
326	0	JSHashNumber keyHash;
327	0	JSHashEntry *he, **hep;
328
329	0	keyHash = (*ht->keyHash)(key);
330	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
331	0	if ((he = *hep) == NULL)
332	0	return JS_FALSE;
333
334		/* Hit; remove element */
335	0	JS_HashTableRawRemove(ht, hep, he);
336	0	return JS_TRUE;
337		}
338
339		JS_PUBLIC_API(void *)
340		JS_HashTableLookup(JSHashTable *ht, const void *key)
341	0	{
342	0	JSHashNumber keyHash;
343	0	JSHashEntry *he, **hep;
344
345	0	keyHash = (*ht->keyHash)(key);
346	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
347	0	if ((he = *hep) != NULL) {
348	0	return he->value;
349		}
350	0	return NULL;
351		}
352
353		/*
354		** Iterate over the entries in the hash table calling func for each
355		** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
356		** Return a count of the number of elements scanned.
357		*/
358		JS_PUBLIC_API(int)
359		JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
360	2839	{
361	2839	JSHashEntry *he, **hep;
362	2839	uint32 i, nbuckets;
363	2839	int rv, n = 0;
364	2839	JSHashEntry *todo = NULL;
365
366	2839	nbuckets = NBUCKETS(ht);
367	611207	for (i = 0; i < nbuckets; i++) {
368	608368	hep = &ht->buckets[i];
369	965857	while ((he = *hep) != NULL) {
370	357489	rv = (*f)(he, n, arg);
371	357489	n++;
372	357489	if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
373	39097	*hep = he->next;
374	39097	if (rv & HT_ENUMERATE_REMOVE) {
375	39097	he->next = todo;
376	39097	todo = he;
377		}
378		} else {
379	318392	hep = &he->next;
380		}
381	357489	if (rv & HT_ENUMERATE_STOP) {
382	0	goto out;
383		}
384		}
385		}
386
387		out:
388	2839	hep = &todo;
389	41936	while ((he = *hep) != NULL) {
390	39097	JS_HashTableRawRemove(ht, hep, he);
391		}
392	2839	return n;
393		}
394
395		#ifdef HASHMETER
396		#include <math.h>
397		#include <stdio.h>
398
399		JS_PUBLIC_API(void)
400		JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
401		{
402		double sqsum, mean, variance, sigma;
403		uint32 nchains, nbuckets, nentries;
404		uint32 i, n, maxChain, maxChainLen;
405		JSHashEntry *he;
406
407		sqsum = 0;
408		nchains = 0;
409		maxChainLen = 0;
410		nbuckets = NBUCKETS(ht);
411		for (i = 0; i < nbuckets; i++) {
412		he = ht->buckets[i];
413		if (!he)
414		continue;
415		nchains++;
416		for (n = 0; he; he = he->next)
417		n++;
418		sqsum += n * n;
419		if (n > maxChainLen) {
420		maxChainLen = n;
421		maxChain = i;
422		}
423		}
424		nentries = ht->nentries;
425		mean = (double)nentries / nchains;
426		variance = nchains * sqsum - nentries * nentries;
427		if (variance < 0 || nchains == 1)
428		variance = 0;
429		else
430		variance /= nchains * (nchains - 1);
431		sigma = sqrt(variance);
432
433		fprintf(fp, "\nHash table statistics:\n");
434		fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
435		fprintf(fp, "     number of entries: %u\n", ht->nentries);
436		fprintf(fp, "       number of grows: %u\n", ht->ngrows);
437		fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
438		fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
439		/ ht->nlookups);
440		fprintf(fp, "mean hash chain length: %g\n", mean);
441		fprintf(fp, "    standard deviation: %g\n", sigma);
442		fprintf(fp, " max hash chain length: %u\n", maxChainLen);
443		fprintf(fp, "        max hash chain: [%u]\n", maxChain);
444
445		for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
446		if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
447		break;
448		}
449		#endif /* HASHMETER */
450
451		JS_PUBLIC_API(int)
452		JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
453	0	{
454	0	int count;
455
456	0	count = JS_HashTableEnumerateEntries(ht, dump, fp);
457		#ifdef HASHMETER
458		JS_HashTableDumpMeter(ht, dump, fp);
459		#endif
460	0	return count;
461		}
462
463		JS_PUBLIC_API(JSHashNumber)
464		JS_HashString(const void *key)
465	4920	{
466	4920	JSHashNumber h;
467	4920	const unsigned char *s;
468
469	4920	h = 0;
470	338207	for (s = (const unsigned char *)key; *s; s++)
471	333287	h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s;
472	4920	return h;
473		}
474
475		JS_PUBLIC_API(int)
476		JS_CompareValues(const void *v1, const void *v2)
477	805175	{
478	805175	return v1 == v2;