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	0	{
62	0	return malloc(nbytes);
63		}
64
65		JS_PUBLIC_API(void)
66		JS_DHashFreeTable(JSDHashTable *table, void *ptr)
67	0	{
68	0	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	0	{
86	0	JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
87
88	0	return stub->key;
89		}
90
91		JS_PUBLIC_API(JSDHashNumber)
92		JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
93	0	{
94	0	return (JSDHashNumber)key >> 2;
95		}
96
97		JS_PUBLIC_API(JSBool)
98		JS_DHashMatchEntryStub(JSDHashTable *table,
99		const JSDHashEntryHdr *entry,
100		const void *key)
101	0	{
102	0	const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
103
104	0	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	0	{
124	0	memcpy(to, from, table->entrySize);
125		}
126
127		JS_PUBLIC_API(void)
128		JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
129	0	{
130	0	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	0	{
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	0	{
162	0	return &stub_ops;
163		}
164
165		JS_PUBLIC_API(JSDHashTable *)
166		JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
167		uint32 capacity)
168	0	{
169	0	JSDHashTable *table;
170
171	0	table = (JSDHashTable *) malloc(sizeof *table);
172	0	if (!table)
173	0	return NULL;
174	0	if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
175	0	free(table);
176	0	return NULL;
177		}
178	0	return table;
179		}
180
181		JS_PUBLIC_API(void)
182		JS_DHashTableDestroy(JSDHashTable *table)
183	0	{
184	0	JS_DHashTableFinish(table);
185	0	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	0	{
192	0	int log2;
193	0	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	0	table->ops = ops;
207	0	table->data = data;
208	0	if (capacity < JS_DHASH_MIN_SIZE)
209	0	capacity = JS_DHASH_MIN_SIZE;
210	0	log2 = JS_CeilingLog2(capacity);
211	0	capacity = JS_BIT(log2);
212	0	if (capacity >= JS_DHASH_SIZE_LIMIT)
213	0	return JS_FALSE;
214	0	table->hashShift = JS_DHASH_BITS - log2;
215	0	table->maxAlphaFrac = 0xC0;                 /* .75 */
216	0	table->minAlphaFrac = 0x40;                 /* .25 */
217	0	table->entrySize = entrySize;
218	0	table->entryCount = table->removedCount = 0;
219	0	table->generation = 0;
220	0	nbytes = capacity * entrySize;
221
222	0	table->entryStore = ops->allocTable(table, nbytes);
223	0	if (!table->entryStore)
224	0	return JS_FALSE;
225	0	memset(table->entryStore, 0, nbytes);
226		METER(memset(&table->stats, 0, sizeof table->stats));
227	0	return JS_TRUE;
228		}
229
230		/*
231		* Compute max and min load numbers (entry counts) from table params.
232		*/
233		#define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
234		#define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
235
236		JS_PUBLIC_API(void)
237		JS_DHashTableSetAlphaBounds(JSDHashTable *table,
238		float maxAlpha,
239		float minAlpha)
240	0	{
241	0	uint32 size;
242
243		/*
244		* Reject obviously insane bounds, rather than trying to guess what the
245		* buggy caller intended.
246		*/
247	0	JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
248	0	if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
249	0	return;
250
251		/*
252		* Ensure that at least one entry will always be free.  If maxAlpha at
253		* minimum size leaves no entries free, reduce maxAlpha based on minimum
254		* size and the precision limit of maxAlphaFrac's fixed point format.
255		*/
256	0	JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
257	0	if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
258	0	maxAlpha = (float)
259		(JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
260		/ JS_DHASH_MIN_SIZE;
261		}
262
263		/*
264		* Ensure that minAlpha is strictly less than half maxAlpha.  Take care
265		* not to truncate an entry's worth of alpha when storing in minAlphaFrac
266		* (8-bit fixed point format).
267		*/
268	0	JS_ASSERT(minAlpha < maxAlpha / 2);
269	0	if (minAlpha >= maxAlpha / 2) {
270	0	size = JS_DHASH_TABLE_SIZE(table);
271	0	minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
272		}
273
274	0	table->maxAlphaFrac = (uint8)(maxAlpha * 256);
275	0	table->minAlphaFrac = (uint8)(minAlpha * 256);
276		}
277
278		/*
279		* Double hashing needs the second hash code to be relatively prime to table
280		* size, so we simply make hash2 odd.
281		*/
282		#define HASH1(hash0, shift)         ((hash0) >> (shift))
283		#define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
284
285		/*
286		* Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
287		* that a removed-entry sentinel need be stored only if the removed entry had
288		* a colliding entry added after it.  Therefore we can use 1 as the collision
289		* flag in addition to the removed-entry sentinel value.  Multiplicative hash
290		* uses the high order bits of keyHash, so this least-significant reservation
291		* should not hurt the hash function's effectiveness much.
292		*
293		* If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
294		* in jsdhash.h.  It used to be private to jsdhash.c, but then became public to
295		* assist iterator writers who inspect table->entryStore directly.
296		*/
297		#define COLLISION_FLAG              ((JSDHashNumber) 1)
298		#define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
299		#define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
300		#define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
301		#define ENTRY_IS_LIVE(entry)        JS_DHASH_ENTRY_IS_LIVE(entry)
302		#define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
303
304		/* Match an entry's keyHash against an unstored one computed from a key. */
305		#define MATCH_ENTRY_KEYHASH(entry,hash0) \
306		(((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
307
308		/* Compute the address of the indexed entry in table. */
309		#define ADDRESS_ENTRY(table, index) \
310		((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
311
312		JS_PUBLIC_API(void)
313		JS_DHashTableFinish(JSDHashTable *table)
314	0	{
315	0	char *entryAddr, *entryLimit;
316	0	uint32 entrySize;
317	0	JSDHashEntryHdr *entry;
318
319		#ifdef DEBUG_XXXbrendan
320		static FILE *dumpfp = NULL;
321		if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
322		if (dumpfp) {
323		#ifdef MOZILLA_CLIENT
324		NS_TraceStack(1, dumpfp);
325		#endif
326		JS_DHashTableDumpMeter(table, NULL, dumpfp);
327		fputc('\n', dumpfp);
328		}
329		#endif
330
331		/* Call finalize before clearing entries, so it can enumerate them. */
332	0	table->ops->finalize(table);
333
334		/* Clear any remaining live entries. */
335	0	entryAddr = table->entryStore;
336	0	entrySize = table->entrySize;
337	0	entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
338	0	while (entryAddr < entryLimit) {
339	0	entry = (JSDHashEntryHdr *)entryAddr;
340	0	if (ENTRY_IS_LIVE(entry)) {
341		METER(table->stats.removeEnums++);
342	0	table->ops->clearEntry(table, entry);
343		}
344	0	entryAddr += entrySize;
345		}
346
347		/* Free entry storage last. */
348	0	table->ops->freeTable(table, table->entryStore);
349		}
350
351		static JSDHashEntryHdr *
352		SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
353		JSDHashOperator op)
354	0	{
355	0	JSDHashNumber hash1, hash2;
356	0	int hashShift, sizeLog2;
357	0	JSDHashEntryHdr *entry, *firstRemoved;
358	0	JSDHashMatchEntry matchEntry;
359	0	uint32 sizeMask;
360
361		METER(table->stats.searches++);
362	0	JS_ASSERT(!(keyHash & COLLISION_FLAG));
363
364		/* Compute the primary hash address. */
365	0	hashShift = table->hashShift;
366	0	hash1 = HASH1(keyHash, hashShift);
367	0	entry = ADDRESS_ENTRY(table, hash1);
368
369		/* Miss: return space for a new entry. */
370	0	if (JS_DHASH_ENTRY_IS_FREE(entry)) {
371		METER(table->stats.misses++);
372	0	return entry;
373		}
374
375		/* Hit: return entry. */
376	0	matchEntry = table->ops->matchEntry;
377	0	if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
378		METER(table->stats.hits++);
379	0	return entry;
380		}
381
382		/* Collision: double hash. */
383	0	sizeLog2 = JS_DHASH_BITS - table->hashShift;
384	0	hash2 = HASH2(keyHash, sizeLog2, hashShift);
385	0	sizeMask = JS_BITMASK(sizeLog2);
386
387		/* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
388	0	if (ENTRY_IS_REMOVED(entry)) {
389	0	firstRemoved = entry;
390		} else {
391	0	firstRemoved = NULL;
392	0	if (op == JS_DHASH_ADD)
393	0	entry->keyHash |= COLLISION_FLAG;
394		}
395
396	0	for (;;) {
397		METER(table->stats.steps++);
398	0	hash1 -= hash2;
399	0	hash1 &= sizeMask;
400
401	0	entry = ADDRESS_ENTRY(table, hash1);
402	0	if (JS_DHASH_ENTRY_IS_FREE(entry)) {
403		METER(table->stats.misses++);
404	0	return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
405		}
406
407	0	if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
408		matchEntry(table, entry, key)) {
409		METER(table->stats.hits++);
410	0	return entry;
411		}
412
413	0	if (ENTRY_IS_REMOVED(entry)) {
414	0	if (!firstRemoved)
415	0	firstRemoved = entry;
416		} else {
417	0	if (op == JS_DHASH_ADD)
418	0	entry->keyHash |= COLLISION_FLAG;
419		}
420		}
421
422		/* NOTREACHED */
423	0	return NULL;
424		}
425
426		static JSBool
427		ChangeTable(JSDHashTable *table, int deltaLog2)
428	0	{
429	0	int oldLog2, newLog2;
430	0	uint32 oldCapacity, newCapacity;
431	0	char *newEntryStore, *oldEntryStore, *oldEntryAddr;
432	0	uint32 entrySize, i, nbytes;
433	0	JSDHashEntryHdr *oldEntry, *newEntry;
434	0	JSDHashGetKey getKey;
435	0	JSDHashMoveEntry moveEntry;
436
437		/* Look, but don't touch, until we succeed in getting new entry store. */
438	0	oldLog2 = JS_DHASH_BITS - table->hashShift;
439	0	newLog2 = oldLog2 + deltaLog2;
440	0	oldCapacity = JS_BIT(oldLog2);
441	0	newCapacity = JS_BIT(newLog2);
442	0	if (newCapacity >= JS_DHASH_SIZE_LIMIT)
443	0	return JS_FALSE;
444	0	entrySize = table->entrySize;
445	0	nbytes = newCapacity * entrySize;
446
447	0	newEntryStore = table->ops->allocTable(table, nbytes);
448	0	if (!newEntryStore)
449	0	return JS_FALSE;
450
451		/* We can't fail from here on, so update table parameters. */
452	0	table->hashShift = JS_DHASH_BITS - newLog2;
453	0	table->removedCount = 0;
454	0	table->generation++;
455
456		/* Assign the new entry store to table. */
457	0	memset(newEntryStore, 0, nbytes);
458	0	oldEntryAddr = oldEntryStore = table->entryStore;
459	0	table->entryStore = newEntryStore;
460	0	getKey = table->ops->getKey;
461	0	moveEntry = table->ops->moveEntry;
462
463		/* Copy only live entries, leaving removed ones behind. */
464	0	for (i = 0; i < oldCapacity; i++) {
465	0	oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
466	0	if (ENTRY_IS_LIVE(oldEntry)) {
467	0	oldEntry->keyHash &= ~COLLISION_FLAG;
468	0	newEntry = SearchTable(table, getKey(table, oldEntry),
469		oldEntry->keyHash, JS_DHASH_ADD);
470	0	JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
471	0	moveEntry(table, oldEntry, newEntry);
472	0	newEntry->keyHash = oldEntry->keyHash;
473		}
474	0	oldEntryAddr += entrySize;
475		}
476
477	0	table->ops->freeTable(table, oldEntryStore);
478	0	return JS_TRUE;
479		}
480
481		JS_PUBLIC_API(JSDHashEntryHdr *)
482		JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
483	0	{
484	0	JSDHashNumber keyHash;
485	0	JSDHashEntryHdr *entry;
486	0	uint32 size;
487	0	int deltaLog2;
488
489	0	keyHash = table->ops->hashKey(table, key);
490	0	keyHash *= JS_DHASH_GOLDEN_RATIO;
491
492		/* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
493	0	ENSURE_LIVE_KEYHASH(keyHash);
494	0	keyHash &= ~COLLISION_FLAG;
495
496	0	switch (op) {
497		case JS_DHASH_LOOKUP:
498		METER(table->stats.lookups++);
499	0	entry = SearchTable(table, key, keyHash, op);
500	0	break;
501
502		case JS_DHASH_ADD:
503		/*
504		* If alpha is >= .75, grow or compress the table.  If key is already
505		* in the table, we may grow once more than necessary, but only if we
506		* are on the edge of being overloaded.
507		*/
508	0	size = JS_DHASH_TABLE_SIZE(table);
509	0	if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
510		/* Compress if a quarter or more of all entries are removed. */
511	0	if (table->removedCount >= size >> 2) {
512		METER(table->stats.compresses++);
513	0	deltaLog2 = 0;
514		} else {
515		METER(table->stats.grows++);
516	0	deltaLog2 = 1;
517		}
518
519		/*
520		* Grow or compress table, returning null if ChangeTable fails and
521		* falling through might claim the last free entry.
522		*/
523	0	if (!ChangeTable(table, deltaLog2) &&
524		table->entryCount + table->removedCount == size - 1) {
525		METER(table->stats.addFailures++);
526	0	return NULL;
527		}
528		}
529
530		/*
531		* Look for entry after possibly growing, so we don't have to add it,
532		* then skip it while growing the table and re-add it after.
533		*/
534	0	entry = SearchTable(table, key, keyHash, op);
535	0	if (!ENTRY_IS_LIVE(entry)) {
536		/* Initialize the entry, indicating that it's no longer free. */
537		METER(table->stats.addMisses++);
538	0	if (ENTRY_IS_REMOVED(entry)) {
539		METER(table->stats.addOverRemoved++);
540	0	table->removedCount--;
541	0	keyHash |= COLLISION_FLAG;
542		}
543	0	if (table->ops->initEntry &&
544		!table->ops->initEntry(table, entry, key)) {
545		/* We haven't claimed entry yet; fail with null return. */
546	0	memset(entry + 1, 0, table->entrySize - sizeof *entry);
547	0	return NULL;
548		}
549	0	entry->keyHash = keyHash;
550	0	table->entryCount++;
551		}
552		METER(else table->stats.addHits++);
553	0	break;
554
555		case JS_DHASH_REMOVE:
556	0	entry = SearchTable(table, key, keyHash, op);
557	0	if (ENTRY_IS_LIVE(entry)) {
558		/* Clear this entry and mark it as "removed". */
559		METER(table->stats.removeHits++);
560	0	JS_DHashTableRawRemove(table, entry);
561
562		/* Shrink if alpha is <= .25 and table isn't too small already. */
563	0	size = JS_DHASH_TABLE_SIZE(table);
564	0	if (size > JS_DHASH_MIN_SIZE &&
565		table->entryCount <= MIN_LOAD(table, size)) {
566		METER(table->stats.shrinks++);
567	0	(void) ChangeTable(table, -1);
568		}
569		}
570		METER(else table->stats.removeMisses++);
571	0	entry = NULL;
572	0	break;
573
574		default:
575	0	JS_ASSERT(0);
576	0	entry = NULL;
577		}
578
579	0	return entry;
580		}
581
582		JS_PUBLIC_API(void)
583		JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
584	0	{
585	0	JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */
586
587	0	JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
588	0	keyHash = entry->keyHash;
589	0	table->ops->clearEntry(table, entry);
590	0	if (keyHash & COLLISION_FLAG) {
591	0	MARK_ENTRY_REMOVED(entry);
592	0	table->removedCount++;
593		} else {
594		METER(table->stats.removeFrees++);
595	0	MARK_ENTRY_FREE(entry);
596		}
597	0	table->entryCount--;
598		}
599
600		JS_PUBLIC_API(uint32)
601		JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
602	0	{
603	0	char *entryAddr, *entryLimit;
604	0	uint32 i, capacity, entrySize;
605	0	JSBool didRemove;
606	0	JSDHashEntryHdr *entry;
607	0	JSDHashOperator op;
608
609	0	entryAddr = table->entryStore;
610	0	entrySize = table->entrySize;
611	0	capacity = JS_DHASH_TABLE_SIZE(table);
612	0	entryLimit = entryAddr + capacity * entrySize;
613	0	i = 0;
614	0	didRemove = JS_FALSE;
615	0	while (entryAddr < entryLimit) {
616	0	entry = (JSDHashEntryHdr *)entryAddr;
617	0	if (ENTRY_IS_LIVE(entry)) {
618	0	op = etor(table, entry, i++, arg);
619	0	if (op & JS_DHASH_REMOVE) {
620		METER(table->stats.removeEnums++);
621	0	JS_DHashTableRawRemove(table, entry);
622	0	didRemove = JS_TRUE;
623		}
624	0	if (op & JS_DHASH_STOP)
625	0	break;
626		}
627	0	entryAddr += entrySize;
628		}
629
630		/*
631		* Shrink or compress if a quarter or more of all entries are removed, or
632		* if the table is underloaded according to the configured minimum alpha,
633		* and is not minimal-size already.  Do this only if we removed above, so
634		* non-removing enumerations can count on stable table->entryStore until
635		* the next non-lookup-Operate or removing-Enumerate.
636		*/
637	0	if (didRemove &&
638		(table->removedCount >= capacity >> 2 ||
639		(capacity > JS_DHASH_MIN_SIZE &&
640		table->entryCount <= MIN_LOAD(table, capacity)))) {
641		METER(table->stats.enumShrinks++);
642	0	capacity = table->entryCount;
643	0	capacity += capacity >> 1;
644	0	if (capacity < JS_DHASH_MIN_SIZE)
645	0	capacity = JS_DHASH_MIN_SIZE;
646	0	(void) ChangeTable(table,
647		JS_CeilingLog2(capacity)
648		- (JS_DHASH_BITS - table->hashShift));
649		}
650	0	return i;
651		}
652
653		#ifdef JS_DHASHMETER
654		#include <math.h>
655
656		JS_PUBLIC_API(void)
657		JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
658		{
659		char *entryAddr;
660		uint32 entrySize, entryCount;
661		int hashShift, sizeLog2;
662		uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
663		JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
664		double sqsum, mean, variance, sigma;
665		JSDHashEntryHdr *entry, *probe;
666
667		entryAddr = table->entryStore;
668		entrySize = table->entrySize;
669		hashShift = table->hashShift;
670		sizeLog2 = JS_DHASH_BITS - hashShift;
671		tableSize = JS_DHASH_TABLE_SIZE(table);
672		sizeMask = JS_BITMASK(sizeLog2);
673		chainCount = maxChainLen = 0;
674		hash2 = 0;
675		sqsum = 0;
676
677		for (i = 0; i < tableSize; i++) {
678		entry = (JSDHashEntryHdr *)entryAddr;
679		entryAddr += entrySize;
680		if (!ENTRY_IS_LIVE(entry))
681		continue;
682		hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
683		saveHash1 = hash1;
684		probe = ADDRESS_ENTRY(table, hash1);
685		chainLen = 1;
686		if (probe == entry) {
687		/* Start of a (possibly unit-length) chain. */
688		chainCount++;
689		} else {
690		hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
691		hashShift);
692		do {
693		chainLen++;
694		hash1 -= hash2;
695		hash1 &= sizeMask;
696		probe = ADDRESS_ENTRY(table, hash1);
697		} while (probe != entry);
698		}
699		sqsum += chainLen * chainLen;
700		if (chainLen > maxChainLen) {
701		maxChainLen = chainLen;
702		maxChainHash1 = saveHash1;
703		maxChainHash2 = hash2;
704		}
705		}
706
707		entryCount = table->entryCount;
708		if (entryCount && chainCount) {
709		mean = (double)entryCount / chainCount;
710		variance = chainCount * sqsum - entryCount * entryCount;
711		if (variance < 0 || chainCount == 1)
712		variance = 0;
713		else
714		variance /= chainCount * (chainCount - 1);
715		sigma = sqrt(variance);
716		} else {
717		mean = sigma = 0;
718		}
719
720		fprintf(fp, "Double hashing statistics:\n");
721		fprintf(fp, "    table size (in entries): %u\n", tableSize);
722		fprintf(fp, "          number of entries: %u\n", table->entryCount);
723		fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
724		fprintf(fp, "         number of searches: %u\n", table->stats.searches);
725		fprintf(fp, "             number of hits: %u\n", table->stats.hits);
726		fprintf(fp, "           number of misses: %u\n", table->stats.misses);
727		fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
728		(double)table->stats.steps
729		/ table->stats.searches :
730		0.);
731		fprintf(fp, "     mean hash chain length: %g\n", mean);
732		fprintf(fp, "         standard deviation: %g\n", sigma);
733		fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
734		fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
735		fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
736		fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
737		fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
738		fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
739		fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
740		fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
741		fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
742		fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
743		fprintf(fp, "            number of grows: %u\n", table->stats.grows);
744		fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
745		fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
746		fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
747
748		if (dump && maxChainLen && hash2) {
749		fputs("Maximum hash chain:\n", fp);
750		hash1 = maxChainHash1;
751		hash2 = maxChainHash2;
752		entry = ADDRESS_ENTRY(table, hash1);
753		i = 0;
754		do {
755		if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
756		break;
757		hash1 -= hash2;
758		hash1 &= sizeMask;
759		entry = ADDRESS_ENTRY(table, hash1);
760		} while (JS_DHASH_ENTRY_IS_BUSY(entry));
761		}
762		}