Bug Summary

File:var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h
Warning:line 1314, column 7
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name DominatorTree.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -ffp-contract=off -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/devtools/shared/heapsnapshot -fcoverage-compilation-dir=/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/devtools/shared/heapsnapshot -resource-dir /usr/lib/llvm-19/lib/clang/19 -include /var/lib/jenkins/workspace/firefox-scan-build/config/gcc_hidden.h -include /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/mozilla-config.h -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/stl_wrappers -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/system_wrappers -U _FORTIFY_SOURCE -D _FORTIFY_SOURCE=2 -D DEBUG=1 -D GOOGLE_PROTOBUF_NO_RTTI -D MOZ_HAS_MOZGLUE -D MOZILLA_INTERNAL_API -D IMPL_LIBXUL -D MOZ_SUPPORT_LEAKCHECKING -D STATIC_EXPORTABLE_JS_API -I /var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/devtools/shared/heapsnapshot -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/ipc/ipdl/_ipdlheaders -I /var/lib/jenkins/workspace/firefox-scan-build/ipc/chromium/src -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/nspr -I /var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/nss -D MOZILLA_CLIENT -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/x86_64-linux-gnu/c++/14 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/backward -internal-isystem /usr/lib/llvm-19/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-error=tautological-type-limit-compare -Wno-invalid-offsetof -Wno-range-loop-analysis -Wno-deprecated-anon-enum-enum-conversion -Wno-deprecated-enum-enum-conversion -Wno-deprecated-this-capture -Wno-inline-new-delete -Wno-error=deprecated-declarations -Wno-error=array-bounds -Wno-error=free-nonheap-object -Wno-error=atomic-alignment -Wno-error=deprecated-builtins -Wno-psabi -Wno-error=builtin-macro-redefined -Wno-vla-cxx-extension -Wno-unknown-warning-option -fdeprecated-macro -ferror-limit 19 -fstrict-flex-arrays=1 -stack-protector 2 -fstack-clash-protection -ftrivial-auto-var-init=pattern -fno-rtti -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fno-sized-deallocation -fno-aligned-allocation -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2024-09-22-115206-3586786-1 -x c++ /var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp

/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp

1/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; -*- */
2/* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6#include "mozilla/devtools/DominatorTree.h"
7#include "mozilla/dom/DominatorTreeBinding.h"
8#include "mozilla/ErrorResult.h"
9
10namespace mozilla {
11namespace devtools {
12
13dom::Nullable<uint64_t> DominatorTree::GetRetainedSize(uint64_t aNodeId,
14 ErrorResult& aRv) {
15 JS::ubi::Node::Id id(aNodeId);
16 auto node = mHeapSnapshot->getNodeById(id);
17 if (node.isNothing()) return dom::Nullable<uint64_t>();
18
19 auto mallocSizeOf = GetCurrentThreadDebuggerMallocSizeOf();
20 JS::ubi::Node::Size size = 0;
21 if (!mDominatorTree.getRetainedSize(*node, mallocSizeOf, size)) {
22 aRv.Throw(NS_ERROR_OUT_OF_MEMORY);
23 return dom::Nullable<uint64_t>();
24 }
25
26 MOZ_ASSERT(size != 0,do { static_assert( mozilla::detail::AssertionConditionType<
decltype(size != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(size != 0))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("size != 0" " (" "The node should not have been unknown since we got it from the "
"heap snapshot." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 28); AnnotateMozCrashReason("MOZ_ASSERT" "(" "size != 0" ") ("
"The node should not have been unknown since we got it from the "
"heap snapshot." ")"); do { *((volatile int*)__null) = 28; __attribute__
((nomerge)) ::abort(); } while (false); } } while (false)
27 "The node should not have been unknown since we got it from the "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(size != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(size != 0))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("size != 0" " (" "The node should not have been unknown since we got it from the "
"heap snapshot." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 28); AnnotateMozCrashReason("MOZ_ASSERT" "(" "size != 0" ") ("
"The node should not have been unknown since we got it from the "
"heap snapshot." ")"); do { *((volatile int*)__null) = 28; __attribute__
((nomerge)) ::abort(); } while (false); } } while (false)
28 "heap snapshot.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(size != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(size != 0))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("size != 0" " (" "The node should not have been unknown since we got it from the "
"heap snapshot." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 28); AnnotateMozCrashReason("MOZ_ASSERT" "(" "size != 0" ") ("
"The node should not have been unknown since we got it from the "
"heap snapshot." ")"); do { *((volatile int*)__null) = 28; __attribute__
((nomerge)) ::abort(); } while (false); } } while (false)
;
29 return dom::Nullable<uint64_t>(size);
30}
31
32struct NodeAndRetainedSize {
33 JS::ubi::Node mNode;
34 JS::ubi::Node::Size mSize;
35
36 NodeAndRetainedSize(const JS::ubi::Node& aNode, JS::ubi::Node::Size aSize)
37 : mNode(aNode), mSize(aSize) {}
38
39 struct Comparator {
40 static bool Equals(const NodeAndRetainedSize& aLhs,
41 const NodeAndRetainedSize& aRhs) {
42 return aLhs.mSize == aRhs.mSize;
43 }
44
45 static bool LessThan(const NodeAndRetainedSize& aLhs,
46 const NodeAndRetainedSize& aRhs) {
47 // Use > because we want to sort from greatest to least retained size.
48 return aLhs.mSize > aRhs.mSize;
49 }
50 };
51};
52
53void DominatorTree::GetImmediatelyDominated(
54 uint64_t aNodeId, dom::Nullable<nsTArray<uint64_t>>& aOutResult,
55 ErrorResult& aRv) {
56 MOZ_ASSERT(aOutResult.IsNull())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aOutResult.IsNull())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aOutResult.IsNull()))), 0)))
{ do { } while (false); MOZ_ReportAssertionFailure("aOutResult.IsNull()"
, "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 56); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aOutResult.IsNull()"
")"); do { *((volatile int*)__null) = 56; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
57
58 JS::ubi::Node::Id id(aNodeId);
59 Maybe<JS::ubi::Node> node = mHeapSnapshot->getNodeById(id);
60 if (node.isNothing()) return;
61
62 // Get all immediately dominated nodes and their retained sizes.
63 MallocSizeOf mallocSizeOf = GetCurrentThreadDebuggerMallocSizeOf();
64 Maybe<JS::ubi::DominatorTree::DominatedSetRange> range =
65 mDominatorTree.getDominatedSet(*node);
66 MOZ_ASSERT(do { static_assert( mozilla::detail::AssertionConditionType<
decltype(range.isSome())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(range.isSome()))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("range.isSome()"
" (" "The node should be known, since we got it from the heap snapshot."
")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 68); AnnotateMozCrashReason("MOZ_ASSERT" "(" "range.isSome()"
") (" "The node should be known, since we got it from the heap snapshot."
")"); do { *((volatile int*)__null) = 68; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
67 range.isSome(),do { static_assert( mozilla::detail::AssertionConditionType<
decltype(range.isSome())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(range.isSome()))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("range.isSome()"
" (" "The node should be known, since we got it from the heap snapshot."
")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 68); AnnotateMozCrashReason("MOZ_ASSERT" "(" "range.isSome()"
") (" "The node should be known, since we got it from the heap snapshot."
")"); do { *((volatile int*)__null) = 68; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
68 "The node should be known, since we got it from the heap snapshot.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(range.isSome())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(range.isSome()))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("range.isSome()"
" (" "The node should be known, since we got it from the heap snapshot."
")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 68); AnnotateMozCrashReason("MOZ_ASSERT" "(" "range.isSome()"
") (" "The node should be known, since we got it from the heap snapshot."
")"); do { *((volatile int*)__null) = 68; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
69 size_t length = range->length();
70 nsTArray<NodeAndRetainedSize> dominatedNodes(length);
71 for (const JS::ubi::Node& dominatedNode : *range) {
72 JS::ubi::Node::Size retainedSize = 0;
73 if (NS_WARN_IF(!mDominatorTree.getRetainedSize(dominatedNode, mallocSizeOf,NS_warn_if_impl(!mDominatorTree.getRetainedSize(dominatedNode
, mallocSizeOf, retainedSize), "!mDominatorTree.getRetainedSize(dominatedNode, mallocSizeOf, retainedSize)"
, "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 74)
74 retainedSize))NS_warn_if_impl(!mDominatorTree.getRetainedSize(dominatedNode
, mallocSizeOf, retainedSize), "!mDominatorTree.getRetainedSize(dominatedNode, mallocSizeOf, retainedSize)"
, "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 74)
) {
75 aRv.Throw(NS_ERROR_OUT_OF_MEMORY);
76 return;
77 }
78 MOZ_ASSERT(retainedSize != 0,do { static_assert( mozilla::detail::AssertionConditionType<
decltype(retainedSize != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(retainedSize != 0))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("retainedSize != 0"
" (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 80); AnnotateMozCrashReason("MOZ_ASSERT" "(" "retainedSize != 0"
") (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")"); do { *((volatile int*)__null) = 80
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
79 "retainedSize should not be zero since we know the node is in "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(retainedSize != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(retainedSize != 0))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("retainedSize != 0"
" (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 80); AnnotateMozCrashReason("MOZ_ASSERT" "(" "retainedSize != 0"
") (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")"); do { *((volatile int*)__null) = 80
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
80 "the dominator tree.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(retainedSize != 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(retainedSize != 0))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("retainedSize != 0"
" (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 80); AnnotateMozCrashReason("MOZ_ASSERT" "(" "retainedSize != 0"
") (" "retainedSize should not be zero since we know the node is in "
"the dominator tree." ")"); do { *((volatile int*)__null) = 80
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
;
81
82 dominatedNodes.AppendElement(
83 NodeAndRetainedSize(dominatedNode, retainedSize));
84 }
85
86 // Sort them by retained size.
87 NodeAndRetainedSize::Comparator comparator;
88 dominatedNodes.Sort(comparator);
89
90 // Fill the result with the nodes' ids.
91 JS::ubi::Node root = mDominatorTree.root();
92 aOutResult.SetValue(nsTArray<uint64_t>(length));
93 for (const NodeAndRetainedSize& entry : dominatedNodes) {
94 // The root dominates itself, but we don't want to expose that to JS.
95 if (entry.mNode == root) continue;
96
97 aOutResult.Value().AppendElement(entry.mNode.identifier());
98 }
99}
100
101dom::Nullable<uint64_t> DominatorTree::GetImmediateDominator(
102 uint64_t aNodeId) const {
103 JS::ubi::Node::Id id(aNodeId);
104 Maybe<JS::ubi::Node> node = mHeapSnapshot->getNodeById(id);
105 if (node.isNothing()) return dom::Nullable<uint64_t>();
1
Taking false branch
106
107 JS::ubi::Node dominator = mDominatorTree.getImmediateDominator(*node);
2
Calling 'DominatorTree::getImmediateDominator'
108 if (!dominator || dominator == *node) return dom::Nullable<uint64_t>();
109
110 return dom::Nullable<uint64_t>(dominator.identifier());
111}
112
113/*** Cycle Collection Boilerplate
114 * *****************************************************************/
115
116NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(DominatorTree, mParent, mHeapSnapshot)static_assert(std::is_base_of<nsWrapperCache, DominatorTree
>::value, "Class should inherit nsWrapperCache"); DominatorTree
::cycleCollection DominatorTree::_cycleCollectorGlobal( nsCycleCollectionParticipant
::FlagMaybeSingleZoneJSHolder); void DominatorTree::cycleCollection
::Trace( void* p, const TraceCallbacks& aCallbacks, void*
aClosure) { DominatorTree* tmp = DowncastCCParticipant<DominatorTree
>(p); TraceWrapper(p, aCallbacks, aClosure); (void)tmp; } void
DominatorTree::cycleCollection::TraceWrapper( void* p, const
TraceCallbacks& aCallbacks, void* aClosure) { DominatorTree
* tmp = DowncastCCParticipant<DominatorTree>(p); tmp->
TraceWrapper(aCallbacks, aClosure); } void DominatorTree::cycleCollection
::Unlink(void* p) { DominatorTree* tmp = DowncastCCParticipant
<DominatorTree>(p); ImplCycleCollectionUnlink(tmp->mParent
); ImplCycleCollectionUnlink(tmp->mHeapSnapshot); tmp->
ReleaseWrapper(p); (void)tmp; } nsresult DominatorTree::cycleCollection
::TraverseNative( void* p, nsCycleCollectionTraversalCallback
& cb) { DominatorTree* tmp = DowncastCCParticipant<DominatorTree
>(p); cb.DescribeRefCountedNode(tmp->mRefCnt.get(), "DominatorTree"
); ImplCycleCollectionTraverse(cb, tmp->mParent, "mParent"
, 0); ImplCycleCollectionTraverse(cb, tmp->mHeapSnapshot, "mHeapSnapshot"
, 0); (void)tmp; return NS_OK; }
117
118NS_IMPL_CYCLE_COLLECTING_ADDREF(DominatorTree)MozExternalRefCountType DominatorTree::AddRef(void) { static_assert
(!std::is_destructible_v<DominatorTree>, "Reference-counted class "
"DominatorTree" " should not have a public destructor. " "Make this class's destructor non-public"
); do { static_assert( mozilla::detail::AssertionConditionType
<decltype(int32_t(mRefCnt) >= 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(int32_t(mRefCnt) >= 0))),
0))) { do { } while (false); MOZ_ReportAssertionFailure("int32_t(mRefCnt) >= 0"
" (" "illegal refcnt" ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 118); AnnotateMozCrashReason("MOZ_ASSERT" "(" "int32_t(mRefCnt) >= 0"
") (" "illegal refcnt" ")"); do { *((volatile int*)__null) =
118; __attribute__((nomerge)) ::abort(); } while (false); } }
while (false); _mOwningThread.AssertOwnership("DominatorTree"
" not thread-safe"); nsISupports* base = DominatorTree::cycleCollection
::Upcast(this); nsrefcnt count = mRefCnt.incr(base); NS_LogAddRef
((this), (count), ("DominatorTree"), (uint32_t)(sizeof(*this)
)); return count; }
119NS_IMPL_CYCLE_COLLECTING_RELEASE(DominatorTree)MozExternalRefCountType DominatorTree::Release(void) { do { static_assert
( mozilla::detail::AssertionConditionType<decltype(int32_t
(mRefCnt) > 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(int32_t(mRefCnt) > 0))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("int32_t(mRefCnt) > 0"
" (" "dup release" ")", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 119); AnnotateMozCrashReason("MOZ_ASSERT" "(" "int32_t(mRefCnt) > 0"
") (" "dup release" ")"); do { *((volatile int*)__null) = 119
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false); _mOwningThread.AssertOwnership("DominatorTree" " not thread-safe"
); nsISupports* base = DominatorTree::cycleCollection::Upcast
(this); nsrefcnt count = mRefCnt.decr(base); NS_LogRelease((this
), (count), ("DominatorTree")); return count; } void DominatorTree
::DeleteCycleCollectable(void) { delete (this); }
120
121NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(DominatorTree)nsresult DominatorTree::QueryInterface(const nsIID& aIID,
void** aInstancePtr) { do { if (!(aInstancePtr)) { NS_DebugBreak
(NS_DEBUG_ASSERTION, "QueryInterface requires a non-NULL destination!"
, "aInstancePtr", "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 121); MOZ_PretendNoReturn(); } } while (0); nsISupports* foundInterface
; if (TopThreeWordsEquals( aIID, (nsXPCOMCycleCollectionParticipant
::COMTypeInfo<nsXPCOMCycleCollectionParticipant, void>::
kIID), (nsCycleCollectionISupports::COMTypeInfo<nsCycleCollectionISupports
, void>::kIID)) && (LowWordEquals(aIID, (nsXPCOMCycleCollectionParticipant
::COMTypeInfo<nsXPCOMCycleCollectionParticipant, void>::
kIID)) || LowWordEquals(aIID, (nsCycleCollectionISupports::COMTypeInfo
<nsCycleCollectionISupports, void>::kIID)))) { if (LowWordEquals
(aIID, (nsXPCOMCycleCollectionParticipant::COMTypeInfo<nsXPCOMCycleCollectionParticipant
, void>::kIID))) { *aInstancePtr = DominatorTree::cycleCollection
::GetParticipant(); return NS_OK; } if (LowWordEquals(aIID, (
nsCycleCollectionISupports::COMTypeInfo<nsCycleCollectionISupports
, void>::kIID))) { *aInstancePtr = DominatorTree::cycleCollection
::Upcast(this); return NS_OK; } foundInterface = nullptr; } else
122 NS_WRAPPERCACHE_INTERFACE_MAP_ENTRYif (aIID.Equals((nsWrapperCache::COMTypeInfo<nsWrapperCache
, void>::kIID))) { *aInstancePtr = static_cast<nsWrapperCache
*>(this); return NS_OK; } else
123 NS_INTERFACE_MAP_ENTRY(nsISupports)if (aIID.Equals(mozilla::detail::kImplementedIID<std::remove_reference_t
<decltype(*this)>, nsISupports>)) foundInterface = static_cast
<nsISupports*>(this); else
124NS_INTERFACE_MAP_ENDfoundInterface = 0; nsresult status; if (!foundInterface) { do
{ static_assert( mozilla::detail::AssertionConditionType<
decltype(!aIID.Equals((nsISupports::COMTypeInfo<nsISupports
, void>::kIID)))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!aIID.Equals((nsISupports::COMTypeInfo
<nsISupports, void>::kIID))))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("!aIID.Equals((nsISupports::COMTypeInfo<nsISupports, void>::kIID))"
, "/var/lib/jenkins/workspace/firefox-scan-build/devtools/shared/heapsnapshot/DominatorTree.cpp"
, 124); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!aIID.Equals((nsISupports::COMTypeInfo<nsISupports, void>::kIID))"
")"); do { *((volatile int*)__null) = 124; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false); status = NS_NOINTERFACE
; } else { (foundInterface)->AddRef(); status = NS_OK; } *
aInstancePtr = foundInterface; return status; }
125
126/* virtual */
127JSObject* DominatorTree::WrapObject(JSContext* aCx,
128 JS::Handle<JSObject*> aGivenProto) {
129 return dom::DominatorTree_Binding::Wrap(aCx, this, aGivenProto);
130}
131
132} // namespace devtools
133} // namespace mozilla

/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h

1/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7#ifndef js_UbiNodeDominatorTree_h
8#define js_UbiNodeDominatorTree_h
9
10#include "mozilla/Attributes.h"
11#include "mozilla/DebugOnly.h"
12#include "mozilla/Maybe.h"
13#include "mozilla/UniquePtr.h"
14
15#include <utility>
16
17#include "js/AllocPolicy.h"
18#include "js/UbiNode.h"
19#include "js/UbiNodePostOrder.h"
20#include "js/Utility.h"
21#include "js/Vector.h"
22
23namespace JS {
24namespace ubi {
25
26/**
27 * In a directed graph with a root node `R`, a node `A` is said to "dominate" a
28 * node `B` iff every path from `R` to `B` contains `A`. A node `A` is said to
29 * be the "immediate dominator" of a node `B` iff it dominates `B`, is not `B`
30 * itself, and does not dominate any other nodes which also dominate `B` in
31 * turn.
32 *
33 * If we take every node from a graph `G` and create a new graph `T` with edges
34 * to each node from its immediate dominator, then `T` is a tree (each node has
35 * only one immediate dominator, or none if it is the root). This tree is called
36 * a "dominator tree".
37 *
38 * This class represents a dominator tree constructed from a `JS::ubi::Node`
39 * heap graph. The domination relationship and dominator trees are useful tools
40 * for analyzing heap graphs because they tell you:
41 *
42 * - Exactly what could be reclaimed by the GC if some node `A` became
43 * unreachable: those nodes which are dominated by `A`,
44 *
45 * - The "retained size" of a node in the heap graph, in contrast to its
46 * "shallow size". The "shallow size" is the space taken by a node itself,
47 * not counting anything it references. The "retained size" of a node is its
48 * shallow size plus the size of all the things that would be collected if
49 * the original node wasn't (directly or indirectly) referencing them. In
50 * other words, the retained size is the shallow size of a node plus the
51 * shallow sizes of every other node it dominates. For example, the root
52 * node in a binary tree might have a small shallow size that does not take
53 * up much space itself, but it dominates the rest of the binary tree and
54 * its retained size is therefore significant (assuming no external
55 * references into the tree).
56 *
57 * The simple, engineered algorithm presented in "A Simple, Fast Dominance
58 * Algorithm" by Cooper el al[0] is used to find dominators and construct the
59 * dominator tree. This algorithm runs in O(n^2) time, but is faster in practice
60 * than alternative algorithms with better theoretical running times, such as
61 * Lengauer-Tarjan which runs in O(e * log(n)). The big caveat to that statement
62 * is that Cooper et al found it is faster in practice *on control flow graphs*
63 * and I'm not convinced that this property also holds on *heap* graphs. That
64 * said, the implementation of this algorithm is *much* simpler than
65 * Lengauer-Tarjan and has been found to be fast enough at least for the time
66 * being.
67 *
68 * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
69 */
70class JS_PUBLIC_API DominatorTree {
71 private:
72 // Types.
73
74 using PredecessorSets = js::HashMap<Node, NodeSetPtr, js::DefaultHasher<Node>,
75 js::SystemAllocPolicy>;
76 using NodeToIndexMap = js::HashMap<Node, uint32_t, js::DefaultHasher<Node>,
77 js::SystemAllocPolicy>;
78 class DominatedSets;
79
80 public:
81 class DominatedSetRange;
82
83 /**
84 * A pointer to an immediately dominated node.
85 *
86 * Don't use this type directly; it is no safer than regular pointers. This
87 * is only for use indirectly with range-based for loops and
88 * `DominatedSetRange`.
89 *
90 * @see JS::ubi::DominatorTree::getDominatedSet
91 */
92 class DominatedNodePtr {
93 friend class DominatedSetRange;
94
95 const JS::ubi::Vector<Node>& postOrder;
96 const uint32_t* ptr;
97
98 DominatedNodePtr(const JS::ubi::Vector<Node>& postOrder,
99 const uint32_t* ptr)
100 : postOrder(postOrder), ptr(ptr) {}
101
102 public:
103 bool operator!=(const DominatedNodePtr& rhs) const {
104 return ptr != rhs.ptr;
105 }
106 void operator++() { ptr++; }
107 const Node& operator*() const { return postOrder[*ptr]; }
108 };
109
110 /**
111 * A range of immediately dominated `JS::ubi::Node`s for use with
112 * range-based for loops.
113 *
114 * @see JS::ubi::DominatorTree::getDominatedSet
115 */
116 class DominatedSetRange {
117 friend class DominatedSets;
118
119 const JS::ubi::Vector<Node>& postOrder;
120 const uint32_t* beginPtr;
121 const uint32_t* endPtr;
122
123 DominatedSetRange(JS::ubi::Vector<Node>& postOrder, const uint32_t* begin,
124 const uint32_t* end)
125 : postOrder(postOrder), beginPtr(begin), endPtr(end) {
126 MOZ_ASSERT(begin <= end)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(begin <= end)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(begin <= end))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("begin <= end"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 126); AnnotateMozCrashReason("MOZ_ASSERT" "(" "begin <= end"
")"); do { *((volatile int*)__null) = 126; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
127 }
128
129 public:
130 DominatedNodePtr begin() const {
131 MOZ_ASSERT(beginPtr <= endPtr)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(beginPtr <= endPtr)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(beginPtr <= endPtr))), 0)
)) { do { } while (false); MOZ_ReportAssertionFailure("beginPtr <= endPtr"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 131); AnnotateMozCrashReason("MOZ_ASSERT" "(" "beginPtr <= endPtr"
")"); do { *((volatile int*)__null) = 131; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
132 return DominatedNodePtr(postOrder, beginPtr);
133 }
134
135 DominatedNodePtr end() const { return DominatedNodePtr(postOrder, endPtr); }
136
137 size_t length() const {
138 MOZ_ASSERT(beginPtr <= endPtr)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(beginPtr <= endPtr)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(beginPtr <= endPtr))), 0)
)) { do { } while (false); MOZ_ReportAssertionFailure("beginPtr <= endPtr"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 138); AnnotateMozCrashReason("MOZ_ASSERT" "(" "beginPtr <= endPtr"
")"); do { *((volatile int*)__null) = 138; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
139 return endPtr - beginPtr;
140 }
141
142 /**
143 * Safely skip ahead `n` dominators in the range, in O(1) time.
144 *
145 * Example usage:
146 *
147 * mozilla::Maybe<DominatedSetRange> range =
148 * myDominatorTree.getDominatedSet(myNode);
149 * if (range.isNothing()) {
150 * // Handle unknown nodes however you see fit...
151 * return false;
152 * }
153 *
154 * // Don't care about the first ten, for whatever reason.
155 * range->skip(10);
156 * for (const JS::ubi::Node& dominatedNode : *range) {
157 * // ...
158 * }
159 */
160 void skip(size_t n) {
161 beginPtr += n;
162 if (beginPtr > endPtr) {
163 beginPtr = endPtr;
164 }
165 }
166 };
167
168 private:
169 /**
170 * The set of all dominated sets in a dominator tree.
171 *
172 * Internally stores the sets in a contiguous array, with a side table of
173 * indices into that contiguous array to denote the start index of each
174 * individual set.
175 */
176 class DominatedSets {
177 JS::ubi::Vector<uint32_t> dominated;
178 JS::ubi::Vector<uint32_t> indices;
179
180 DominatedSets(JS::ubi::Vector<uint32_t>&& dominated,
181 JS::ubi::Vector<uint32_t>&& indices)
182 : dominated(std::move(dominated)), indices(std::move(indices)) {}
183
184 public:
185 // DominatedSets is not copy-able.
186 DominatedSets(const DominatedSets& rhs) = delete;
187 DominatedSets& operator=(const DominatedSets& rhs) = delete;
188
189 // DominatedSets is move-able.
190 DominatedSets(DominatedSets&& rhs)
191 : dominated(std::move(rhs.dominated)), indices(std::move(rhs.indices)) {
192 MOZ_ASSERT(this != &rhs, "self-move not allowed")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this != &rhs)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(this != &rhs))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("this != &rhs"
" (" "self-move not allowed" ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 192); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this != &rhs"
") (" "self-move not allowed" ")"); do { *((volatile int*)__null
) = 192; __attribute__((nomerge)) ::abort(); } while (false);
} } while (false)
;
193 }
194 DominatedSets& operator=(DominatedSets&& rhs) {
195 this->~DominatedSets();
196 new (this) DominatedSets(std::move(rhs));
197 return *this;
198 }
199
200 /**
201 * Create the DominatedSets given the mapping of a node index to its
202 * immediate dominator. Returns `Some` on success, `Nothing` on OOM
203 * failure.
204 */
205 static mozilla::Maybe<DominatedSets> Create(
206 const JS::ubi::Vector<uint32_t>& doms) {
207 auto length = doms.length();
208 MOZ_ASSERT(length < UINT32_MAX)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(length < (4294967295U))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(length < (4294967295U))))
, 0))) { do { } while (false); MOZ_ReportAssertionFailure("length < (4294967295U)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 208); AnnotateMozCrashReason("MOZ_ASSERT" "(" "length < (4294967295U)"
")"); do { *((volatile int*)__null) = 208; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
209
210 // Create a vector `dominated` holding a flattened set of buckets of
211 // immediately dominated children nodes, with a lookup table
212 // `indices` mapping from each node to the beginning of its bucket.
213 //
214 // This has three phases:
215 //
216 // 1. Iterate over the full set of nodes and count up the size of
217 // each bucket. These bucket sizes are temporarily stored in the
218 // `indices` vector.
219 //
220 // 2. Convert the `indices` vector to store the cumulative sum of
221 // the sizes of all buckets before each index, resulting in a
222 // mapping from node index to one past the end of that node's
223 // bucket.
224 //
225 // 3. Iterate over the full set of nodes again, filling in bucket
226 // entries from the end of the bucket's range to its
227 // beginning. This decrements each index as a bucket entry is
228 // filled in. After having filled in all of a bucket's entries,
229 // the index points to the start of the bucket.
230
231 JS::ubi::Vector<uint32_t> dominated;
232 JS::ubi::Vector<uint32_t> indices;
233 if (!dominated.growBy(length) || !indices.growBy(length)) {
234 return mozilla::Nothing();
235 }
236
237 // 1
238 memset(indices.begin(), 0, length * sizeof(uint32_t));
239 for (uint32_t i = 0; i < length; i++) {
240 indices[doms[i]]++;
241 }
242
243 // 2
244 uint32_t sumOfSizes = 0;
245 for (uint32_t i = 0; i < length; i++) {
246 sumOfSizes += indices[i];
247 MOZ_ASSERT(sumOfSizes <= length)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(sumOfSizes <= length)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(sumOfSizes <= length))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("sumOfSizes <= length"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 247); AnnotateMozCrashReason("MOZ_ASSERT" "(" "sumOfSizes <= length"
")"); do { *((volatile int*)__null) = 247; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
248 indices[i] = sumOfSizes;
249 }
250
251 // 3
252 for (uint32_t i = 0; i < length; i++) {
253 auto idxOfDom = doms[i];
254 indices[idxOfDom]--;
255 dominated[indices[idxOfDom]] = i;
256 }
257
258#ifdef DEBUG1
259 // Assert that our buckets are non-overlapping and don't run off the
260 // end of the vector.
261 uint32_t lastIndex = 0;
262 for (uint32_t i = 0; i < length; i++) {
263 MOZ_ASSERT(indices[i] >= lastIndex)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(indices[i] >= lastIndex)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(indices[i] >= lastIndex))
), 0))) { do { } while (false); MOZ_ReportAssertionFailure("indices[i] >= lastIndex"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 263); AnnotateMozCrashReason("MOZ_ASSERT" "(" "indices[i] >= lastIndex"
")"); do { *((volatile int*)__null) = 263; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
264 MOZ_ASSERT(indices[i] < length)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(indices[i] < length)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(indices[i] < length))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("indices[i] < length"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 264); AnnotateMozCrashReason("MOZ_ASSERT" "(" "indices[i] < length"
")"); do { *((volatile int*)__null) = 264; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
265 lastIndex = indices[i];
266 }
267#endif
268
269 return mozilla::Some(
270 DominatedSets(std::move(dominated), std::move(indices)));
271 }
272
273 /**
274 * Get the set of nodes immediately dominated by the node at
275 * `postOrder[nodeIndex]`.
276 */
277 DominatedSetRange dominatedSet(JS::ubi::Vector<Node>& postOrder,
278 uint32_t nodeIndex) const {
279 MOZ_ASSERT(postOrder.length() == indices.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() == indices.length())>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(postOrder.length() == indices.length()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("postOrder.length() == indices.length()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 279); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() == indices.length()"
")"); do { *((volatile int*)__null) = 279; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
280 MOZ_ASSERT(nodeIndex < indices.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(nodeIndex < indices.length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(nodeIndex < indices.length
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("nodeIndex < indices.length()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 280); AnnotateMozCrashReason("MOZ_ASSERT" "(" "nodeIndex < indices.length()"
")"); do { *((volatile int*)__null) = 280; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
281 auto end = nodeIndex == indices.length() - 1
282 ? dominated.end()
283 : &dominated[indices[nodeIndex + 1]];
284 return DominatedSetRange(postOrder, &dominated[indices[nodeIndex]], end);
285 }
286 };
287
288 private:
289 // Data members.
290 JS::ubi::Vector<Node> postOrder;
291 NodeToIndexMap nodeToPostOrderIndex;
292 JS::ubi::Vector<uint32_t> doms;
293 DominatedSets dominatedSets;
294 mozilla::Maybe<JS::ubi::Vector<JS::ubi::Node::Size>> retainedSizes;
295
296 private:
297 // We use `UNDEFINED` as a sentinel value in the `doms` vector to signal
298 // that we haven't found any dominators for the node at the corresponding
299 // index in `postOrder` yet.
300 static const uint32_t UNDEFINED = UINT32_MAX(4294967295U);
301
302 DominatorTree(JS::ubi::Vector<Node>&& postOrder,
303 NodeToIndexMap&& nodeToPostOrderIndex,
304 JS::ubi::Vector<uint32_t>&& doms, DominatedSets&& dominatedSets)
305 : postOrder(std::move(postOrder)),
306 nodeToPostOrderIndex(std::move(nodeToPostOrderIndex)),
307 doms(std::move(doms)),
308 dominatedSets(std::move(dominatedSets)),
309 retainedSizes(mozilla::Nothing()) {}
310
311 static uint32_t intersect(JS::ubi::Vector<uint32_t>& doms, uint32_t finger1,
312 uint32_t finger2) {
313 while (finger1 != finger2) {
314 if (finger1 < finger2) {
315 finger1 = doms[finger1];
316 } else if (finger2 < finger1) {
317 finger2 = doms[finger2];
318 }
319 }
320 return finger1;
321 }
322
323 // Do the post order traversal of the heap graph and populate our
324 // predecessor sets.
325 [[nodiscard]] static bool doTraversal(JSContext* cx, AutoCheckCannotGC& noGC,
326 const Node& root,
327 JS::ubi::Vector<Node>& postOrder,
328 PredecessorSets& predecessorSets) {
329 uint32_t nodeCount = 0;
330 auto onNode = [&](const Node& node) {
331 nodeCount++;
332 if (MOZ_UNLIKELY(nodeCount == UINT32_MAX)(__builtin_expect(!!(nodeCount == (4294967295U)), 0))) {
333 return false;
334 }
335 return postOrder.append(node);
336 };
337
338 auto onEdge = [&](const Node& origin, const Edge& edge) {
339 auto p = predecessorSets.lookupForAdd(edge.referent);
340 if (!p) {
341 mozilla::UniquePtr<NodeSet, DeletePolicy<NodeSet>> set(
342 js_new<NodeSet>());
343 if (!set || !predecessorSets.add(p, edge.referent, std::move(set))) {
344 return false;
345 }
346 }
347 MOZ_ASSERT(p && p->value())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(p && p->value())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(p && p->value()))
), 0))) { do { } while (false); MOZ_ReportAssertionFailure("p && p->value()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 347); AnnotateMozCrashReason("MOZ_ASSERT" "(" "p && p->value()"
")"); do { *((volatile int*)__null) = 347; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
348 return p->value()->put(origin);
349 };
350
351 PostOrder traversal(cx, noGC);
352 return traversal.addStart(root) && traversal.traverse(onNode, onEdge);
353 }
354
355 // Populates the given `map` with an entry for each node to its index in
356 // `postOrder`.
357 [[nodiscard]] static bool mapNodesToTheirIndices(
358 JS::ubi::Vector<Node>& postOrder, NodeToIndexMap& map) {
359 MOZ_ASSERT(map.empty())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(map.empty())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(map.empty()))), 0))) { do { }
while (false); MOZ_ReportAssertionFailure("map.empty()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 359); AnnotateMozCrashReason("MOZ_ASSERT" "(" "map.empty()"
")"); do { *((volatile int*)__null) = 359; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
360 MOZ_ASSERT(postOrder.length() < UINT32_MAX)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() < (4294967295U))>::isValid,
"invalid assertion condition"); if ((__builtin_expect(!!(!(!
!(postOrder.length() < (4294967295U)))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("postOrder.length() < (4294967295U)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 360); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() < (4294967295U)"
")"); do { *((volatile int*)__null) = 360; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
361 uint32_t length = postOrder.length();
362 if (!map.reserve(length)) {
363 return false;
364 }
365 for (uint32_t i = 0; i < length; i++) {
366 map.putNewInfallible(postOrder[i], i);
367 }
368 return true;
369 }
370
371 // Convert the Node -> NodeSet predecessorSets to a index -> Vector<index>
372 // form.
373 [[nodiscard]] static bool convertPredecessorSetsToVectors(
374 const Node& root, JS::ubi::Vector<Node>& postOrder,
375 PredecessorSets& predecessorSets, NodeToIndexMap& nodeToPostOrderIndex,
376 JS::ubi::Vector<JS::ubi::Vector<uint32_t>>& predecessorVectors) {
377 MOZ_ASSERT(postOrder.length() < UINT32_MAX)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() < (4294967295U))>::isValid,
"invalid assertion condition"); if ((__builtin_expect(!!(!(!
!(postOrder.length() < (4294967295U)))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("postOrder.length() < (4294967295U)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 377); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() < (4294967295U)"
")"); do { *((volatile int*)__null) = 377; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
378 uint32_t length = postOrder.length();
379
380 MOZ_ASSERT(predecessorVectors.length() == 0)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(predecessorVectors.length() == 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(predecessorVectors.length() ==
0))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("predecessorVectors.length() == 0", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 380); AnnotateMozCrashReason("MOZ_ASSERT" "(" "predecessorVectors.length() == 0"
")"); do { *((volatile int*)__null) = 380; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
381 if (!predecessorVectors.growBy(length)) {
382 return false;
383 }
384
385 for (uint32_t i = 0; i < length - 1; i++) {
386 auto& node = postOrder[i];
387 MOZ_ASSERT(node != root,do { static_assert( mozilla::detail::AssertionConditionType<
decltype(node != root)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(node != root))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("node != root" " ("
"Only the last node should be root, since this was a post " "order traversal."
")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 389); AnnotateMozCrashReason("MOZ_ASSERT" "(" "node != root"
") (" "Only the last node should be root, since this was a post "
"order traversal." ")"); do { *((volatile int*)__null) = 389
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
388 "Only the last node should be root, since this was a post "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(node != root)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(node != root))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("node != root" " ("
"Only the last node should be root, since this was a post " "order traversal."
")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 389); AnnotateMozCrashReason("MOZ_ASSERT" "(" "node != root"
") (" "Only the last node should be root, since this was a post "
"order traversal." ")"); do { *((volatile int*)__null) = 389
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
389 "order traversal.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(node != root)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(node != root))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("node != root" " ("
"Only the last node should be root, since this was a post " "order traversal."
")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 389); AnnotateMozCrashReason("MOZ_ASSERT" "(" "node != root"
") (" "Only the last node should be root, since this was a post "
"order traversal." ")"); do { *((volatile int*)__null) = 389
; __attribute__((nomerge)) ::abort(); } while (false); } } while
(false)
;
390
391 auto ptr = predecessorSets.lookup(node);
392 MOZ_ASSERT(ptr,do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr" " (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 395); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ") (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")"); do
{ *((volatile int*)__null) = 395; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
393 "Because this isn't the root, it had better have "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr" " (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 395); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ") (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")"); do
{ *((volatile int*)__null) = 395; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
394 "predecessors, or else how "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr" " (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 395); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ") (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")"); do
{ *((volatile int*)__null) = 395; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
395 "did we even find it.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr" " (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 395); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ") (" "Because this isn't the root, it had better have "
"predecessors, or else how " "did we even find it." ")"); do
{ *((volatile int*)__null) = 395; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
;
396
397 auto& predecessors = ptr->value();
398 if (!predecessorVectors[i].reserve(predecessors->count())) {
399 return false;
400 }
401 for (auto range = predecessors->all(); !range.empty(); range.popFront()) {
402 auto ptr = nodeToPostOrderIndex.lookup(range.front());
403 MOZ_ASSERT(ptr)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 403); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ")"); do
{ *((volatile int*)__null) = 403; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
;
404 predecessorVectors[i].infallibleAppend(ptr->value());
405 }
406 }
407 predecessorSets.clearAndCompact();
408 return true;
409 }
410
411 // Initialize `doms` such that the immediate dominator of the `root` is the
412 // `root` itself and all others are `UNDEFINED`.
413 [[nodiscard]] static bool initializeDominators(
414 JS::ubi::Vector<uint32_t>& doms, uint32_t length) {
415 MOZ_ASSERT(doms.length() == 0)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(doms.length() == 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(doms.length() == 0))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("doms.length() == 0"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 415); AnnotateMozCrashReason("MOZ_ASSERT" "(" "doms.length() == 0"
")"); do { *((volatile int*)__null) = 415; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
416 if (!doms.growByUninitialized(length)) {
417 return false;
418 }
419 doms[length - 1] = length - 1;
420 for (uint32_t i = 0; i < length - 1; i++) {
421 doms[i] = UNDEFINED;
422 }
423 return true;
424 }
425
426 void assertSanity() const {
427 MOZ_ASSERT(postOrder.length() == doms.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() == doms.length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(postOrder.length() == doms.length
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("postOrder.length() == doms.length()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 427); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() == doms.length()"
")"); do { *((volatile int*)__null) = 427; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
428 MOZ_ASSERT(postOrder.length() == nodeToPostOrderIndex.count())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() == nodeToPostOrderIndex.count())>
::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!(postOrder.length() == nodeToPostOrderIndex.count()))
), 0))) { do { } while (false); MOZ_ReportAssertionFailure("postOrder.length() == nodeToPostOrderIndex.count()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 428); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() == nodeToPostOrderIndex.count()"
")"); do { *((volatile int*)__null) = 428; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
429 MOZ_ASSERT_IF(retainedSizes.isSome(),do { if (retainedSizes.isSome()) { do { static_assert( mozilla
::detail::AssertionConditionType<decltype(postOrder.length
() == retainedSizes->length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(postOrder.length() == retainedSizes
->length()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("postOrder.length() == retainedSizes->length()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 430); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() == retainedSizes->length()"
")"); do { *((volatile int*)__null) = 430; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false); } } while (
false)
430 postOrder.length() == retainedSizes->length())do { if (retainedSizes.isSome()) { do { static_assert( mozilla
::detail::AssertionConditionType<decltype(postOrder.length
() == retainedSizes->length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(postOrder.length() == retainedSizes
->length()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("postOrder.length() == retainedSizes->length()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 430); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() == retainedSizes->length()"
")"); do { *((volatile int*)__null) = 430; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false); } } while (
false)
;
431 }
432
433 [[nodiscard]] bool computeRetainedSizes(mozilla::MallocSizeOf mallocSizeOf) {
434 MOZ_ASSERT(retainedSizes.isNothing())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(retainedSizes.isNothing())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(retainedSizes.isNothing())))
, 0))) { do { } while (false); MOZ_ReportAssertionFailure("retainedSizes.isNothing()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 434); AnnotateMozCrashReason("MOZ_ASSERT" "(" "retainedSizes.isNothing()"
")"); do { *((volatile int*)__null) = 434; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
435 auto length = postOrder.length();
436
437 retainedSizes.emplace();
438 if (!retainedSizes->growBy(length)) {
439 retainedSizes = mozilla::Nothing();
440 return false;
441 }
442
443 // Iterate in forward order so that we know all of a node's children in
444 // the dominator tree have already had their retained size
445 // computed. Then we can simply say that the retained size of a node is
446 // its shallow size (JS::ubi::Node::size) plus the retained sizes of its
447 // immediate children in the tree.
448
449 for (uint32_t i = 0; i < length; i++) {
450 auto size = postOrder[i].size(mallocSizeOf);
451
452 for (const auto& dominated : dominatedSets.dominatedSet(postOrder, i)) {
453 // The root node dominates itself, but shouldn't contribute to
454 // its own retained size.
455 if (dominated == postOrder[length - 1]) {
456 MOZ_ASSERT(i == length - 1)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(i == length - 1)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(i == length - 1))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("i == length - 1"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 456); AnnotateMozCrashReason("MOZ_ASSERT" "(" "i == length - 1"
")"); do { *((volatile int*)__null) = 456; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
457 continue;
458 }
459
460 auto ptr = nodeToPostOrderIndex.lookup(dominated);
461 MOZ_ASSERT(ptr)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(ptr)>::isValid, "invalid assertion condition"); if
((__builtin_expect(!!(!(!!(ptr))), 0))) { do { } while (false
); MOZ_ReportAssertionFailure("ptr", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 461); AnnotateMozCrashReason("MOZ_ASSERT" "(" "ptr" ")"); do
{ *((volatile int*)__null) = 461; __attribute__((nomerge)) ::
abort(); } while (false); } } while (false)
;
462 auto idxOfDominated = ptr->value();
463 MOZ_ASSERT(idxOfDominated < i)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(idxOfDominated < i)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(idxOfDominated < i))), 0)
)) { do { } while (false); MOZ_ReportAssertionFailure("idxOfDominated < i"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 463); AnnotateMozCrashReason("MOZ_ASSERT" "(" "idxOfDominated < i"
")"); do { *((volatile int*)__null) = 463; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
464 size += retainedSizes.ref()[idxOfDominated];
465 }
466
467 retainedSizes.ref()[i] = size;
468 }
469
470 return true;
471 }
472
473 public:
474 // DominatorTree is not copy-able.
475 DominatorTree(const DominatorTree&) = delete;
476 DominatorTree& operator=(const DominatorTree&) = delete;
477
478 // DominatorTree is move-able.
479 DominatorTree(DominatorTree&& rhs)
480 : postOrder(std::move(rhs.postOrder)),
481 nodeToPostOrderIndex(std::move(rhs.nodeToPostOrderIndex)),
482 doms(std::move(rhs.doms)),
483 dominatedSets(std::move(rhs.dominatedSets)),
484 retainedSizes(std::move(rhs.retainedSizes)) {
485 MOZ_ASSERT(this != &rhs, "self-move is not allowed")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this != &rhs)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(this != &rhs))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("this != &rhs"
" (" "self-move is not allowed" ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 485); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this != &rhs"
") (" "self-move is not allowed" ")"); do { *((volatile int*
)__null) = 485; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
;
486 }
487 DominatorTree& operator=(DominatorTree&& rhs) {
488 this->~DominatorTree();
489 new (this) DominatorTree(std::move(rhs));
490 return *this;
491 }
492
493 /**
494 * Construct a `DominatorTree` of the heap graph visible from `root`. The
495 * `root` is also used as the root of the resulting dominator tree.
496 *
497 * The resulting `DominatorTree` instance must not outlive the
498 * `JS::ubi::Node` graph it was constructed from.
499 *
500 * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
501 * that the `DominatorTree`'s lifetime _must_ be contained within the
502 * scope of the provided `AutoCheckCannotGC` reference because a GC will
503 * invalidate the nodes.
504 *
505 * - For `JS::ubi::Node` graphs backed by some other offline structure
506 * provided by the embedder, the resulting `DominatorTree`'s lifetime is
507 * bounded by that offline structure's lifetime.
508 *
509 * In practice, this means that within SpiderMonkey we must treat
510 * `DominatorTree` as if it were backed by the live heap graph and trust
511 * that embedders with knowledge of the graph's implementation will do the
512 * Right Thing.
513 *
514 * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
515 * responsibility to handle and report the OOM.
516 */
517 static mozilla::Maybe<DominatorTree> Create(JSContext* cx,
518 AutoCheckCannotGC& noGC,
519 const Node& root) {
520 JS::ubi::Vector<Node> postOrder;
521 PredecessorSets predecessorSets;
522 if (!doTraversal(cx, noGC, root, postOrder, predecessorSets)) {
523 return mozilla::Nothing();
524 }
525
526 MOZ_ASSERT(postOrder.length() < UINT32_MAX)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder.length() < (4294967295U))>::isValid,
"invalid assertion condition"); if ((__builtin_expect(!!(!(!
!(postOrder.length() < (4294967295U)))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("postOrder.length() < (4294967295U)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 526); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder.length() < (4294967295U)"
")"); do { *((volatile int*)__null) = 526; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
527 uint32_t length = postOrder.length();
528 MOZ_ASSERT(postOrder[length - 1] == root)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder[length - 1] == root)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(postOrder[length - 1] == root
))), 0))) { do { } while (false); MOZ_ReportAssertionFailure(
"postOrder[length - 1] == root", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 528); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder[length - 1] == root"
")"); do { *((volatile int*)__null) = 528; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
529
530 // From here on out we wish to avoid hash table lookups, and we use
531 // indices into `postOrder` instead of actual nodes wherever
532 // possible. This greatly improves the performance of this
533 // implementation, but we have to pay a little bit of upfront cost to
534 // convert our data structures to play along first.
535
536 NodeToIndexMap nodeToPostOrderIndex(postOrder.length());
537 if (!mapNodesToTheirIndices(postOrder, nodeToPostOrderIndex)) {
538 return mozilla::Nothing();
539 }
540
541 JS::ubi::Vector<JS::ubi::Vector<uint32_t>> predecessorVectors;
542 if (!convertPredecessorSetsToVectors(root, postOrder, predecessorSets,
543 nodeToPostOrderIndex,
544 predecessorVectors))
545 return mozilla::Nothing();
546
547 JS::ubi::Vector<uint32_t> doms;
548 if (!initializeDominators(doms, length)) {
549 return mozilla::Nothing();
550 }
551
552 bool changed = true;
553 while (changed) {
554 changed = false;
555
556 // Iterate over the non-root nodes in reverse post order.
557 for (uint32_t indexPlusOne = length - 1; indexPlusOne > 0;
558 indexPlusOne--) {
559 MOZ_ASSERT(postOrder[indexPlusOne - 1] != root)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(postOrder[indexPlusOne - 1] != root)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(postOrder[indexPlusOne - 1] !=
root))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("postOrder[indexPlusOne - 1] != root", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 559); AnnotateMozCrashReason("MOZ_ASSERT" "(" "postOrder[indexPlusOne - 1] != root"
")"); do { *((volatile int*)__null) = 559; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
560
561 // Take the intersection of every predecessor's dominator set;
562 // that is the current best guess at the immediate dominator for
563 // this node.
564
565 uint32_t newIDomIdx = UNDEFINED;
566
567 auto& predecessors = predecessorVectors[indexPlusOne - 1];
568 auto range = predecessors.all();
569 for (; !range.empty(); range.popFront()) {
570 auto idx = range.front();
571 if (doms[idx] != UNDEFINED) {
572 newIDomIdx = idx;
573 break;
574 }
575 }
576
577 MOZ_ASSERT(newIDomIdx != UNDEFINED,do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
578 "Because the root is initialized to dominate itself and is "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
579 "the first "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
580 "node in every path, there must exist a predecessor to this "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
581 "node that "do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
582 "also has a dominator.")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(newIDomIdx != UNDEFINED)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(newIDomIdx != UNDEFINED))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("newIDomIdx != UNDEFINED"
" (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 582); AnnotateMozCrashReason("MOZ_ASSERT" "(" "newIDomIdx != UNDEFINED"
") (" "Because the root is initialized to dominate itself and is "
"the first " "node in every path, there must exist a predecessor to this "
"node that " "also has a dominator." ")"); do { *((volatile int
*)__null) = 582; __attribute__((nomerge)) ::abort(); } while (
false); } } while (false)
;
583
584 for (; !range.empty(); range.popFront()) {
585 auto idx = range.front();
586 if (doms[idx] != UNDEFINED) {
587 newIDomIdx = intersect(doms, newIDomIdx, idx);
588 }
589 }
590
591 // If the immediate dominator changed, we will have to do
592 // another pass of the outer while loop to continue the forward
593 // dataflow.
594 if (newIDomIdx != doms[indexPlusOne - 1]) {
595 doms[indexPlusOne - 1] = newIDomIdx;
596 changed = true;
597 }
598 }
599 }
600
601 auto maybeDominatedSets = DominatedSets::Create(doms);
602 if (maybeDominatedSets.isNothing()) {
603 return mozilla::Nothing();
604 }
605
606 return mozilla::Some(
607 DominatorTree(std::move(postOrder), std::move(nodeToPostOrderIndex),
608 std::move(doms), std::move(*maybeDominatedSets)));
609 }
610
611 /**
612 * Get the root node for this dominator tree.
613 */
614 const Node& root() const { return postOrder[postOrder.length() - 1]; }
615
616 /**
617 * Return the immediate dominator of the given `node`. If `node` was not
618 * reachable from the `root` that this dominator tree was constructed from,
619 * then return the null `JS::ubi::Node`.
620 */
621 Node getImmediateDominator(const Node& node) const {
622 assertSanity();
623 auto ptr = nodeToPostOrderIndex.lookup(node);
3
Calling 'HashMap::lookup'
12
Returning from 'HashMap::lookup'
624 if (!ptr) {
13
Assuming the condition is false
14
Taking false branch
625 return Node();
626 }
627
628 auto idx = ptr->value();
15
Calling 'Ptr::operator->'
629 MOZ_ASSERT(idx < postOrder.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(idx < postOrder.length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(idx < postOrder.length())
)), 0))) { do { } while (false); MOZ_ReportAssertionFailure("idx < postOrder.length()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 629); AnnotateMozCrashReason("MOZ_ASSERT" "(" "idx < postOrder.length()"
")"); do { *((volatile int*)__null) = 629; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
630 return postOrder[doms[idx]];
631 }
632
633 /**
634 * Get the set of nodes immediately dominated by the given `node`. If `node`
635 * is not a member of this dominator tree, return `Nothing`.
636 *
637 * Example usage:
638 *
639 * mozilla::Maybe<DominatedSetRange> range =
640 * myDominatorTree.getDominatedSet(myNode);
641 * if (range.isNothing()) {
642 * // Handle unknown node however you see fit...
643 * return false;
644 * }
645 *
646 * for (const JS::ubi::Node& dominatedNode : *range) {
647 * // Do something with each immediately dominated node...
648 * }
649 */
650 mozilla::Maybe<DominatedSetRange> getDominatedSet(const Node& node) {
651 assertSanity();
652 auto ptr = nodeToPostOrderIndex.lookup(node);
653 if (!ptr) {
654 return mozilla::Nothing();
655 }
656
657 auto idx = ptr->value();
658 MOZ_ASSERT(idx < postOrder.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(idx < postOrder.length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(idx < postOrder.length())
)), 0))) { do { } while (false); MOZ_ReportAssertionFailure("idx < postOrder.length()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 658); AnnotateMozCrashReason("MOZ_ASSERT" "(" "idx < postOrder.length()"
")"); do { *((volatile int*)__null) = 658; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
659 return mozilla::Some(dominatedSets.dominatedSet(postOrder, idx));
660 }
661
662 /**
663 * Get the retained size of the given `node`. The size is placed in
664 * `outSize`, or 0 if `node` is not a member of the dominator tree. Returns
665 * false on OOM failure, leaving `outSize` unchanged.
666 */
667 [[nodiscard]] bool getRetainedSize(const Node& node,
668 mozilla::MallocSizeOf mallocSizeOf,
669 Node::Size& outSize) {
670 assertSanity();
671 auto ptr = nodeToPostOrderIndex.lookup(node);
672 if (!ptr) {
673 outSize = 0;
674 return true;
675 }
676
677 if (retainedSizes.isNothing() && !computeRetainedSizes(mallocSizeOf)) {
678 return false;
679 }
680
681 auto idx = ptr->value();
682 MOZ_ASSERT(idx < postOrder.length())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(idx < postOrder.length())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(idx < postOrder.length())
)), 0))) { do { } while (false); MOZ_ReportAssertionFailure("idx < postOrder.length()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/js/UbiNodeDominatorTree.h"
, 682); AnnotateMozCrashReason("MOZ_ASSERT" "(" "idx < postOrder.length()"
")"); do { *((volatile int*)__null) = 682; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
683 outSize = retainedSizes.ref()[idx];
684 return true;
685 }
686};
687
688} // namespace ubi
689} // namespace JS
690
691#endif // js_UbiNodeDominatorTree_h

/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h

1/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3/* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7//---------------------------------------------------------------------------
8// Overview
9//---------------------------------------------------------------------------
10//
11// This file defines HashMap<Key, Value> and HashSet<T>, hash tables that are
12// fast and have a nice API.
13//
14// Both hash tables have two optional template parameters.
15//
16// - HashPolicy. This defines the operations for hashing and matching keys. The
17// default HashPolicy is appropriate when both of the following two
18// conditions are true.
19//
20// - The key type stored in the table (|Key| for |HashMap<Key, Value>|, |T|
21// for |HashSet<T>|) is an integer, pointer, UniquePtr, float, or double.
22//
23// - The type used for lookups (|Lookup|) is the same as the key type. This
24// is usually the case, but not always.
25//
26// There is also a |CStringHasher| policy for |char*| keys. If your keys
27// don't match any of the above cases, you must provide your own hash policy;
28// see the "Hash Policy" section below.
29//
30// - AllocPolicy. This defines how allocations are done by the table.
31//
32// - |MallocAllocPolicy| is the default and is usually appropriate; note that
33// operations (such as insertions) that might cause allocations are
34// fallible and must be checked for OOM. These checks are enforced by the
35// use of [[nodiscard]].
36//
37// - |InfallibleAllocPolicy| is another possibility; it allows the
38// abovementioned OOM checks to be done with MOZ_ALWAYS_TRUE().
39//
40// Note that entry storage allocation is lazy, and not done until the first
41// lookupForAdd(), put(), or putNew() is performed.
42//
43// See AllocPolicy.h for more details.
44//
45// Documentation on how to use HashMap and HashSet, including examples, is
46// present within those classes. Search for "class HashMap" and "class
47// HashSet".
48//
49// Both HashMap and HashSet are implemented on top of a third class, HashTable.
50// You only need to look at HashTable if you want to understand the
51// implementation.
52//
53// How does mozilla::HashTable (this file) compare with PLDHashTable (and its
54// subclasses, such as nsTHashtable)?
55//
56// - mozilla::HashTable is a lot faster, largely because it uses templates
57// throughout *and* inlines everything. PLDHashTable inlines operations much
58// less aggressively, and also uses "virtual ops" for operations like hashing
59// and matching entries that require function calls.
60//
61// - Correspondingly, mozilla::HashTable use is likely to increase executable
62// size much more than PLDHashTable.
63//
64// - mozilla::HashTable has a nicer API, with a proper HashSet vs. HashMap
65// distinction.
66//
67// - mozilla::HashTable requires more explicit OOM checking. As mentioned
68// above, the use of |InfallibleAllocPolicy| can simplify things.
69//
70// - mozilla::HashTable has a default capacity on creation of 32 and a minimum
71// capacity of 4. PLDHashTable has a default capacity on creation of 8 and a
72// minimum capacity of 8.
73
74#ifndef mozilla_HashTable_h
75#define mozilla_HashTable_h
76
77#include <utility>
78#include <type_traits>
79
80#include "mozilla/AllocPolicy.h"
81#include "mozilla/Assertions.h"
82#include "mozilla/Attributes.h"
83#include "mozilla/Casting.h"
84#include "mozilla/HashFunctions.h"
85#include "mozilla/MathAlgorithms.h"
86#include "mozilla/Maybe.h"
87#include "mozilla/MemoryChecking.h"
88#include "mozilla/MemoryReporting.h"
89#include "mozilla/Opaque.h"
90#include "mozilla/OperatorNewExtensions.h"
91#include "mozilla/ReentrancyGuard.h"
92#include "mozilla/UniquePtr.h"
93#include "mozilla/WrappingOperations.h"
94
95namespace mozilla {
96
97template <class, class = void>
98struct DefaultHasher;
99
100template <class, class>
101class HashMapEntry;
102
103namespace detail {
104
105template <typename T>
106class HashTableEntry;
107
108template <class T, class HashPolicy, class AllocPolicy>
109class HashTable;
110
111} // namespace detail
112
113// The "generation" of a hash table is an opaque value indicating the state of
114// modification of the hash table through its lifetime. If the generation of
115// a hash table compares equal at times T1 and T2, then lookups in the hash
116// table, pointers to (or into) hash table entries, etc. at time T1 are valid
117// at time T2. If the generation compares unequal, these computations are all
118// invalid and must be performed again to be used.
119//
120// Generations are meaningfully comparable only with respect to a single hash
121// table. It's always nonsensical to compare the generation of distinct hash
122// tables H1 and H2.
123using Generation = Opaque<uint64_t>;
124
125//---------------------------------------------------------------------------
126// HashMap
127//---------------------------------------------------------------------------
128
129// HashMap is a fast hash-based map from keys to values.
130//
131// Template parameter requirements:
132// - Key/Value: movable, destructible, assignable.
133// - HashPolicy: see the "Hash Policy" section below.
134// - AllocPolicy: see AllocPolicy.h.
135//
136// Note:
137// - HashMap is not reentrant: Key/Value/HashPolicy/AllocPolicy members
138// called by HashMap must not call back into the same HashMap object.
139//
140template <class Key, class Value, class HashPolicy = DefaultHasher<Key>,
141 class AllocPolicy = MallocAllocPolicy>
142class HashMap {
143 // -- Implementation details -----------------------------------------------
144
145 // HashMap is not copyable or assignable.
146 HashMap(const HashMap& hm) = delete;
147 HashMap& operator=(const HashMap& hm) = delete;
148
149 using TableEntry = HashMapEntry<Key, Value>;
150
151 struct MapHashPolicy : HashPolicy {
152 using Base = HashPolicy;
153 using KeyType = Key;
154
155 static const Key& getKey(TableEntry& aEntry) { return aEntry.key(); }
156
157 static void setKey(TableEntry& aEntry, Key& aKey) {
158 HashPolicy::rekey(aEntry.mutableKey(), aKey);
159 }
160 };
161
162 using Impl = detail::HashTable<TableEntry, MapHashPolicy, AllocPolicy>;
163 Impl mImpl;
164
165 friend class Impl::Enum;
166
167 public:
168 using Lookup = typename HashPolicy::Lookup;
169 using Entry = TableEntry;
170
171 // -- Initialization -------------------------------------------------------
172
173 explicit HashMap(AllocPolicy aAllocPolicy = AllocPolicy(),
174 uint32_t aLen = Impl::sDefaultLen)
175 : mImpl(std::move(aAllocPolicy), aLen) {}
176
177 explicit HashMap(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
178
179 // HashMap is movable.
180 HashMap(HashMap&& aRhs) = default;
181 HashMap& operator=(HashMap&& aRhs) = default;
182
183 // -- Status and sizing ----------------------------------------------------
184
185 // The map's current generation.
186 Generation generation() const { return mImpl.generation(); }
187
188 // Is the map empty?
189 bool empty() const { return mImpl.empty(); }
190
191 // Number of keys/values in the map.
192 uint32_t count() const { return mImpl.count(); }
193
194 // Number of key/value slots in the map. Note: resize will happen well before
195 // count() == capacity().
196 uint32_t capacity() const { return mImpl.capacity(); }
197
198 // The size of the map's entry storage, in bytes. If the keys/values contain
199 // pointers to other heap blocks, you must iterate over the map and measure
200 // them separately; hence the "shallow" prefix.
201 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
202 return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
203 }
204 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
205 return aMallocSizeOf(this) +
206 mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
207 }
208
209 // Attempt to minimize the capacity(). If the table is empty, this will free
210 // the empty storage and upon regrowth it will be given the minimum capacity.
211 void compact() { mImpl.compact(); }
212
213 // Attempt to reserve enough space to fit at least |aLen| elements. This is
214 // total capacity, including elements already present. Does nothing if the
215 // map already has sufficient capacity.
216 [[nodiscard]] bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
217
218 // -- Lookups --------------------------------------------------------------
219
220 // Does the map contain a key/value matching |aLookup|?
221 bool has(const Lookup& aLookup) const {
222 return mImpl.lookup(aLookup).found();
223 }
224
225 // Return a Ptr indicating whether a key/value matching |aLookup| is
226 // present in the map. E.g.:
227 //
228 // using HM = HashMap<int,char>;
229 // HM h;
230 // if (HM::Ptr p = h.lookup(3)) {
231 // assert(p->key() == 3);
232 // char val = p->value();
233 // }
234 //
235 using Ptr = typename Impl::Ptr;
236 MOZ_ALWAYS_INLINEinline Ptr lookup(const Lookup& aLookup) const {
237 return mImpl.lookup(aLookup);
4
Calling 'HashTable::lookup'
11
Returning from 'HashTable::lookup'
238 }
239
240 // Like lookup(), but does not assert if two threads call it at the same
241 // time. Only use this method when none of the threads will modify the map.
242 MOZ_ALWAYS_INLINEinline Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
243 return mImpl.readonlyThreadsafeLookup(aLookup);
244 }
245
246 // -- Insertions -----------------------------------------------------------
247
248 // Overwrite existing value with |aValue|, or add it if not present. Returns
249 // false on OOM.
250 template <typename KeyInput, typename ValueInput>
251 [[nodiscard]] bool put(KeyInput&& aKey, ValueInput&& aValue) {
252 return put(aKey, std::forward<KeyInput>(aKey),
253 std::forward<ValueInput>(aValue));
254 }
255
256 template <typename KeyInput, typename ValueInput>
257 [[nodiscard]] bool put(const Lookup& aLookup, KeyInput&& aKey,
258 ValueInput&& aValue) {
259 AddPtr p = lookupForAdd(aLookup);
260 if (p) {
261 p->value() = std::forward<ValueInput>(aValue);
262 return true;
263 }
264 return add(p, std::forward<KeyInput>(aKey),
265 std::forward<ValueInput>(aValue));
266 }
267
268 // Like put(), but slightly faster. Must only be used when the given key is
269 // not already present. (In debug builds, assertions check this.)
270 template <typename KeyInput, typename ValueInput>
271 [[nodiscard]] bool putNew(KeyInput&& aKey, ValueInput&& aValue) {
272 return mImpl.putNew(aKey, std::forward<KeyInput>(aKey),
273 std::forward<ValueInput>(aValue));
274 }
275
276 template <typename KeyInput, typename ValueInput>
277 [[nodiscard]] bool putNew(const Lookup& aLookup, KeyInput&& aKey,
278 ValueInput&& aValue) {
279 return mImpl.putNew(aLookup, std::forward<KeyInput>(aKey),
280 std::forward<ValueInput>(aValue));
281 }
282
283 // Like putNew(), but should be only used when the table is known to be big
284 // enough for the insertion, and hashing cannot fail. Typically this is used
285 // to populate an empty map with known-unique keys after reserving space with
286 // reserve(), e.g.
287 //
288 // using HM = HashMap<int,char>;
289 // HM h;
290 // if (!h.reserve(3)) {
291 // MOZ_CRASH("OOM");
292 // }
293 // h.putNewInfallible(1, 'a'); // unique key
294 // h.putNewInfallible(2, 'b'); // unique key
295 // h.putNewInfallible(3, 'c'); // unique key
296 //
297 template <typename KeyInput, typename ValueInput>
298 void putNewInfallible(KeyInput&& aKey, ValueInput&& aValue) {
299 mImpl.putNewInfallible(aKey, std::forward<KeyInput>(aKey),
300 std::forward<ValueInput>(aValue));
301 }
302
303 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
304 // insertion of Key |k| (where |HashPolicy::match(k,l) == true|) using
305 // |add(p,k,v)|. After |add(p,k,v)|, |p| points to the new key/value. E.g.:
306 //
307 // using HM = HashMap<int,char>;
308 // HM h;
309 // HM::AddPtr p = h.lookupForAdd(3);
310 // if (!p) {
311 // if (!h.add(p, 3, 'a')) {
312 // return false;
313 // }
314 // }
315 // assert(p->key() == 3);
316 // char val = p->value();
317 //
318 // N.B. The caller must ensure that no mutating hash table operations occur
319 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
320 // key a second time, the caller may use the more efficient relookupOrAdd()
321 // method. This method reuses part of the hashing computation to more
322 // efficiently insert the key if it has not been added. For example, a
323 // mutation-handling version of the previous example:
324 //
325 // HM::AddPtr p = h.lookupForAdd(3);
326 // if (!p) {
327 // call_that_may_mutate_h();
328 // if (!h.relookupOrAdd(p, 3, 'a')) {
329 // return false;
330 // }
331 // }
332 // assert(p->key() == 3);
333 // char val = p->value();
334 //
335 using AddPtr = typename Impl::AddPtr;
336 MOZ_ALWAYS_INLINEinline AddPtr lookupForAdd(const Lookup& aLookup) {
337 return mImpl.lookupForAdd(aLookup);
338 }
339
340 // Add a key/value. Returns false on OOM.
341 template <typename KeyInput, typename ValueInput>
342 [[nodiscard]] bool add(AddPtr& aPtr, KeyInput&& aKey, ValueInput&& aValue) {
343 return mImpl.add(aPtr, std::forward<KeyInput>(aKey),
344 std::forward<ValueInput>(aValue));
345 }
346
347 // See the comment above lookupForAdd() for details.
348 template <typename KeyInput, typename ValueInput>
349 [[nodiscard]] bool relookupOrAdd(AddPtr& aPtr, KeyInput&& aKey,
350 ValueInput&& aValue) {
351 return mImpl.relookupOrAdd(aPtr, aKey, std::forward<KeyInput>(aKey),
352 std::forward<ValueInput>(aValue));
353 }
354
355 // -- Removal --------------------------------------------------------------
356
357 // Lookup and remove the key/value matching |aLookup|, if present.
358 void remove(const Lookup& aLookup) {
359 if (Ptr p = lookup(aLookup)) {
360 remove(p);
361 }
362 }
363
364 // Remove a previously found key/value (assuming aPtr.found()). The map must
365 // not have been mutated in the interim.
366 void remove(Ptr aPtr) { mImpl.remove(aPtr); }
367
368 // Remove all keys/values without changing the capacity.
369 void clear() { mImpl.clear(); }
370
371 // Like clear() followed by compact().
372 void clearAndCompact() { mImpl.clearAndCompact(); }
373
374 // -- Rekeying -------------------------------------------------------------
375
376 // Infallibly rekey one entry, if necessary. Requires that template
377 // parameters Key and HashPolicy::Lookup are the same type.
378 void rekeyIfMoved(const Key& aOldKey, const Key& aNewKey) {
379 if (aOldKey != aNewKey) {
380 rekeyAs(aOldKey, aNewKey, aNewKey);
381 }
382 }
383
384 // Infallibly rekey one entry if present, and return whether that happened.
385 bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
386 const Key& aNewKey) {
387 if (Ptr p = lookup(aOldLookup)) {
388 mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewKey);
389 return true;
390 }
391 return false;
392 }
393
394 // -- Iteration ------------------------------------------------------------
395
396 // |iter()| returns an Iterator:
397 //
398 // HashMap<int, char> h;
399 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
400 // char c = iter.get().value();
401 // }
402 //
403 using Iterator = typename Impl::Iterator;
404 Iterator iter() const { return mImpl.iter(); }
405
406 // |modIter()| returns a ModIterator:
407 //
408 // HashMap<int, char> h;
409 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
410 // if (iter.get().value() == 'l') {
411 // iter.remove();
412 // }
413 // }
414 //
415 // Table resize may occur in ModIterator's destructor.
416 using ModIterator = typename Impl::ModIterator;
417 ModIterator modIter() { return mImpl.modIter(); }
418
419 // These are similar to Iterator/ModIterator/iter(), but use different
420 // terminology.
421 using Range = typename Impl::Range;
422 using Enum = typename Impl::Enum;
423 Range all() const { return mImpl.all(); }
424};
425
426//---------------------------------------------------------------------------
427// HashSet
428//---------------------------------------------------------------------------
429
430// HashSet is a fast hash-based set of values.
431//
432// Template parameter requirements:
433// - T: movable, destructible, assignable.
434// - HashPolicy: see the "Hash Policy" section below.
435// - AllocPolicy: see AllocPolicy.h
436//
437// Note:
438// - HashSet is not reentrant: T/HashPolicy/AllocPolicy members called by
439// HashSet must not call back into the same HashSet object.
440//
441template <class T, class HashPolicy = DefaultHasher<T>,
442 class AllocPolicy = MallocAllocPolicy>
443class HashSet {
444 // -- Implementation details -----------------------------------------------
445
446 // HashSet is not copyable or assignable.
447 HashSet(const HashSet& hs) = delete;
448 HashSet& operator=(const HashSet& hs) = delete;
449
450 struct SetHashPolicy : HashPolicy {
451 using Base = HashPolicy;
452 using KeyType = T;
453
454 static const KeyType& getKey(const T& aT) { return aT; }
455
456 static void setKey(T& aT, KeyType& aKey) { HashPolicy::rekey(aT, aKey); }
457 };
458
459 using Impl = detail::HashTable<const T, SetHashPolicy, AllocPolicy>;
460 Impl mImpl;
461
462 friend class Impl::Enum;
463
464 public:
465 using Lookup = typename HashPolicy::Lookup;
466 using Entry = T;
467
468 // -- Initialization -------------------------------------------------------
469
470 explicit HashSet(AllocPolicy aAllocPolicy = AllocPolicy(),
471 uint32_t aLen = Impl::sDefaultLen)
472 : mImpl(std::move(aAllocPolicy), aLen) {}
473
474 explicit HashSet(uint32_t aLen) : mImpl(AllocPolicy(), aLen) {}
475
476 // HashSet is movable.
477 HashSet(HashSet&& aRhs) = default;
478 HashSet& operator=(HashSet&& aRhs) = default;
479
480 // -- Status and sizing ----------------------------------------------------
481
482 // The set's current generation.
483 Generation generation() const { return mImpl.generation(); }
484
485 // Is the set empty?
486 bool empty() const { return mImpl.empty(); }
487
488 // Number of elements in the set.
489 uint32_t count() const { return mImpl.count(); }
490
491 // Number of element slots in the set. Note: resize will happen well before
492 // count() == capacity().
493 uint32_t capacity() const { return mImpl.capacity(); }
494
495 // The size of the set's entry storage, in bytes. If the elements contain
496 // pointers to other heap blocks, you must iterate over the set and measure
497 // them separately; hence the "shallow" prefix.
498 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
499 return mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
500 }
501 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
502 return aMallocSizeOf(this) +
503 mImpl.shallowSizeOfExcludingThis(aMallocSizeOf);
504 }
505
506 // Attempt to minimize the capacity(). If the table is empty, this will free
507 // the empty storage and upon regrowth it will be given the minimum capacity.
508 void compact() { mImpl.compact(); }
509
510 // Attempt to reserve enough space to fit at least |aLen| elements. This is
511 // total capacity, including elements already present. Does nothing if the
512 // map already has sufficient capacity.
513 [[nodiscard]] bool reserve(uint32_t aLen) { return mImpl.reserve(aLen); }
514
515 // -- Lookups --------------------------------------------------------------
516
517 // Does the set contain an element matching |aLookup|?
518 bool has(const Lookup& aLookup) const {
519 return mImpl.lookup(aLookup).found();
520 }
521
522 // Return a Ptr indicating whether an element matching |aLookup| is present
523 // in the set. E.g.:
524 //
525 // using HS = HashSet<int>;
526 // HS h;
527 // if (HS::Ptr p = h.lookup(3)) {
528 // assert(*p == 3); // p acts like a pointer to int
529 // }
530 //
531 using Ptr = typename Impl::Ptr;
532 MOZ_ALWAYS_INLINEinline Ptr lookup(const Lookup& aLookup) const {
533 return mImpl.lookup(aLookup);
534 }
535
536 // Like lookup(), but does not assert if two threads call it at the same
537 // time. Only use this method when none of the threads will modify the set.
538 MOZ_ALWAYS_INLINEinline Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
539 return mImpl.readonlyThreadsafeLookup(aLookup);
540 }
541
542 // -- Insertions -----------------------------------------------------------
543
544 // Add |aU| if it is not present already. Returns false on OOM.
545 template <typename U>
546 [[nodiscard]] bool put(U&& aU) {
547 AddPtr p = lookupForAdd(aU);
548 return p ? true : add(p, std::forward<U>(aU));
549 }
550
551 // Like put(), but slightly faster. Must only be used when the given element
552 // is not already present. (In debug builds, assertions check this.)
553 template <typename U>
554 [[nodiscard]] bool putNew(U&& aU) {
555 return mImpl.putNew(aU, std::forward<U>(aU));
556 }
557
558 // Like the other putNew(), but for when |Lookup| is different to |T|.
559 template <typename U>
560 [[nodiscard]] bool putNew(const Lookup& aLookup, U&& aU) {
561 return mImpl.putNew(aLookup, std::forward<U>(aU));
562 }
563
564 // Like putNew(), but should be only used when the table is known to be big
565 // enough for the insertion, and hashing cannot fail. Typically this is used
566 // to populate an empty set with known-unique elements after reserving space
567 // with reserve(), e.g.
568 //
569 // using HS = HashMap<int>;
570 // HS h;
571 // if (!h.reserve(3)) {
572 // MOZ_CRASH("OOM");
573 // }
574 // h.putNewInfallible(1); // unique element
575 // h.putNewInfallible(2); // unique element
576 // h.putNewInfallible(3); // unique element
577 //
578 template <typename U>
579 void putNewInfallible(const Lookup& aLookup, U&& aU) {
580 mImpl.putNewInfallible(aLookup, std::forward<U>(aU));
581 }
582
583 // Like |lookup(l)|, but on miss, |p = lookupForAdd(l)| allows efficient
584 // insertion of T value |t| (where |HashPolicy::match(t,l) == true|) using
585 // |add(p,t)|. After |add(p,t)|, |p| points to the new element. E.g.:
586 //
587 // using HS = HashSet<int>;
588 // HS h;
589 // HS::AddPtr p = h.lookupForAdd(3);
590 // if (!p) {
591 // if (!h.add(p, 3)) {
592 // return false;
593 // }
594 // }
595 // assert(*p == 3); // p acts like a pointer to int
596 //
597 // N.B. The caller must ensure that no mutating hash table operations occur
598 // between a pair of lookupForAdd() and add() calls. To avoid looking up the
599 // key a second time, the caller may use the more efficient relookupOrAdd()
600 // method. This method reuses part of the hashing computation to more
601 // efficiently insert the key if it has not been added. For example, a
602 // mutation-handling version of the previous example:
603 //
604 // HS::AddPtr p = h.lookupForAdd(3);
605 // if (!p) {
606 // call_that_may_mutate_h();
607 // if (!h.relookupOrAdd(p, 3, 3)) {
608 // return false;
609 // }
610 // }
611 // assert(*p == 3);
612 //
613 // Note that relookupOrAdd(p,l,t) performs Lookup using |l| and adds the
614 // entry |t|, where the caller ensures match(l,t).
615 using AddPtr = typename Impl::AddPtr;
616 MOZ_ALWAYS_INLINEinline AddPtr lookupForAdd(const Lookup& aLookup) {
617 return mImpl.lookupForAdd(aLookup);
618 }
619
620 // Add an element. Returns false on OOM.
621 template <typename U>
622 [[nodiscard]] bool add(AddPtr& aPtr, U&& aU) {
623 return mImpl.add(aPtr, std::forward<U>(aU));
624 }
625
626 // See the comment above lookupForAdd() for details.
627 template <typename U>
628 [[nodiscard]] bool relookupOrAdd(AddPtr& aPtr, const Lookup& aLookup,
629 U&& aU) {
630 return mImpl.relookupOrAdd(aPtr, aLookup, std::forward<U>(aU));
631 }
632
633 // -- Removal --------------------------------------------------------------
634
635 // Lookup and remove the element matching |aLookup|, if present.
636 void remove(const Lookup& aLookup) {
637 if (Ptr p = lookup(aLookup)) {
638 remove(p);
639 }
640 }
641
642 // Remove a previously found element (assuming aPtr.found()). The set must
643 // not have been mutated in the interim.
644 void remove(Ptr aPtr) { mImpl.remove(aPtr); }
645
646 // Remove all keys/values without changing the capacity.
647 void clear() { mImpl.clear(); }
648
649 // Like clear() followed by compact().
650 void clearAndCompact() { mImpl.clearAndCompact(); }
651
652 // -- Rekeying -------------------------------------------------------------
653
654 // Infallibly rekey one entry, if present. Requires that template parameters
655 // T and HashPolicy::Lookup are the same type.
656 void rekeyIfMoved(const Lookup& aOldValue, const T& aNewValue) {
657 if (aOldValue != aNewValue) {
658 rekeyAs(aOldValue, aNewValue, aNewValue);
659 }
660 }
661
662 // Infallibly rekey one entry if present, and return whether that happened.
663 bool rekeyAs(const Lookup& aOldLookup, const Lookup& aNewLookup,
664 const T& aNewValue) {
665 if (Ptr p = lookup(aOldLookup)) {
666 mImpl.rekeyAndMaybeRehash(p, aNewLookup, aNewValue);
667 return true;
668 }
669 return false;
670 }
671
672 // Infallibly replace the current key at |aPtr| with an equivalent key.
673 // Specifically, both HashPolicy::hash and HashPolicy::match must return
674 // identical results for the new and old key when applied against all
675 // possible matching values.
676 void replaceKey(Ptr aPtr, const Lookup& aLookup, const T& aNewValue) {
677 MOZ_ASSERT(aPtr.found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.found()))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("aPtr.found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 677); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.found()"
")"); do { *((volatile int*)__null) = 677; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
678 MOZ_ASSERT(*aPtr != aNewValue)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(*aPtr != aNewValue)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(*aPtr != aNewValue))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("*aPtr != aNewValue"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 678); AnnotateMozCrashReason("MOZ_ASSERT" "(" "*aPtr != aNewValue"
")"); do { *((volatile int*)__null) = 678; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
679 MOZ_ASSERT(HashPolicy::match(*aPtr, aLookup))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(HashPolicy::match(*aPtr, aLookup))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(HashPolicy::match(*aPtr, aLookup
)))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("HashPolicy::match(*aPtr, aLookup)", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 679); AnnotateMozCrashReason("MOZ_ASSERT" "(" "HashPolicy::match(*aPtr, aLookup)"
")"); do { *((volatile int*)__null) = 679; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
680 MOZ_ASSERT(HashPolicy::match(aNewValue, aLookup))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(HashPolicy::match(aNewValue, aLookup))>::isValid,
"invalid assertion condition"); if ((__builtin_expect(!!(!(!
!(HashPolicy::match(aNewValue, aLookup)))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("HashPolicy::match(aNewValue, aLookup)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 680); AnnotateMozCrashReason("MOZ_ASSERT" "(" "HashPolicy::match(aNewValue, aLookup)"
")"); do { *((volatile int*)__null) = 680; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
681 const_cast<T&>(*aPtr) = aNewValue;
682 MOZ_ASSERT(*lookup(aLookup) == aNewValue)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(*lookup(aLookup) == aNewValue)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(*lookup(aLookup) == aNewValue
))), 0))) { do { } while (false); MOZ_ReportAssertionFailure(
"*lookup(aLookup) == aNewValue", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 682); AnnotateMozCrashReason("MOZ_ASSERT" "(" "*lookup(aLookup) == aNewValue"
")"); do { *((volatile int*)__null) = 682; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
683 }
684 void replaceKey(Ptr aPtr, const T& aNewValue) {
685 replaceKey(aPtr, aNewValue, aNewValue);
686 }
687
688 // -- Iteration ------------------------------------------------------------
689
690 // |iter()| returns an Iterator:
691 //
692 // HashSet<int> h;
693 // for (auto iter = h.iter(); !iter.done(); iter.next()) {
694 // int i = iter.get();
695 // }
696 //
697 using Iterator = typename Impl::Iterator;
698 Iterator iter() const { return mImpl.iter(); }
699
700 // |modIter()| returns a ModIterator:
701 //
702 // HashSet<int> h;
703 // for (auto iter = h.modIter(); !iter.done(); iter.next()) {
704 // if (iter.get() == 42) {
705 // iter.remove();
706 // }
707 // }
708 //
709 // Table resize may occur in ModIterator's destructor.
710 using ModIterator = typename Impl::ModIterator;
711 ModIterator modIter() { return mImpl.modIter(); }
712
713 // These are similar to Iterator/ModIterator/iter(), but use different
714 // terminology.
715 using Range = typename Impl::Range;
716 using Enum = typename Impl::Enum;
717 Range all() const { return mImpl.all(); }
718};
719
720//---------------------------------------------------------------------------
721// Hash Policy
722//---------------------------------------------------------------------------
723
724// A hash policy |HP| for a hash table with key-type |Key| must provide:
725//
726// - a type |HP::Lookup| to use to lookup table entries;
727//
728// - a static member function |HP::hash| that hashes lookup values:
729//
730// static mozilla::HashNumber hash(const Lookup&);
731//
732// - a static member function |HP::match| that tests equality of key and
733// lookup values:
734//
735// static bool match(const Key& aKey, const Lookup& aLookup);
736//
737// |aKey| and |aLookup| can have different hash numbers, only when a
738// collision happens with |prepareHash| operation, which is less frequent.
739// Thus, |HP::match| shouldn't assume the hash equality in the comparison,
740// even if the hash numbers are almost always same between them.
741//
742// Normally, Lookup = Key. In general, though, different values and types of
743// values can be used to lookup and store. If a Lookup value |l| is not equal
744// to the added Key value |k|, the user must ensure that |HP::match(k,l)| is
745// true. E.g.:
746//
747// mozilla::HashSet<Key, HP>::AddPtr p = h.lookup(l);
748// if (!p) {
749// assert(HP::match(k, l)); // must hold
750// h.add(p, k);
751// }
752
753// A pointer hashing policy that uses HashGeneric() to create good hashes for
754// pointers. Note that we don't shift out the lowest k bits because we don't
755// want to assume anything about the alignment of the pointers.
756template <typename Key>
757struct PointerHasher {
758 using Lookup = Key;
759
760 static HashNumber hash(const Lookup& aLookup) { return HashGeneric(aLookup); }
761
762 static bool match(const Key& aKey, const Lookup& aLookup) {
763 return aKey == aLookup;
764 }
765
766 static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
767};
768
769// The default hash policy, which only works with integers.
770template <class Key, typename>
771struct DefaultHasher {
772 using Lookup = Key;
773
774 static HashNumber hash(const Lookup& aLookup) {
775 // Just convert the integer to a HashNumber and use that as is. (This
776 // discards the high 32-bits of 64-bit integers!) ScrambleHashCode() is
777 // subsequently called on the value to improve the distribution.
778 return aLookup;
779 }
780
781 static bool match(const Key& aKey, const Lookup& aLookup) {
782 // Use builtin or overloaded operator==.
783 return aKey == aLookup;
784 }
785
786 static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
787};
788
789// A DefaultHasher specialization for enums.
790template <class T>
791struct DefaultHasher<T, std::enable_if_t<std::is_enum_v<T>>> {
792 using Key = T;
793 using Lookup = Key;
794
795 static HashNumber hash(const Lookup& aLookup) { return HashGeneric(aLookup); }
796
797 static bool match(const Key& aKey, const Lookup& aLookup) {
798 // Use builtin or overloaded operator==.
799 return aKey == static_cast<Key>(aLookup);
800 }
801
802 static void rekey(Key& aKey, const Key& aNewKey) { aKey = aNewKey; }
803};
804
805// A DefaultHasher specialization for pointers.
806template <class T>
807struct DefaultHasher<T*> : PointerHasher<T*> {};
808
809// A DefaultHasher specialization for mozilla::UniquePtr.
810template <class T, class D>
811struct DefaultHasher<UniquePtr<T, D>> {
812 using Key = UniquePtr<T, D>;
813 using Lookup = Key;
814 using PtrHasher = PointerHasher<T*>;
815
816 static HashNumber hash(const Lookup& aLookup) {
817 return PtrHasher::hash(aLookup.get());
818 }
819
820 static bool match(const Key& aKey, const Lookup& aLookup) {
821 return PtrHasher::match(aKey.get(), aLookup.get());
822 }
823
824 static void rekey(UniquePtr<T, D>& aKey, UniquePtr<T, D>&& aNewKey) {
825 aKey = std::move(aNewKey);
826 }
827};
828
829// A DefaultHasher specialization for doubles.
830template <>
831struct DefaultHasher<double> {
832 using Key = double;
833 using Lookup = Key;
834
835 static HashNumber hash(const Lookup& aLookup) {
836 // Just xor the high bits with the low bits, and then treat the bits of the
837 // result as a uint32_t.
838 static_assert(sizeof(HashNumber) == 4,
839 "subsequent code assumes a four-byte hash");
840 uint64_t u = BitwiseCast<uint64_t>(aLookup);
841 return HashNumber(u ^ (u >> 32));
842 }
843
844 static bool match(const Key& aKey, const Lookup& aLookup) {
845 return BitwiseCast<uint64_t>(aKey) == BitwiseCast<uint64_t>(aLookup);
846 }
847};
848
849// A DefaultHasher specialization for floats.
850template <>
851struct DefaultHasher<float> {
852 using Key = float;
853 using Lookup = Key;
854
855 static HashNumber hash(const Lookup& aLookup) {
856 // Just use the value as if its bits form an integer. ScrambleHashCode() is
857 // subsequently called on the value to improve the distribution.
858 static_assert(sizeof(HashNumber) == 4,
859 "subsequent code assumes a four-byte hash");
860 return HashNumber(BitwiseCast<uint32_t>(aLookup));
861 }
862
863 static bool match(const Key& aKey, const Lookup& aLookup) {
864 return BitwiseCast<uint32_t>(aKey) == BitwiseCast<uint32_t>(aLookup);
865 }
866};
867
868// A hash policy for C strings.
869struct CStringHasher {
870 using Key = const char*;
871 using Lookup = const char*;
872
873 static HashNumber hash(const Lookup& aLookup) { return HashString(aLookup); }
874
875 static bool match(const Key& aKey, const Lookup& aLookup) {
876 return strcmp(aKey, aLookup) == 0;
877 }
878};
879
880//---------------------------------------------------------------------------
881// Fallible Hashing Interface
882//---------------------------------------------------------------------------
883
884// Most of the time generating a hash code is infallible, but sometimes it is
885// necessary to generate hash codes on demand in a way that can fail. Specialize
886// this class for your own hash policy to provide fallible hashing.
887//
888// This is used by MovableCellHasher to handle the fact that generating a unique
889// ID for cell pointer may fail due to OOM.
890//
891// The default implementations of these methods delegate to the usual HashPolicy
892// implementation and always succeed.
893template <typename HashPolicy>
894struct FallibleHashMethods {
895 // Return true if a hashcode is already available for its argument, and
896 // sets |aHashOut|. Once this succeeds for a specific argument it
897 // must continue to do so.
898 //
899 // Return false if a hashcode is not already available. This implies that any
900 // lookup must fail, as the hash code would have to have been successfully
901 // created on insertion.
902 template <typename Lookup>
903 static bool maybeGetHash(Lookup&& aLookup, HashNumber* aHashOut) {
904 *aHashOut = HashPolicy::hash(aLookup);
905 return true;
906 }
907
908 // Fallible method to ensure a hashcode exists for its argument and create one
909 // if not. Sets |aHashOut| to the hashcode and retuns true on success. Returns
910 // false on error, e.g. out of memory.
911 template <typename Lookup>
912 static bool ensureHash(Lookup&& aLookup, HashNumber* aHashOut) {
913 *aHashOut = HashPolicy::hash(aLookup);
914 return true;
915 }
916};
917
918template <typename HashPolicy, typename Lookup>
919static bool MaybeGetHash(Lookup&& aLookup, HashNumber* aHashOut) {
920 return FallibleHashMethods<typename HashPolicy::Base>::maybeGetHash(
921 std::forward<Lookup>(aLookup), aHashOut);
922}
923
924template <typename HashPolicy, typename Lookup>
925static bool EnsureHash(Lookup&& aLookup, HashNumber* aHashOut) {
926 return FallibleHashMethods<typename HashPolicy::Base>::ensureHash(
927 std::forward<Lookup>(aLookup), aHashOut);
928}
929
930//---------------------------------------------------------------------------
931// Implementation Details (HashMapEntry, HashTableEntry, HashTable)
932//---------------------------------------------------------------------------
933
934// Both HashMap and HashSet are implemented by a single HashTable that is even
935// more heavily parameterized than the other two. This leaves HashTable gnarly
936// and extremely coupled to HashMap and HashSet; thus code should not use
937// HashTable directly.
938
939template <class Key, class Value>
940class HashMapEntry {
941 Key key_;
942 Value value_;
943
944 template <class, class, class>
945 friend class detail::HashTable;
946 template <class>
947 friend class detail::HashTableEntry;
948 template <class, class, class, class>
949 friend class HashMap;
950
951 public:
952 template <typename KeyInput, typename ValueInput>
953 HashMapEntry(KeyInput&& aKey, ValueInput&& aValue)
954 : key_(std::forward<KeyInput>(aKey)),
955 value_(std::forward<ValueInput>(aValue)) {}
956
957 HashMapEntry(HashMapEntry&& aRhs) = default;
958 HashMapEntry& operator=(HashMapEntry&& aRhs) = default;
959
960 using KeyType = Key;
961 using ValueType = Value;
962
963 const Key& key() const { return key_; }
964
965 // Use this method with caution! If the key is changed such that its hash
966 // value also changes, the map will be left in an invalid state.
967 Key& mutableKey() { return key_; }
968
969 const Value& value() const { return value_; }
970 Value& value() { return value_; }
971
972 private:
973 HashMapEntry(const HashMapEntry&) = delete;
974 void operator=(const HashMapEntry&) = delete;
975};
976
977namespace detail {
978
979template <class T, class HashPolicy, class AllocPolicy>
980class HashTable;
981
982template <typename T>
983class EntrySlot;
984
985template <typename T>
986class HashTableEntry {
987 private:
988 using NonConstT = std::remove_const_t<T>;
989
990 // Instead of having a hash table entry store that looks like this:
991 //
992 // +--------+--------+--------+--------+
993 // | entry0 | entry1 | .... | entryN |
994 // +--------+--------+--------+--------+
995 //
996 // where the entries contained their cached hash code, we're going to lay out
997 // the entry store thusly:
998 //
999 // +-------+-------+-------+-------+--------+--------+--------+--------+
1000 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
1001 // +-------+-------+-------+-------+--------+--------+--------+--------+
1002 //
1003 // with all the cached hashes prior to the actual entries themselves.
1004 //
1005 // We do this because implementing the first strategy requires us to make
1006 // HashTableEntry look roughly like:
1007 //
1008 // template <typename T>
1009 // class HashTableEntry {
1010 // HashNumber mKeyHash;
1011 // T mValue;
1012 // };
1013 //
1014 // The problem with this setup is that, depending on the layout of `T`, there
1015 // may be platform ABI-mandated padding between `mKeyHash` and the first
1016 // member of `T`. This ABI-mandated padding is wasted space, and can be
1017 // surprisingly common, e.g. when `T` is a single pointer on 64-bit platforms.
1018 // In such cases, we're throwing away a quarter of our entry store on padding,
1019 // which is undesirable.
1020 //
1021 // The second layout above, namely:
1022 //
1023 // +-------+-------+-------+-------+--------+--------+--------+--------+
1024 // | hash0 | hash1 | ... | hashN | entry0 | entry1 | .... | entryN |
1025 // +-------+-------+-------+-------+--------+--------+--------+--------+
1026 //
1027 // means there is no wasted space between the hashes themselves, and no wasted
1028 // space between the entries themselves. However, we would also like there to
1029 // be no gap between the last hash and the first entry. The memory allocator
1030 // guarantees the alignment of the start of the hashes. The use of a
1031 // power-of-two capacity of at least 4 guarantees that the alignment of the
1032 // *end* of the hash array is no less than the alignment of the start.
1033 // Finally, the static_asserts here guarantee that the entries themselves
1034 // don't need to be any more aligned than the alignment of the entry store
1035 // itself.
1036 //
1037 // This assertion is safe for 32-bit builds because on both Windows and Linux
1038 // (including Android), the minimum alignment for allocations larger than 8
1039 // bytes is 8 bytes, and the actual data for entries in our entry store is
1040 // guaranteed to have that alignment as well, thanks to the power-of-two
1041 // number of cached hash values stored prior to the entry data.
1042
1043 // The allocation policy must allocate a table with at least this much
1044 // alignment.
1045 static constexpr size_t kMinimumAlignment = 8;
1046
1047 static_assert(alignof(HashNumber) <= kMinimumAlignment,
1048 "[N*2 hashes, N*2 T values] allocation's alignment must be "
1049 "enough to align each hash");
1050 static_assert(alignof(NonConstT) <= 2 * sizeof(HashNumber),
1051 "subsequent N*2 T values must not require more than an even "
1052 "number of HashNumbers provides");
1053
1054 static const HashNumber sFreeKey = 0;
1055 static const HashNumber sRemovedKey = 1;
1056 static const HashNumber sCollisionBit = 1;
1057
1058 alignas(NonConstT) unsigned char mValueData[sizeof(NonConstT)];
1059
1060 private:
1061 template <class, class, class>
1062 friend class HashTable;
1063 template <typename>
1064 friend class EntrySlot;
1065
1066 // Some versions of GCC treat it as a -Wstrict-aliasing violation (ergo a
1067 // -Werror compile error) to reinterpret_cast<> |mValueData| to |T*|, even
1068 // through |void*|. Placing the latter cast in these separate functions
1069 // breaks the chain such that affected GCC versions no longer warn/error.
1070 void* rawValuePtr() { return mValueData; }
1071
1072 static bool isLiveHash(HashNumber hash) { return hash > sRemovedKey; }
1073
1074 HashTableEntry(const HashTableEntry&) = delete;
1075 void operator=(const HashTableEntry&) = delete;
1076
1077 NonConstT* valuePtr() { return reinterpret_cast<NonConstT*>(rawValuePtr()); }
1078
1079 void destroyStoredT() {
1080 NonConstT* ptr = valuePtr();
1081 ptr->~T();
1082 MOZ_MAKE_MEM_UNDEFINED(ptr, sizeof(*ptr))do { } while (0);
1083 }
1084
1085 public:
1086 HashTableEntry() = default;
1087
1088 ~HashTableEntry() { MOZ_MAKE_MEM_UNDEFINED(this, sizeof(*this))do { } while (0); }
1089
1090 void destroy() { destroyStoredT(); }
1091
1092 void swap(HashTableEntry* aOther, bool aIsLive) {
1093 // This allows types to use Argument-Dependent-Lookup, and thus use a custom
1094 // std::swap, which is needed by types like JS::Heap and such.
1095 using std::swap;
1096
1097 if (this == aOther) {
1098 return;
1099 }
1100 if (aIsLive) {
1101 swap(*valuePtr(), *aOther->valuePtr());
1102 } else {
1103 *aOther->valuePtr() = std::move(*valuePtr());
1104 destroy();
1105 }
1106 }
1107
1108 T& get() { return *valuePtr(); }
1109
1110 NonConstT& getMutable() { return *valuePtr(); }
1111};
1112
1113// A slot represents a cached hash value and its associated entry stored
1114// in the hash table. These two things are not stored in contiguous memory.
1115template <class T>
1116class EntrySlot {
1117 using NonConstT = std::remove_const_t<T>;
1118
1119 using Entry = HashTableEntry<T>;
1120
1121 Entry* mEntry;
1122 HashNumber* mKeyHash;
1123
1124 template <class, class, class>
1125 friend class HashTable;
1126
1127 EntrySlot(Entry* aEntry, HashNumber* aKeyHash)
1128 : mEntry(aEntry), mKeyHash(aKeyHash) {}
1129
1130 public:
1131 static bool isLiveHash(HashNumber hash) { return hash > Entry::sRemovedKey; }
1132
1133 EntrySlot(const EntrySlot&) = default;
1134 EntrySlot(EntrySlot&& aOther) = default;
1135
1136 EntrySlot& operator=(const EntrySlot&) = default;
1137 EntrySlot& operator=(EntrySlot&&) = default;
1138
1139 bool operator==(const EntrySlot& aRhs) const { return mEntry == aRhs.mEntry; }
1140
1141 bool operator<(const EntrySlot& aRhs) const { return mEntry < aRhs.mEntry; }
1142
1143 EntrySlot& operator++() {
1144 ++mEntry;
1145 ++mKeyHash;
1146 return *this;
1147 }
1148
1149 void destroy() { mEntry->destroy(); }
1150
1151 void swap(EntrySlot& aOther) {
1152 mEntry->swap(aOther.mEntry, aOther.isLive());
1153 std::swap(*mKeyHash, *aOther.mKeyHash);
1154 }
1155
1156 T& get() const { return mEntry->get(); }
1157
1158 NonConstT& getMutable() { return mEntry->getMutable(); }
1159
1160 bool isFree() const { return *mKeyHash == Entry::sFreeKey; }
1161
1162 void clearLive() {
1163 MOZ_ASSERT(isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1163); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLive()" ")"
); do { *((volatile int*)__null) = 1163; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1164 *mKeyHash = Entry::sFreeKey;
1165 mEntry->destroyStoredT();
1166 }
1167
1168 void clear() {
1169 if (isLive()) {
1170 mEntry->destroyStoredT();
1171 }
1172 MOZ_MAKE_MEM_UNDEFINED(mEntry, sizeof(*mEntry))do { } while (0);
1173 *mKeyHash = Entry::sFreeKey;
1174 }
1175
1176 bool isRemoved() const { return *mKeyHash == Entry::sRemovedKey; }
1177
1178 void removeLive() {
1179 MOZ_ASSERT(isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1179); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLive()" ")"
); do { *((volatile int*)__null) = 1179; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1180 *mKeyHash = Entry::sRemovedKey;
1181 mEntry->destroyStoredT();
1182 }
1183
1184 bool isLive() const { return isLiveHash(*mKeyHash); }
1185
1186 void setCollision() {
1187 MOZ_ASSERT(isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1187); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLive()" ")"
); do { *((volatile int*)__null) = 1187; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1188 *mKeyHash |= Entry::sCollisionBit;
1189 }
1190 void unsetCollision() { *mKeyHash &= ~Entry::sCollisionBit; }
1191 bool hasCollision() const { return *mKeyHash & Entry::sCollisionBit; }
1192 bool matchHash(HashNumber hn) {
1193 return (*mKeyHash & ~Entry::sCollisionBit) == hn;
1194 }
1195 HashNumber getKeyHash() const { return *mKeyHash & ~Entry::sCollisionBit; }
1196
1197 template <typename... Args>
1198 void setLive(HashNumber aHashNumber, Args&&... aArgs) {
1199 MOZ_ASSERT(!isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("!isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1199); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!isLive()" ")"
); do { *((volatile int*)__null) = 1199; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1200 *mKeyHash = aHashNumber;
1201 new (KnownNotNull, mEntry->valuePtr()) T(std::forward<Args>(aArgs)...);
1202 MOZ_ASSERT(isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1202); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLive()" ")"
); do { *((volatile int*)__null) = 1202; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1203 }
1204
1205 Entry* toEntry() const { return mEntry; }
1206};
1207
1208template <class T, class HashPolicy, class AllocPolicy>
1209class HashTable : private AllocPolicy {
1210 friend class mozilla::ReentrancyGuard;
1211
1212 using NonConstT = std::remove_const_t<T>;
1213 using Key = typename HashPolicy::KeyType;
1214 using Lookup = typename HashPolicy::Lookup;
1215
1216 public:
1217 using Entry = HashTableEntry<T>;
1218 using Slot = EntrySlot<T>;
1219
1220 template <typename F>
1221 static void forEachSlot(char* aTable, uint32_t aCapacity, F&& f) {
1222 auto hashes = reinterpret_cast<HashNumber*>(aTable);
1223 auto entries = reinterpret_cast<Entry*>(&hashes[aCapacity]);
1224 Slot slot(entries, hashes);
1225 for (size_t i = 0; i < size_t(aCapacity); ++i) {
1226 f(slot);
1227 ++slot;
1228 }
1229 }
1230
1231 // A nullable pointer to a hash table element. A Ptr |p| can be tested
1232 // either explicitly |if (p.found()) p->...| or using boolean conversion
1233 // |if (p) p->...|. Ptr objects must not be used after any mutating hash
1234 // table operations unless |generation()| is tested.
1235 class Ptr {
1236 friend class HashTable;
1237
1238 Slot mSlot;
1239#ifdef DEBUG1
1240 const HashTable* mTable;
1241 Generation mGeneration;
1242#endif
1243
1244 protected:
1245 Ptr(Slot aSlot, const HashTable& aTable)
1246 : mSlot(aSlot)
1247#ifdef DEBUG1
1248 ,
1249 mTable(&aTable),
1250 mGeneration(aTable.generation())
1251#endif
1252 {
1253 }
1254
1255 // This constructor is used only by AddPtr() within lookupForAdd().
1256 explicit Ptr(const HashTable& aTable)
1257 : mSlot(nullptr, nullptr)
1258#ifdef DEBUG1
1259 ,
1260 mTable(&aTable),
1261 mGeneration(aTable.generation())
1262#endif
1263 {
1264 }
1265
1266 bool isValid() const { return !!mSlot.toEntry(); }
1267
1268 public:
1269 Ptr()
1270 : mSlot(nullptr, nullptr)
1271#ifdef DEBUG1
1272 ,
1273 mTable(nullptr),
8
Null pointer value stored to 'ptr.mTable'
1274 mGeneration(0)
1275#endif
1276 {
1277 }
1278
1279 bool found() const {
1280 if (!isValid()) {
1281 return false;
1282 }
1283#ifdef DEBUG1
1284 MOZ_ASSERT(mGeneration == mTable->generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable->generation())>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mGeneration == mTable->generation()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mGeneration == mTable->generation()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1284); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable->generation()"
")"); do { *((volatile int*)__null) = 1284; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1285#endif
1286 return mSlot.isLive();
1287 }
1288
1289 explicit operator bool() const { return found(); }
1290
1291 bool operator==(const Ptr& aRhs) const {
1292 MOZ_ASSERT(found() && aRhs.found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(found() && aRhs.found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(found() && aRhs.found
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("found() && aRhs.found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1292); AnnotateMozCrashReason("MOZ_ASSERT" "(" "found() && aRhs.found()"
")"); do { *((volatile int*)__null) = 1292; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1293 return mSlot == aRhs.mSlot;
1294 }
1295
1296 bool operator!=(const Ptr& aRhs) const {
1297#ifdef DEBUG1
1298 MOZ_ASSERT(mGeneration == mTable->generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable->generation())>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mGeneration == mTable->generation()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mGeneration == mTable->generation()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1298); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable->generation()"
")"); do { *((volatile int*)__null) = 1298; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1299#endif
1300 return !(*this == aRhs);
1301 }
1302
1303 T& operator*() const {
1304#ifdef DEBUG1
1305 MOZ_ASSERT(found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(found()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1305); AnnotateMozCrashReason("MOZ_ASSERT" "(" "found()" ")"
); do { *((volatile int*)__null) = 1305; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1306 MOZ_ASSERT(mGeneration == mTable->generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable->generation())>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mGeneration == mTable->generation()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mGeneration == mTable->generation()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1306); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable->generation()"
")"); do { *((volatile int*)__null) = 1306; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1307#endif
1308 return mSlot.get();
1309 }
1310
1311 T* operator->() const {
1312#ifdef DEBUG1
1313 MOZ_ASSERT(found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(found()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1313); AnnotateMozCrashReason("MOZ_ASSERT" "(" "found()" ")"
); do { *((volatile int*)__null) = 1313; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
16
Assuming the condition is false
17
Taking false branch
18
Loop condition is false. Exiting loop
1314 MOZ_ASSERT(mGeneration == mTable->generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable->generation())>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mGeneration == mTable->generation()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mGeneration == mTable->generation()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1314); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable->generation()"
")"); do { *((volatile int*)__null) = 1314; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
19
Called C++ object pointer is null
1315#endif
1316 return &mSlot.get();
1317 }
1318 };
1319
1320 // A Ptr that can be used to add a key after a failed lookup.
1321 class AddPtr : public Ptr {
1322 friend class HashTable;
1323
1324 HashNumber mKeyHash;
1325#ifdef DEBUG1
1326 uint64_t mMutationCount;
1327#endif
1328
1329 AddPtr(Slot aSlot, const HashTable& aTable, HashNumber aHashNumber)
1330 : Ptr(aSlot, aTable),
1331 mKeyHash(aHashNumber)
1332#ifdef DEBUG1
1333 ,
1334 mMutationCount(aTable.mMutationCount)
1335#endif
1336 {
1337 }
1338
1339 // This constructor is used when lookupForAdd() is performed on a table
1340 // lacking entry storage; it leaves mSlot null but initializes everything
1341 // else.
1342 AddPtr(const HashTable& aTable, HashNumber aHashNumber)
1343 : Ptr(aTable),
1344 mKeyHash(aHashNumber)
1345#ifdef DEBUG1
1346 ,
1347 mMutationCount(aTable.mMutationCount)
1348#endif
1349 {
1350 MOZ_ASSERT(isLive())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLive())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLive()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("isLive()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1350); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLive()" ")"
); do { *((volatile int*)__null) = 1350; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1351 }
1352
1353 bool isLive() const { return isLiveHash(mKeyHash); }
1354
1355 public:
1356 AddPtr() : mKeyHash(0) {}
1357 };
1358
1359 // A hash table iterator that (mostly) doesn't allow table modifications.
1360 // As with Ptr/AddPtr, Iterator objects must not be used after any mutating
1361 // hash table operation unless the |generation()| is tested.
1362 class Iterator {
1363 void moveToNextLiveEntry() {
1364 while (++mCur < mEnd && !mCur.isLive()) {
1365 continue;
1366 }
1367 }
1368
1369 protected:
1370 friend class HashTable;
1371
1372 explicit Iterator(const HashTable& aTable)
1373 : mCur(aTable.slotForIndex(0)),
1374 mEnd(aTable.slotForIndex(aTable.capacity()))
1375#ifdef DEBUG1
1376 ,
1377 mTable(aTable),
1378 mMutationCount(aTable.mMutationCount),
1379 mGeneration(aTable.generation()),
1380 mValidEntry(true)
1381#endif
1382 {
1383 if (!done() && !mCur.isLive()) {
1384 moveToNextLiveEntry();
1385 }
1386 }
1387
1388 Slot mCur;
1389 Slot mEnd;
1390#ifdef DEBUG1
1391 const HashTable& mTable;
1392 uint64_t mMutationCount;
1393 Generation mGeneration;
1394 bool mValidEntry;
1395#endif
1396
1397 public:
1398 bool done() const {
1399 MOZ_ASSERT(mGeneration == mTable.generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable.generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(mGeneration == mTable.generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("mGeneration == mTable.generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1399); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable.generation()"
")"); do { *((volatile int*)__null) = 1399; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1400 MOZ_ASSERT(mMutationCount == mTable.mMutationCount)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mMutationCount == mTable.mMutationCount)>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mMutationCount == mTable.mMutationCount))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mMutationCount == mTable.mMutationCount"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1400); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mMutationCount == mTable.mMutationCount"
")"); do { *((volatile int*)__null) = 1400; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1401 return mCur == mEnd;
1402 }
1403
1404 T& get() const {
1405 MOZ_ASSERT(!done())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!done())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!done()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("!done()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1405); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!done()" ")"
); do { *((volatile int*)__null) = 1405; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1406 MOZ_ASSERT(mValidEntry)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mValidEntry)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(mValidEntry))), 0))) { do { }
while (false); MOZ_ReportAssertionFailure("mValidEntry", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1406); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mValidEntry"
")"); do { *((volatile int*)__null) = 1406; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1407 MOZ_ASSERT(mGeneration == mTable.generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable.generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(mGeneration == mTable.generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("mGeneration == mTable.generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1407); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable.generation()"
")"); do { *((volatile int*)__null) = 1407; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1408 MOZ_ASSERT(mMutationCount == mTable.mMutationCount)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mMutationCount == mTable.mMutationCount)>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mMutationCount == mTable.mMutationCount))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mMutationCount == mTable.mMutationCount"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1408); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mMutationCount == mTable.mMutationCount"
")"); do { *((volatile int*)__null) = 1408; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1409 return mCur.get();
1410 }
1411
1412 void next() {
1413 MOZ_ASSERT(!done())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!done())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!done()))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("!done()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1413); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!done()" ")"
); do { *((volatile int*)__null) = 1413; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1414 MOZ_ASSERT(mGeneration == mTable.generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mGeneration == mTable.generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(mGeneration == mTable.generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("mGeneration == mTable.generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1414); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mGeneration == mTable.generation()"
")"); do { *((volatile int*)__null) = 1414; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1415 MOZ_ASSERT(mMutationCount == mTable.mMutationCount)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mMutationCount == mTable.mMutationCount)>::isValid
, "invalid assertion condition"); if ((__builtin_expect(!!(!(
!!(mMutationCount == mTable.mMutationCount))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mMutationCount == mTable.mMutationCount"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1415); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mMutationCount == mTable.mMutationCount"
")"); do { *((volatile int*)__null) = 1415; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1416 moveToNextLiveEntry();
1417#ifdef DEBUG1
1418 mValidEntry = true;
1419#endif
1420 }
1421 };
1422
1423 // A hash table iterator that permits modification, removal and rekeying.
1424 // Since rehashing when elements were removed during enumeration would be
1425 // bad, it is postponed until the ModIterator is destructed. Since the
1426 // ModIterator's destructor touches the hash table, the user must ensure
1427 // that the hash table is still alive when the destructor runs.
1428 class ModIterator : public Iterator {
1429 friend class HashTable;
1430
1431 HashTable& mTable;
1432 bool mRekeyed;
1433 bool mRemoved;
1434
1435 // ModIterator is movable but not copyable.
1436 ModIterator(const ModIterator&) = delete;
1437 void operator=(const ModIterator&) = delete;
1438
1439 protected:
1440 explicit ModIterator(HashTable& aTable)
1441 : Iterator(aTable), mTable(aTable), mRekeyed(false), mRemoved(false) {}
1442
1443 public:
1444 MOZ_IMPLICIT ModIterator(ModIterator&& aOther)
1445 : Iterator(aOther),
1446 mTable(aOther.mTable),
1447 mRekeyed(aOther.mRekeyed),
1448 mRemoved(aOther.mRemoved) {
1449 aOther.mRekeyed = false;
1450 aOther.mRemoved = false;
1451 }
1452
1453 // Removes the current element from the table, leaving |get()|
1454 // invalid until the next call to |next()|.
1455 void remove() {
1456 mTable.remove(this->mCur);
1457 mRemoved = true;
1458#ifdef DEBUG1
1459 this->mValidEntry = false;
1460 this->mMutationCount = mTable.mMutationCount;
1461#endif
1462 }
1463
1464 NonConstT& getMutable() {
1465 MOZ_ASSERT(!this->done())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!this->done())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!this->done()))), 0))) { do
{ } while (false); MOZ_ReportAssertionFailure("!this->done()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1465); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!this->done()"
")"); do { *((volatile int*)__null) = 1465; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1466 MOZ_ASSERT(this->mValidEntry)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this->mValidEntry)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(this->mValidEntry))), 0))
) { do { } while (false); MOZ_ReportAssertionFailure("this->mValidEntry"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1466); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this->mValidEntry"
")"); do { *((volatile int*)__null) = 1466; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1467 MOZ_ASSERT(this->mGeneration == this->Iterator::mTable.generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this->mGeneration == this->Iterator::mTable.generation
())>::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!(this->mGeneration == this->Iterator::mTable.generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("this->mGeneration == this->Iterator::mTable.generation()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1467); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this->mGeneration == this->Iterator::mTable.generation()"
")"); do { *((volatile int*)__null) = 1467; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1468 MOZ_ASSERT(this->mMutationCount == this->Iterator::mTable.mMutationCount)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this->mMutationCount == this->Iterator::mTable
.mMutationCount)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(this->mMutationCount == this
->Iterator::mTable.mMutationCount))), 0))) { do { } while (
false); MOZ_ReportAssertionFailure("this->mMutationCount == this->Iterator::mTable.mMutationCount"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1468); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this->mMutationCount == this->Iterator::mTable.mMutationCount"
")"); do { *((volatile int*)__null) = 1468; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1469 return this->mCur.getMutable();
1470 }
1471
1472 // Removes the current element and re-inserts it into the table with
1473 // a new key at the new Lookup position. |get()| is invalid after
1474 // this operation until the next call to |next()|.
1475 void rekey(const Lookup& l, const Key& k) {
1476 MOZ_ASSERT(&k != &HashPolicy::getKey(this->mCur.get()))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(&k != &HashPolicy::getKey(this->mCur.get(
)))>::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!(&k != &HashPolicy::getKey(this->mCur.get(
))))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("&k != &HashPolicy::getKey(this->mCur.get())", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1476); AnnotateMozCrashReason("MOZ_ASSERT" "(" "&k != &HashPolicy::getKey(this->mCur.get())"
")"); do { *((volatile int*)__null) = 1476; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1477 Ptr p(this->mCur, mTable);
1478 mTable.rekeyWithoutRehash(p, l, k);
1479 mRekeyed = true;
1480#ifdef DEBUG1
1481 this->mValidEntry = false;
1482 this->mMutationCount = mTable.mMutationCount;
1483#endif
1484 }
1485
1486 void rekey(const Key& k) { rekey(k, k); }
1487
1488 // Potentially rehashes the table.
1489 ~ModIterator() {
1490 if (mRekeyed) {
1491 mTable.mGen++;
1492 mTable.infallibleRehashIfOverloaded();
1493 }
1494
1495 if (mRemoved) {
1496 mTable.compact();
1497 }
1498 }
1499 };
1500
1501 // Range is similar to Iterator, but uses different terminology.
1502 class Range {
1503 friend class HashTable;
1504
1505 Iterator mIter;
1506
1507 protected:
1508 explicit Range(const HashTable& table) : mIter(table) {}
1509
1510 public:
1511 bool empty() const { return mIter.done(); }
1512
1513 T& front() const { return mIter.get(); }
1514
1515 void popFront() { return mIter.next(); }
1516 };
1517
1518 // Enum is similar to ModIterator, but uses different terminology.
1519 class Enum {
1520 ModIterator mIter;
1521
1522 // Enum is movable but not copyable.
1523 Enum(const Enum&) = delete;
1524 void operator=(const Enum&) = delete;
1525
1526 public:
1527 template <class Map>
1528 explicit Enum(Map& map) : mIter(map.mImpl) {}
1529
1530 MOZ_IMPLICIT Enum(Enum&& other) : mIter(std::move(other.mIter)) {}
1531
1532 bool empty() const { return mIter.done(); }
1533
1534 T& front() const { return mIter.get(); }
1535
1536 void popFront() { return mIter.next(); }
1537
1538 void removeFront() { mIter.remove(); }
1539
1540 NonConstT& mutableFront() { return mIter.getMutable(); }
1541
1542 void rekeyFront(const Lookup& aLookup, const Key& aKey) {
1543 mIter.rekey(aLookup, aKey);
1544 }
1545
1546 void rekeyFront(const Key& aKey) { mIter.rekey(aKey); }
1547 };
1548
1549 // HashTable is movable
1550 HashTable(HashTable&& aRhs) : AllocPolicy(std::move(aRhs)) { moveFrom(aRhs); }
1551 HashTable& operator=(HashTable&& aRhs) {
1552 MOZ_ASSERT(this != &aRhs, "self-move assignment is prohibited")do { static_assert( mozilla::detail::AssertionConditionType<
decltype(this != &aRhs)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(this != &aRhs))), 0))) {
do { } while (false); MOZ_ReportAssertionFailure("this != &aRhs"
" (" "self-move assignment is prohibited" ")", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1552); AnnotateMozCrashReason("MOZ_ASSERT" "(" "this != &aRhs"
") (" "self-move assignment is prohibited" ")"); do { *((volatile
int*)__null) = 1552; __attribute__((nomerge)) ::abort(); } while
(false); } } while (false)
;
1553 if (mTable) {
1554 destroyTable(*this, mTable, capacity());
1555 }
1556 AllocPolicy::operator=(std::move(aRhs));
1557 moveFrom(aRhs);
1558 return *this;
1559 }
1560
1561 private:
1562 void moveFrom(HashTable& aRhs) {
1563 mGen = aRhs.mGen;
1564 mHashShift = aRhs.mHashShift;
1565 mTable = aRhs.mTable;
1566 mEntryCount = aRhs.mEntryCount;
1567 mRemovedCount = aRhs.mRemovedCount;
1568#ifdef DEBUG1
1569 mMutationCount = aRhs.mMutationCount;
1570 mEntered = aRhs.mEntered;
1571#endif
1572 aRhs.mTable = nullptr;
1573 aRhs.clearAndCompact();
1574 }
1575
1576 // HashTable is not copyable or assignable
1577 HashTable(const HashTable&) = delete;
1578 void operator=(const HashTable&) = delete;
1579
1580 static const uint32_t CAP_BITS = 30;
1581
1582 public:
1583 uint64_t mGen : 56; // entry storage generation number
1584 uint64_t mHashShift : 8; // multiplicative hash shift
1585 char* mTable; // entry storage
1586 uint32_t mEntryCount; // number of entries in mTable
1587 uint32_t mRemovedCount; // removed entry sentinels in mTable
1588
1589#ifdef DEBUG1
1590 uint64_t mMutationCount;
1591 mutable bool mEntered;
1592#endif
1593
1594 // The default initial capacity is 32 (enough to hold 16 elements), but it
1595 // can be as low as 4.
1596 static const uint32_t sDefaultLen = 16;
1597 static const uint32_t sMinCapacity = 4;
1598 // See the comments in HashTableEntry about this value.
1599 static_assert(sMinCapacity >= 4, "too-small sMinCapacity breaks assumptions");
1600 static const uint32_t sMaxInit = 1u << (CAP_BITS - 1);
1601 static const uint32_t sMaxCapacity = 1u << CAP_BITS;
1602
1603 // Hash-table alpha is conceptually a fraction, but to avoid floating-point
1604 // math we implement it as a ratio of integers.
1605 static const uint8_t sAlphaDenominator = 4;
1606 static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
1607 static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
1608
1609 static const HashNumber sFreeKey = Entry::sFreeKey;
1610 static const HashNumber sRemovedKey = Entry::sRemovedKey;
1611 static const HashNumber sCollisionBit = Entry::sCollisionBit;
1612
1613 static uint32_t bestCapacity(uint32_t aLen) {
1614 static_assert(
1615 (sMaxInit * sAlphaDenominator) / sAlphaDenominator == sMaxInit,
1616 "multiplication in numerator below could overflow");
1617 static_assert(
1618 sMaxInit * sAlphaDenominator <= UINT32_MAX(4294967295U) - sMaxAlphaNumerator,
1619 "numerator calculation below could potentially overflow");
1620
1621 // Callers should ensure this is true.
1622 MOZ_ASSERT(aLen <= sMaxInit)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aLen <= sMaxInit)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aLen <= sMaxInit))), 0)))
{ do { } while (false); MOZ_ReportAssertionFailure("aLen <= sMaxInit"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1622); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aLen <= sMaxInit"
")"); do { *((volatile int*)__null) = 1622; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1623
1624 // Compute the smallest capacity allowing |aLen| elements to be
1625 // inserted without rehashing: ceil(aLen / max-alpha). (Ceiling
1626 // integral division: <http://stackoverflow.com/a/2745086>.)
1627 uint32_t capacity = (aLen * sAlphaDenominator + sMaxAlphaNumerator - 1) /
1628 sMaxAlphaNumerator;
1629 capacity = (capacity < sMinCapacity) ? sMinCapacity : RoundUpPow2(capacity);
1630
1631 MOZ_ASSERT(capacity >= aLen)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(capacity >= aLen)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(capacity >= aLen))), 0)))
{ do { } while (false); MOZ_ReportAssertionFailure("capacity >= aLen"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1631); AnnotateMozCrashReason("MOZ_ASSERT" "(" "capacity >= aLen"
")"); do { *((volatile int*)__null) = 1631; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1632 MOZ_ASSERT(capacity <= sMaxCapacity)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(capacity <= sMaxCapacity)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(capacity <= sMaxCapacity)
)), 0))) { do { } while (false); MOZ_ReportAssertionFailure("capacity <= sMaxCapacity"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1632); AnnotateMozCrashReason("MOZ_ASSERT" "(" "capacity <= sMaxCapacity"
")"); do { *((volatile int*)__null) = 1632; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1633
1634 return capacity;
1635 }
1636
1637 static uint32_t hashShift(uint32_t aLen) {
1638 // Reject all lengths whose initial computed capacity would exceed
1639 // sMaxCapacity. Round that maximum aLen down to the nearest power of two
1640 // for speedier code.
1641 if (MOZ_UNLIKELY(aLen > sMaxInit)(__builtin_expect(!!(aLen > sMaxInit), 0))) {
1642 MOZ_CRASH("initial length is too large")do { do { } while (false); MOZ_ReportCrash("" "initial length is too large"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1642); AnnotateMozCrashReason("MOZ_CRASH(" "initial length is too large"
")"); do { *((volatile int*)__null) = 1642; __attribute__((nomerge
)) ::abort(); } while (false); } while (false)
;
1643 }
1644
1645 return kHashNumberBits - mozilla::CeilingLog2(bestCapacity(aLen));
1646 }
1647
1648 static bool isLiveHash(HashNumber aHash) { return Entry::isLiveHash(aHash); }
1649
1650 static HashNumber prepareHash(HashNumber aInputHash) {
1651 HashNumber keyHash = ScrambleHashCode(aInputHash);
1652
1653 // Avoid reserved hash codes.
1654 if (!isLiveHash(keyHash)) {
1655 keyHash -= (sRemovedKey + 1);
1656 }
1657 return keyHash & ~sCollisionBit;
1658 }
1659
1660 enum FailureBehavior { DontReportFailure = false, ReportFailure = true };
1661
1662 // Fake a struct that we're going to alloc. See the comments in
1663 // HashTableEntry about how the table is laid out, and why it's safe.
1664 struct FakeSlot {
1665 unsigned char c[sizeof(HashNumber) + sizeof(typename Entry::NonConstT)];
1666 };
1667
1668 static char* createTable(AllocPolicy& aAllocPolicy, uint32_t aCapacity,
1669 FailureBehavior aReportFailure = ReportFailure) {
1670 FakeSlot* fake =
1671 aReportFailure
1672 ? aAllocPolicy.template pod_malloc<FakeSlot>(aCapacity)
1673 : aAllocPolicy.template maybe_pod_malloc<FakeSlot>(aCapacity);
1674
1675 MOZ_ASSERT((reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment) ==do { static_assert( mozilla::detail::AssertionConditionType<
decltype((reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment
) == 0)>::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!((reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment
) == 0))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("(reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment) == 0"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1676); AnnotateMozCrashReason("MOZ_ASSERT" "(" "(reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment) == 0"
")"); do { *((volatile int*)__null) = 1676; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
1676 0)do { static_assert( mozilla::detail::AssertionConditionType<
decltype((reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment
) == 0)>::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!((reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment
) == 0))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("(reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment) == 0"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1676); AnnotateMozCrashReason("MOZ_ASSERT" "(" "(reinterpret_cast<uintptr_t>(fake) % Entry::kMinimumAlignment) == 0"
")"); do { *((volatile int*)__null) = 1676; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1677
1678 char* table = reinterpret_cast<char*>(fake);
1679 if (table) {
1680 forEachSlot(table, aCapacity, [&](Slot& slot) {
1681 *slot.mKeyHash = sFreeKey;
1682 new (KnownNotNull, slot.toEntry()) Entry();
1683 });
1684 }
1685 return table;
1686 }
1687
1688 static void destroyTable(AllocPolicy& aAllocPolicy, char* aOldTable,
1689 uint32_t aCapacity) {
1690 forEachSlot(aOldTable, aCapacity, [&](const Slot& slot) {
1691 if (slot.isLive()) {
1692 slot.toEntry()->destroyStoredT();
1693 }
1694 });
1695 freeTable(aAllocPolicy, aOldTable, aCapacity);
1696 }
1697
1698 static void freeTable(AllocPolicy& aAllocPolicy, char* aOldTable,
1699 uint32_t aCapacity) {
1700 FakeSlot* fake = reinterpret_cast<FakeSlot*>(aOldTable);
1701 aAllocPolicy.free_(fake, aCapacity);
1702 }
1703
1704 public:
1705 HashTable(AllocPolicy aAllocPolicy, uint32_t aLen)
1706 : AllocPolicy(std::move(aAllocPolicy)),
1707 mGen(0),
1708 mHashShift(hashShift(aLen)),
1709 mTable(nullptr),
1710 mEntryCount(0),
1711 mRemovedCount(0)
1712#ifdef DEBUG1
1713 ,
1714 mMutationCount(0),
1715 mEntered(false)
1716#endif
1717 {
1718 }
1719
1720 explicit HashTable(AllocPolicy aAllocPolicy)
1721 : HashTable(aAllocPolicy, sDefaultLen) {}
1722
1723 ~HashTable() {
1724 if (mTable) {
1725 destroyTable(*this, mTable, capacity());
1726 }
1727 }
1728
1729 private:
1730 HashNumber hash1(HashNumber aHash0) const { return aHash0 >> mHashShift; }
1731
1732 struct DoubleHash {
1733 HashNumber mHash2;
1734 HashNumber mSizeMask;
1735 };
1736
1737 DoubleHash hash2(HashNumber aCurKeyHash) const {
1738 uint32_t sizeLog2 = kHashNumberBits - mHashShift;
1739 DoubleHash dh = {((aCurKeyHash << sizeLog2) >> mHashShift) | 1,
1740 (HashNumber(1) << sizeLog2) - 1};
1741 return dh;
1742 }
1743
1744 static HashNumber applyDoubleHash(HashNumber aHash1,
1745 const DoubleHash& aDoubleHash) {
1746 return WrappingSubtract(aHash1, aDoubleHash.mHash2) & aDoubleHash.mSizeMask;
1747 }
1748
1749 static MOZ_ALWAYS_INLINEinline bool match(T& aEntry, const Lookup& aLookup) {
1750 return HashPolicy::match(HashPolicy::getKey(aEntry), aLookup);
1751 }
1752
1753 enum LookupReason { ForNonAdd, ForAdd };
1754
1755 Slot slotForIndex(HashNumber aIndex) const {
1756 auto hashes = reinterpret_cast<HashNumber*>(mTable);
1757 auto entries = reinterpret_cast<Entry*>(&hashes[capacity()]);
1758 return Slot(&entries[aIndex], &hashes[aIndex]);
1759 }
1760
1761 // Warning: in order for readonlyThreadsafeLookup() to be safe this
1762 // function must not modify the table in any way when Reason==ForNonAdd.
1763 template <LookupReason Reason>
1764 MOZ_ALWAYS_INLINEinline Slot lookup(const Lookup& aLookup,
1765 HashNumber aKeyHash) const {
1766 MOZ_ASSERT(isLiveHash(aKeyHash))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(isLiveHash(aKeyHash))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(isLiveHash(aKeyHash)))), 0))
) { do { } while (false); MOZ_ReportAssertionFailure("isLiveHash(aKeyHash)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1766); AnnotateMozCrashReason("MOZ_ASSERT" "(" "isLiveHash(aKeyHash)"
")"); do { *((volatile int*)__null) = 1766; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1767 MOZ_ASSERT(!(aKeyHash & sCollisionBit))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!(aKeyHash & sCollisionBit))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!(aKeyHash & sCollisionBit
)))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("!(aKeyHash & sCollisionBit)", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1767); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!(aKeyHash & sCollisionBit)"
")"); do { *((volatile int*)__null) = 1767; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1768 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1768); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 1768; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1769
1770 // Compute the primary hash address.
1771 HashNumber h1 = hash1(aKeyHash);
1772 Slot slot = slotForIndex(h1);
1773
1774 // Miss: return space for a new entry.
1775 if (slot.isFree()) {
1776 return slot;
1777 }
1778
1779 // Hit: return entry.
1780 if (slot.matchHash(aKeyHash) && match(slot.get(), aLookup)) {
1781 return slot;
1782 }
1783
1784 // Collision: double hash.
1785 DoubleHash dh = hash2(aKeyHash);
1786
1787 // Save the first removed entry pointer so we can recycle later.
1788 Maybe<Slot> firstRemoved;
1789
1790 while (true) {
1791 if (Reason == ForAdd && !firstRemoved) {
1792 if (MOZ_UNLIKELY(slot.isRemoved())(__builtin_expect(!!(slot.isRemoved()), 0))) {
1793 firstRemoved.emplace(slot);
1794 } else {
1795 slot.setCollision();
1796 }
1797 }
1798
1799 h1 = applyDoubleHash(h1, dh);
1800
1801 slot = slotForIndex(h1);
1802 if (slot.isFree()) {
1803 return firstRemoved.refOr(slot);
1804 }
1805
1806 if (slot.matchHash(aKeyHash) && match(slot.get(), aLookup)) {
1807 return slot;
1808 }
1809 }
1810 }
1811
1812 // This is a copy of lookup() hardcoded to the assumptions:
1813 // 1. the lookup is for an add;
1814 // 2. the key, whose |keyHash| has been passed, is not in the table.
1815 Slot findNonLiveSlot(HashNumber aKeyHash) {
1816 MOZ_ASSERT(!(aKeyHash & sCollisionBit))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!(aKeyHash & sCollisionBit))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!(aKeyHash & sCollisionBit
)))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("!(aKeyHash & sCollisionBit)", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1816); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!(aKeyHash & sCollisionBit)"
")"); do { *((volatile int*)__null) = 1816; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1817 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1817); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 1817; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1818
1819 // We assume 'aKeyHash' has already been distributed.
1820
1821 // Compute the primary hash address.
1822 HashNumber h1 = hash1(aKeyHash);
1823 Slot slot = slotForIndex(h1);
1824
1825 // Miss: return space for a new entry.
1826 if (!slot.isLive()) {
1827 return slot;
1828 }
1829
1830 // Collision: double hash.
1831 DoubleHash dh = hash2(aKeyHash);
1832
1833 while (true) {
1834 slot.setCollision();
1835
1836 h1 = applyDoubleHash(h1, dh);
1837
1838 slot = slotForIndex(h1);
1839 if (!slot.isLive()) {
1840 return slot;
1841 }
1842 }
1843 }
1844
1845 enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };
1846
1847 RebuildStatus changeTableSize(
1848 uint32_t newCapacity, FailureBehavior aReportFailure = ReportFailure) {
1849 MOZ_ASSERT(IsPowerOfTwo(newCapacity))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(IsPowerOfTwo(newCapacity))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(IsPowerOfTwo(newCapacity))))
, 0))) { do { } while (false); MOZ_ReportAssertionFailure("IsPowerOfTwo(newCapacity)"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1849); AnnotateMozCrashReason("MOZ_ASSERT" "(" "IsPowerOfTwo(newCapacity)"
")"); do { *((volatile int*)__null) = 1849; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1850 MOZ_ASSERT(!!mTable == !!capacity())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!!mTable == !!capacity())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!!mTable == !!capacity()))),
0))) { do { } while (false); MOZ_ReportAssertionFailure("!!mTable == !!capacity()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1850); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!!mTable == !!capacity()"
")"); do { *((volatile int*)__null) = 1850; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1851
1852 // Look, but don't touch, until we succeed in getting new entry store.
1853 char* oldTable = mTable;
1854 uint32_t oldCapacity = capacity();
1855 uint32_t newLog2 = mozilla::CeilingLog2(newCapacity);
1856
1857 if (MOZ_UNLIKELY(newCapacity > sMaxCapacity)(__builtin_expect(!!(newCapacity > sMaxCapacity), 0))) {
1858 if (aReportFailure) {
1859 this->reportAllocOverflow();
1860 }
1861 return RehashFailed;
1862 }
1863
1864 char* newTable = createTable(*this, newCapacity, aReportFailure);
1865 if (!newTable) {
1866 return RehashFailed;
1867 }
1868
1869 // We can't fail from here on, so update table parameters.
1870 mHashShift = kHashNumberBits - newLog2;
1871 mRemovedCount = 0;
1872 mGen++;
1873 mTable = newTable;
1874
1875 // Copy only live entries, leaving removed ones behind.
1876 forEachSlot(oldTable, oldCapacity, [&](Slot& slot) {
1877 if (slot.isLive()) {
1878 HashNumber hn = slot.getKeyHash();
1879 findNonLiveSlot(hn).setLive(
1880 hn, std::move(const_cast<typename Entry::NonConstT&>(slot.get())));
1881 }
1882
1883 slot.clear();
1884 });
1885
1886 // All entries have been destroyed, no need to destroyTable.
1887 freeTable(*this, oldTable, oldCapacity);
1888 return Rehashed;
1889 }
1890
1891 RebuildStatus rehashIfOverloaded(
1892 FailureBehavior aReportFailure = ReportFailure) {
1893 static_assert(sMaxCapacity <= UINT32_MAX(4294967295U) / sMaxAlphaNumerator,
1894 "multiplication below could overflow");
1895
1896 // Note: if capacity() is zero, this will always succeed, which is
1897 // what we want.
1898 bool overloaded = mEntryCount + mRemovedCount >=
1899 capacity() * sMaxAlphaNumerator / sAlphaDenominator;
1900
1901 if (!overloaded) {
1902 return NotOverloaded;
1903 }
1904
1905 // Succeed if a quarter or more of all entries are removed. Note that this
1906 // always succeeds if capacity() == 0 (i.e. entry storage has not been
1907 // allocated), which is what we want, because it means changeTableSize()
1908 // will allocate the requested capacity rather than doubling it.
1909 bool manyRemoved = mRemovedCount >= (capacity() >> 2);
1910 uint32_t newCapacity = manyRemoved ? rawCapacity() : rawCapacity() * 2;
1911 return changeTableSize(newCapacity, aReportFailure);
1912 }
1913
1914 void infallibleRehashIfOverloaded() {
1915 if (rehashIfOverloaded(DontReportFailure) == RehashFailed) {
1916 rehashTableInPlace();
1917 }
1918 }
1919
1920 void remove(Slot& aSlot) {
1921 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1921); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 1921; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1922
1923 if (aSlot.hasCollision()) {
1924 aSlot.removeLive();
1925 mRemovedCount++;
1926 } else {
1927 aSlot.clearLive();
1928 }
1929 mEntryCount--;
1930#ifdef DEBUG1
1931 mMutationCount++;
1932#endif
1933 }
1934
1935 void shrinkIfUnderloaded() {
1936 static_assert(sMaxCapacity <= UINT32_MAX(4294967295U) / sMinAlphaNumerator,
1937 "multiplication below could overflow");
1938 bool underloaded =
1939 capacity() > sMinCapacity &&
1940 mEntryCount <= capacity() * sMinAlphaNumerator / sAlphaDenominator;
1941
1942 if (underloaded) {
1943 (void)changeTableSize(capacity() / 2, DontReportFailure);
1944 }
1945 }
1946
1947 // This is identical to changeTableSize(currentSize), but without requiring
1948 // a second table. We do this by recycling the collision bits to tell us if
1949 // the element is already inserted or still waiting to be inserted. Since
1950 // already-inserted elements win any conflicts, we get the same table as we
1951 // would have gotten through random insertion order.
1952 void rehashTableInPlace() {
1953 mRemovedCount = 0;
1954 mGen++;
1955 forEachSlot(mTable, capacity(), [&](Slot& slot) { slot.unsetCollision(); });
1956 for (uint32_t i = 0; i < capacity();) {
1957 Slot src = slotForIndex(i);
1958
1959 if (!src.isLive() || src.hasCollision()) {
1960 ++i;
1961 continue;
1962 }
1963
1964 HashNumber keyHash = src.getKeyHash();
1965 HashNumber h1 = hash1(keyHash);
1966 DoubleHash dh = hash2(keyHash);
1967 Slot tgt = slotForIndex(h1);
1968 while (true) {
1969 if (!tgt.hasCollision()) {
1970 src.swap(tgt);
1971 tgt.setCollision();
1972 break;
1973 }
1974
1975 h1 = applyDoubleHash(h1, dh);
1976 tgt = slotForIndex(h1);
1977 }
1978 }
1979
1980 // TODO: this algorithm leaves collision bits on *all* elements, even if
1981 // they are on no collision path. We have the option of setting the
1982 // collision bits correctly on a subsequent pass or skipping the rehash
1983 // unless we are totally filled with tombstones: benchmark to find out
1984 // which approach is best.
1985 }
1986
1987 // Prefer to use putNewInfallible; this function does not check
1988 // invariants.
1989 template <typename... Args>
1990 void putNewInfallibleInternal(HashNumber aKeyHash, Args&&... aArgs) {
1991 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 1991); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 1991; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
1992
1993 Slot slot = findNonLiveSlot(aKeyHash);
1994
1995 if (slot.isRemoved()) {
1996 mRemovedCount--;
1997 aKeyHash |= sCollisionBit;
1998 }
1999
2000 slot.setLive(aKeyHash, std::forward<Args>(aArgs)...);
2001 mEntryCount++;
2002#ifdef DEBUG1
2003 mMutationCount++;
2004#endif
2005 }
2006
2007 public:
2008 void clear() {
2009 forEachSlot(mTable, capacity(), [&](Slot& slot) { slot.clear(); });
2010 mRemovedCount = 0;
2011 mEntryCount = 0;
2012#ifdef DEBUG1
2013 mMutationCount++;
2014#endif
2015 }
2016
2017 // Resize the table down to the smallest capacity that doesn't overload the
2018 // table. Since we call shrinkIfUnderloaded() on every remove, you only need
2019 // to call this after a bulk removal of items done without calling remove().
2020 void compact() {
2021 if (empty()) {
2022 // Free the entry storage.
2023 freeTable(*this, mTable, capacity());
2024 mGen++;
2025 mHashShift = hashShift(0); // gives minimum capacity on regrowth
2026 mTable = nullptr;
2027 mRemovedCount = 0;
2028 return;
2029 }
2030
2031 uint32_t bestCapacity = this->bestCapacity(mEntryCount);
2032 MOZ_ASSERT(bestCapacity <= capacity())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(bestCapacity <= capacity())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(bestCapacity <= capacity(
)))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("bestCapacity <= capacity()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2032); AnnotateMozCrashReason("MOZ_ASSERT" "(" "bestCapacity <= capacity()"
")"); do { *((volatile int*)__null) = 2032; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2033
2034 if (bestCapacity < capacity()) {
2035 (void)changeTableSize(bestCapacity, DontReportFailure);
2036 }
2037 }
2038
2039 void clearAndCompact() {
2040 clear();
2041 compact();
2042 }
2043
2044 [[nodiscard]] bool reserve(uint32_t aLen) {
2045 if (aLen == 0) {
2046 return true;
2047 }
2048
2049 if (MOZ_UNLIKELY(aLen > sMaxInit)(__builtin_expect(!!(aLen > sMaxInit), 0))) {
2050 this->reportAllocOverflow();
2051 return false;
2052 }
2053
2054 uint32_t bestCapacity = this->bestCapacity(aLen);
2055 if (bestCapacity <= capacity()) {
2056 return true; // Capacity is already sufficient.
2057 }
2058
2059 RebuildStatus status = changeTableSize(bestCapacity, ReportFailure);
2060 MOZ_ASSERT(status != NotOverloaded)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(status != NotOverloaded)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(status != NotOverloaded))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("status != NotOverloaded"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2060); AnnotateMozCrashReason("MOZ_ASSERT" "(" "status != NotOverloaded"
")"); do { *((volatile int*)__null) = 2060; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2061 return status != RehashFailed;
2062 }
2063
2064 Iterator iter() const { return Iterator(*this); }
2065
2066 ModIterator modIter() { return ModIterator(*this); }
2067
2068 Range all() const { return Range(*this); }
2069
2070 bool empty() const { return mEntryCount == 0; }
2071
2072 uint32_t count() const { return mEntryCount; }
2073
2074 uint32_t rawCapacity() const { return 1u << (kHashNumberBits - mHashShift); }
2075
2076 uint32_t capacity() const { return mTable ? rawCapacity() : 0; }
2077
2078 Generation generation() const { return Generation(mGen); }
2079
2080 size_t shallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
2081 return aMallocSizeOf(mTable);
2082 }
2083
2084 size_t shallowSizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
2085 return aMallocSizeOf(this) + shallowSizeOfExcludingThis(aMallocSizeOf);
2086 }
2087
2088 MOZ_ALWAYS_INLINEinline Ptr readonlyThreadsafeLookup(const Lookup& aLookup) const {
2089 if (empty()) {
6
Taking true branch
2090 return Ptr();
7
Calling default constructor for 'Ptr'
9
Returning from default constructor for 'Ptr'
2091 }
2092
2093 HashNumber inputHash;
2094 if (!MaybeGetHash<HashPolicy>(aLookup, &inputHash)) {
2095 return Ptr();
2096 }
2097
2098 HashNumber keyHash = prepareHash(inputHash);
2099 return Ptr(lookup<ForNonAdd>(aLookup, keyHash), *this);
2100 }
2101
2102 MOZ_ALWAYS_INLINEinline Ptr lookup(const Lookup& aLookup) const {
2103 ReentrancyGuard g(*this);
2104 return readonlyThreadsafeLookup(aLookup);
5
Calling 'HashTable::readonlyThreadsafeLookup'
10
Returning from 'HashTable::readonlyThreadsafeLookup'
2105 }
2106
2107 MOZ_ALWAYS_INLINEinline AddPtr lookupForAdd(const Lookup& aLookup) {
2108 ReentrancyGuard g(*this);
2109
2110 HashNumber inputHash;
2111 if (!EnsureHash<HashPolicy>(aLookup, &inputHash)) {
2112 return AddPtr();
2113 }
2114
2115 HashNumber keyHash = prepareHash(inputHash);
2116
2117 if (!mTable) {
2118 return AddPtr(*this, keyHash);
2119 }
2120
2121 // Directly call the constructor in the return statement to avoid
2122 // excess copying when building with Visual Studio 2017.
2123 // See bug 1385181.
2124 return AddPtr(lookup<ForAdd>(aLookup, keyHash), *this, keyHash);
2125 }
2126
2127 template <typename... Args>
2128 [[nodiscard]] bool add(AddPtr& aPtr, Args&&... aArgs) {
2129 ReentrancyGuard g(*this);
2130 MOZ_ASSERT_IF(aPtr.isValid(), mTable)do { if (aPtr.isValid()) { do { static_assert( mozilla::detail
::AssertionConditionType<decltype(mTable)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2130); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 2130; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false); } } while (
false)
;
2131 MOZ_ASSERT_IF(aPtr.isValid(), aPtr.mTable == this)do { if (aPtr.isValid()) { do { static_assert( mozilla::detail
::AssertionConditionType<decltype(aPtr.mTable == this)>
::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!(aPtr.mTable == this))), 0))) { do { } while (false);
MOZ_ReportAssertionFailure("aPtr.mTable == this", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2131); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.mTable == this"
")"); do { *((volatile int*)__null) = 2131; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false); } } while (
false)
;
2132 MOZ_ASSERT(!aPtr.found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!aPtr.found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!aPtr.found()))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("!aPtr.found()",
"/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2132); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!aPtr.found()"
")"); do { *((volatile int*)__null) = 2132; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2133 MOZ_ASSERT(!(aPtr.mKeyHash & sCollisionBit))do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!(aPtr.mKeyHash & sCollisionBit))>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!(aPtr.mKeyHash & sCollisionBit
)))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("!(aPtr.mKeyHash & sCollisionBit)", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2133); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!(aPtr.mKeyHash & sCollisionBit)"
")"); do { *((volatile int*)__null) = 2133; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2134
2135 // Check for error from ensureHash() here.
2136 if (!aPtr.isLive()) {
2137 return false;
2138 }
2139
2140 MOZ_ASSERT(aPtr.mGeneration == generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.mGeneration == generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.mGeneration == generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("aPtr.mGeneration == generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2140); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.mGeneration == generation()"
")"); do { *((volatile int*)__null) = 2140; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2141#ifdef DEBUG1
2142 MOZ_ASSERT(aPtr.mMutationCount == mMutationCount)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.mMutationCount == mMutationCount)>::isValid,
"invalid assertion condition"); if ((__builtin_expect(!!(!(!
!(aPtr.mMutationCount == mMutationCount))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("aPtr.mMutationCount == mMutationCount"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2142); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.mMutationCount == mMutationCount"
")"); do { *((volatile int*)__null) = 2142; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2143#endif
2144
2145 if (!aPtr.isValid()) {
2146 MOZ_ASSERT(!mTable && mEntryCount == 0)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!mTable && mEntryCount == 0)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!mTable && mEntryCount
== 0))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("!mTable && mEntryCount == 0", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2146); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!mTable && mEntryCount == 0"
")"); do { *((volatile int*)__null) = 2146; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2147 uint32_t newCapacity = rawCapacity();
2148 RebuildStatus status = changeTableSize(newCapacity, ReportFailure);
2149 MOZ_ASSERT(status != NotOverloaded)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(status != NotOverloaded)>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(status != NotOverloaded))), 0
))) { do { } while (false); MOZ_ReportAssertionFailure("status != NotOverloaded"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2149); AnnotateMozCrashReason("MOZ_ASSERT" "(" "status != NotOverloaded"
")"); do { *((volatile int*)__null) = 2149; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2150 if (status == RehashFailed) {
2151 return false;
2152 }
2153 aPtr.mSlot = findNonLiveSlot(aPtr.mKeyHash);
2154
2155 } else if (aPtr.mSlot.isRemoved()) {
2156 // Changing an entry from removed to live does not affect whether we are
2157 // overloaded and can be handled separately.
2158 if (!this->checkSimulatedOOM()) {
2159 return false;
2160 }
2161 mRemovedCount--;
2162 aPtr.mKeyHash |= sCollisionBit;
2163
2164 } else {
2165 // Preserve the validity of |aPtr.mSlot|.
2166 RebuildStatus status = rehashIfOverloaded();
2167 if (status == RehashFailed) {
2168 return false;
2169 }
2170 if (status == NotOverloaded && !this->checkSimulatedOOM()) {
2171 return false;
2172 }
2173 if (status == Rehashed) {
2174 aPtr.mSlot = findNonLiveSlot(aPtr.mKeyHash);
2175 }
2176 }
2177
2178 aPtr.mSlot.setLive(aPtr.mKeyHash, std::forward<Args>(aArgs)...);
2179 mEntryCount++;
2180#ifdef DEBUG1
2181 mMutationCount++;
2182 aPtr.mGeneration = generation();
2183 aPtr.mMutationCount = mMutationCount;
2184#endif
2185 return true;
2186 }
2187
2188 // Note: |aLookup| may reference pieces of arguments in |aArgs|, so this
2189 // function must take care not to use |aLookup| after moving |aArgs|.
2190 template <typename... Args>
2191 void putNewInfallible(const Lookup& aLookup, Args&&... aArgs) {
2192 MOZ_ASSERT(!lookup(aLookup).found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!lookup(aLookup).found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!lookup(aLookup).found()))),
0))) { do { } while (false); MOZ_ReportAssertionFailure("!lookup(aLookup).found()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2192); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!lookup(aLookup).found()"
")"); do { *((volatile int*)__null) = 2192; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2193 ReentrancyGuard g(*this);
2194 HashNumber keyHash = prepareHash(HashPolicy::hash(aLookup));
2195 putNewInfallibleInternal(keyHash, std::forward<Args>(aArgs)...);
2196 }
2197
2198 // Note: |aLookup| may alias arguments in |aArgs|, so this function must take
2199 // care not to use |aLookup| after moving |aArgs|.
2200 template <typename... Args>
2201 [[nodiscard]] bool putNew(const Lookup& aLookup, Args&&... aArgs) {
2202 MOZ_ASSERT(!lookup(aLookup).found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(!lookup(aLookup).found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(!lookup(aLookup).found()))),
0))) { do { } while (false); MOZ_ReportAssertionFailure("!lookup(aLookup).found()"
, "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2202); AnnotateMozCrashReason("MOZ_ASSERT" "(" "!lookup(aLookup).found()"
")"); do { *((volatile int*)__null) = 2202; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2203 ReentrancyGuard g(*this);
2204 if (!this->checkSimulatedOOM()) {
2205 return false;
2206 }
2207 HashNumber inputHash;
2208 if (!EnsureHash<HashPolicy>(aLookup, &inputHash)) {
2209 return false;
2210 }
2211 HashNumber keyHash = prepareHash(inputHash);
2212 if (rehashIfOverloaded() == RehashFailed) {
2213 return false;
2214 }
2215 putNewInfallibleInternal(keyHash, std::forward<Args>(aArgs)...);
2216 return true;
2217 }
2218
2219 // Note: |aLookup| may be a reference pieces of arguments in |aArgs|, so this
2220 // function must take care not to use |aLookup| after moving |aArgs|.
2221 template <typename... Args>
2222 [[nodiscard]] bool relookupOrAdd(AddPtr& aPtr, const Lookup& aLookup,
2223 Args&&... aArgs) {
2224 // Check for error from ensureHash() here.
2225 if (!aPtr.isLive()) {
2226 return false;
2227 }
2228#ifdef DEBUG1
2229 aPtr.mGeneration = generation();
2230 aPtr.mMutationCount = mMutationCount;
2231#endif
2232 if (mTable) {
2233 ReentrancyGuard g(*this);
2234 // Check that aLookup has not been destroyed.
2235 MOZ_ASSERT(prepareHash(HashPolicy::hash(aLookup)) == aPtr.mKeyHash)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(prepareHash(HashPolicy::hash(aLookup)) == aPtr.mKeyHash
)>::isValid, "invalid assertion condition"); if ((__builtin_expect
(!!(!(!!(prepareHash(HashPolicy::hash(aLookup)) == aPtr.mKeyHash
))), 0))) { do { } while (false); MOZ_ReportAssertionFailure(
"prepareHash(HashPolicy::hash(aLookup)) == aPtr.mKeyHash", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2235); AnnotateMozCrashReason("MOZ_ASSERT" "(" "prepareHash(HashPolicy::hash(aLookup)) == aPtr.mKeyHash"
")"); do { *((volatile int*)__null) = 2235; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2236 aPtr.mSlot = lookup<ForAdd>(aLookup, aPtr.mKeyHash);
2237 if (aPtr.found()) {
2238 return true;
2239 }
2240 } else {
2241 // Clear aPtr so it's invalid; add() will allocate storage and redo the
2242 // lookup.
2243 aPtr.mSlot = Slot(nullptr, nullptr);
2244 }
2245 return add(aPtr, std::forward<Args>(aArgs)...);
2246 }
2247
2248 void remove(Ptr aPtr) {
2249 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2249); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 2249; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2250 ReentrancyGuard g(*this);
2251 MOZ_ASSERT(aPtr.found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.found()))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("aPtr.found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2251); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.found()"
")"); do { *((volatile int*)__null) = 2251; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2252 MOZ_ASSERT(aPtr.mGeneration == generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.mGeneration == generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.mGeneration == generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("aPtr.mGeneration == generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2252); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.mGeneration == generation()"
")"); do { *((volatile int*)__null) = 2252; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2253 remove(aPtr.mSlot);
2254 shrinkIfUnderloaded();
2255 }
2256
2257 void rekeyWithoutRehash(Ptr aPtr, const Lookup& aLookup, const Key& aKey) {
2258 MOZ_ASSERT(mTable)do { static_assert( mozilla::detail::AssertionConditionType<
decltype(mTable)>::isValid, "invalid assertion condition")
; if ((__builtin_expect(!!(!(!!(mTable))), 0))) { do { } while
(false); MOZ_ReportAssertionFailure("mTable", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2258); AnnotateMozCrashReason("MOZ_ASSERT" "(" "mTable" ")"
); do { *((volatile int*)__null) = 2258; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2259 ReentrancyGuard g(*this);
2260 MOZ_ASSERT(aPtr.found())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.found())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.found()))), 0))) { do {
} while (false); MOZ_ReportAssertionFailure("aPtr.found()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2260); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.found()"
")"); do { *((volatile int*)__null) = 2260; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2261 MOZ_ASSERT(aPtr.mGeneration == generation())do { static_assert( mozilla::detail::AssertionConditionType<
decltype(aPtr.mGeneration == generation())>::isValid, "invalid assertion condition"
); if ((__builtin_expect(!!(!(!!(aPtr.mGeneration == generation
()))), 0))) { do { } while (false); MOZ_ReportAssertionFailure
("aPtr.mGeneration == generation()", "/var/lib/jenkins/workspace/firefox-scan-build/obj-x86_64-pc-linux-gnu/dist/include/mozilla/HashTable.h"
, 2261); AnnotateMozCrashReason("MOZ_ASSERT" "(" "aPtr.mGeneration == generation()"
")"); do { *((volatile int*)__null) = 2261; __attribute__((nomerge
)) ::abort(); } while (false); } } while (false)
;
2262 typename HashTableEntry<T>::NonConstT t(std::move(*aPtr));
2263 HashPolicy::setKey(t, const_cast<Key&>(aKey));
2264 remove(aPtr.mSlot);
2265 HashNumber keyHash = prepareHash(HashPolicy::hash(aLookup));
2266 putNewInfallibleInternal(keyHash, std::move(t));
2267 }
2268
2269 void rekeyAndMaybeRehash(Ptr aPtr, const Lookup& aLookup, const Key& aKey) {
2270 rekeyWithoutRehash(aPtr, aLookup, aKey);
2271 infallibleRehashIfOverloaded();
2272 }
2273};
2274
2275} // namespace detail
2276} // namespace mozilla
2277
2278#endif /* mozilla_HashTable_h */