1		/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2		/* ***** BEGIN LICENSE BLOCK *****
3		* Version: MPL 1.1/GPL 2.0/LGPL 2.1
4		*
5		* The contents of this file are subject to the Mozilla Public License Version
6		* 1.1 (the "License"); you may not use this file except in compliance with
7		* the License. You may obtain a copy of the License at
8		* http://www.mozilla.org/MPL/
9		*
10		* Software distributed under the License is distributed on an "AS IS" basis,
11		* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12		* for the specific language governing rights and limitations under the
13		* License.
14		*
15		* The Original Code is Mozilla JavaScript code.
16		*
17		* The Initial Developer of the Original Code is
18		* Netscape Communications Corporation.
19		* Portions created by the Initial Developer are Copyright (C) 1999-2001
20		* the Initial Developer. All Rights Reserved.
21		*
22		* Contributor(s):
23		*   Brendan Eich <brendan@mozilla.org> (Original Author)
24		*   Chris Waterson <waterson@netscape.com>
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		* Double hashing implementation.
42		*/
43		#include <stdio.h>
44		#include <stdlib.h>
45		#include <string.h>
46		#include "jsbit.h"
47		#include "jsdhash.h"
48		#include "jsutil.h"     /* for JS_ASSERT */
49
50		#ifdef JS_DHASHMETER
51		# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
52		#  include "nsTraceMalloc.h"
53		# endif
54		# define METER(x)       x
55		#else
56		# define METER(x)       /* nothing */
57		#endif
58
59		JS_PUBLIC_API(void *)
60		JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
61	253	{
62	253	return malloc(nbytes);
63		}
64
65		JS_PUBLIC_API(void)
66		JS_DHashFreeTable(JSDHashTable *table, void *ptr)
67	253	{
68	253	free(ptr);
69		}
70
71		JS_PUBLIC_API(JSDHashNumber)
72		JS_DHashStringKey(JSDHashTable *table, const void *key)
73	0	{
74	0	JSDHashNumber h;
75	0	const unsigned char *s;
76
77	0	h = 0;
78	0	for (s = key; *s != '\0'; s++)
79	0	h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
80	0	return h;
81		}
82
83		JS_PUBLIC_API(const void *)
84		JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
85	49939	{
86	49939	JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
87
88	49939	return stub->key;
89		}
90
91		JS_PUBLIC_API(JSDHashNumber)
92		JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
93	44022	{
94	44022	return (JSDHashNumber)(unsigned long)key >> 2;
95		}
96
97		JS_PUBLIC_API(JSBool)
98		JS_DHashMatchEntryStub(JSDHashTable *table,
99		const JSDHashEntryHdr *entry,
100		const void *key)
101	22011	{
102	22011	const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
103
104	22011	return stub->key == key;
105		}
106
107		JS_PUBLIC_API(JSBool)
108		JS_DHashMatchStringKey(JSDHashTable *table,
109		const JSDHashEntryHdr *entry,
110		const void *key)
111	0	{
112	0	const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
113
114		/* XXX tolerate null keys on account of sloppy Mozilla callers. */
115	0	return stub->key == key ||
116		(stub->key && key && strcmp(stub->key, key) == 0);
117		}
118
119		JS_PUBLIC_API(void)
120		JS_DHashMoveEntryStub(JSDHashTable *table,
121		const JSDHashEntryHdr *from,
122		JSDHashEntryHdr *to)
123	49939	{
124	49939	memcpy(to, from, table->entrySize);
125		}
126
127		JS_PUBLIC_API(void)
128		JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
129	327208	{
130	327208	memset(entry, 0, table->entrySize);
131		}
132
133		JS_PUBLIC_API(void)
134		JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
135	0	{
136	0	const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
137
138	0	free((void *) stub->key);
139	0	memset(entry, 0, table->entrySize);
140		}
141
142		JS_PUBLIC_API(void)
143		JS_DHashFinalizeStub(JSDHashTable *table)
144	48	{
145		}
146
147		static const JSDHashTableOps stub_ops = {
148		JS_DHashAllocTable,
149		JS_DHashFreeTable,
150		JS_DHashGetKeyStub,
151		JS_DHashVoidPtrKeyStub,
152		JS_DHashMatchEntryStub,
153		JS_DHashMoveEntryStub,
154		JS_DHashClearEntryStub,
155		JS_DHashFinalizeStub,
156		NULL
157		};
158
159		JS_PUBLIC_API(const JSDHashTableOps *)
160		JS_DHashGetStubOps(void)
161	16	{
162	16	return &stub_ops;
163		}
164
165		JS_PUBLIC_API(JSDHashTable *)
166		JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
167		uint32 capacity)
168	16	{
169	16	JSDHashTable *table;
170
171	16	table = (JSDHashTable *) malloc(sizeof *table);
172	16	if (!table)
173	0	return NULL;
174	16	if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
175	0	free(table);
176	0	return NULL;
177		}
178	16	return table;
179		}
180
181		JS_PUBLIC_API(void)
182		JS_DHashTableDestroy(JSDHashTable *table)
183	16	{
184	16	JS_DHashTableFinish(table);
185	16	free(table);
186		}
187
188		JS_PUBLIC_API(JSBool)
189		JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
190		uint32 entrySize, uint32 capacity)
191	48	{
192	48	int log2;
193	48	uint32 nbytes;
194
195		#ifdef DEBUG
196		if (entrySize > 10 * sizeof(void *)) {
197		fprintf(stderr,
198		"jsdhash: for the table at address %p, the given entrySize"
199		" of %lu %s favors chaining over double hashing.\n",
200		(void *)table,
201		(unsigned long) entrySize,
202		(entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
203		}
204		#endif
205
206	48	table->ops = ops;
207	48	table->data = data;
208	48	if (capacity < JS_DHASH_MIN_SIZE)
209	0	capacity = JS_DHASH_MIN_SIZE;
210
211	48	JS_CEILING_LOG2(log2, capacity);
212
213	48	capacity = JS_BIT(log2);
214	48	if (capacity >= JS_DHASH_SIZE_LIMIT)
215	0	return JS_FALSE;
216	48	table->hashShift = JS_DHASH_BITS - log2;
217	48	table->maxAlphaFrac = 0xC0;                 /* .75 */
218	48	table->minAlphaFrac = 0x40;                 /* .25 */
219	48	table->entrySize = entrySize;
220	48	table->entryCount = table->removedCount = 0;
221	48	table->generation = 0;
222	48	nbytes = capacity * entrySize;
223
224	48	table->entryStore = ops->allocTable(table, nbytes);
225	48	if (!table->entryStore)
226	0	return JS_FALSE;
227	48	memset(table->entryStore, 0, nbytes);
228		METER(memset(&table->stats, 0, sizeof table->stats));
229	48	return JS_TRUE;
230		}
231
232		/*
233		* Compute max and min load numbers (entry counts) from table params.
234		*/
235		#define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
236		#define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
237
238		JS_PUBLIC_API(void)
239		JS_DHashTableSetAlphaBounds(JSDHashTable *table,
240		float maxAlpha,
241		float minAlpha)
242	0	{
243	0	uint32 size;
244
245		/*
246		* Reject obviously insane bounds, rather than trying to guess what the
247		* buggy caller intended.
248		*/
249	0	JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
250	0	if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
251	0	return;
252
253		/*
254		* Ensure that at least one entry will always be free.  If maxAlpha at
255		* minimum size leaves no entries free, reduce maxAlpha based on minimum
256		* size and the precision limit of maxAlphaFrac's fixed point format.
257		*/
258	0	JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
259	0	if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
260	0	maxAlpha = (float)
261		(JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
262		/ JS_DHASH_MIN_SIZE;
263		}
264
265		/*
266		* Ensure that minAlpha is strictly less than half maxAlpha.  Take care
267		* not to truncate an entry's worth of alpha when storing in minAlphaFrac
268		* (8-bit fixed point format).
269		*/
270	0	JS_ASSERT(minAlpha < maxAlpha / 2);
271	0	if (minAlpha >= maxAlpha / 2) {
272	0	size = JS_DHASH_TABLE_SIZE(table);
273	0	minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
274		}
275
276	0	table->maxAlphaFrac = (uint8)(maxAlpha * 256);
277	0	table->minAlphaFrac = (uint8)(minAlpha * 256);
278		}
279
280		/*
281		* Double hashing needs the second hash code to be relatively prime to table
282		* size, so we simply make hash2 odd.
283		*/
284		#define HASH1(hash0, shift)         ((hash0) >> (shift))
285		#define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
286
287		/*
288		* Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
289		* that a removed-entry sentinel need be stored only if the removed entry had
290		* a colliding entry added after it.  Therefore we can use 1 as the collision
291		* flag in addition to the removed-entry sentinel value.  Multiplicative hash
292		* uses the high order bits of keyHash, so this least-significant reservation
293		* should not hurt the hash function's effectiveness much.
294		*
295		* If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
296		* in jsdhash.h.  It used to be private to jsdhash.c, but then became public to
297		* assist iterator writers who inspect table->entryStore directly.
298		*/
299		#define COLLISION_FLAG              ((JSDHashNumber) 1)
300		#define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
301		#define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
302		#define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
303		#define ENTRY_IS_LIVE(entry)        JS_DHASH_ENTRY_IS_LIVE(entry)
304		#define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
305
306		/* Match an entry's keyHash against an unstored one computed from a key. */
307		#define MATCH_ENTRY_KEYHASH(entry,hash0) \
308		(((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
309
310		/* Compute the address of the indexed entry in table. */
311		#define ADDRESS_ENTRY(table, index) \
312		((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
313
314		JS_PUBLIC_API(void)
315		JS_DHashTableFinish(JSDHashTable *table)
316	48	{
317	48	char *entryAddr, *entryLimit;
318	48	uint32 entrySize;
319	48	JSDHashEntryHdr *entry;
320
321		#ifdef DEBUG_XXXbrendan
322		static FILE *dumpfp = NULL;
323		if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
324		if (dumpfp) {
325		#ifdef MOZILLA_CLIENT
326		NS_TraceStack(1, dumpfp);
327		#endif
328		JS_DHashTableDumpMeter(table, NULL, dumpfp);
329		fputc('\n', dumpfp);
330		}
331		#endif
332
333		/* Call finalize before clearing entries, so it can enumerate them. */
334	48	table->ops->finalize(table);
335
336		/* Clear any remaining live entries. */
337	48	entryAddr = table->entryStore;
338	48	entrySize = table->entrySize;
339	48	entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
340	3248	while (entryAddr < entryLimit) {
341	3200	entry = (JSDHashEntryHdr *)entryAddr;
342	3200	if (ENTRY_IS_LIVE(entry)) {
343		METER(table->stats.removeEnums++);
344	0	table->ops->clearEntry(table, entry);
345		}
346	3200	entryAddr += entrySize;
347		}
348
349		/* Free entry storage last. */
350	48	table->ops->freeTable(table, table->entryStore);
351		}
352
353		static JSDHashEntryHdr * JS_DHASH_FASTCALL
354		SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
355		JSDHashOperator op)
356	570343	{
357	570343	JSDHashNumber hash1, hash2;
358	570343	int hashShift, sizeLog2;
359	570343	JSDHashEntryHdr *entry, *firstRemoved;
360	570343	JSDHashMatchEntry matchEntry;
361	570343	uint32 sizeMask;
362
363		METER(table->stats.searches++);
364	570343	JS_ASSERT(!(keyHash & COLLISION_FLAG));
365
366		/* Compute the primary hash address. */
367	570343	hashShift = table->hashShift;
368	570343	hash1 = HASH1(keyHash, hashShift);
369	570343	entry = ADDRESS_ENTRY(table, hash1);
370
371		/* Miss: return space for a new entry. */
372	570343	if (JS_DHASH_ENTRY_IS_FREE(entry)) {
373		METER(table->stats.misses++);
374	338843	return entry;
375		}
376
377		/* Hit: return entry. */
378	231500	matchEntry = table->ops->matchEntry;
379	231500	if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
380		METER(table->stats.hits++);
381	157445	return entry;
382		}
383
384		/* Collision: double hash. */
385	74055	sizeLog2 = JS_DHASH_BITS - table->hashShift;
386	74055	hash2 = HASH2(keyHash, sizeLog2, hashShift);
387	74055	sizeMask = JS_BITMASK(sizeLog2);
388
389		/* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
390	74055	if (ENTRY_IS_REMOVED(entry)) {
391	12992	firstRemoved = entry;
392		} else {
393	61063	firstRemoved = NULL;
394	61063	if (op == JS_DHASH_ADD)
395	52404	entry->keyHash |= COLLISION_FLAG;
396		}
397
398	164182	for (;;) {
399		METER(table->stats.steps++);
400	126148	hash1 -= hash2;
401	126148	hash1 &= sizeMask;
402
403	126148	entry = ADDRESS_ENTRY(table, hash1);
404	126148	if (JS_DHASH_ENTRY_IS_FREE(entry)) {
405		METER(table->stats.misses++);
406	38320	return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
407		}
408
409	87828	if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
410		matchEntry(table, entry, key)) {
411		METER(table->stats.hits++);
412	35735	return entry;
413		}
414
415	52093	if (ENTRY_IS_REMOVED(entry)) {
416	9255	if (!firstRemoved)
417	1847	firstRemoved = entry;
418		} else {
419	42838	if (op == JS_DHASH_ADD)
420	38034	entry->keyHash |= COLLISION_FLAG;
421		}
422		}
423
424		/* NOTREACHED */
425	570343	return NULL;
426		}
427
428		static JSBool
429		ChangeTable(JSDHashTable *table, int deltaLog2)
430	205	{
431	205	int oldLog2, newLog2;
432	205	uint32 oldCapacity, newCapacity;
433	205	char *newEntryStore, *oldEntryStore, *oldEntryAddr;
434	205	uint32 entrySize, i, nbytes;
435	205	JSDHashEntryHdr *oldEntry, *newEntry;
436	205	JSDHashGetKey getKey;
437	205	JSDHashMoveEntry moveEntry;
438
439		/* Look, but don't touch, until we succeed in getting new entry store. */
440	205	oldLog2 = JS_DHASH_BITS - table->hashShift;
441	205	newLog2 = oldLog2 + deltaLog2;
442	205	oldCapacity = JS_BIT(oldLog2);
443	205	newCapacity = JS_BIT(newLog2);
444	205	if (newCapacity >= JS_DHASH_SIZE_LIMIT)
445	0	return JS_FALSE;
446	205	entrySize = table->entrySize;
447	205	nbytes = newCapacity * entrySize;
448
449	205	newEntryStore = table->ops->allocTable(table, nbytes);
450	205	if (!newEntryStore)
451	0	return JS_FALSE;
452
453		/* We can't fail from here on, so update table parameters. */
454	205	table->hashShift = JS_DHASH_BITS - newLog2;
455	205	table->removedCount = 0;
456	205	table->generation++;
457
458		/* Assign the new entry store to table. */
459	205	memset(newEntryStore, 0, nbytes);
460	205	oldEntryAddr = oldEntryStore = table->entryStore;
461	205	table->entryStore = newEntryStore;
462	205	getKey = table->ops->getKey;
463	205	moveEntry = table->ops->moveEntry;
464
465		/* Copy only live entries, leaving removed ones behind. */
466	121933	for (i = 0; i < oldCapacity; i++) {
467	121728	oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
468	121728	if (ENTRY_IS_LIVE(oldEntry)) {
469	49939	oldEntry->keyHash &= ~COLLISION_FLAG;
470	49939	newEntry = SearchTable(table, getKey(table, oldEntry),
471		oldEntry->keyHash, JS_DHASH_ADD);
472	49939	JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
473	49939	moveEntry(table, oldEntry, newEntry);
474	49939	newEntry->keyHash = oldEntry->keyHash;
475		}
476	121728	oldEntryAddr += entrySize;
477		}
478
479	205	table->ops->freeTable(table, oldEntryStore);
480	205	return JS_TRUE;
481		}
482
483		JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
484		JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
485	520404	{
486	520404	JSDHashNumber keyHash;
487	520404	JSDHashEntryHdr *entry;
488	520404	uint32 size;
489	520404	int deltaLog2;
490
491	520404	keyHash = table->ops->hashKey(table, key);
492	520404	keyHash *= JS_DHASH_GOLDEN_RATIO;
493
494		/* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
495	520404	ENSURE_LIVE_KEYHASH(keyHash);
496	520404	keyHash &= ~COLLISION_FLAG;
497
498	520404	switch (op) {
499		case JS_DHASH_LOOKUP:
500		METER(table->stats.lookups++);
501	24765	entry = SearchTable(table, key, keyHash, op);
502	24765	break;
503
504		case JS_DHASH_ADD:
505		/*
506		* If alpha is >= .75, grow or compress the table.  If key is already
507		* in the table, we may grow once more than necessary, but only if we
508		* are on the edge of being overloaded.
509		*/
510	468652	size = JS_DHASH_TABLE_SIZE(table);
511	468652	if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
512		/* Compress if a quarter or more of all entries are removed. */
513	101	if (table->removedCount >= size >> 2) {
514		METER(table->stats.compresses++);
515	8	deltaLog2 = 0;
516		} else {
517		METER(table->stats.grows++);
518	93	deltaLog2 = 1;
519		}
520
521		/*
522		* Grow or compress table, returning null if ChangeTable fails and
523		* falling through might claim the last free entry.
524		*/
525	101	if (!ChangeTable(table, deltaLog2) &&
526		table->entryCount + table->removedCount == size - 1) {
527		METER(table->stats.addFailures++);
528	0	return NULL;
529		}
530		}
531
532		/*
533		* Look for entry after possibly growing, so we don't have to add it,
534		* then skip it while growing the table and re-add it after.
535		*/
536	468652	entry = SearchTable(table, key, keyHash, op);
537	468652	if (!ENTRY_IS_LIVE(entry)) {
538		/* Initialize the entry, indicating that it's no longer free. */
539		METER(table->stats.addMisses++);
540	327208	if (ENTRY_IS_REMOVED(entry)) {
541		METER(table->stats.addOverRemoved++);
542	12704	table->removedCount--;
543	12704	keyHash |= COLLISION_FLAG;
544		}
545	327208	if (table->ops->initEntry &&
546		!table->ops->initEntry(table, entry, key)) {
547		/* We haven't claimed entry yet; fail with null return. */
548	0	memset(entry + 1, 0, table->entrySize - sizeof *entry);
549	0	return NULL;
550		}
551	327208	entry->keyHash = keyHash;
552	327208	table->entryCount++;
553		}
554		METER(else table->stats.addHits++);
555	327208	break;
556
557		case JS_DHASH_REMOVE:
558	26987	entry = SearchTable(table, key, keyHash, op);
559	26987	if (ENTRY_IS_LIVE(entry)) {
560		/* Clear this entry and mark it as "removed". */
561		METER(table->stats.removeHits++);
562	26987	JS_DHashTableRawRemove(table, entry);
563
564		/* Shrink if alpha is <= .25 and table isn't too small already. */
565	26987	size = JS_DHASH_TABLE_SIZE(table);
566	26987	if (size > JS_DHASH_MIN_SIZE &&
567		table->entryCount <= MIN_LOAD(table, size)) {
568		METER(table->stats.shrinks++);
569	104	(void) ChangeTable(table, -1);
570		}
571		}
572		METER(else table->stats.removeMisses++);
573	26987	entry = NULL;
574	26987	break;
575
576		default:
577	0	JS_ASSERT(0);
578	0	entry = NULL;
579		}
580
581	520404	return entry;
582		}
583
584		JS_PUBLIC_API(void)
585		JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
586	327208	{
587	327208	JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */
588
589	327208	JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
590	327208	keyHash = entry->keyHash;
591	327208	table->ops->clearEntry(table, entry);
592	327208	if (keyHash & COLLISION_FLAG) {
593	22662	MARK_ENTRY_REMOVED(entry);
594	22662	table->removedCount++;
595		} else {
596		METER(table->stats.removeFrees++);
597	304546	MARK_ENTRY_FREE(entry);
598		}
599	327208	table->entryCount--;
600		}
601
602		JS_PUBLIC_API(uint32)
603		JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
604	32	{
605	32	char *entryAddr, *entryLimit;
606	32	uint32 i, capacity, entrySize, ceiling;
607	32	JSBool didRemove;
608	32	JSDHashEntryHdr *entry;
609	32	JSDHashOperator op;
610
611	32	entryAddr = table->entryStore;
612	32	entrySize = table->entrySize;
613	32	capacity = JS_DHASH_TABLE_SIZE(table);
614	32	entryLimit = entryAddr + capacity * entrySize;
615	32	i = 0;
616	32	didRemove = JS_FALSE;
617	40992	while (entryAddr < entryLimit) {
618	40960	entry = (JSDHashEntryHdr *)entryAddr;
619	40960	if (ENTRY_IS_LIVE(entry)) {
620	21995	op = etor(table, entry, i++, arg);
621	21995	if (op & JS_DHASH_REMOVE) {
622		METER(table->stats.removeEnums++);
623	0	JS_DHashTableRawRemove(table, entry);
624	0	didRemove = JS_TRUE;
625		}
626	21995	if (op & JS_DHASH_STOP)
627	0	break;
628		}
629	40960	entryAddr += entrySize;
630		}
631
632		/*
633		* Shrink or compress if a quarter or more of all entries are removed, or
634		* if the table is underloaded according to the configured minimum alpha,
635		* and is not minimal-size already.  Do this only if we removed above, so
636		* non-removing enumerations can count on stable table->entryStore until
637		* the next non-lookup-Operate or removing-Enumerate.
638		*/
639	32	if (didRemove &&
640		(table->removedCount >= capacity >> 2 ||
641		(capacity > JS_DHASH_MIN_SIZE &&
642		table->entryCount <= MIN_LOAD(table, capacity)))) {
643		METER(table->stats.enumShrinks++);
644	0	capacity = table->entryCount;
645	0	capacity += capacity >> 1;
646	0	if (capacity < JS_DHASH_MIN_SIZE)
647	0	capacity = JS_DHASH_MIN_SIZE;
648
649	0	JS_CEILING_LOG2(ceiling, capacity);
650	0	ceiling -= JS_DHASH_BITS - table->hashShift;
651
652	0	(void) ChangeTable(table, ceiling);
653		}
654	32	return i;
655		}
656
657		#ifdef JS_DHASHMETER
658		#include <math.h>
659
660		JS_PUBLIC_API(void)
661		JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
662		{
663		char *entryAddr;
664		uint32 entrySize, entryCount;
665		int hashShift, sizeLog2;
666		uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
667		JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
668		double sqsum, mean, variance, sigma;
669		JSDHashEntryHdr *entry, *probe;
670
671		entryAddr = table->entryStore;
672		entrySize = table->entrySize;
673		hashShift = table->hashShift;
674		sizeLog2 = JS_DHASH_BITS - hashShift;
675		tableSize = JS_DHASH_TABLE_SIZE(table);
676		sizeMask = JS_BITMASK(sizeLog2);
677		chainCount = maxChainLen = 0;
678		hash2 = 0;
679		sqsum = 0;
680
681		for (i = 0; i < tableSize; i++) {
682		entry = (JSDHashEntryHdr *)entryAddr;
683		entryAddr += entrySize;
684		if (!ENTRY_IS_LIVE(entry))
685		continue;
686		hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
687		saveHash1 = hash1;
688		probe = ADDRESS_ENTRY(table, hash1);
689		chainLen = 1;
690		if (probe == entry) {
691		/* Start of a (possibly unit-length) chain. */
692		chainCount++;
693		} else {
694		hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
695		hashShift);
696		do {
697		chainLen++;
698		hash1 -= hash2;
699		hash1 &= sizeMask;
700		probe = ADDRESS_ENTRY(table, hash1);
701		} while (probe != entry);
702		}
703		sqsum += chainLen * chainLen;
704		if (chainLen > maxChainLen) {
705		maxChainLen = chainLen;
706		maxChainHash1 = saveHash1;
707		maxChainHash2 = hash2;
708		}
709		}
710
711		entryCount = table->entryCount;
712		if (entryCount && chainCount) {
713		mean = (double)entryCount / chainCount;
714		variance = chainCount * sqsum - entryCount * entryCount;
715		if (variance < 0 || chainCount == 1)
716		variance = 0;
717		else
718		variance /= chainCount * (chainCount - 1);
719		sigma = sqrt(variance);
720		} else {
721		mean = sigma = 0;
722		}
723
724		fprintf(fp, "Double hashing statistics:\n");
725		fprintf(fp, "    table size (in entries): %u\n", tableSize);
726		fprintf(fp, "          number of entries: %u\n", table->entryCount);
727		fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
728		fprintf(fp, "         number of searches: %u\n", table->stats.searches);
729		fprintf(fp, "             number of hits: %u\n", table->stats.hits);
730		fprintf(fp, "           number of misses: %u\n", table->stats.misses);
731		fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
732		(double)table->stats.steps
733		/ table->stats.searches :
734		0.);
735		fprintf(fp, "     mean hash chain length: %g\n", mean);
736		fprintf(fp, "         standard deviation: %g\n", sigma);
737		fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
738		fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
739		fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
740		fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
741		fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
742		fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
743		fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
744		fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
745		fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
746		fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
747		fprintf(fp, "            number of grows: %u\n", table->stats.grows);
748		fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
749		fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
750		fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
751
752		if (dump && maxChainLen && hash2) {
753		fputs("Maximum hash chain:\n", fp);
754		hash1 = maxChainHash1;
755		hash2 = maxChainHash2;
756		entry = ADDRESS_ENTRY(table, hash1);
757		i = 0;
758		do {
759		if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
760		break;
761		hash1 -= hash2;
762		hash1 &= sizeMask;
763		entry = ADDRESS_ENTRY(table, hash1);
764		} while (JS_DHASH_ENTRY_IS_BUSY(entry));
765		}
766		}