diff options
Diffstat (limited to 'dom/base/nsAttrAndChildArray.cpp')
| -rw-r--r-- | dom/base/nsAttrAndChildArray.cpp | 907 |
1 files changed, 907 insertions, 0 deletions
diff --git a/dom/base/nsAttrAndChildArray.cpp b/dom/base/nsAttrAndChildArray.cpp new file mode 100644 index 000000000..b285ee003 --- /dev/null +++ b/dom/base/nsAttrAndChildArray.cpp @@ -0,0 +1,907 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * Storage of the children and attributes of a DOM node; storage for + * the two is unified to minimize footprint. + */ + +#include "nsAttrAndChildArray.h" + +#include "mozilla/CheckedInt.h" +#include "mozilla/MathAlgorithms.h" +#include "mozilla/MemoryReporting.h" + +#include "nsMappedAttributeElement.h" +#include "nsString.h" +#include "nsHTMLStyleSheet.h" +#include "nsRuleWalker.h" +#include "nsMappedAttributes.h" +#include "nsUnicharUtils.h" +#include "nsContentUtils.h" // nsAutoScriptBlocker + +using mozilla::CheckedUint32; + +/* +CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer. +It should be small enough to not cause collisions between adjecent arrays, and +large enough to make sure that all indexes are used. The size below is based +on the size of the smallest possible element (currently 24[*] bytes) which is +the smallest distance between two nsAttrAndChildArray. 24/(2^_5_) is 0.75. +This means that two adjacent nsAttrAndChildArrays will overlap one in 4 times. +However not all elements will have enough children to get cached. And any +allocator that doesn't return addresses aligned to 64 bytes will ensure that +any index will get used. + +[*] sizeof(Element) + 4 bytes for nsIDOMElement vtable pointer. +*/ + +#define CACHE_POINTER_SHIFT 5 +#define CACHE_NUM_SLOTS 128 +#define CACHE_CHILD_LIMIT 10 + +#define CACHE_GET_INDEX(_array) \ + ((NS_PTR_TO_INT32(_array) >> CACHE_POINTER_SHIFT) & \ + (CACHE_NUM_SLOTS - 1)) + +struct IndexCacheSlot +{ + const nsAttrAndChildArray* array; + int32_t index; +}; + +// This is inited to all zeroes since it's static. Though even if it wasn't +// the worst thing that'd happen is a small inefficency if you'd get a false +// positive cachehit. +static IndexCacheSlot indexCache[CACHE_NUM_SLOTS]; + +static +inline +void +AddIndexToCache(const nsAttrAndChildArray* aArray, int32_t aIndex) +{ + uint32_t ix = CACHE_GET_INDEX(aArray); + indexCache[ix].array = aArray; + indexCache[ix].index = aIndex; +} + +static +inline +int32_t +GetIndexFromCache(const nsAttrAndChildArray* aArray) +{ + uint32_t ix = CACHE_GET_INDEX(aArray); + return indexCache[ix].array == aArray ? indexCache[ix].index : -1; +} + + +/** + * Due to a compiler bug in VisualAge C++ for AIX, we need to return the + * address of the first index into mBuffer here, instead of simply returning + * mBuffer itself. + * + * See Bug 231104 for more information. + */ +#define ATTRS(_impl) \ + reinterpret_cast<InternalAttr*>(&((_impl)->mBuffer[0])) + + +#define NS_IMPL_EXTRA_SIZE \ + ((sizeof(Impl) - sizeof(mImpl->mBuffer)) / sizeof(void*)) + +nsAttrAndChildArray::nsAttrAndChildArray() + : mImpl(nullptr) +{ +} + +nsAttrAndChildArray::~nsAttrAndChildArray() +{ + if (!mImpl) { + return; + } + + Clear(); + + free(mImpl); +} + +nsIContent* +nsAttrAndChildArray::GetSafeChildAt(uint32_t aPos) const +{ + if (aPos < ChildCount()) { + return ChildAt(aPos); + } + + return nullptr; +} + +nsIContent * const * +nsAttrAndChildArray::GetChildArray(uint32_t* aChildCount) const +{ + *aChildCount = ChildCount(); + + if (!*aChildCount) { + return nullptr; + } + + return reinterpret_cast<nsIContent**>(mImpl->mBuffer + AttrSlotsSize()); +} + +nsresult +nsAttrAndChildArray::InsertChildAt(nsIContent* aChild, uint32_t aPos) +{ + NS_ASSERTION(aChild, "nullchild"); + NS_ASSERTION(aPos <= ChildCount(), "out-of-bounds"); + + uint32_t offset = AttrSlotsSize(); + uint32_t childCount = ChildCount(); + + NS_ENSURE_TRUE(childCount < ATTRCHILD_ARRAY_MAX_CHILD_COUNT, + NS_ERROR_FAILURE); + + // First try to fit new child in existing childlist + if (mImpl && offset + childCount < mImpl->mBufferSize) { + void** pos = mImpl->mBuffer + offset + aPos; + if (childCount != aPos) { + memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*)); + } + SetChildAtPos(pos, aChild, aPos, childCount); + + SetChildCount(childCount + 1); + + return NS_OK; + } + + // Try to fit new child in existing buffer by compressing attrslots + if (offset && !mImpl->mBuffer[offset - ATTRSIZE]) { + // Compress away all empty slots while we're at it. This might not be the + // optimal thing to do. + uint32_t attrCount = NonMappedAttrCount(); + void** newStart = mImpl->mBuffer + attrCount * ATTRSIZE; + void** oldStart = mImpl->mBuffer + offset; + memmove(newStart, oldStart, aPos * sizeof(nsIContent*)); + memmove(&newStart[aPos + 1], &oldStart[aPos], + (childCount - aPos) * sizeof(nsIContent*)); + SetChildAtPos(newStart + aPos, aChild, aPos, childCount); + + SetAttrSlotAndChildCount(attrCount, childCount + 1); + + return NS_OK; + } + + // We can't fit in current buffer, Realloc time! + if (!GrowBy(1)) { + return NS_ERROR_OUT_OF_MEMORY; + } + + void** pos = mImpl->mBuffer + offset + aPos; + if (childCount != aPos) { + memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*)); + } + SetChildAtPos(pos, aChild, aPos, childCount); + + SetChildCount(childCount + 1); + + return NS_OK; +} + +void +nsAttrAndChildArray::RemoveChildAt(uint32_t aPos) +{ + // Just store the return value of TakeChildAt in an nsCOMPtr to + // trigger a release. + nsCOMPtr<nsIContent> child = TakeChildAt(aPos); +} + +already_AddRefed<nsIContent> +nsAttrAndChildArray::TakeChildAt(uint32_t aPos) +{ + NS_ASSERTION(aPos < ChildCount(), "out-of-bounds"); + + uint32_t childCount = ChildCount(); + void** pos = mImpl->mBuffer + AttrSlotsSize() + aPos; + nsIContent* child = static_cast<nsIContent*>(*pos); + if (child->mPreviousSibling) { + child->mPreviousSibling->mNextSibling = child->mNextSibling; + } + if (child->mNextSibling) { + child->mNextSibling->mPreviousSibling = child->mPreviousSibling; + } + child->mPreviousSibling = child->mNextSibling = nullptr; + + memmove(pos, pos + 1, (childCount - aPos - 1) * sizeof(nsIContent*)); + SetChildCount(childCount - 1); + + return dont_AddRef(child); +} + +int32_t +nsAttrAndChildArray::IndexOfChild(const nsINode* aPossibleChild) const +{ + if (!mImpl) { + return -1; + } + void** children = mImpl->mBuffer + AttrSlotsSize(); + // Use signed here since we compare count to cursor which has to be signed + int32_t i, count = ChildCount(); + + if (count >= CACHE_CHILD_LIMIT) { + int32_t cursor = GetIndexFromCache(this); + // Need to compare to count here since we may have removed children since + // the index was added to the cache. + // We're also relying on that GetIndexFromCache returns -1 if no cached + // index was found. + if (cursor >= count) { + cursor = -1; + } + + // Seek outward from the last found index. |inc| will change sign every + // run through the loop. |sign| just exists to make sure the absolute + // value of |inc| increases each time through. + int32_t inc = 1, sign = 1; + while (cursor >= 0 && cursor < count) { + if (children[cursor] == aPossibleChild) { + AddIndexToCache(this, cursor); + + return cursor; + } + + cursor += inc; + inc = -inc - sign; + sign = -sign; + } + + // We ran into one 'edge'. Add inc to cursor once more to get back to + // the 'side' where we still need to search, then step in the |sign| + // direction. + cursor += inc; + + if (sign > 0) { + for (; cursor < count; ++cursor) { + if (children[cursor] == aPossibleChild) { + AddIndexToCache(this, cursor); + + return static_cast<int32_t>(cursor); + } + } + } + else { + for (; cursor >= 0; --cursor) { + if (children[cursor] == aPossibleChild) { + AddIndexToCache(this, cursor); + + return static_cast<int32_t>(cursor); + } + } + } + + // The child wasn't even in the remaining children + return -1; + } + + for (i = 0; i < count; ++i) { + if (children[i] == aPossibleChild) { + return static_cast<int32_t>(i); + } + } + + return -1; +} + +uint32_t +nsAttrAndChildArray::AttrCount() const +{ + return NonMappedAttrCount() + MappedAttrCount(); +} + +const nsAttrValue* +nsAttrAndChildArray::GetAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const +{ + uint32_t i, slotCount = AttrSlotCount(); + if (aNamespaceID == kNameSpaceID_None) { + // This should be the common case so lets make an optimized loop + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) { + return &ATTRS(mImpl)[i].mValue; + } + } + + if (mImpl && mImpl->mMappedAttrs) { + return mImpl->mMappedAttrs->GetAttr(aLocalName); + } + } + else { + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) { + return &ATTRS(mImpl)[i].mValue; + } + } + } + + return nullptr; +} + +const nsAttrValue* +nsAttrAndChildArray::GetAttr(const nsAString& aLocalName) const +{ + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) { + return &ATTRS(mImpl)[i].mValue; + } + } + + if (mImpl && mImpl->mMappedAttrs) { + return mImpl->mMappedAttrs->GetAttr(aLocalName); + } + + return nullptr; +} + +const nsAttrValue* +nsAttrAndChildArray::GetAttr(const nsAString& aName, + nsCaseTreatment aCaseSensitive) const +{ + // Check whether someone is being silly and passing non-lowercase + // attr names. + if (aCaseSensitive == eIgnoreCase && + nsContentUtils::StringContainsASCIIUpper(aName)) { + // Try again with a lowercased name, but make sure we can't reenter this + // block by passing eCaseSensitive for aCaseSensitive. + nsAutoString lowercase; + nsContentUtils::ASCIIToLower(aName, lowercase); + return GetAttr(lowercase, eCaseMatters); + } + + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) { + return &ATTRS(mImpl)[i].mValue; + } + } + + if (mImpl && mImpl->mMappedAttrs) { + const nsAttrValue* val = + mImpl->mMappedAttrs->GetAttr(aName); + if (val) { + return val; + } + } + + return nullptr; +} + +const nsAttrValue* +nsAttrAndChildArray::AttrAt(uint32_t aPos) const +{ + NS_ASSERTION(aPos < AttrCount(), + "out-of-bounds access in nsAttrAndChildArray"); + + uint32_t nonmapped = NonMappedAttrCount(); + if (aPos < nonmapped) { + return &ATTRS(mImpl)[aPos].mValue; + } + + return mImpl->mMappedAttrs->AttrAt(aPos - nonmapped); +} + +nsresult +nsAttrAndChildArray::SetAndSwapAttr(nsIAtom* aLocalName, nsAttrValue& aValue) +{ + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) { + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue); + return NS_OK; + } + } + + NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT, + NS_ERROR_FAILURE); + + if (i == slotCount && !AddAttrSlot()) { + return NS_ERROR_OUT_OF_MEMORY; + } + + new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName); + new (&ATTRS(mImpl)[i].mValue) nsAttrValue(); + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue); + + return NS_OK; +} + +nsresult +nsAttrAndChildArray::SetAndSwapAttr(mozilla::dom::NodeInfo* aName, nsAttrValue& aValue) +{ + int32_t namespaceID = aName->NamespaceID(); + nsIAtom* localName = aName->NameAtom(); + if (namespaceID == kNameSpaceID_None) { + return SetAndSwapAttr(localName, aValue); + } + + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(localName, namespaceID)) { + ATTRS(mImpl)[i].mName.SetTo(aName); + ATTRS(mImpl)[i].mValue.Reset(); + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue); + + return NS_OK; + } + } + + NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT, + NS_ERROR_FAILURE); + + if (i == slotCount && !AddAttrSlot()) { + return NS_ERROR_OUT_OF_MEMORY; + } + + new (&ATTRS(mImpl)[i].mName) nsAttrName(aName); + new (&ATTRS(mImpl)[i].mValue) nsAttrValue(); + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue); + + return NS_OK; +} + + +nsresult +nsAttrAndChildArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue) +{ + NS_ASSERTION(aPos < AttrCount(), "out-of-bounds"); + + uint32_t nonmapped = NonMappedAttrCount(); + if (aPos < nonmapped) { + ATTRS(mImpl)[aPos].mValue.SwapValueWith(aValue); + ATTRS(mImpl)[aPos].~InternalAttr(); + + uint32_t slotCount = AttrSlotCount(); + memmove(&ATTRS(mImpl)[aPos], + &ATTRS(mImpl)[aPos + 1], + (slotCount - aPos - 1) * sizeof(InternalAttr)); + memset(&ATTRS(mImpl)[slotCount - 1], 0, sizeof(InternalAttr)); + + return NS_OK; + } + + if (MappedAttrCount() == 1) { + // We're removing the last mapped attribute. Can't swap in this + // case; have to copy. + aValue.SetTo(*mImpl->mMappedAttrs->AttrAt(0)); + NS_RELEASE(mImpl->mMappedAttrs); + + return NS_OK; + } + + RefPtr<nsMappedAttributes> mapped = + GetModifiableMapped(nullptr, nullptr, false); + + mapped->RemoveAttrAt(aPos - nonmapped, aValue); + + return MakeMappedUnique(mapped); +} + +mozilla::dom::BorrowedAttrInfo +nsAttrAndChildArray::AttrInfoAt(uint32_t aPos) const +{ + NS_ASSERTION(aPos < AttrCount(), + "out-of-bounds access in nsAttrAndChildArray"); + + uint32_t nonmapped = NonMappedAttrCount(); + if (aPos < nonmapped) { + return BorrowedAttrInfo(&ATTRS(mImpl)[aPos].mName, &ATTRS(mImpl)[aPos].mValue); + } + + return BorrowedAttrInfo(mImpl->mMappedAttrs->NameAt(aPos - nonmapped), + mImpl->mMappedAttrs->AttrAt(aPos - nonmapped)); +} + +const nsAttrName* +nsAttrAndChildArray::AttrNameAt(uint32_t aPos) const +{ + NS_ASSERTION(aPos < AttrCount(), + "out-of-bounds access in nsAttrAndChildArray"); + + uint32_t nonmapped = NonMappedAttrCount(); + if (aPos < nonmapped) { + return &ATTRS(mImpl)[aPos].mName; + } + + return mImpl->mMappedAttrs->NameAt(aPos - nonmapped); +} + +const nsAttrName* +nsAttrAndChildArray::GetSafeAttrNameAt(uint32_t aPos) const +{ + uint32_t nonmapped = NonMappedAttrCount(); + if (aPos < nonmapped) { + void** pos = mImpl->mBuffer + aPos * ATTRSIZE; + if (!*pos) { + return nullptr; + } + + return &reinterpret_cast<InternalAttr*>(pos)->mName; + } + + if (aPos >= AttrCount()) { + return nullptr; + } + + return mImpl->mMappedAttrs->NameAt(aPos - nonmapped); +} + +const nsAttrName* +nsAttrAndChildArray::GetExistingAttrNameFromQName(const nsAString& aName) const +{ + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) { + return &ATTRS(mImpl)[i].mName; + } + } + + if (mImpl && mImpl->mMappedAttrs) { + return mImpl->mMappedAttrs->GetExistingAttrNameFromQName(aName); + } + + return nullptr; +} + +int32_t +nsAttrAndChildArray::IndexOfAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const +{ + int32_t idx; + if (mImpl && mImpl->mMappedAttrs && aNamespaceID == kNameSpaceID_None) { + idx = mImpl->mMappedAttrs->IndexOfAttr(aLocalName); + if (idx >= 0) { + return NonMappedAttrCount() + idx; + } + } + + uint32_t i; + uint32_t slotCount = AttrSlotCount(); + if (aNamespaceID == kNameSpaceID_None) { + // This should be the common case so lets make an optimized loop + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) { + return i; + } + } + } + else { + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) { + return i; + } + } + } + + return -1; +} + +nsresult +nsAttrAndChildArray::SetAndTakeMappedAttr(nsIAtom* aLocalName, + nsAttrValue& aValue, + nsMappedAttributeElement* aContent, + nsHTMLStyleSheet* aSheet) +{ + bool willAdd = true; + if (mImpl && mImpl->mMappedAttrs) { + willAdd = !mImpl->mMappedAttrs->GetAttr(aLocalName); + } + + RefPtr<nsMappedAttributes> mapped = + GetModifiableMapped(aContent, aSheet, willAdd); + + mapped->SetAndTakeAttr(aLocalName, aValue); + + return MakeMappedUnique(mapped); +} + +nsresult +nsAttrAndChildArray::DoSetMappedAttrStyleSheet(nsHTMLStyleSheet* aSheet) +{ + NS_PRECONDITION(mImpl && mImpl->mMappedAttrs, + "Should have mapped attrs here!"); + if (aSheet == mImpl->mMappedAttrs->GetStyleSheet()) { + return NS_OK; + } + + RefPtr<nsMappedAttributes> mapped = + GetModifiableMapped(nullptr, nullptr, false); + + mapped->SetStyleSheet(aSheet); + + return MakeMappedUnique(mapped); +} + +void +nsAttrAndChildArray::WalkMappedAttributeStyleRules(nsRuleWalker* aRuleWalker) +{ + if (mImpl && mImpl->mMappedAttrs) { + aRuleWalker->Forward(mImpl->mMappedAttrs); + } +} + +void +nsAttrAndChildArray::Compact() +{ + if (!mImpl) { + return; + } + + // First compress away empty attrslots + uint32_t slotCount = AttrSlotCount(); + uint32_t attrCount = NonMappedAttrCount(); + uint32_t childCount = ChildCount(); + + if (attrCount < slotCount) { + memmove(mImpl->mBuffer + attrCount * ATTRSIZE, + mImpl->mBuffer + slotCount * ATTRSIZE, + childCount * sizeof(nsIContent*)); + SetAttrSlotCount(attrCount); + } + + // Then resize or free buffer + uint32_t newSize = attrCount * ATTRSIZE + childCount; + if (!newSize && !mImpl->mMappedAttrs) { + free(mImpl); + mImpl = nullptr; + } + else if (newSize < mImpl->mBufferSize) { + mImpl = static_cast<Impl*>(realloc(mImpl, (newSize + NS_IMPL_EXTRA_SIZE) * sizeof(nsIContent*))); + NS_ASSERTION(mImpl, "failed to reallocate to smaller buffer"); + + mImpl->mBufferSize = newSize; + } +} + +void +nsAttrAndChildArray::Clear() +{ + if (!mImpl) { + return; + } + + if (mImpl->mMappedAttrs) { + NS_RELEASE(mImpl->mMappedAttrs); + } + + uint32_t i, slotCount = AttrSlotCount(); + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + ATTRS(mImpl)[i].~InternalAttr(); + } + + nsAutoScriptBlocker scriptBlocker; + uint32_t end = slotCount * ATTRSIZE + ChildCount(); + for (i = slotCount * ATTRSIZE; i < end; ++i) { + nsIContent* child = static_cast<nsIContent*>(mImpl->mBuffer[i]); + // making this false so tree teardown doesn't end up being + // O(N*D) (number of nodes times average depth of tree). + child->UnbindFromTree(false); // XXX is it better to let the owner do this? + // Make sure to unlink our kids from each other, since someone + // else could stil be holding references to some of them. + + // XXXbz We probably can't push this assignment down into the |aNullParent| + // case of UnbindFromTree because we still need the assignment in + // RemoveChildAt. In particular, ContentRemoved fires between + // RemoveChildAt and UnbindFromTree, and in ContentRemoved the sibling + // chain needs to be correct. Though maybe we could set the prev and next + // to point to each other but keep the kid being removed pointing to them + // through ContentRemoved so consumers can find where it used to be in the + // list? + child->mPreviousSibling = child->mNextSibling = nullptr; + NS_RELEASE(child); + } + + SetAttrSlotAndChildCount(0, 0); +} + +uint32_t +nsAttrAndChildArray::NonMappedAttrCount() const +{ + if (!mImpl) { + return 0; + } + + uint32_t count = AttrSlotCount(); + while (count > 0 && !mImpl->mBuffer[(count - 1) * ATTRSIZE]) { + --count; + } + + return count; +} + +uint32_t +nsAttrAndChildArray::MappedAttrCount() const +{ + return mImpl && mImpl->mMappedAttrs ? (uint32_t)mImpl->mMappedAttrs->Count() : 0; +} + +nsMappedAttributes* +nsAttrAndChildArray::GetModifiableMapped(nsMappedAttributeElement* aContent, + nsHTMLStyleSheet* aSheet, + bool aWillAddAttr) +{ + if (mImpl && mImpl->mMappedAttrs) { + return mImpl->mMappedAttrs->Clone(aWillAddAttr); + } + + MOZ_ASSERT(aContent, "Trying to create modifiable without content"); + + nsMapRuleToAttributesFunc mapRuleFunc = + aContent->GetAttributeMappingFunction(); + return new nsMappedAttributes(aSheet, mapRuleFunc); +} + +nsresult +nsAttrAndChildArray::MakeMappedUnique(nsMappedAttributes* aAttributes) +{ + NS_ASSERTION(aAttributes, "missing attributes"); + + if (!mImpl && !GrowBy(1)) { + return NS_ERROR_OUT_OF_MEMORY; + } + + if (!aAttributes->GetStyleSheet()) { + // This doesn't currently happen, but it could if we do loading right + + RefPtr<nsMappedAttributes> mapped(aAttributes); + mapped.swap(mImpl->mMappedAttrs); + + return NS_OK; + } + + RefPtr<nsMappedAttributes> mapped = + aAttributes->GetStyleSheet()->UniqueMappedAttributes(aAttributes); + NS_ENSURE_TRUE(mapped, NS_ERROR_OUT_OF_MEMORY); + + if (mapped != aAttributes) { + // Reset the stylesheet of aAttributes so that it doesn't spend time + // trying to remove itself from the hash. There is no risk that aAttributes + // is in the hash since it will always have come from GetModifiableMapped, + // which never returns maps that are in the hash (such hashes are by + // nature not modifiable). + aAttributes->DropStyleSheetReference(); + } + mapped.swap(mImpl->mMappedAttrs); + + return NS_OK; +} + + +bool +nsAttrAndChildArray::GrowBy(uint32_t aGrowSize) +{ + CheckedUint32 size = 0; + if (mImpl) { + size += mImpl->mBufferSize; + size += NS_IMPL_EXTRA_SIZE; + if (!size.isValid()) { + return false; + } + } + + CheckedUint32 minSize = size.value(); + minSize += aGrowSize; + if (!minSize.isValid()) { + return false; + } + + if (minSize.value() <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) { + do { + size += ATTRCHILD_ARRAY_GROWSIZE; + if (!size.isValid()) { + return false; + } + } while (size.value() < minSize.value()); + } + else { + uint32_t shift = mozilla::CeilingLog2(minSize.value()); + if (shift >= 32) { + return false; + } + + size = 1u << shift; + } + + bool needToInitialize = !mImpl; + CheckedUint32 neededSize = size; + neededSize *= sizeof(void*); + if (!neededSize.isValid()) { + return false; + } + + Impl* newImpl = static_cast<Impl*>(realloc(mImpl, neededSize.value())); + NS_ENSURE_TRUE(newImpl, false); + + mImpl = newImpl; + + // Set initial counts if we didn't have a buffer before + if (needToInitialize) { + mImpl->mMappedAttrs = nullptr; + SetAttrSlotAndChildCount(0, 0); + } + + mImpl->mBufferSize = size.value() - NS_IMPL_EXTRA_SIZE; + + return true; +} + +bool +nsAttrAndChildArray::AddAttrSlot() +{ + uint32_t slotCount = AttrSlotCount(); + uint32_t childCount = ChildCount(); + + CheckedUint32 size = slotCount; + size += 1; + size *= ATTRSIZE; + size += childCount; + if (!size.isValid()) { + return false; + } + + // Grow buffer if needed + if (!(mImpl && mImpl->mBufferSize >= size.value()) && + !GrowBy(ATTRSIZE)) { + return false; + } + + void** offset = mImpl->mBuffer + slotCount * ATTRSIZE; + + if (childCount > 0) { + memmove(&ATTRS(mImpl)[slotCount + 1], &ATTRS(mImpl)[slotCount], + childCount * sizeof(nsIContent*)); + } + + SetAttrSlotCount(slotCount + 1); + offset[0] = nullptr; + offset[1] = nullptr; + + return true; +} + +inline void +nsAttrAndChildArray::SetChildAtPos(void** aPos, nsIContent* aChild, + uint32_t aIndex, uint32_t aChildCount) +{ + NS_PRECONDITION(!aChild->GetNextSibling(), "aChild with next sibling?"); + NS_PRECONDITION(!aChild->GetPreviousSibling(), "aChild with prev sibling?"); + + *aPos = aChild; + NS_ADDREF(aChild); + if (aIndex != 0) { + nsIContent* previous = static_cast<nsIContent*>(*(aPos - 1)); + aChild->mPreviousSibling = previous; + previous->mNextSibling = aChild; + } + if (aIndex != aChildCount) { + nsIContent* next = static_cast<nsIContent*>(*(aPos + 1)); + aChild->mNextSibling = next; + next->mPreviousSibling = aChild; + } +} + +size_t +nsAttrAndChildArray::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const +{ + size_t n = 0; + if (mImpl) { + // Don't add the size taken by *mMappedAttrs because it's shared. + + n += aMallocSizeOf(mImpl); + + uint32_t slotCount = AttrSlotCount(); + for (uint32_t i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) { + nsAttrValue* value = &ATTRS(mImpl)[i].mValue; + n += value->SizeOfExcludingThis(aMallocSizeOf); + } + } + + return n; +} + |