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

Subscribers

People subscribed via source and target branches

to all changes: