SeaMonkey

Merge lp:~joe-nationnet-deactivatedaccount/seamonkey/seamonkey-beta into lp:~mozillateam/seamonkey/seamonkey-beta.head

  1. seamonkey-beta
  2. Merge into seamonkey-beta.head
Proposed by Joe Lesko
Status: Merged
Merged at revision: 257
Proposed branch: lp:~joe-nationnet-deactivatedaccount/seamonkey/seamonkey-beta
Merge into: lp:~mozillateam/seamonkey/seamonkey-beta.head
Diff against target: 2353 lines (+90/-2148)
13 files modified
debian/build/create-tarball (+1/-2)
debian/changelog (+51/-0)
debian/config/branch.mk (+2/-2)
debian/control (+2/-1)
debian/control.in (+2/-1)
debian/patches/build-fix-for-no-ENABLE_YARR_JIT.patch (+0/-109)
debian/patches/compile-pldhash-as-C++.patch (+0/-1970)
debian/patches/fix-build-failure-without-yarr-jit.patch (+27/-0)
debian/patches/only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch (+0/-55)
debian/patches/printf-fix.patch (+1/-1)
debian/patches/series (+1/-3)
debian/rules (+2/-3)
debian/seamonkey.desktop.in (+1/-1)
To merge this branch: bzr merge lp:~joe-nationnet-deactivatedaccount/seamonkey/seamonkey-beta
Reviewer Review Type Date Requested Status
Mozilla Team Pending
Review via email: mp+85248@code.launchpad.net

Description of the change

  * New upstream release from the beta channel (SEAMONKEY_2_6b3_RELEASE)
  * Updated build/create_tarball with fix from Chris Coulson
  * Removed patch correctly-handle-EOF.patch as it was applied upstream.

To post a comment you must log in.
lp:~joe-nationnet-deactivatedaccount/seamonkey/seamonkey-beta updated
260. By Joe Lesko

* New upstream release from the release channel (SEAMONKEY_2_6_RELEASE)
* Updated build/create_tarball with fix from Chris Coulson
* Removed patch correctly-handle-EOF.patch as it was applied upstream.
* Added patch to correct powerpc build.
  - fix-build-failure-without-yarr-jit.patch
  - Updated series.
* Above changes were brought over from beta revisions 266 through 271.

261. By Joe Lesko

