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	280	{
70	280	return malloc(size);
71		}
72
73		static void
74		DefaultFreeTable(void *pool, void *item)
75	248	{
76	248	free(item);
77		}
78
79		static JSHashEntry *
80		DefaultAllocEntry(void *pool, const void *key)
81	35436	{
82	35436	return (JSHashEntry*) malloc(sizeof(JSHashEntry));
83		}
84
85		static void
86		DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag)
87	35436	{
88	35436	if (flag == HT_FREE_ENTRY)
89	35436	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	2833	{
102	2833	JSHashTable *ht;
103	2833	size_t nb;
104
105	2833	if (n <= MINBUCKETS) {
106	2817	n = MINBUCKETSLOG2;
107		} else {
108	16	n = JS_CeilingLog2(n);
109	16	if ((int32)n < 0)
110	0	return NULL;
111		}
112
113	2833	if (!allocOps) allocOps = &defaultHashAllocOps;
114
115	2833	ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht);
116	2833	if (!ht)
117	0	return NULL;
118	2833	memset(ht, 0, sizeof *ht);
119	2833	ht->shift = JS_HASH_BITS - n;
120	2833	n = JS_BIT(n);
121	2833	nb = n * sizeof(JSHashEntry *);
122	2833	ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb);
123	2833	if (!ht->buckets) {
124	0	allocOps->freeTable(allocPriv, ht);
125	0	return NULL;
126		}
127	2833	memset(ht->buckets, 0, nb);
128
129	2833	ht->keyHash = keyHash;
130	2833	ht->keyCompare = keyCompare;
131	2833	ht->valueCompare = valueCompare;
132	2833	ht->allocOps = allocOps;
133	2833	ht->allocPriv = allocPriv;
134	2833	return ht;
135		}
136
137		JS_PUBLIC_API(void)
138		JS_HashTableDestroy(JSHashTable *ht)
139	32	{
140	32	uint32 i, n;
141	32	JSHashEntry *he, **hep;
142	32	JSHashAllocOps *allocOps = ht->allocOps;
143	32	void *allocPriv = ht->allocPriv;
144
145	32	n = NBUCKETS(ht);
146	23200	for (i = 0; i < n; i++) {
147	23168	hep = &ht->buckets[i];
148	31000	while ((he = *hep) != NULL) {
149	7832	*hep = he->next;
150	7832	allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY);
151		}
152		}
153		#ifdef DEBUG
154		memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
155		#endif
156	32	allocOps->freeTable(allocPriv, ht->buckets);
157		#ifdef DEBUG
158		memset(ht, 0xDB, sizeof *ht);
159		#endif
160	32	allocOps->freeTable(allocPriv, ht);
161		}
162
163		/*
164		** Multiplicative hash, from Knuth 6.4.
165		*/
166		JS_PUBLIC_API(JSHashEntry **)
167		JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
168	3779041	{
169	3779041	JSHashEntry *he, **hep, **hep0;
170	3779041	JSHashNumber h;
171
172		#ifdef HASHMETER
173		ht->nlookups++;
174		#endif
175	3779041	h = keyHash * JS_GOLDEN_RATIO;
176	3779041	h >>= ht->shift;
177	3779041	hep = hep0 = &ht->buckets[h];
178	4076568	while ((he = *hep) != NULL) {
179	3371921	if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) {
180		/* Move to front of chain if not already there */
181	3074394	if (hep != hep0) {
182	95423	*hep = he->next;
183	95423	he->next = *hep0;
184	95423	*hep0 = he;
185		}
186	3074394	return hep0;
187		}
188	297527	hep = &he->next;
189		#ifdef HASHMETER
190		ht->nsteps++;
191		#endif
192		}
193	704647	return hep;
194		}
195
196		JS_PUBLIC_API(JSHashEntry *)
197		JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep,
198		JSHashNumber keyHash, const void *key, void *value)
199	215632	{
200	215632	uint32 i, n;
201	215632	JSHashEntry *he, *next, **oldbuckets;
202	215632	size_t nb;
203
204		/* Grow the table if it is overloaded */
205	215632	n = NBUCKETS(ht);
206	215632	if (ht->nentries >= OVERLOADED(n)) {
207	5187	oldbuckets = ht->buckets;
208	5187	nb = 2 * n * sizeof(JSHashEntry *);
209	5187	ht->buckets = (JSHashEntry**)
210		ht->allocOps->allocTable(ht->allocPriv, nb);
211	5187	if (!ht->buckets) {
212	0	ht->buckets = oldbuckets;
213	0	return NULL;
214		}
215	5187	memset(ht->buckets, 0, nb);
216		#ifdef HASHMETER
217		ht->ngrows++;
218		#endif
219	5187	ht->shift--;
220
221	359891	for (i = 0; i < n; i++) {
222	665070	for (he = oldbuckets[i]; he; he = next) {
223	310366	next = he->next;
224	310366	hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
225	310366	JS_ASSERT(*hep == NULL);
226	310366	he->next = NULL;
227	310366	*hep = he;
228		}
229		}
230		#ifdef DEBUG
231		memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
232		#endif
233	5187	ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
234	5187	hep = JS_HashTableRawLookup(ht, keyHash, key);
235		}
236
237		/* Make a new key value entry */
238	215632	he = ht->allocOps->allocEntry(ht->allocPriv, key);
239	215632	if (!he)
240	0	return NULL;
241	215632	he->keyHash = keyHash;
242	215632	he->key = key;
243	215632	he->value = value;
244	215632	he->next = *hep;
245	215632	*hep = he;
246	215632	ht->nentries++;
247	215632	return he;
248		}
249
250		JS_PUBLIC_API(JSHashEntry *)
251		JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
252	0	{
253	0	JSHashNumber keyHash;
254	0	JSHashEntry *he, **hep;
255
256	0	keyHash = ht->keyHash(key);
257	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
258	0	if ((he = *hep) != NULL) {
259		/* Hit; see if values match */
260	0	if (ht->valueCompare(he->value, value)) {
261		/* key,value pair is already present in table */
262	0	return he;
263		}
264	0	if (he->value)
265	0	ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
266	0	he->value = value;
267	0	return he;
268		}
269	0	return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
270		}
271
272		JS_PUBLIC_API(void)
273		JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
274	76304	{
275	76304	uint32 i, n;
276	76304	JSHashEntry *next, **oldbuckets;
277	76304	size_t nb;
278
279	76304	*hep = he->next;
280	76304	ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
281
282		/* Shrink table if it's underloaded */
283	76304	n = NBUCKETS(ht);
284	76304	if (--ht->nentries < UNDERLOADED(n)) {
285	158	oldbuckets = ht->buckets;
286	158	nb = n * sizeof(JSHashEntry*) / 2;
287	158	ht->buckets = (JSHashEntry**)
288		ht->allocOps->allocTable(ht->allocPriv, nb);
289	158	if (!ht->buckets) {
290	0	ht->buckets = oldbuckets;
291	0	return;
292		}
293	158	memset(ht->buckets, 0, nb);
294		#ifdef HASHMETER
295		ht->nshrinks++;
296		#endif
297	158	ht->shift++;
298
299	207902	for (i = 0; i < n; i++) {
300	247933	for (he = oldbuckets[i]; he; he = next) {
301	40189	next = he->next;
302	40189	hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
303	40189	JS_ASSERT(*hep == NULL);
304	40189	he->next = NULL;
305	40189	*hep = he;
306		}
307		}
308		#ifdef DEBUG
309		memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
310		#endif
311	158	ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
312		}
313		}
314
315		JS_PUBLIC_API(JSBool)
316		JS_HashTableRemove(JSHashTable *ht, const void *key)
317	0	{
318	0	JSHashNumber keyHash;
319	0	JSHashEntry *he, **hep;
320
321	0	keyHash = ht->keyHash(key);
322	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
323	0	if ((he = *hep) == NULL)
324	0	return JS_FALSE;
325
326		/* Hit; remove element */
327	0	JS_HashTableRawRemove(ht, hep, he);
328	0	return JS_TRUE;
329		}
330
331		JS_PUBLIC_API(void *)
332		JS_HashTableLookup(JSHashTable *ht, const void *key)
333	0	{
334	0	JSHashNumber keyHash;
335	0	JSHashEntry *he, **hep;
336
337	0	keyHash = ht->keyHash(key);
338	0	hep = JS_HashTableRawLookup(ht, keyHash, key);
339	0	if ((he = *hep) != NULL) {
340	0	return he->value;
341		}
342	0	return NULL;
343		}
344
345		/*
346		** Iterate over the entries in the hash table calling func for each
347		** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
348		** Return a count of the number of elements scanned.
349		*/
350		JS_PUBLIC_API(int)
351		JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
352	2705	{
353	2705	JSHashEntry *he, **hep;
354	2705	uint32 i, nbuckets;
355	2705	int rv, n = 0;
356	2705	JSHashEntry *todo = NULL;
357
358	2705	nbuckets = NBUCKETS(ht);
359	654481	for (i = 0; i < nbuckets; i++) {
360	651776	hep = &ht->buckets[i];
361	1013370	while ((he = *hep) != NULL) {
362	361594	rv = f(he, n, arg);
363	361594	n++;
364	361594	if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
365	40868	*hep = he->next;
366	40868	if (rv & HT_ENUMERATE_REMOVE) {
367	40868	he->next = todo;
368	40868	todo = he;
369		}
370		} else {
371	320726	hep = &he->next;
372		}
373	361594	if (rv & HT_ENUMERATE_STOP) {
374	0	goto out;
375		}
376		}
377		}
378
379		out:
380	2705	hep = &todo;
381	43573	while ((he = *hep) != NULL) {
382	40868	JS_HashTableRawRemove(ht, hep, he);
383		}
384	2705	return n;
385		}
386
387		#ifdef HASHMETER
388		#include <math.h>
389		#include <stdio.h>
390
391		JS_PUBLIC_API(void)
392		JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
393		{
394		double sqsum, mean, variance, sigma;
395		uint32 nchains, nbuckets, nentries;
396		uint32 i, n, maxChain, maxChainLen;
397		JSHashEntry *he;
398
399		sqsum = 0;
400		nchains = 0;
401		maxChainLen = 0;
402		nbuckets = NBUCKETS(ht);
403		for (i = 0; i < nbuckets; i++) {
404		he = ht->buckets[i];
405		if (!he)
406		continue;
407		nchains++;
408		for (n = 0; he; he = he->next)
409		n++;
410		sqsum += n * n;
411		if (n > maxChainLen) {
412		maxChainLen = n;
413		maxChain = i;
414		}
415		}
416		nentries = ht->nentries;
417		mean = (double)nentries / nchains;
418		variance = nchains * sqsum - nentries * nentries;
419		if (variance < 0 || nchains == 1)
420		variance = 0;
421		else
422		variance /= nchains * (nchains - 1);
423		sigma = sqrt(variance);
424
425		fprintf(fp, "\nHash table statistics:\n");
426		fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
427		fprintf(fp, "     number of entries: %u\n", ht->nentries);
428		fprintf(fp, "       number of grows: %u\n", ht->ngrows);
429		fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
430		fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
431		/ ht->nlookups);
432		fprintf(fp, "mean hash chain length: %g\n", mean);
433		fprintf(fp, "    standard deviation: %g\n", sigma);
434		fprintf(fp, " max hash chain length: %u\n", maxChainLen);
435		fprintf(fp, "        max hash chain: [%u]\n", maxChain);
436
437		for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
438		if (dump(he, i, fp) != HT_ENUMERATE_NEXT)
439		break;
440		}
441		#endif /* HASHMETER */
442
443		JS_PUBLIC_API(int)
444		JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
445	0	{
446	0	int count;
447
448	0	count = JS_HashTableEnumerateEntries(ht, dump, fp);
449		#ifdef HASHMETER
450		JS_HashTableDumpMeter(ht, dump, fp);
451		#endif
452	0	return count;
453		}
454
455		JS_PUBLIC_API(JSHashNumber)
456		JS_HashString(const void *key)
457	4759	{
458	4759	JSHashNumber h;
459	4759	const unsigned char *s;
460
461	4759	h = 0;
462	427118	for (s = (const unsigned char *)key; *s; s++)
463	422359	h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s;
464	4759	return h;
465		}
466
467		JS_PUBLIC_API(int)
468		JS_CompareValues(const void *v1, const void *v2)
469	776050	{
470	776050	return v1 == v2;