* New upstream release from the release channel (SEAMONKEY_2_6_1_RELEASE)

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'debian/build/create-tarball'
2--- debian/build/create-tarball 2011-09-23 14:46:57 +0000
3+++ debian/build/create-tarball 2011-12-16 00:06:23 +0000
4@@ -232,10 +232,9 @@
5 if moz_local != None:
6 args.append('--mozilla-repo=%s' % moz_local)
7 if tag != None:
8+ args.append('--comm-rev=%s' % tag)
9 args.append('--mozilla-rev=%s' % tag)
10 do_exec(args, cwd=os.path.join(os.getcwd(), DEB_TAR_SRCDIR))
11- args = ['hg', 'update', '-r', tag]
12- do_exec(args, cwd=os.path.join(os.getcwd(), DEB_TAR_SRCDIR))
13
14 def verify_all_locales(all_locales, blfile):
15 # When we also use translations from Launchpad, there will be a file
16
17=== modified file 'debian/changelog'
18--- debian/changelog 2011-10-11 08:49:38 +0000
19+++ debian/changelog 2011-12-16 00:06:23 +0000
20@@ -1,3 +1,54 @@
21+seamonkey (2.6~b4-0ubuntu1) UNRELEASED; urgency=low
22+
23+ * New upstream release from the beta channel (SEAMONKEY_2_6b4_RELEASE)
24+
25+ -- Joe Lesko <joe@nationnet.com> Thu, 15 Dec 2011 17:01:19 -0700
26+
27+seamonkey (2.6~b3-0ubuntu1) UNRELEASED; urgency=low
28+
29+ * New upstream release from the beta channel (SEAMONKEY_2_6b3_RELEASE)
30+ * Updated build/create_tarball with fix from Chris Coulson
31+ * Removed patch correctly-handle-EOF.patch as it was applied upstream.
32+ * Added patch to correct powerpc build.
33+ - fix-build-failure-without-yarr-jit.patch
34+ - Updated series.
35+
36+ -- Joe Lesko <joe@nationnet.com> Sun, 11 Dec 2011 00:17:27 -0700
37+
38+seamonkey (2.5~b4-0ubuntu1) UNRELEASED; urgency=low
39+
40+ * New upstream release from the beta channel (SEAMONKEY_2_5b4_RELEASE)
41+ * Backport patch from aurora to correctly handle EOF in
42+ js::TokenStream::getAtSourceMappingURL on platforms with unsigned chars
43+ - add debian/patches/correctly-handle-EOF.patch
44+ - update debian/patches/series
45+ * Set MOZ_DISABLE_LIBJPEG if build is for karmic as well as lucid.
46+ - update debian/rules
47+ * Updated build/create_tarball with fix from Chris Coulson
48+
49+ -- Joe <joe@nationnet.com> Tue, 08 Nov 2011 11:26:27 -0700
50+
51+seamonkey (2.5~b3-0ubuntu1) UNRELEASED; urgency=low
52+
53+ * New upstream release from the beta channel (SEAMONKEY_2_5b3_RELEASE)
54+ - Removed DEBIAN_TAG from rules
55+ - Updated config/branch.mk to pull from beta channels
56+
57+ * Fixed patches for SEAMONKEY_2_5b3_RELEASE
58+ - Removed compile-pldhash-as-C++.patch. Included in upstream
59+ - Fixed printf-fix.patch with new diff
60+ - Updated series
61+
62+ * Fixed MimeTypes in desktop. (LP #865036 )
63+
64+ * Removed patches that were applied upstream
65+ - build-fix-for-no-ENABLE_YARR_JIT.patch
66+ - only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch
67+ * Fixed shlibs for libstartup-notification0. (LP #877925)
68+ - Refreshed control file
69+
70+ -- Joe <joe@nationnet.com> Mon, 17 Oct 2011 17:07:02 -0700
71+
72 seamonkey (2.4.1-0ubuntu1) oneiric; urgency=low
73
74 [ Joe Lesko <joe@nationnet.com> ]
75
76=== modified file 'debian/config/branch.mk'
77--- debian/config/branch.mk 2011-09-13 05:05:14 +0000
78+++ debian/config/branch.mk 2011-12-16 00:06:23 +0000
79@@ -4,5 +4,5 @@
80 DISTRIB_VERSION_MAJOR = $(shell lsb_release -s -r | cut -d '.' -f 1)
81 DISTRIB_VERSION_MINOR = $(shell lsb_release -s -r | cut -d '.' -f 2)
82
83-COMM_REPO = http://hg.mozilla.org/releases/comm-release
84-L10N_REPO = http://hg.mozilla.org/releases/l10n/mozilla-release
85+COMM_REPO = http://hg.mozilla.org/releases/comm-beta
86+L10N_REPO = http://hg.mozilla.org/releases/l10n/mozilla-beta
87
88=== modified file 'debian/control'
89--- debian/control 2011-10-11 08:49:05 +0000
90+++ debian/control 2011-12-16 00:06:23 +0000
91@@ -43,7 +43,8 @@
92 Package: seamonkey
93 Architecture: any
94 Depends: debianutils (>= 1.16),
95- ${misc:Depends}
96+ ${misc:Depends},
97+ ${shlibs:Depends}
98 Recommends: myspell-en-us | hunspell-dictionary | myspell-dictionary
99 Suggests: seamonkey-gnome-support (= ${binary:Version}),
100 latex-xft-fonts,
101
102=== modified file 'debian/control.in'
103--- debian/control.in 2011-10-11 08:49:05 +0000
104+++ debian/control.in 2011-12-16 00:06:23 +0000
105@@ -43,7 +43,8 @@
106 Package: @MOZ_APP_NAME@
107 Architecture: any
108 Depends: debianutils (>= 1.16),
109- ${misc:Depends}
110+ ${misc:Depends},
111+ ${shlibs:Depends}
112 Recommends: myspell-en-us | hunspell-dictionary | myspell-dictionary
113 Suggests: @MOZ_APP_NAME@-gnome-support (= ${binary:Version}),
114 latex-xft-fonts,
115
116=== removed file 'debian/patches/build-fix-for-no-ENABLE_YARR_JIT.patch'
117--- debian/patches/build-fix-for-no-ENABLE_YARR_JIT.patch 2011-10-11 07:49:14 +0000
118+++ debian/patches/build-fix-for-no-ENABLE_YARR_JIT.patch 1970-01-01 00:00:00 +0000
119@@ -1,109 +0,0 @@
120-# HG changeset patch
121-# User Andrew Paprocki <andrew@ishiboo.com>
122-# Date 1310430767 25200
123-# Node ID 691294843828d5b4108559b27bfe342ce3b146ef
124-# Parent 9b2e6ea86756ae95f7f5b03799663e810877ecfc
125-Bug 665819: build fix for ENABLE_YARR_JIT=0, r=dmandelin
126-
127-diff --git a/mozilla/js/src/jsregexpinlines.h b/mozilla/js/src/jsregexpinlines.h
128---- a/mozilla/js/src/jsregexpinlines.h
129-+++ b/mozilla/js/src/jsregexpinlines.h
130-@@ -486,17 +486,19 @@ RegExp::compileHelper(JSContext *cx, JSL
131- return false;
132- JSC::Yarr::JSGlobalData globalData(cx->compartment->jaegerCompartment()->execAlloc());
133- JSC::Yarr::jitCompile(yarrPattern, &globalData, codeBlock);
134- if (!codeBlock.isFallBack())
135- return true;
136- }
137- #endif
138-
139-+#if ENABLE_YARR_JIT
140- codeBlock.setFallBack(true);
141-+#endif
142- byteCode = JSC::Yarr::byteCompile(yarrPattern, cx->compartment->regExpAllocator).get();
143-
144- return true;
145- }
146-
147- inline bool
148- RegExp::compile(JSContext *cx, TokenStream *ts)
149- {
150-diff --git a/mozilla/js/src/yarr/OSAllocatorPosix.cpp b/mozilla/js/src/yarr/OSAllocatorPosix.cpp
151---- a/mozilla/js/src/yarr/OSAllocatorPosix.cpp
152-+++ b/mozilla/js/src/yarr/OSAllocatorPosix.cpp
153-@@ -24,17 +24,17 @@
154- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
155- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
156- * THE POSSIBILITY OF SUCH DAMAGE.
157- *
158- * ***** END LICENSE BLOCK ***** */
159-
160- #include "assembler/wtf/Platform.h"
161-
162--#if ENABLE_ASSEMBLER && WTF_OS_UNIX && !WTF_OS_SYMBIAN
163-+#if WTF_OS_UNIX && !WTF_OS_SYMBIAN
164-
165- #include "OSAllocator.h"
166-
167- #include <errno.h>
168- #include <sys/mman.h>
169- #include "wtf/Assertions.h"
170-
171- namespace WTF {
172-diff --git a/mozilla/js/src/yarr/wtfbridge.h b/mozilla/js/src/yarr/wtfbridge.h
173---- a/mozilla/js/src/yarr/wtfbridge.h
174-+++ b/mozilla/js/src/yarr/wtfbridge.h
175-@@ -45,17 +45,19 @@
176- * definitions for use by Yarr.
177- */
178-
179- #include "jsstr.h"
180- #include "jsprvtd.h"
181- #include "jstl.h"
182- #include "vm/String.h"
183- #include "assembler/wtf/Platform.h"
184-+#if ENABLE_YARR_JIT
185- #include "assembler/jit/ExecutableAllocator.h"
186-+#endif
187-
188- namespace JSC { namespace Yarr {
189-
190- /*
191- * Basic type definitions.
192- */
193-
194- typedef jschar UChar;
195-@@ -256,27 +258,31 @@ class Vector<OwnPtr<T> > {
196- };
197-
198- template <typename T, size_t N>
199- inline void
200- deleteAllValues(Vector<T, N> &v) {
201- v.deleteAllValues();
202- }
203-
204-+#if ENABLE_YARR_JIT
205-+
206- /*
207- * Minimal JSGlobalData. This used by Yarr to get the allocator.
208- */
209- class JSGlobalData {
210- public:
211- ExecutableAllocator *regexAllocator;
212-
213- JSGlobalData(ExecutableAllocator *regexAllocator)
214- : regexAllocator(regexAllocator) { }
215- };
216-
217-+#endif
218-+
219- /*
220- * Sentinel value used in Yarr.
221- */
222- const size_t notFound = size_t(-1);
223-
224- /*
225- * Do-nothing version of a macro used by WTF to avoid unused
226- * parameter warnings.
227-
228-
229
230=== removed file 'debian/patches/compile-pldhash-as-C++.patch'
231--- debian/patches/compile-pldhash-as-C++.patch 2011-10-11 07:49:14 +0000
232+++ debian/patches/compile-pldhash-as-C++.patch 1970-01-01 00:00:00 +0000
233@@ -1,1970 +0,0 @@
234-# HG changeset patch
235-# User Mike Hommey <mh+mozilla@glandium.org>
236-# Date 1312873597 -7200
237-# Node ID 3d20269baeeef329887625951d46872c15b4c861
238-# Parent 4c3bcc010d85f1ac063e76da0329d4df3ae6dadc
239-Bug 675618 - Compile pldhash as C++. r=bsmedberg
240-
241---- a/mozilla/xpcom/build/Makefile.in
242-+++ b/mozilla/xpcom/build/Makefile.in
243-@@ -55,10 +55,6 @@ EXPORT_LIBRARY = 1
244- GRE_MODULE = 1
245- MOZILLA_INTERNAL_API = 1
246-
247--CSRCS = \
248-- $(XPCOM_GLUE_SRC_LCSRCS) \
249-- $(NULL)
250--
251- CPPSRCS = \
252- $(XPCOM_GLUE_SRC_LCPPSRCS) \
253- $(XPCOM_GLUENS_SRC_LCPPSRCS) \
254-@@ -128,7 +124,7 @@ EXPORTS_mozilla = \
255- # Force use of PIC
256- FORCE_USE_PIC = 1
257-
258--GARBAGE += $(XPCOM_GLUE_SRC_LCSRCS) $(XPCOM_GLUE_SRC_LCPPSRCS) $(XPCOM_GLUENS_SRC_LCPPSRCS) $(wildcard *.$(OBJ_SUFFIX))
259-+GARBAGE += $(XPCOM_GLUE_SRC_LCPPSRCS) $(XPCOM_GLUENS_SRC_LCPPSRCS) $(wildcard *.$(OBJ_SUFFIX))
260-
261- include $(topsrcdir)/config/config.mk
262- include $(topsrcdir)/ipc/chromium/chromium-config.mk
263-@@ -148,5 +144,5 @@ ifeq (cocoa,$(MOZ_WIDGET_TOOLKIT))
264- CXXFLAGS += $(TK_CFLAGS)
265- endif
266-
267--export:: $(XPCOM_GLUE_SRC_CSRCS) $(XPCOM_GLUE_SRC_CPPSRCS) $(XPCOM_GLUENS_SRC_CPPSRCS)
268-+export:: $(XPCOM_GLUE_SRC_CPPSRCS) $(XPCOM_GLUENS_SRC_CPPSRCS)
269- $(INSTALL) $^ .
270---- a/mozilla/xpcom/glue/Makefile.in
271-+++ b/mozilla/xpcom/glue/Makefile.in
272-@@ -55,10 +55,6 @@ LOCAL_INCLUDES = \
273- -I$(srcdir)/../build \
274- $(NULL)
275-
276--CSRCS = \
277-- $(XPCOM_GLUE_SRC_LCSRCS) \
278-- $(NULL)
279--
280- CPPSRCS = \
281- $(XPCOM_GLUE_SRC_LCPPSRCS) \
282- $(XPCOM_GLUENS_SRC_LCPPSRCS) \
283---- a/mozilla/xpcom/glue/nomozalloc/Makefile.in
284-+++ b/mozilla/xpcom/glue/nomozalloc/Makefile.in
285-@@ -54,10 +54,6 @@ LOCAL_INCLUDES = \
286- -I$(srcdir)/../../build \
287- $(NULL)
288-
289--CSRCS = \
290-- $(XPCOM_GLUE_SRC_LCSRCS) \
291-- $(NULL)
292--
293- CPPSRCS = \
294- $(XPCOM_GLUE_SRC_LCPPSRCS) \
295- $(XPCOM_GLUENS_SRC_LCPPSRCS) \
296-@@ -69,7 +65,7 @@ SDK_LIBRARY =
297- $(LIB_PREFIX)xpcomglue_s_nomozalloc.$(LIB_SUFFIX) \
298- $(NULL)
299-
300--GARBAGE += $(CSRCS) $(CPPSRCS) DeadlockDetector.h SSE.h arm.h
301-+GARBAGE += $(CPPSRCS) DeadlockDetector.h SSE.h arm.h
302-
303- # we don't want the shared lib, but we want to force the creation of a static lib.
304- FORCE_STATIC_LIB = 1
305-@@ -94,7 +90,7 @@ OS_COMPILE_CFLAGS += -Zl
306- DEFINES += -D_USE_ANSI_CPP
307- endif
308-
309--export:: $(XPCOM_GLUE_SRC_CSRCS) $(XPCOM_GLUE_SRC_CPPSRCS) $(XPCOM_GLUENS_SRC_CPPSRCS) $(topsrcdir)/xpcom/glue/nsStringAPI.cpp $(topsrcdir)/xpcom/glue/GenericModule.cpp $(topsrcdir)/xpcom/glue/DeadlockDetector.h $(topsrcdir)/xpcom/glue/SSE.h $(topsrcdir)/xpcom/glue/arm.h
310-+export:: $(XPCOM_GLUE_SRC_CPPSRCS) $(XPCOM_GLUENS_SRC_CPPSRCS) $(topsrcdir)/xpcom/glue/nsStringAPI.cpp $(topsrcdir)/xpcom/glue/GenericModule.cpp $(topsrcdir)/xpcom/glue/DeadlockDetector.h $(topsrcdir)/xpcom/glue/SSE.h $(topsrcdir)/xpcom/glue/arm.h
311- $(INSTALL) $^ .
312-
313- ifdef TARGET_XPCOM_ABI
314---- a/mozilla/xpcom/glue/objs.mk
315-+++ b/mozilla/xpcom/glue/objs.mk
316-@@ -34,12 +34,6 @@
317- #
318- # ***** END LICENSE BLOCK *****
319-
320--XPCOM_GLUE_SRC_LCSRCS = \
321-- pldhash.c \
322-- $(NULL)
323--
324--XPCOM_GLUE_SRC_CSRCS = $(addprefix $(topsrcdir)/xpcom/glue/, $(XPCOM_GLUE_SRC_LCSRCS))
325--
326- XPCOM_GLUE_SRC_LCPPSRCS = \
327- nsArrayEnumerator.cpp \
328- nsArrayUtils.cpp \
329-@@ -66,6 +60,7 @@ XPCOM_GLUE_SRC_LCPPSRCS = \
330- nsCycleCollectionParticipant.cpp \
331- nsCycleCollectorUtils.cpp \
332- nsDeque.cpp \
333-+ pldhash.cpp \
334- $(NULL)
335-
336- XPCOM_GLUE_SRC_CPPSRCS = $(addprefix $(topsrcdir)/xpcom/glue/, $(XPCOM_GLUE_SRC_LCPPSRCS))
337---- a/mozilla/xpcom/glue/standalone/Makefile.in
338-+++ b/mozilla/xpcom/glue/standalone/Makefile.in
339-@@ -71,10 +71,6 @@ LINKSRC = nsGlueLinkingNull.cpp
340- $(warning TinderboxPrint:<a href="https://bugzilla.mozilla.org/show_bug.cgi?id=298044">Error: XPCOM Glue</a>)
341- endif
342-
343--CSRCS = \
344-- $(XPCOM_GLUE_SRC_LCSRCS) \
345-- $(NULL)
346--
347- CPPSRCS = \
348- $(XPCOM_GLUE_SRC_LCPPSRCS) \
349- nsStringAPI.cpp \
350-@@ -104,7 +100,7 @@ USE_STATIC_LIBS = 1
351- # Don't use STL wrappers here (i.e. wrapped <new>); they require mozalloc
352- STL_FLAGS =
353-
354--GARBAGE += $(XPCOM_GLUE_SRC_LCSRCS) $(XPCOM_GLUE_SRC_LCPPSRCS) $(wildcard *.$(OBJ_SUFFIX))
355-+GARBAGE += $(XPCOM_GLUE_SRC_LCPPSRCS) $(wildcard *.$(OBJ_SUFFIX))
356-
357- SRCS_IN_OBJDIR = 1
358-
359-@@ -117,7 +113,7 @@ OS_COMPILE_CFLAGS += -Zl
360- DEFINES += -D_USE_ANSI_CPP
361- endif
362-
363--export:: $(XPCOM_GLUE_SRC_CSRCS) $(XPCOM_GLUE_SRC_CPPSRCS) $(topsrcdir)/xpcom/glue/nsStringAPI.cpp
364-+export:: $(XPCOM_GLUE_SRC_CPPSRCS) $(topsrcdir)/xpcom/glue/nsStringAPI.cpp
365- $(INSTALL) $^ .
366-
367- GARBAGE += nsStringAPI.cpp
368---- a/mozilla/xpcom/glue/pldhash.c
369-+++ /dev/null
370-@@ -1,915 +0,0 @@
371--/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
372--/* ***** BEGIN LICENSE BLOCK *****
373-- * Version: MPL 1.1/GPL 2.0/LGPL 2.1
374-- *
375-- * The contents of this file are subject to the Mozilla Public License Version
376-- * 1.1 (the "License"); you may not use this file except in compliance with
377-- * the License. You may obtain a copy of the License at
378-- * http://www.mozilla.org/MPL/
379-- *
380-- * Software distributed under the License is distributed on an "AS IS" basis,
381-- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
382-- * for the specific language governing rights and limitations under the
383-- * License.
384-- *
385-- * The Original Code is Mozilla JavaScript code.
386-- *
387-- * The Initial Developer of the Original Code is
388-- * Netscape Communications Corporation.
389-- * Portions created by the Initial Developer are Copyright (C) 1999-2001
390-- * the Initial Developer. All Rights Reserved.
391-- *
392-- * Contributor(s):
393-- * Brendan Eich <brendan@mozilla.org> (Original Author)
394-- * Chris Waterson <waterson@netscape.com>
395-- * L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
396-- *
397-- * Alternatively, the contents of this file may be used under the terms of
398-- * either of the GNU General Public License Version 2 or later (the "GPL"),
399-- * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
400-- * in which case the provisions of the GPL or the LGPL are applicable instead
401-- * of those above. If you wish to allow use of your version of this file only
402-- * under the terms of either the GPL or the LGPL, and not to allow others to
403-- * use your version of this file under the terms of the MPL, indicate your
404-- * decision by deleting the provisions above and replace them with the notice
405-- * and other provisions required by the GPL or the LGPL. If you do not delete
406-- * the provisions above, a recipient may use your version of this file under
407-- * the terms of any one of the MPL, the GPL or the LGPL.
408-- *
409-- * ***** END LICENSE BLOCK ***** */
410--
411--/*
412-- * Double hashing implementation.
413-- * GENERATED BY js/src/plify_jsdhash.sed -- DO NOT EDIT!!!
414-- */
415--#include <stdio.h>
416--#include <stdlib.h>
417--#include <string.h>
418--#include "prbit.h"
419--#include "pldhash.h"
420--#include "nsDebug.h" /* for PR_ASSERT */
421--
422--#ifdef PL_DHASHMETER
423--# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
424--# include "nsTraceMalloc.h"
425--# endif
426--# define METER(x) x
427--#else
428--# define METER(x) /* nothing */
429--#endif
430--
431--/*
432-- * The following DEBUG-only code is used to assert that calls to one of
433-- * table->ops or to an enumerator do not cause re-entry into a call that
434-- * can mutate the table. The recursion level is stored in additional
435-- * space allocated at the end of the entry store to avoid changing
436-- * PLDHashTable, which could cause issues when mixing DEBUG and
437-- * non-DEBUG components.
438-- */
439--#ifdef DEBUG
440--
441--#define JSDHASH_ONELINE_ASSERT PR_ASSERT
442--#define RECURSION_LEVEL(table_) (*(PRUint32*)(table_->entryStore + \
443-- PL_DHASH_TABLE_SIZE(table_) * \
444-- table_->entrySize))
445--/*
446-- * Most callers that assert about the recursion level don't care about
447-- * this magical value because they are asserting that mutation is
448-- * allowed (and therefore the level is 0 or 1, depending on whether they
449-- * incremented it).
450-- *
451-- * Only PL_DHashTableFinish needs to allow this special value.
452-- */
453--#define IMMUTABLE_RECURSION_LEVEL ((PRUint32)-1)
454--
455--#define RECURSION_LEVEL_SAFE_TO_FINISH(table_) \
456-- (RECURSION_LEVEL(table_) == 0 || \
457-- RECURSION_LEVEL(table_) == IMMUTABLE_RECURSION_LEVEL)
458--
459--#define ENTRY_STORE_EXTRA sizeof(PRUint32)
460--#define INCREMENT_RECURSION_LEVEL(table_) \
461-- PR_BEGIN_MACRO \
462-- if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) \
463-- ++RECURSION_LEVEL(table_); \
464-- PR_END_MACRO
465--#define DECREMENT_RECURSION_LEVEL(table_) \
466-- PR_BEGIN_MACRO \
467-- if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) { \
468-- NS_ASSERTION(RECURSION_LEVEL(table_) > 0, "RECURSION_LEVEL(table_) > 0"); \
469-- --RECURSION_LEVEL(table_); \
470-- } \
471-- PR_END_MACRO
472--
473--#else
474--
475--#define ENTRY_STORE_EXTRA 0
476--#define INCREMENT_RECURSION_LEVEL(table_) PR_BEGIN_MACRO PR_END_MACRO
477--#define DECREMENT_RECURSION_LEVEL(table_) PR_BEGIN_MACRO PR_END_MACRO
478--
479--#endif /* defined(DEBUG) */
480--
481--void *
482--PL_DHashAllocTable(PLDHashTable *table, PRUint32 nbytes)
483--{
484-- return malloc(nbytes);
485--}
486--
487--void
488--PL_DHashFreeTable(PLDHashTable *table, void *ptr)
489--{
490-- free(ptr);
491--}
492--
493--PLDHashNumber
494--PL_DHashStringKey(PLDHashTable *table, const void *key)
495--{
496-- PLDHashNumber h;
497-- const unsigned char *s;
498--
499-- h = 0;
500-- for (s = (const unsigned char *) key; *s != '\0'; s++)
501-- h = PR_ROTATE_LEFT32(h, 4) ^ *s;
502-- return h;
503--}
504--
505--PLDHashNumber
506--PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key)
507--{
508-- return (PLDHashNumber)(unsigned long)key >> 2;
509--}
510--
511--PRBool
512--PL_DHashMatchEntryStub(PLDHashTable *table,
513-- const PLDHashEntryHdr *entry,
514-- const void *key)
515--{
516-- const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
517--
518-- return stub->key == key;
519--}
520--
521--PRBool
522--PL_DHashMatchStringKey(PLDHashTable *table,
523-- const PLDHashEntryHdr *entry,
524-- const void *key)
525--{
526-- const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
527--
528-- /* XXX tolerate null keys on account of sloppy Mozilla callers. */
529-- return stub->key == key ||
530-- (stub->key && key &&
531-- strcmp((const char *) stub->key, (const char *) key) == 0);
532--}
533--
534--void
535--PL_DHashMoveEntryStub(PLDHashTable *table,
536-- const PLDHashEntryHdr *from,
537-- PLDHashEntryHdr *to)
538--{
539-- memcpy(to, from, table->entrySize);
540--}
541--
542--void
543--PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry)
544--{
545-- memset(entry, 0, table->entrySize);
546--}
547--
548--void
549--PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry)
550--{
551-- const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
552--
553-- free((void *) stub->key);
554-- memset(entry, 0, table->entrySize);
555--}
556--
557--void
558--PL_DHashFinalizeStub(PLDHashTable *table)
559--{
560--}
561--
562--static const PLDHashTableOps stub_ops = {
563-- PL_DHashAllocTable,
564-- PL_DHashFreeTable,
565-- PL_DHashVoidPtrKeyStub,
566-- PL_DHashMatchEntryStub,
567-- PL_DHashMoveEntryStub,
568-- PL_DHashClearEntryStub,
569-- PL_DHashFinalizeStub,
570-- NULL
571--};
572--
573--const PLDHashTableOps *
574--PL_DHashGetStubOps(void)
575--{
576-- return &stub_ops;
577--}
578--
579--PLDHashTable *
580--PL_NewDHashTable(const PLDHashTableOps *ops, void *data, PRUint32 entrySize,
581-- PRUint32 capacity)
582--{
583-- PLDHashTable *table;
584--
585-- table = (PLDHashTable *) malloc(sizeof *table);
586-- if (!table)
587-- return NULL;
588-- if (!PL_DHashTableInit(table, ops, data, entrySize, capacity)) {
589-- free(table);
590-- return NULL;
591-- }
592-- return table;
593--}
594--
595--void
596--PL_DHashTableDestroy(PLDHashTable *table)
597--{
598-- PL_DHashTableFinish(table);
599-- free(table);
600--}
601--
602--PRBool
603--PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data,
604-- PRUint32 entrySize, PRUint32 capacity)
605--{
606-- int log2;
607-- PRUint32 nbytes;
608--
609--#ifdef DEBUG
610-- if (entrySize > 10 * sizeof(void *)) {
611-- printf_stderr(
612-- "pldhash: for the table at address %p, the given entrySize"
613-- " of %lu %s favors chaining over double hashing.\n",
614-- (void *) table,
615-- (unsigned long) entrySize,
616-- (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
617-- }
618--#endif
619--
620-- table->ops = ops;
621-- table->data = data;
622-- if (capacity < PL_DHASH_MIN_SIZE)
623-- capacity = PL_DHASH_MIN_SIZE;
624--
625-- PR_CEILING_LOG2(log2, capacity);
626--
627-- capacity = PR_BIT(log2);
628-- if (capacity >= PL_DHASH_SIZE_LIMIT)
629-- return PR_FALSE;
630-- table->hashShift = PL_DHASH_BITS - log2;
631-- table->maxAlphaFrac = (PRUint8)(0x100 * PL_DHASH_DEFAULT_MAX_ALPHA);
632-- table->minAlphaFrac = (PRUint8)(0x100 * PL_DHASH_DEFAULT_MIN_ALPHA);
633-- table->entrySize = entrySize;
634-- table->entryCount = table->removedCount = 0;
635-- table->generation = 0;
636-- nbytes = capacity * entrySize;
637--
638-- table->entryStore = (char *) ops->allocTable(table,
639-- nbytes + ENTRY_STORE_EXTRA);
640-- if (!table->entryStore)
641-- return PR_FALSE;
642-- memset(table->entryStore, 0, nbytes);
643-- METER(memset(&table->stats, 0, sizeof table->stats));
644--
645--#ifdef DEBUG
646-- RECURSION_LEVEL(table) = 0;
647--#endif
648--
649-- return PR_TRUE;
650--}
651--
652--/*
653-- * Compute max and min load numbers (entry counts) from table params.
654-- */
655--#define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
656--#define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
657--
658--void
659--PL_DHashTableSetAlphaBounds(PLDHashTable *table,
660-- float maxAlpha,
661-- float minAlpha)
662--{
663-- PRUint32 size;
664--
665-- /*
666-- * Reject obviously insane bounds, rather than trying to guess what the
667-- * buggy caller intended.
668-- */
669-- NS_ASSERTION(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha,
670-- "0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha");
671-- if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
672-- return;
673--
674-- /*
675-- * Ensure that at least one entry will always be free. If maxAlpha at
676-- * minimum size leaves no entries free, reduce maxAlpha based on minimum
677-- * size and the precision limit of maxAlphaFrac's fixed point format.
678-- */
679-- NS_ASSERTION(PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1,
680-- "PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1");
681-- if (PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) < 1) {
682-- maxAlpha = (float)
683-- (PL_DHASH_MIN_SIZE - PR_MAX(PL_DHASH_MIN_SIZE / 256, 1))
684-- / PL_DHASH_MIN_SIZE;
685-- }
686--
687-- /*
688-- * Ensure that minAlpha is strictly less than half maxAlpha. Take care
689-- * not to truncate an entry's worth of alpha when storing in minAlphaFrac
690-- * (8-bit fixed point format).
691-- */
692-- NS_ASSERTION(minAlpha < maxAlpha / 2,
693-- "minAlpha < maxAlpha / 2");
694-- if (minAlpha >= maxAlpha / 2) {
695-- size = PL_DHASH_TABLE_SIZE(table);
696-- minAlpha = (size * maxAlpha - PR_MAX(size / 256, 1)) / (2 * size);
697-- }
698--
699-- table->maxAlphaFrac = (PRUint8)(maxAlpha * 256);
700-- table->minAlphaFrac = (PRUint8)(minAlpha * 256);
701--}
702--
703--/*
704-- * Double hashing needs the second hash code to be relatively prime to table
705-- * size, so we simply make hash2 odd.
706-- */
707--#define HASH1(hash0, shift) ((hash0) >> (shift))
708--#define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
709--
710--/*
711-- * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
712-- * that a removed-entry sentinel need be stored only if the removed entry had
713-- * a colliding entry added after it. Therefore we can use 1 as the collision
714-- * flag in addition to the removed-entry sentinel value. Multiplicative hash
715-- * uses the high order bits of keyHash, so this least-significant reservation
716-- * should not hurt the hash function's effectiveness much.
717-- *
718-- * If you change any of these magic numbers, also update PL_DHASH_ENTRY_IS_LIVE
719-- * in pldhash.h. It used to be private to pldhash.c, but then became public to
720-- * assist iterator writers who inspect table->entryStore directly.
721-- */
722--#define COLLISION_FLAG ((PLDHashNumber) 1)
723--#define MARK_ENTRY_FREE(entry) ((entry)->keyHash = 0)
724--#define MARK_ENTRY_REMOVED(entry) ((entry)->keyHash = 1)
725--#define ENTRY_IS_REMOVED(entry) ((entry)->keyHash == 1)
726--#define ENTRY_IS_LIVE(entry) PL_DHASH_ENTRY_IS_LIVE(entry)
727--#define ENSURE_LIVE_KEYHASH(hash0) if (hash0 < 2) hash0 -= 2; else (void)0
728--
729--/* Match an entry's keyHash against an unstored one computed from a key. */
730--#define MATCH_ENTRY_KEYHASH(entry,hash0) \
731-- (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
732--
733--/* Compute the address of the indexed entry in table. */
734--#define ADDRESS_ENTRY(table, index) \
735-- ((PLDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
736--
737--void
738--PL_DHashTableFinish(PLDHashTable *table)
739--{
740-- char *entryAddr, *entryLimit;
741-- PRUint32 entrySize;
742-- PLDHashEntryHdr *entry;
743--
744--#ifdef DEBUG_XXXbrendan
745-- static FILE *dumpfp = NULL;
746-- if (!dumpfp) dumpfp = fopen("/tmp/pldhash.bigdump", "w");
747-- if (dumpfp) {
748--#ifdef MOZILLA_CLIENT
749-- NS_TraceStack(1, dumpfp);
750--#endif
751-- PL_DHashTableDumpMeter(table, NULL, dumpfp);
752-- fputc('\n', dumpfp);
753-- }
754--#endif
755--
756-- INCREMENT_RECURSION_LEVEL(table);
757--
758-- /* Call finalize before clearing entries, so it can enumerate them. */
759-- table->ops->finalize(table);
760--
761-- /* Clear any remaining live entries. */
762-- entryAddr = table->entryStore;
763-- entrySize = table->entrySize;
764-- entryLimit = entryAddr + PL_DHASH_TABLE_SIZE(table) * entrySize;
765-- while (entryAddr < entryLimit) {
766-- entry = (PLDHashEntryHdr *)entryAddr;
767-- if (ENTRY_IS_LIVE(entry)) {
768-- METER(table->stats.removeEnums++);
769-- table->ops->clearEntry(table, entry);
770-- }
771-- entryAddr += entrySize;
772-- }
773--
774-- DECREMENT_RECURSION_LEVEL(table);
775-- NS_ASSERTION(RECURSION_LEVEL_SAFE_TO_FINISH(table),
776-- "RECURSION_LEVEL_SAFE_TO_FINISH(table)");
777--
778-- /* Free entry storage last. */
779-- table->ops->freeTable(table, table->entryStore);
780--}
781--
782--static PLDHashEntryHdr * PL_DHASH_FASTCALL
783--SearchTable(PLDHashTable *table, const void *key, PLDHashNumber keyHash,
784-- PLDHashOperator op)
785--{
786-- PLDHashNumber hash1, hash2;
787-- int hashShift, sizeLog2;
788-- PLDHashEntryHdr *entry, *firstRemoved;
789-- PLDHashMatchEntry matchEntry;
790-- PRUint32 sizeMask;
791--
792-- METER(table->stats.searches++);
793-- NS_ASSERTION(!(keyHash & COLLISION_FLAG),
794-- "!(keyHash & COLLISION_FLAG)");
795--
796-- /* Compute the primary hash address. */
797-- hashShift = table->hashShift;
798-- hash1 = HASH1(keyHash, hashShift);
799-- entry = ADDRESS_ENTRY(table, hash1);
800--
801-- /* Miss: return space for a new entry. */
802-- if (PL_DHASH_ENTRY_IS_FREE(entry)) {
803-- METER(table->stats.misses++);
804-- return entry;
805-- }
806--
807-- /* Hit: return entry. */
808-- matchEntry = table->ops->matchEntry;
809-- if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
810-- METER(table->stats.hits++);
811-- return entry;
812-- }
813--
814-- /* Collision: double hash. */
815-- sizeLog2 = PL_DHASH_BITS - table->hashShift;
816-- hash2 = HASH2(keyHash, sizeLog2, hashShift);
817-- sizeMask = PR_BITMASK(sizeLog2);
818--
819-- /* Save the first removed entry pointer so PL_DHASH_ADD can recycle it. */
820-- firstRemoved = NULL;
821--
822-- for (;;) {
823-- if (NS_UNLIKELY(ENTRY_IS_REMOVED(entry))) {
824-- if (!firstRemoved)
825-- firstRemoved = entry;
826-- } else {
827-- if (op == PL_DHASH_ADD)
828-- entry->keyHash |= COLLISION_FLAG;
829-- }
830--
831-- METER(table->stats.steps++);
832-- hash1 -= hash2;
833-- hash1 &= sizeMask;
834--
835-- entry = ADDRESS_ENTRY(table, hash1);
836-- if (PL_DHASH_ENTRY_IS_FREE(entry)) {
837-- METER(table->stats.misses++);
838-- return (firstRemoved && op == PL_DHASH_ADD) ? firstRemoved : entry;
839-- }
840--
841-- if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
842-- matchEntry(table, entry, key)) {
843-- METER(table->stats.hits++);
844-- return entry;
845-- }
846-- }
847--
848-- /* NOTREACHED */
849-- return NULL;
850--}
851--
852--/*
853-- * This is a copy of SearchTable, used by ChangeTable, hardcoded to
854-- * 1. assume |op == PL_DHASH_ADD|,
855-- * 2. assume that |key| will never match an existing entry, and
856-- * 3. assume that no entries have been removed from the current table
857-- * structure.
858-- * Avoiding the need for |key| means we can avoid needing a way to map
859-- * entries to keys, which means callers can use complex key types more
860-- * easily.
861-- */
862--static PLDHashEntryHdr * PL_DHASH_FASTCALL
863--FindFreeEntry(PLDHashTable *table, PLDHashNumber keyHash)
864--{
865-- PLDHashNumber hash1, hash2;
866-- int hashShift, sizeLog2;
867-- PLDHashEntryHdr *entry;
868-- PRUint32 sizeMask;
869--
870-- METER(table->stats.searches++);
871-- NS_ASSERTION(!(keyHash & COLLISION_FLAG),
872-- "!(keyHash & COLLISION_FLAG)");
873--
874-- /* Compute the primary hash address. */
875-- hashShift = table->hashShift;
876-- hash1 = HASH1(keyHash, hashShift);
877-- entry = ADDRESS_ENTRY(table, hash1);
878--
879-- /* Miss: return space for a new entry. */
880-- if (PL_DHASH_ENTRY_IS_FREE(entry)) {
881-- METER(table->stats.misses++);
882-- return entry;
883-- }
884--
885-- /* Collision: double hash. */
886-- sizeLog2 = PL_DHASH_BITS - table->hashShift;
887-- hash2 = HASH2(keyHash, sizeLog2, hashShift);
888-- sizeMask = PR_BITMASK(sizeLog2);
889--
890-- for (;;) {
891-- NS_ASSERTION(!ENTRY_IS_REMOVED(entry),
892-- "!ENTRY_IS_REMOVED(entry)");
893-- entry->keyHash |= COLLISION_FLAG;
894--
895-- METER(table->stats.steps++);
896-- hash1 -= hash2;
897-- hash1 &= sizeMask;
898--
899-- entry = ADDRESS_ENTRY(table, hash1);
900-- if (PL_DHASH_ENTRY_IS_FREE(entry)) {
901-- METER(table->stats.misses++);
902-- return entry;
903-- }
904-- }
905--
906-- /* NOTREACHED */
907-- return NULL;
908--}
909--
910--static PRBool
911--ChangeTable(PLDHashTable *table, int deltaLog2)
912--{
913-- int oldLog2, newLog2;
914-- PRUint32 oldCapacity, newCapacity;
915-- char *newEntryStore, *oldEntryStore, *oldEntryAddr;
916-- PRUint32 entrySize, i, nbytes;
917-- PLDHashEntryHdr *oldEntry, *newEntry;
918-- PLDHashMoveEntry moveEntry;
919--#ifdef DEBUG
920-- PRUint32 recursionLevel;
921--#endif
922--
923-- /* Look, but don't touch, until we succeed in getting new entry store. */
924-- oldLog2 = PL_DHASH_BITS - table->hashShift;
925-- newLog2 = oldLog2 + deltaLog2;
926-- oldCapacity = PR_BIT(oldLog2);
927-- newCapacity = PR_BIT(newLog2);
928-- if (newCapacity >= PL_DHASH_SIZE_LIMIT)
929-- return PR_FALSE;
930-- entrySize = table->entrySize;
931-- nbytes = newCapacity * entrySize;
932--
933-- newEntryStore = (char *) table->ops->allocTable(table,
934-- nbytes + ENTRY_STORE_EXTRA);
935-- if (!newEntryStore)
936-- return PR_FALSE;
937--
938-- /* We can't fail from here on, so update table parameters. */
939--#ifdef DEBUG
940-- recursionLevel = RECURSION_LEVEL(table);
941--#endif
942-- table->hashShift = PL_DHASH_BITS - newLog2;
943-- table->removedCount = 0;
944-- table->generation++;
945--
946-- /* Assign the new entry store to table. */
947-- memset(newEntryStore, 0, nbytes);
948-- oldEntryAddr = oldEntryStore = table->entryStore;
949-- table->entryStore = newEntryStore;
950-- moveEntry = table->ops->moveEntry;
951--#ifdef DEBUG
952-- RECURSION_LEVEL(table) = recursionLevel;
953--#endif
954--
955-- /* Copy only live entries, leaving removed ones behind. */
956-- for (i = 0; i < oldCapacity; i++) {
957-- oldEntry = (PLDHashEntryHdr *)oldEntryAddr;
958-- if (ENTRY_IS_LIVE(oldEntry)) {
959-- oldEntry->keyHash &= ~COLLISION_FLAG;
960-- newEntry = FindFreeEntry(table, oldEntry->keyHash);
961-- NS_ASSERTION(PL_DHASH_ENTRY_IS_FREE(newEntry),
962-- "PL_DHASH_ENTRY_IS_FREE(newEntry)");
963-- moveEntry(table, oldEntry, newEntry);
964-- newEntry->keyHash = oldEntry->keyHash;
965-- }
966-- oldEntryAddr += entrySize;
967-- }
968--
969-- table->ops->freeTable(table, oldEntryStore);
970-- return PR_TRUE;
971--}
972--
973--PLDHashEntryHdr * PL_DHASH_FASTCALL
974--PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op)
975--{
976-- PLDHashNumber keyHash;
977-- PLDHashEntryHdr *entry;
978-- PRUint32 size;
979-- int deltaLog2;
980--
981-- NS_ASSERTION(op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0,
982-- "op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0");
983-- INCREMENT_RECURSION_LEVEL(table);
984--
985-- keyHash = table->ops->hashKey(table, key);
986-- keyHash *= PL_DHASH_GOLDEN_RATIO;
987--
988-- /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
989-- ENSURE_LIVE_KEYHASH(keyHash);
990-- keyHash &= ~COLLISION_FLAG;
991--
992-- switch (op) {
993-- case PL_DHASH_LOOKUP:
994-- METER(table->stats.lookups++);
995-- entry = SearchTable(table, key, keyHash, op);
996-- break;
997--
998-- case PL_DHASH_ADD:
999-- /*
1000-- * If alpha is >= .75, grow or compress the table. If key is already
1001-- * in the table, we may grow once more than necessary, but only if we
1002-- * are on the edge of being overloaded.
1003-- */
1004-- size = PL_DHASH_TABLE_SIZE(table);
1005-- if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
1006-- /* Compress if a quarter or more of all entries are removed. */
1007-- if (table->removedCount >= size >> 2) {
1008-- METER(table->stats.compresses++);
1009-- deltaLog2 = 0;
1010-- } else {
1011-- METER(table->stats.grows++);
1012-- deltaLog2 = 1;
1013-- }
1014--
1015-- /*
1016-- * Grow or compress table, returning null if ChangeTable fails and
1017-- * falling through might claim the last free entry.
1018-- */
1019-- if (!ChangeTable(table, deltaLog2) &&
1020-- table->entryCount + table->removedCount == size - 1) {
1021-- METER(table->stats.addFailures++);
1022-- entry = NULL;
1023-- break;
1024-- }
1025-- }
1026--
1027-- /*
1028-- * Look for entry after possibly growing, so we don't have to add it,
1029-- * then skip it while growing the table and re-add it after.
1030-- */
1031-- entry = SearchTable(table, key, keyHash, op);
1032-- if (!ENTRY_IS_LIVE(entry)) {
1033-- /* Initialize the entry, indicating that it's no longer free. */
1034-- METER(table->stats.addMisses++);
1035-- if (ENTRY_IS_REMOVED(entry)) {
1036-- METER(table->stats.addOverRemoved++);
1037-- table->removedCount--;
1038-- keyHash |= COLLISION_FLAG;
1039-- }
1040-- if (table->ops->initEntry &&
1041-- !table->ops->initEntry(table, entry, key)) {
1042-- /* We haven't claimed entry yet; fail with null return. */
1043-- memset(entry + 1, 0, table->entrySize - sizeof *entry);
1044-- entry = NULL;
1045-- break;
1046-- }
1047-- entry->keyHash = keyHash;
1048-- table->entryCount++;
1049-- }
1050-- METER(else table->stats.addHits++);
1051-- break;
1052--
1053-- case PL_DHASH_REMOVE:
1054-- entry = SearchTable(table, key, keyHash, op);
1055-- if (ENTRY_IS_LIVE(entry)) {
1056-- /* Clear this entry and mark it as "removed". */
1057-- METER(table->stats.removeHits++);
1058-- PL_DHashTableRawRemove(table, entry);
1059--
1060-- /* Shrink if alpha is <= .25 and table isn't too small already. */
1061-- size = PL_DHASH_TABLE_SIZE(table);
1062-- if (size > PL_DHASH_MIN_SIZE &&
1063-- table->entryCount <= MIN_LOAD(table, size)) {
1064-- METER(table->stats.shrinks++);
1065-- (void) ChangeTable(table, -1);
1066-- }
1067-- }
1068-- METER(else table->stats.removeMisses++);
1069-- entry = NULL;
1070-- break;
1071--
1072-- default:
1073-- NS_NOTREACHED("0");
1074-- entry = NULL;
1075-- }
1076--
1077-- DECREMENT_RECURSION_LEVEL(table);
1078--
1079-- return entry;
1080--}
1081--
1082--void
1083--PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry)
1084--{
1085-- PLDHashNumber keyHash; /* load first in case clearEntry goofs it */
1086--
1087-- NS_ASSERTION(RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL,
1088-- "RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL");
1089--
1090-- NS_ASSERTION(PL_DHASH_ENTRY_IS_LIVE(entry),
1091-- "PL_DHASH_ENTRY_IS_LIVE(entry)");
1092-- keyHash = entry->keyHash;
1093-- table->ops->clearEntry(table, entry);
1094-- if (keyHash & COLLISION_FLAG) {
1095-- MARK_ENTRY_REMOVED(entry);
1096-- table->removedCount++;
1097-- } else {
1098-- METER(table->stats.removeFrees++);
1099-- MARK_ENTRY_FREE(entry);
1100-- }
1101-- table->entryCount--;
1102--}
1103--
1104--PRUint32
1105--PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg)
1106--{
1107-- char *entryAddr, *entryLimit;
1108-- PRUint32 i, capacity, entrySize, ceiling;
1109-- PRBool didRemove;
1110-- PLDHashEntryHdr *entry;
1111-- PLDHashOperator op;
1112--
1113-- INCREMENT_RECURSION_LEVEL(table);
1114--
1115-- entryAddr = table->entryStore;
1116-- entrySize = table->entrySize;
1117-- capacity = PL_DHASH_TABLE_SIZE(table);
1118-- entryLimit = entryAddr + capacity * entrySize;
1119-- i = 0;
1120-- didRemove = PR_FALSE;
1121-- while (entryAddr < entryLimit) {
1122-- entry = (PLDHashEntryHdr *)entryAddr;
1123-- if (ENTRY_IS_LIVE(entry)) {
1124-- op = etor(table, entry, i++, arg);
1125-- if (op & PL_DHASH_REMOVE) {
1126-- METER(table->stats.removeEnums++);
1127-- PL_DHashTableRawRemove(table, entry);
1128-- didRemove = PR_TRUE;
1129-- }
1130-- if (op & PL_DHASH_STOP)
1131-- break;
1132-- }
1133-- entryAddr += entrySize;
1134-- }
1135--
1136-- NS_ASSERTION(!didRemove || RECURSION_LEVEL(table) == 1,
1137-- "!didRemove || RECURSION_LEVEL(table) == 1");
1138--
1139-- /*
1140-- * Shrink or compress if a quarter or more of all entries are removed, or
1141-- * if the table is underloaded according to the configured minimum alpha,
1142-- * and is not minimal-size already. Do this only if we removed above, so
1143-- * non-removing enumerations can count on stable table->entryStore until
1144-- * the next non-lookup-Operate or removing-Enumerate.
1145-- */
1146-- if (didRemove &&
1147-- (table->removedCount >= capacity >> 2 ||
1148-- (capacity > PL_DHASH_MIN_SIZE &&
1149-- table->entryCount <= MIN_LOAD(table, capacity)))) {
1150-- METER(table->stats.enumShrinks++);
1151-- capacity = table->entryCount;
1152-- capacity += capacity >> 1;
1153-- if (capacity < PL_DHASH_MIN_SIZE)
1154-- capacity = PL_DHASH_MIN_SIZE;
1155--
1156-- PR_CEILING_LOG2(ceiling, capacity);
1157-- ceiling -= PL_DHASH_BITS - table->hashShift;
1158--
1159-- (void) ChangeTable(table, ceiling);
1160-- }
1161--
1162-- DECREMENT_RECURSION_LEVEL(table);
1163--
1164-- return i;
1165--}
1166--
1167--#ifdef DEBUG
1168--void
1169--PL_DHashMarkTableImmutable(PLDHashTable *table)
1170--{
1171-- RECURSION_LEVEL(table) = IMMUTABLE_RECURSION_LEVEL;
1172--}
1173--#endif
1174--
1175--#ifdef PL_DHASHMETER
1176--#include <math.h>
1177--
1178--void
1179--PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp)
1180--{
1181-- char *entryAddr;
1182-- PRUint32 entrySize, entryCount;
1183-- int hashShift, sizeLog2;
1184-- PRUint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
1185-- PLDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
1186-- double sqsum, mean, variance, sigma;
1187-- PLDHashEntryHdr *entry, *probe;
1188--
1189-- entryAddr = table->entryStore;
1190-- entrySize = table->entrySize;
1191-- hashShift = table->hashShift;
1192-- sizeLog2 = PL_DHASH_BITS - hashShift;
1193-- tableSize = PL_DHASH_TABLE_SIZE(table);
1194-- sizeMask = PR_BITMASK(sizeLog2);
1195-- chainCount = maxChainLen = 0;
1196-- hash2 = 0;
1197-- sqsum = 0;
1198--
1199-- for (i = 0; i < tableSize; i++) {
1200-- entry = (PLDHashEntryHdr *)entryAddr;
1201-- entryAddr += entrySize;
1202-- if (!ENTRY_IS_LIVE(entry))
1203-- continue;
1204-- hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
1205-- saveHash1 = hash1;
1206-- probe = ADDRESS_ENTRY(table, hash1);
1207-- chainLen = 1;
1208-- if (probe == entry) {
1209-- /* Start of a (possibly unit-length) chain. */
1210-- chainCount++;
1211-- } else {
1212-- hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
1213-- hashShift);
1214-- do {
1215-- chainLen++;
1216-- hash1 -= hash2;
1217-- hash1 &= sizeMask;
1218-- probe = ADDRESS_ENTRY(table, hash1);
1219-- } while (probe != entry);
1220-- }
1221-- sqsum += chainLen * chainLen;
1222-- if (chainLen > maxChainLen) {
1223-- maxChainLen = chainLen;
1224-- maxChainHash1 = saveHash1;
1225-- maxChainHash2 = hash2;
1226-- }
1227-- }
1228--
1229-- entryCount = table->entryCount;
1230-- if (entryCount && chainCount) {
1231-- mean = (double)entryCount / chainCount;
1232-- variance = chainCount * sqsum - entryCount * entryCount;
1233-- if (variance < 0 || chainCount == 1)
1234-- variance = 0;
1235-- else
1236-- variance /= chainCount * (chainCount - 1);
1237-- sigma = sqrt(variance);
1238-- } else {
1239-- mean = sigma = 0;
1240-- }
1241--
1242-- fprintf(fp, "Double hashing statistics:\n");
1243-- fprintf(fp, " table size (in entries): %u\n", tableSize);
1244-- fprintf(fp, " number of entries: %u\n", table->entryCount);
1245-- fprintf(fp, " number of removed entries: %u\n", table->removedCount);
1246-- fprintf(fp, " number of searches: %u\n", table->stats.searches);
1247-- fprintf(fp, " number of hits: %u\n", table->stats.hits);
1248-- fprintf(fp, " number of misses: %u\n", table->stats.misses);
1249-- fprintf(fp, " mean steps per search: %g\n", table->stats.searches ?
1250-- (double)table->stats.steps
1251-- / table->stats.searches :
1252-- 0.);
1253-- fprintf(fp, " mean hash chain length: %g\n", mean);
1254-- fprintf(fp, " standard deviation: %g\n", sigma);
1255-- fprintf(fp, " maximum hash chain length: %u\n", maxChainLen);
1256-- fprintf(fp, " number of lookups: %u\n", table->stats.lookups);
1257-- fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
1258-- fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
1259-- fprintf(fp, " adds that found an entry: %u\n", table->stats.addHits);
1260-- fprintf(fp, " add failures: %u\n", table->stats.addFailures);
1261-- fprintf(fp, " useful removes: %u\n", table->stats.removeHits);
1262-- fprintf(fp, " useless removes: %u\n", table->stats.removeMisses);
1263-- fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
1264-- fprintf(fp, " removes while enumerating: %u\n", table->stats.removeEnums);
1265-- fprintf(fp, " number of grows: %u\n", table->stats.grows);
1266-- fprintf(fp, " number of shrinks: %u\n", table->stats.shrinks);
1267-- fprintf(fp, " number of compresses: %u\n", table->stats.compresses);
1268-- fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
1269--
1270-- if (dump && maxChainLen && hash2) {
1271-- fputs("Maximum hash chain:\n", fp);
1272-- hash1 = maxChainHash1;
1273-- hash2 = maxChainHash2;
1274-- entry = ADDRESS_ENTRY(table, hash1);
1275-- i = 0;
1276-- do {
1277-- if (dump(table, entry, i++, fp) != PL_DHASH_NEXT)
1278-- break;
1279-- hash1 -= hash2;
1280-- hash1 &= sizeMask;
1281-- entry = ADDRESS_ENTRY(table, hash1);
1282-- } while (PL_DHASH_ENTRY_IS_BUSY(entry));
1283-- }
1284--}
1285--#endif /* PL_DHASHMETER */
1286---- /dev/null
1287-+++ b/mozilla/xpcom/glue/pldhash.cpp
1288-@@ -0,0 +1,915 @@
1289-+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1290-+/* ***** BEGIN LICENSE BLOCK *****
1291-+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
1292-+ *
1293-+ * The contents of this file are subject to the Mozilla Public License Version
1294-+ * 1.1 (the "License"); you may not use this file except in compliance with
1295-+ * the License. You may obtain a copy of the License at
1296-+ * http://www.mozilla.org/MPL/
1297-+ *
1298-+ * Software distributed under the License is distributed on an "AS IS" basis,
1299-+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
1300-+ * for the specific language governing rights and limitations under the
1301-+ * License.
1302-+ *
1303-+ * The Original Code is Mozilla JavaScript code.
1304-+ *
1305-+ * The Initial Developer of the Original Code is
1306-+ * Netscape Communications Corporation.
1307-+ * Portions created by the Initial Developer are Copyright (C) 1999-2001
1308-+ * the Initial Developer. All Rights Reserved.
1309-+ *
1310-+ * Contributor(s):
1311-+ * Brendan Eich <brendan@mozilla.org> (Original Author)
1312-+ * Chris Waterson <waterson@netscape.com>
1313-+ * L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
1314-+ *
1315-+ * Alternatively, the contents of this file may be used under the terms of
1316-+ * either of the GNU General Public License Version 2 or later (the "GPL"),
1317-+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
1318-+ * in which case the provisions of the GPL or the LGPL are applicable instead
1319-+ * of those above. If you wish to allow use of your version of this file only
1320-+ * under the terms of either the GPL or the LGPL, and not to allow others to
1321-+ * use your version of this file under the terms of the MPL, indicate your
1322-+ * decision by deleting the provisions above and replace them with the notice
1323-+ * and other provisions required by the GPL or the LGPL. If you do not delete
1324-+ * the provisions above, a recipient may use your version of this file under
1325-+ * the terms of any one of the MPL, the GPL or the LGPL.
1326-+ *
1327-+ * ***** END LICENSE BLOCK ***** */
1328-+
1329-+/*
1330-+ * Double hashing implementation.
1331-+ * GENERATED BY js/src/plify_jsdhash.sed -- DO NOT EDIT!!!
1332-+ */
1333-+#include <stdio.h>
1334-+#include <stdlib.h>
1335-+#include <string.h>
1336-+#include "prbit.h"
1337-+#include "pldhash.h"
1338-+#include "nsDebug.h" /* for PR_ASSERT */
1339-+
1340-+#ifdef PL_DHASHMETER
1341-+# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
1342-+# include "nsTraceMalloc.h"
1343-+# endif
1344-+# define METER(x) x
1345-+#else
1346-+# define METER(x) /* nothing */
1347-+#endif
1348-+
1349-+/*
1350-+ * The following DEBUG-only code is used to assert that calls to one of
1351-+ * table->ops or to an enumerator do not cause re-entry into a call that
1352-+ * can mutate the table. The recursion level is stored in additional
1353-+ * space allocated at the end of the entry store to avoid changing
1354-+ * PLDHashTable, which could cause issues when mixing DEBUG and
1355-+ * non-DEBUG components.
1356-+ */
1357-+#ifdef DEBUG
1358-+
1359-+#define JSDHASH_ONELINE_ASSERT PR_ASSERT
1360-+#define RECURSION_LEVEL(table_) (*(PRUint32*)(table_->entryStore + \
1361-+ PL_DHASH_TABLE_SIZE(table_) * \
1362-+ table_->entrySize))
1363-+/*
1364-+ * Most callers that assert about the recursion level don't care about
1365-+ * this magical value because they are asserting that mutation is
1366-+ * allowed (and therefore the level is 0 or 1, depending on whether they
1367-+ * incremented it).
1368-+ *
1369-+ * Only PL_DHashTableFinish needs to allow this special value.
1370-+ */
1371-+#define IMMUTABLE_RECURSION_LEVEL ((PRUint32)-1)
1372-+
1373-+#define RECURSION_LEVEL_SAFE_TO_FINISH(table_) \
1374-+ (RECURSION_LEVEL(table_) == 0 || \
1375-+ RECURSION_LEVEL(table_) == IMMUTABLE_RECURSION_LEVEL)
1376-+
1377-+#define ENTRY_STORE_EXTRA sizeof(PRUint32)
1378-+#define INCREMENT_RECURSION_LEVEL(table_) \
1379-+ PR_BEGIN_MACRO \
1380-+ if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) \
1381-+ ++RECURSION_LEVEL(table_); \
1382-+ PR_END_MACRO
1383-+#define DECREMENT_RECURSION_LEVEL(table_) \
1384-+ PR_BEGIN_MACRO \
1385-+ if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) { \
1386-+ NS_ASSERTION(RECURSION_LEVEL(table_) > 0, "RECURSION_LEVEL(table_) > 0"); \
1387-+ --RECURSION_LEVEL(table_); \
1388-+ } \
1389-+ PR_END_MACRO
1390-+
1391-+#else
1392-+
1393-+#define ENTRY_STORE_EXTRA 0
1394-+#define INCREMENT_RECURSION_LEVEL(table_) PR_BEGIN_MACRO PR_END_MACRO
1395-+#define DECREMENT_RECURSION_LEVEL(table_) PR_BEGIN_MACRO PR_END_MACRO
1396-+
1397-+#endif /* defined(DEBUG) */
1398-+
1399-+void *
1400-+PL_DHashAllocTable(PLDHashTable *table, PRUint32 nbytes)
1401-+{
1402-+ return malloc(nbytes);
1403-+}
1404-+
1405-+void
1406-+PL_DHashFreeTable(PLDHashTable *table, void *ptr)
1407-+{
1408-+ free(ptr);
1409-+}
1410-+
1411-+PLDHashNumber
1412-+PL_DHashStringKey(PLDHashTable *table, const void *key)
1413-+{
1414-+ PLDHashNumber h;
1415-+ const unsigned char *s;
1416-+
1417-+ h = 0;
1418-+ for (s = (const unsigned char *) key; *s != '\0'; s++)
1419-+ h = PR_ROTATE_LEFT32(h, 4) ^ *s;
1420-+ return h;
1421-+}
1422-+
1423-+PLDHashNumber
1424-+PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key)
1425-+{
1426-+ return (PLDHashNumber)(unsigned long)key >> 2;
1427-+}
1428-+
1429-+PRBool
1430-+PL_DHashMatchEntryStub(PLDHashTable *table,
1431-+ const PLDHashEntryHdr *entry,
1432-+ const void *key)
1433-+{
1434-+ const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
1435-+
1436-+ return stub->key == key;
1437-+}
1438-+
1439-+PRBool
1440-+PL_DHashMatchStringKey(PLDHashTable *table,
1441-+ const PLDHashEntryHdr *entry,
1442-+ const void *key)
1443-+{
1444-+ const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
1445-+
1446-+ /* XXX tolerate null keys on account of sloppy Mozilla callers. */
1447-+ return stub->key == key ||
1448-+ (stub->key && key &&
1449-+ strcmp((const char *) stub->key, (const char *) key) == 0);
1450-+}
1451-+
1452-+void
1453-+PL_DHashMoveEntryStub(PLDHashTable *table,
1454-+ const PLDHashEntryHdr *from,
1455-+ PLDHashEntryHdr *to)
1456-+{
1457-+ memcpy(to, from, table->entrySize);
1458-+}
1459-+
1460-+void
1461-+PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry)
1462-+{
1463-+ memset(entry, 0, table->entrySize);
1464-+}
1465-+
1466-+void
1467-+PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry)
1468-+{
1469-+ const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
1470-+
1471-+ free((void *) stub->key);
1472-+ memset(entry, 0, table->entrySize);
1473-+}
1474-+
1475-+void
1476-+PL_DHashFinalizeStub(PLDHashTable *table)
1477-+{
1478-+}
1479-+
1480-+static const PLDHashTableOps stub_ops = {
1481-+ PL_DHashAllocTable,
1482-+ PL_DHashFreeTable,
1483-+ PL_DHashVoidPtrKeyStub,
1484-+ PL_DHashMatchEntryStub,
1485-+ PL_DHashMoveEntryStub,
1486-+ PL_DHashClearEntryStub,
1487-+ PL_DHashFinalizeStub,
1488-+ NULL
1489-+};
1490-+
1491-+const PLDHashTableOps *
1492-+PL_DHashGetStubOps(void)
1493-+{
1494-+ return &stub_ops;
1495-+}
1496-+
1497-+PLDHashTable *
1498-+PL_NewDHashTable(const PLDHashTableOps *ops, void *data, PRUint32 entrySize,
1499-+ PRUint32 capacity)
1500-+{
1501-+ PLDHashTable *table;
1502-+
1503-+ table = (PLDHashTable *) malloc(sizeof *table);
1504-+ if (!table)
1505-+ return NULL;
1506-+ if (!PL_DHashTableInit(table, ops, data, entrySize, capacity)) {
1507-+ free(table);
1508-+ return NULL;
1509-+ }
1510-+ return table;
1511-+}
1512-+
1513-+void
1514-+PL_DHashTableDestroy(PLDHashTable *table)
1515-+{
1516-+ PL_DHashTableFinish(table);
1517-+ free(table);
1518-+}
1519-+
1520-+PRBool
1521-+PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data,
1522-+ PRUint32 entrySize, PRUint32 capacity)
1523-+{
1524-+ int log2;
1525-+ PRUint32 nbytes;
1526-+
1527-+#ifdef DEBUG
1528-+ if (entrySize > 10 * sizeof(void *)) {
1529-+ printf_stderr(
1530-+ "pldhash: for the table at address %p, the given entrySize"
1531-+ " of %lu %s favors chaining over double hashing.\n",
1532-+ (void *) table,
1533-+ (unsigned long) entrySize,
1534-+ (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
1535-+ }
1536-+#endif
1537-+
1538-+ table->ops = ops;
1539-+ table->data = data;
1540-+ if (capacity < PL_DHASH_MIN_SIZE)
1541-+ capacity = PL_DHASH_MIN_SIZE;
1542-+
1543-+ PR_CEILING_LOG2(log2, capacity);
1544-+
1545-+ capacity = PR_BIT(log2);
1546-+ if (capacity >= PL_DHASH_SIZE_LIMIT)
1547-+ return PR_FALSE;
1548-+ table->hashShift = PL_DHASH_BITS - log2;
1549-+ table->maxAlphaFrac = (PRUint8)(0x100 * PL_DHASH_DEFAULT_MAX_ALPHA);
1550-+ table->minAlphaFrac = (PRUint8)(0x100 * PL_DHASH_DEFAULT_MIN_ALPHA);
1551-+ table->entrySize = entrySize;
1552-+ table->entryCount = table->removedCount = 0;
1553-+ table->generation = 0;
1554-+ nbytes = capacity * entrySize;
1555-+
1556-+ table->entryStore = (char *) ops->allocTable(table,
1557-+ nbytes + ENTRY_STORE_EXTRA);
1558-+ if (!table->entryStore)
1559-+ return PR_FALSE;
1560-+ memset(table->entryStore, 0, nbytes);
1561-+ METER(memset(&table->stats, 0, sizeof table->stats));
1562-+
1563-+#ifdef DEBUG
1564-+ RECURSION_LEVEL(table) = 0;
1565-+#endif
1566-+
1567-+ return PR_TRUE;
1568-+}
1569-+
1570-+/*
1571-+ * Compute max and min load numbers (entry counts) from table params.
1572-+ */
1573-+#define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
1574-+#define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
1575-+
1576-+void
1577-+PL_DHashTableSetAlphaBounds(PLDHashTable *table,
1578-+ float maxAlpha,
1579-+ float minAlpha)
1580-+{
1581-+ PRUint32 size;
1582-+
1583-+ /*
1584-+ * Reject obviously insane bounds, rather than trying to guess what the
1585-+ * buggy caller intended.
1586-+ */
1587-+ NS_ASSERTION(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha,
1588-+ "0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha");
1589-+ if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
1590-+ return;
1591-+
1592-+ /*
1593-+ * Ensure that at least one entry will always be free. If maxAlpha at
1594-+ * minimum size leaves no entries free, reduce maxAlpha based on minimum
1595-+ * size and the precision limit of maxAlphaFrac's fixed point format.
1596-+ */
1597-+ NS_ASSERTION(PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1,
1598-+ "PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) >= 1");
1599-+ if (PL_DHASH_MIN_SIZE - (maxAlpha * PL_DHASH_MIN_SIZE) < 1) {
1600-+ maxAlpha = (float)
1601-+ (PL_DHASH_MIN_SIZE - PR_MAX(PL_DHASH_MIN_SIZE / 256, 1))
1602-+ / PL_DHASH_MIN_SIZE;
1603-+ }
1604-+
1605-+ /*
1606-+ * Ensure that minAlpha is strictly less than half maxAlpha. Take care
1607-+ * not to truncate an entry's worth of alpha when storing in minAlphaFrac
1608-+ * (8-bit fixed point format).
1609-+ */
1610-+ NS_ASSERTION(minAlpha < maxAlpha / 2,
1611-+ "minAlpha < maxAlpha / 2");
1612-+ if (minAlpha >= maxAlpha / 2) {
1613-+ size = PL_DHASH_TABLE_SIZE(table);
1614-+ minAlpha = (size * maxAlpha - PR_MAX(size / 256, 1)) / (2 * size);
1615-+ }
1616-+
1617-+ table->maxAlphaFrac = (PRUint8)(maxAlpha * 256);
1618-+ table->minAlphaFrac = (PRUint8)(minAlpha * 256);
1619-+}
1620-+
1621-+/*
1622-+ * Double hashing needs the second hash code to be relatively prime to table
1623-+ * size, so we simply make hash2 odd.
1624-+ */
1625-+#define HASH1(hash0, shift) ((hash0) >> (shift))
1626-+#define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
1627-+
1628-+/*
1629-+ * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
1630-+ * that a removed-entry sentinel need be stored only if the removed entry had
1631-+ * a colliding entry added after it. Therefore we can use 1 as the collision
1632-+ * flag in addition to the removed-entry sentinel value. Multiplicative hash
1633-+ * uses the high order bits of keyHash, so this least-significant reservation
1634-+ * should not hurt the hash function's effectiveness much.
1635-+ *
1636-+ * If you change any of these magic numbers, also update PL_DHASH_ENTRY_IS_LIVE
1637-+ * in pldhash.h. It used to be private to pldhash.c, but then became public to
1638-+ * assist iterator writers who inspect table->entryStore directly.
1639-+ */
1640-+#define COLLISION_FLAG ((PLDHashNumber) 1)
1641-+#define MARK_ENTRY_FREE(entry) ((entry)->keyHash = 0)
1642-+#define MARK_ENTRY_REMOVED(entry) ((entry)->keyHash = 1)
1643-+#define ENTRY_IS_REMOVED(entry) ((entry)->keyHash == 1)
1644-+#define ENTRY_IS_LIVE(entry) PL_DHASH_ENTRY_IS_LIVE(entry)
1645-+#define ENSURE_LIVE_KEYHASH(hash0) if (hash0 < 2) hash0 -= 2; else (void)0
1646-+
1647-+/* Match an entry's keyHash against an unstored one computed from a key. */
1648-+#define MATCH_ENTRY_KEYHASH(entry,hash0) \
1649-+ (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
1650-+
1651-+/* Compute the address of the indexed entry in table. */
1652-+#define ADDRESS_ENTRY(table, index) \
1653-+ ((PLDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
1654-+
1655-+void
1656-+PL_DHashTableFinish(PLDHashTable *table)
1657-+{
1658-+ char *entryAddr, *entryLimit;
1659-+ PRUint32 entrySize;
1660-+ PLDHashEntryHdr *entry;
1661-+
1662-+#ifdef DEBUG_XXXbrendan
1663-+ static FILE *dumpfp = NULL;
1664-+ if (!dumpfp) dumpfp = fopen("/tmp/pldhash.bigdump", "w");
1665-+ if (dumpfp) {
1666-+#ifdef MOZILLA_CLIENT
1667-+ NS_TraceStack(1, dumpfp);
1668-+#endif
1669-+ PL_DHashTableDumpMeter(table, NULL, dumpfp);
1670-+ fputc('\n', dumpfp);
1671-+ }
1672-+#endif
1673-+
1674-+ INCREMENT_RECURSION_LEVEL(table);
1675-+
1676-+ /* Call finalize before clearing entries, so it can enumerate them. */
1677-+ table->ops->finalize(table);
1678-+
1679-+ /* Clear any remaining live entries. */
1680-+ entryAddr = table->entryStore;
1681-+ entrySize = table->entrySize;
1682-+ entryLimit = entryAddr + PL_DHASH_TABLE_SIZE(table) * entrySize;
1683-+ while (entryAddr < entryLimit) {
1684-+ entry = (PLDHashEntryHdr *)entryAddr;
1685-+ if (ENTRY_IS_LIVE(entry)) {
1686-+ METER(table->stats.removeEnums++);
1687-+ table->ops->clearEntry(table, entry);
1688-+ }
1689-+ entryAddr += entrySize;
1690-+ }
1691-+
1692-+ DECREMENT_RECURSION_LEVEL(table);
1693-+ NS_ASSERTION(RECURSION_LEVEL_SAFE_TO_FINISH(table),
1694-+ "RECURSION_LEVEL_SAFE_TO_FINISH(table)");
1695-+
1696-+ /* Free entry storage last. */
1697-+ table->ops->freeTable(table, table->entryStore);
1698-+}
1699-+
1700-+static PLDHashEntryHdr * PL_DHASH_FASTCALL
1701-+SearchTable(PLDHashTable *table, const void *key, PLDHashNumber keyHash,
1702-+ PLDHashOperator op)
1703-+{
1704-+ PLDHashNumber hash1, hash2;
1705-+ int hashShift, sizeLog2;
1706-+ PLDHashEntryHdr *entry, *firstRemoved;
1707-+ PLDHashMatchEntry matchEntry;
1708-+ PRUint32 sizeMask;
1709-+
1710-+ METER(table->stats.searches++);
1711-+ NS_ASSERTION(!(keyHash & COLLISION_FLAG),
1712-+ "!(keyHash & COLLISION_FLAG)");
1713-+
1714-+ /* Compute the primary hash address. */
1715-+ hashShift = table->hashShift;
1716-+ hash1 = HASH1(keyHash, hashShift);
1717-+ entry = ADDRESS_ENTRY(table, hash1);
1718-+
1719-+ /* Miss: return space for a new entry. */
1720-+ if (PL_DHASH_ENTRY_IS_FREE(entry)) {
1721-+ METER(table->stats.misses++);
1722-+ return entry;
1723-+ }
1724-+
1725-+ /* Hit: return entry. */
1726-+ matchEntry = table->ops->matchEntry;
1727-+ if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
1728-+ METER(table->stats.hits++);
1729-+ return entry;
1730-+ }
1731-+
1732-+ /* Collision: double hash. */
1733-+ sizeLog2 = PL_DHASH_BITS - table->hashShift;
1734-+ hash2 = HASH2(keyHash, sizeLog2, hashShift);
1735-+ sizeMask = PR_BITMASK(sizeLog2);
1736-+
1737-+ /* Save the first removed entry pointer so PL_DHASH_ADD can recycle it. */
1738-+ firstRemoved = NULL;
1739-+
1740-+ for (;;) {
1741-+ if (NS_UNLIKELY(ENTRY_IS_REMOVED(entry))) {
1742-+ if (!firstRemoved)
1743-+ firstRemoved = entry;
1744-+ } else {
1745-+ if (op == PL_DHASH_ADD)
1746-+ entry->keyHash |= COLLISION_FLAG;
1747-+ }
1748-+
1749-+ METER(table->stats.steps++);
1750-+ hash1 -= hash2;
1751-+ hash1 &= sizeMask;
1752-+
1753-+ entry = ADDRESS_ENTRY(table, hash1);
1754-+ if (PL_DHASH_ENTRY_IS_FREE(entry)) {
1755-+ METER(table->stats.misses++);
1756-+ return (firstRemoved && op == PL_DHASH_ADD) ? firstRemoved : entry;
1757-+ }
1758-+
1759-+ if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
1760-+ matchEntry(table, entry, key)) {
1761-+ METER(table->stats.hits++);
1762-+ return entry;
1763-+ }
1764-+ }
1765-+
1766-+ /* NOTREACHED */
1767-+ return NULL;
1768-+}
1769-+
1770-+/*
1771-+ * This is a copy of SearchTable, used by ChangeTable, hardcoded to
1772-+ * 1. assume |op == PL_DHASH_ADD|,
1773-+ * 2. assume that |key| will never match an existing entry, and
1774-+ * 3. assume that no entries have been removed from the current table
1775-+ * structure.
1776-+ * Avoiding the need for |key| means we can avoid needing a way to map
1777-+ * entries to keys, which means callers can use complex key types more
1778-+ * easily.
1779-+ */
1780-+static PLDHashEntryHdr * PL_DHASH_FASTCALL
1781-+FindFreeEntry(PLDHashTable *table, PLDHashNumber keyHash)
1782-+{
1783-+ PLDHashNumber hash1, hash2;
1784-+ int hashShift, sizeLog2;
1785-+ PLDHashEntryHdr *entry;
1786-+ PRUint32 sizeMask;
1787-+
1788-+ METER(table->stats.searches++);
1789-+ NS_ASSERTION(!(keyHash & COLLISION_FLAG),
1790-+ "!(keyHash & COLLISION_FLAG)");
1791-+
1792-+ /* Compute the primary hash address. */
1793-+ hashShift = table->hashShift;
1794-+ hash1 = HASH1(keyHash, hashShift);
1795-+ entry = ADDRESS_ENTRY(table, hash1);
1796-+
1797-+ /* Miss: return space for a new entry. */
1798-+ if (PL_DHASH_ENTRY_IS_FREE(entry)) {
1799-+ METER(table->stats.misses++);
1800-+ return entry;
1801-+ }
1802-+
1803-+ /* Collision: double hash. */
1804-+ sizeLog2 = PL_DHASH_BITS - table->hashShift;
1805-+ hash2 = HASH2(keyHash, sizeLog2, hashShift);
1806-+ sizeMask = PR_BITMASK(sizeLog2);
1807-+
1808-+ for (;;) {
1809-+ NS_ASSERTION(!ENTRY_IS_REMOVED(entry),
1810-+ "!ENTRY_IS_REMOVED(entry)");
1811-+ entry->keyHash |= COLLISION_FLAG;
1812-+
1813-+ METER(table->stats.steps++);
1814-+ hash1 -= hash2;
1815-+ hash1 &= sizeMask;
1816-+
1817-+ entry = ADDRESS_ENTRY(table, hash1);
1818-+ if (PL_DHASH_ENTRY_IS_FREE(entry)) {
1819-+ METER(table->stats.misses++);
1820-+ return entry;
1821-+ }
1822-+ }
1823-+
1824-+ /* NOTREACHED */
1825-+ return NULL;
1826-+}
1827-+
1828-+static PRBool
1829-+ChangeTable(PLDHashTable *table, int deltaLog2)
1830-+{
1831-+ int oldLog2, newLog2;
1832-+ PRUint32 oldCapacity, newCapacity;
1833-+ char *newEntryStore, *oldEntryStore, *oldEntryAddr;
1834-+ PRUint32 entrySize, i, nbytes;
1835-+ PLDHashEntryHdr *oldEntry, *newEntry;
1836-+ PLDHashMoveEntry moveEntry;
1837-+#ifdef DEBUG
1838-+ PRUint32 recursionLevel;
1839-+#endif
1840-+
1841-+ /* Look, but don't touch, until we succeed in getting new entry store. */
1842-+ oldLog2 = PL_DHASH_BITS - table->hashShift;
1843-+ newLog2 = oldLog2 + deltaLog2;
1844-+ oldCapacity = PR_BIT(oldLog2);
1845-+ newCapacity = PR_BIT(newLog2);
1846-+ if (newCapacity >= PL_DHASH_SIZE_LIMIT)
1847-+ return PR_FALSE;
1848-+ entrySize = table->entrySize;
1849-+ nbytes = newCapacity * entrySize;
1850-+
1851-+ newEntryStore = (char *) table->ops->allocTable(table,
1852-+ nbytes + ENTRY_STORE_EXTRA);
1853-+ if (!newEntryStore)
1854-+ return PR_FALSE;
1855-+
1856-+ /* We can't fail from here on, so update table parameters. */
1857-+#ifdef DEBUG
1858-+ recursionLevel = RECURSION_LEVEL(table);
1859-+#endif
1860-+ table->hashShift = PL_DHASH_BITS - newLog2;
1861-+ table->removedCount = 0;
1862-+ table->generation++;
1863-+
1864-+ /* Assign the new entry store to table. */
1865-+ memset(newEntryStore, 0, nbytes);
1866-+ oldEntryAddr = oldEntryStore = table->entryStore;
1867-+ table->entryStore = newEntryStore;
1868-+ moveEntry = table->ops->moveEntry;
1869-+#ifdef DEBUG
1870-+ RECURSION_LEVEL(table) = recursionLevel;
1871-+#endif
1872-+
1873-+ /* Copy only live entries, leaving removed ones behind. */
1874-+ for (i = 0; i < oldCapacity; i++) {
1875-+ oldEntry = (PLDHashEntryHdr *)oldEntryAddr;
1876-+ if (ENTRY_IS_LIVE(oldEntry)) {
1877-+ oldEntry->keyHash &= ~COLLISION_FLAG;
1878-+ newEntry = FindFreeEntry(table, oldEntry->keyHash);
1879-+ NS_ASSERTION(PL_DHASH_ENTRY_IS_FREE(newEntry),
1880-+ "PL_DHASH_ENTRY_IS_FREE(newEntry)");
1881-+ moveEntry(table, oldEntry, newEntry);
1882-+ newEntry->keyHash = oldEntry->keyHash;
1883-+ }
1884-+ oldEntryAddr += entrySize;
1885-+ }
1886-+
1887-+ table->ops->freeTable(table, oldEntryStore);
1888-+ return PR_TRUE;
1889-+}
1890-+
1891-+PLDHashEntryHdr * PL_DHASH_FASTCALL
1892-+PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op)
1893-+{
1894-+ PLDHashNumber keyHash;
1895-+ PLDHashEntryHdr *entry;
1896-+ PRUint32 size;
1897-+ int deltaLog2;
1898-+
1899-+ NS_ASSERTION(op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0,
1900-+ "op == PL_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0");
1901-+ INCREMENT_RECURSION_LEVEL(table);
1902-+
1903-+ keyHash = table->ops->hashKey(table, key);
1904-+ keyHash *= PL_DHASH_GOLDEN_RATIO;
1905-+
1906-+ /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
1907-+ ENSURE_LIVE_KEYHASH(keyHash);
1908-+ keyHash &= ~COLLISION_FLAG;
1909-+
1910-+ switch (op) {
1911-+ case PL_DHASH_LOOKUP:
1912-+ METER(table->stats.lookups++);
1913-+ entry = SearchTable(table, key, keyHash, op);
1914-+ break;
1915-+
1916-+ case PL_DHASH_ADD:
1917-+ /*
1918-+ * If alpha is >= .75, grow or compress the table. If key is already
1919-+ * in the table, we may grow once more than necessary, but only if we
1920-+ * are on the edge of being overloaded.
1921-+ */
1922-+ size = PL_DHASH_TABLE_SIZE(table);
1923-+ if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
1924-+ /* Compress if a quarter or more of all entries are removed. */
1925-+ if (table->removedCount >= size >> 2) {
1926-+ METER(table->stats.compresses++);
1927-+ deltaLog2 = 0;
1928-+ } else {
1929-+ METER(table->stats.grows++);
1930-+ deltaLog2 = 1;
1931-+ }
1932-+
1933-+ /*
1934-+ * Grow or compress table, returning null if ChangeTable fails and
1935-+ * falling through might claim the last free entry.
1936-+ */
1937-+ if (!ChangeTable(table, deltaLog2) &&
1938-+ table->entryCount + table->removedCount == size - 1) {
1939-+ METER(table->stats.addFailures++);
1940-+ entry = NULL;
1941-+ break;
1942-+ }
1943-+ }
1944-+
1945-+ /*
1946-+ * Look for entry after possibly growing, so we don't have to add it,
1947-+ * then skip it while growing the table and re-add it after.
1948-+ */
1949-+ entry = SearchTable(table, key, keyHash, op);
1950-+ if (!ENTRY_IS_LIVE(entry)) {
1951-+ /* Initialize the entry, indicating that it's no longer free. */
1952-+ METER(table->stats.addMisses++);
1953-+ if (ENTRY_IS_REMOVED(entry)) {
1954-+ METER(table->stats.addOverRemoved++);
1955-+ table->removedCount--;
1956-+ keyHash |= COLLISION_FLAG;
1957-+ }
1958-+ if (table->ops->initEntry &&
1959-+ !table->ops->initEntry(table, entry, key)) {
1960-+ /* We haven't claimed entry yet; fail with null return. */
1961-+ memset(entry + 1, 0, table->entrySize - sizeof *entry);
1962-+ entry = NULL;
1963-+ break;
1964-+ }
1965-+ entry->keyHash = keyHash;
1966-+ table->entryCount++;
1967-+ }
1968-+ METER(else table->stats.addHits++);
1969-+ break;
1970-+
1971-+ case PL_DHASH_REMOVE:
1972-+ entry = SearchTable(table, key, keyHash, op);
1973-+ if (ENTRY_IS_LIVE(entry)) {
1974-+ /* Clear this entry and mark it as "removed". */
1975-+ METER(table->stats.removeHits++);
1976-+ PL_DHashTableRawRemove(table, entry);
1977-+
1978-+ /* Shrink if alpha is <= .25 and table isn't too small already. */
1979-+ size = PL_DHASH_TABLE_SIZE(table);
1980-+ if (size > PL_DHASH_MIN_SIZE &&
1981-+ table->entryCount <= MIN_LOAD(table, size)) {
1982-+ METER(table->stats.shrinks++);
1983-+ (void) ChangeTable(table, -1);
1984-+ }
1985-+ }
1986-+ METER(else table->stats.removeMisses++);
1987-+ entry = NULL;
1988-+ break;
1989-+
1990-+ default:
1991-+ NS_NOTREACHED("0");
1992-+ entry = NULL;
1993-+ }
1994-+
1995-+ DECREMENT_RECURSION_LEVEL(table);
1996-+
1997-+ return entry;
1998-+}
1999-+
2000-+void
2001-+PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry)
2002-+{
2003-+ PLDHashNumber keyHash; /* load first in case clearEntry goofs it */
2004-+
2005-+ NS_ASSERTION(RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL,
2006-+ "RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL");
2007-+
2008-+ NS_ASSERTION(PL_DHASH_ENTRY_IS_LIVE(entry),
2009-+ "PL_DHASH_ENTRY_IS_LIVE(entry)");
2010-+ keyHash = entry->keyHash;
2011-+ table->ops->clearEntry(table, entry);
2012-+ if (keyHash & COLLISION_FLAG) {
2013-+ MARK_ENTRY_REMOVED(entry);
2014-+ table->removedCount++;
2015-+ } else {
2016-+ METER(table->stats.removeFrees++);
2017-+ MARK_ENTRY_FREE(entry);
2018-+ }
2019-+ table->entryCount--;
2020-+}
2021-+
2022-+PRUint32
2023-+PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg)
2024-+{
2025-+ char *entryAddr, *entryLimit;
2026-+ PRUint32 i, capacity, entrySize, ceiling;
2027-+ PRBool didRemove;
2028-+ PLDHashEntryHdr *entry;
2029-+ PLDHashOperator op;
2030-+
2031-+ INCREMENT_RECURSION_LEVEL(table);
2032-+
2033-+ entryAddr = table->entryStore;
2034-+ entrySize = table->entrySize;
2035-+ capacity = PL_DHASH_TABLE_SIZE(table);
2036-+ entryLimit = entryAddr + capacity * entrySize;
2037-+ i = 0;
2038-+ didRemove = PR_FALSE;
2039-+ while (entryAddr < entryLimit) {
2040-+ entry = (PLDHashEntryHdr *)entryAddr;
2041-+ if (ENTRY_IS_LIVE(entry)) {
2042-+ op = etor(table, entry, i++, arg);
2043-+ if (op & PL_DHASH_REMOVE) {
2044-+ METER(table->stats.removeEnums++);
2045-+ PL_DHashTableRawRemove(table, entry);
2046-+ didRemove = PR_TRUE;
2047-+ }
2048-+ if (op & PL_DHASH_STOP)
2049-+ break;
2050-+ }
2051-+ entryAddr += entrySize;
2052-+ }
2053-+
2054-+ NS_ASSERTION(!didRemove || RECURSION_LEVEL(table) == 1,
2055-+ "!didRemove || RECURSION_LEVEL(table) == 1");
2056-+
2057-+ /*
2058-+ * Shrink or compress if a quarter or more of all entries are removed, or
2059-+ * if the table is underloaded according to the configured minimum alpha,
2060-+ * and is not minimal-size already. Do this only if we removed above, so
2061-+ * non-removing enumerations can count on stable table->entryStore until
2062-+ * the next non-lookup-Operate or removing-Enumerate.
2063-+ */
2064-+ if (didRemove &&
2065-+ (table->removedCount >= capacity >> 2 ||
2066-+ (capacity > PL_DHASH_MIN_SIZE &&
2067-+ table->entryCount <= MIN_LOAD(table, capacity)))) {
2068-+ METER(table->stats.enumShrinks++);
2069-+ capacity = table->entryCount;
2070-+ capacity += capacity >> 1;
2071-+ if (capacity < PL_DHASH_MIN_SIZE)
2072-+ capacity = PL_DHASH_MIN_SIZE;
2073-+
2074-+ PR_CEILING_LOG2(ceiling, capacity);
2075-+ ceiling -= PL_DHASH_BITS - table->hashShift;
2076-+
2077-+ (void) ChangeTable(table, ceiling);
2078-+ }
2079-+
2080-+ DECREMENT_RECURSION_LEVEL(table);
2081-+
2082-+ return i;
2083-+}
2084-+
2085-+#ifdef DEBUG
2086-+void
2087-+PL_DHashMarkTableImmutable(PLDHashTable *table)
2088-+{
2089-+ RECURSION_LEVEL(table) = IMMUTABLE_RECURSION_LEVEL;
2090-+}
2091-+#endif
2092-+
2093-+#ifdef PL_DHASHMETER
2094-+#include <math.h>
2095-+
2096-+void
2097-+PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp)
2098-+{
2099-+ char *entryAddr;
2100-+ PRUint32 entrySize, entryCount;
2101-+ int hashShift, sizeLog2;
2102-+ PRUint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
2103-+ PLDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
2104-+ double sqsum, mean, variance, sigma;
2105-+ PLDHashEntryHdr *entry, *probe;
2106-+
2107-+ entryAddr = table->entryStore;
2108-+ entrySize = table->entrySize;
2109-+ hashShift = table->hashShift;
2110-+ sizeLog2 = PL_DHASH_BITS - hashShift;
2111-+ tableSize = PL_DHASH_TABLE_SIZE(table);
2112-+ sizeMask = PR_BITMASK(sizeLog2);
2113-+ chainCount = maxChainLen = 0;
2114-+ hash2 = 0;
2115-+ sqsum = 0;
2116-+
2117-+ for (i = 0; i < tableSize; i++) {
2118-+ entry = (PLDHashEntryHdr *)entryAddr;
2119-+ entryAddr += entrySize;
2120-+ if (!ENTRY_IS_LIVE(entry))
2121-+ continue;
2122-+ hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
2123-+ saveHash1 = hash1;
2124-+ probe = ADDRESS_ENTRY(table, hash1);
2125-+ chainLen = 1;
2126-+ if (probe == entry) {
2127-+ /* Start of a (possibly unit-length) chain. */
2128-+ chainCount++;
2129-+ } else {
2130-+ hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
2131-+ hashShift);
2132-+ do {
2133-+ chainLen++;
2134-+ hash1 -= hash2;
2135-+ hash1 &= sizeMask;
2136-+ probe = ADDRESS_ENTRY(table, hash1);
2137-+ } while (probe != entry);
2138-+ }
2139-+ sqsum += chainLen * chainLen;
2140-+ if (chainLen > maxChainLen) {
2141-+ maxChainLen = chainLen;
2142-+ maxChainHash1 = saveHash1;
2143-+ maxChainHash2 = hash2;
2144-+ }
2145-+ }
2146-+
2147-+ entryCount = table->entryCount;
2148-+ if (entryCount && chainCount) {
2149-+ mean = (double)entryCount / chainCount;
2150-+ variance = chainCount * sqsum - entryCount * entryCount;
2151-+ if (variance < 0 || chainCount == 1)
2152-+ variance = 0;
2153-+ else
2154-+ variance /= chainCount * (chainCount - 1);
2155-+ sigma = sqrt(variance);
2156-+ } else {
2157-+ mean = sigma = 0;
2158-+ }
2159-+
2160-+ fprintf(fp, "Double hashing statistics:\n");
2161-+ fprintf(fp, " table size (in entries): %u\n", tableSize);
2162-+ fprintf(fp, " number of entries: %u\n", table->entryCount);
2163-+ fprintf(fp, " number of removed entries: %u\n", table->removedCount);
2164-+ fprintf(fp, " number of searches: %u\n", table->stats.searches);
2165-+ fprintf(fp, " number of hits: %u\n", table->stats.hits);
2166-+ fprintf(fp, " number of misses: %u\n", table->stats.misses);
2167-+ fprintf(fp, " mean steps per search: %g\n", table->stats.searches ?
2168-+ (double)table->stats.steps
2169-+ / table->stats.searches :
2170-+ 0.);
2171-+ fprintf(fp, " mean hash chain length: %g\n", mean);
2172-+ fprintf(fp, " standard deviation: %g\n", sigma);
2173-+ fprintf(fp, " maximum hash chain length: %u\n", maxChainLen);
2174-+ fprintf(fp, " number of lookups: %u\n", table->stats.lookups);
2175-+ fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
2176-+ fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
2177-+ fprintf(fp, " adds that found an entry: %u\n", table->stats.addHits);
2178-+ fprintf(fp, " add failures: %u\n", table->stats.addFailures);
2179-+ fprintf(fp, " useful removes: %u\n", table->stats.removeHits);
2180-+ fprintf(fp, " useless removes: %u\n", table->stats.removeMisses);
2181-+ fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
2182-+ fprintf(fp, " removes while enumerating: %u\n", table->stats.removeEnums);
2183-+ fprintf(fp, " number of grows: %u\n", table->stats.grows);
2184-+ fprintf(fp, " number of shrinks: %u\n", table->stats.shrinks);
2185-+ fprintf(fp, " number of compresses: %u\n", table->stats.compresses);
2186-+ fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
2187-+
2188-+ if (dump && maxChainLen && hash2) {
2189-+ fputs("Maximum hash chain:\n", fp);
2190-+ hash1 = maxChainHash1;
2191-+ hash2 = maxChainHash2;
2192-+ entry = ADDRESS_ENTRY(table, hash1);
2193-+ i = 0;
2194-+ do {
2195-+ if (dump(table, entry, i++, fp) != PL_DHASH_NEXT)
2196-+ break;
2197-+ hash1 -= hash2;
2198-+ hash1 &= sizeMask;
2199-+ entry = ADDRESS_ENTRY(table, hash1);
2200-+ } while (PL_DHASH_ENTRY_IS_BUSY(entry));
2201-+ }
2202-+}
2203-+#endif /* PL_DHASHMETER */
2204
2205=== added file 'debian/patches/fix-build-failure-without-yarr-jit.patch'
2206--- debian/patches/fix-build-failure-without-yarr-jit.patch 1970-01-01 00:00:00 +0000
2207+++ debian/patches/fix-build-failure-without-yarr-jit.patch 2011-12-16 00:06:23 +0000
2208@@ -0,0 +1,27 @@
2209+Subject: Fix build failure on platforms without YARR JIT
2210+Bug-Mozilla: https://bugzilla.mozilla.org/show_bug.cgi?id=703534
2211+Origin: upstream, https://hg.mozilla.org/mozilla-central/raw-rev/15cf58eb7923
2212+Author: Mike Hommey <mh+mozilla@glandium.org>
2213+# Rebased for Firefox 9 and Thunderbird directory structure
2214+# HG changeset patch
2215+# User Mike Hommey <mh+mozilla@glandium.org>
2216+# Date 1321613368 -3600
2217+# Node ID 15cf58eb7923d34de7e61df80fa5f8a18a995abf
2218+# Parent aeb035da53283c56370992f254e4f79d7dd180f8
2219+
2220+---
2221+ js/src/jscompartment.cpp | 1 -
2222+ 1 file changed, 1 deletion(-)
2223+
2224+Index: mozilla/mozilla/js/src/jscompartment.cpp
2225+===================================================================
2226+--- mozilla.orig/mozilla/js/src/jscompartment.cpp
2227++++ mozilla/mozilla/js/src/jscompartment.cpp
2228+@@ -50,7 +50,6 @@
2229+ #include "jswatchpoint.h"
2230+ #include "jswrapper.h"
2231+ #include "assembler/wtf/Platform.h"
2232+-#include "assembler/jit/ExecutableAllocator.h"
2233+ #include "yarr/BumpPointerAllocator.h"
2234+ #include "methodjit/MethodJIT.h"
2235+ #include "methodjit/PolyIC.h"
2236
2237=== removed file 'debian/patches/only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch'
2238--- debian/patches/only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch 2011-10-11 07:49:14 +0000
2239+++ debian/patches/only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch 1970-01-01 00:00:00 +0000
2240@@ -1,55 +0,0 @@
2241-# HG changeset patch
2242-# User Mike Hommey <mh+mozilla@glandium.org>
2243-# Date 1314108801 -7200
2244-# Node ID 5847fed3426746e8692fdf4221acbd0917237d42
2245-# Parent 93e8590445364cc0a5710e276912aa55b8a938e4
2246-Bug 670719 - Only add -DENABLE_JIT=1 to CXXFLAGS if any of trace/method/yarr jit is enabled. r=dmandelin
2247-
2248-diff --git a/mozilla/js/src/Makefile.in b/mozilla/js/src/Makefile.in
2249---- a/mozilla/js/src/Makefile.in
2250-+++ b/mozilla/js/src/Makefile.in
2251-@@ -433,16 +433,19 @@ CPPSRCS += \
2252- YarrPattern.cpp \
2253- YarrSyntaxChecker.cpp \
2254- $(NULL)
2255- else
2256-
2257- ###############################################
2258- # BEGIN include sources for the Nitro assembler
2259- #
2260-+
2261-+ENABLE_YARR_JIT = 1
2262-+
2263- VPATH += $(srcdir)/assembler \
2264- $(srcdir)/assembler/wtf \
2265- $(srcdir)/assembler/jit \
2266- $(srcdir)/assembler/assembler \
2267- $(srcdir)/methodjit \
2268- $(srcdir)/yarr \
2269- $(NONE)
2270-
2271-@@ -1076,17 +1079,21 @@ endif
2272-
2273- ###############################################
2274- # BEGIN kludges for the Nitro assembler
2275- #
2276-
2277- # Needed to "configure" it correctly. Unfortunately these
2278- # flags wind up being applied to all code in js/src, not just
2279- # the code in js/src/assembler.
2280--CXXFLAGS += -DUSE_SYSTEM_MALLOC=1 -DENABLE_ASSEMBLER=1 -DENABLE_JIT=1
2281-+CXXFLAGS += -DUSE_SYSTEM_MALLOC=1 -DENABLE_ASSEMBLER=1
2282-+
2283-+ifneq (,$(ENABLE_YARR_JIT)$(ENABLE_TRACEJIT)$(ENABLE_METHODJIT))
2284-+CXXFLAGS += -DENABLE_JIT=1
2285-+endif
2286-
2287- INCLUDES += -I$(srcdir)/assembler -I$(srcdir)/yarr
2288-
2289- ifdef ENABLE_METHODJIT
2290- # Build a standalone test program that exercises the assembler
2291- # sources a bit.
2292- TESTMAIN_OBJS = \
2293- Assertions.$(OBJ_SUFFIX) \
2294-
2295-
2296
2297=== modified file 'debian/patches/printf-fix.patch'
2298--- debian/patches/printf-fix.patch 2011-10-11 07:49:14 +0000
2299+++ debian/patches/printf-fix.patch 2011-12-16 00:06:23 +0000
2300@@ -1,6 +1,6 @@
2301 --- a/mozilla/gfx/2d/Logging.h
2302 +++ b/mozilla/gfx/2d/Logging.h
2303-@@ -86,7 +86,7 @@ static void OutputMessage(const std::str
2304+@@ -87,7 +87,7 @@
2305 }
2306 #else
2307 if (aLevel >= sGfxLogLevel) {
2308
2309=== modified file 'debian/patches/series'
2310--- debian/patches/series 2011-10-11 07:49:14 +0000
2311+++ debian/patches/series 2011-12-16 00:06:23 +0000
2312@@ -1,4 +1,2 @@
2313-build-fix-for-no-ENABLE_YARR_JIT.patch
2314-compile-pldhash-as-C++.patch
2315-only-add-ENABLE_JIT-to-CXXFLAGS-if-jit-is-enabled.patch
2316 printf-fix.patch
2317+fix-build-failure-without-yarr-jit.patch
2318
2319=== modified file 'debian/rules'
2320--- debian/rules 2011-09-30 12:45:15 +0000
2321+++ debian/rules 2011-12-16 00:06:23 +0000
2322@@ -7,7 +7,6 @@
2323
2324 MOZ_APP_BASENAME := seamonkey
2325 MOZ_MOZDIR := mozilla
2326-DEBIAN_TAG := SEAMONKEY_2_4_1_RELEASE
2327
2328 # Various build options
2329 # tree = use in-tree libs, system = use system libs
2330@@ -179,8 +178,8 @@
2331 export LDFLAGS
2332 export DEB_BUILD_HARDENING=1
2333
2334-# Lucid has old yasm and does not compile turbo-jpeg.
2335-ifeq (1,$(shell test "$(DISTRIB_VERSION_MAJOR)$(DISTRIB_VERSION_MINOR)" -eq "1004" && echo "1"))
2336+# Lucid and Karmic have old yasm and does not compile turbo-jpeg.
2337+ifeq (1,$(shell test "$(DISTRIB_VERSION_MAJOR)$(DISTRIB_VERSION_MINOR)" -lt "1104" && echo "1"))
2338 MOZ_DISABLE_LIBJPEG := 1
2339 endif
2340 ifeq (1,$(shell test "$(DISTRIB_VERSION_MAJOR)$(DISTRIB_VERSION_MINOR)" -ge "1010" && echo "1"))
2341
2342=== modified file 'debian/seamonkey.desktop.in'
2343--- debian/seamonkey.desktop.in 2011-09-10 07:29:03 +0000
2344+++ debian/seamonkey.desktop.in 2011-12-16 00:06:23 +0000
2345@@ -108,7 +108,7 @@
2346 Type=Application
2347 Icon=@MOZ_APP_NAME@
2348 Categories=Application;Network;Email;
2349-MimeType=text/html;text/xml;application/xhtml+xml;application/xml;application/vnd.mozilla.xul+xml;application/rss+xml;application/rdf+xml;x-scheme-handler/mailto;
2350+MimeType=text/html;text/xml;application/xhtml+xml;application/xml;application/vnd.mozilla.xul+xml;application/rss+xml;application/rdf+xml;x-scheme-handler/mailto;x-scheme-handler/http;x-scheme-handler/https;x-scheme-handler/ftp;
2351 StartupWMClass=@MOZ_DISPLAY_NAME@
2352 StartupNotify=true
2353 GenericName[ast]=Client de correu

Subscribers

People subscribed via source and target branches

to all changes: