1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/base/src/nsAttrAndChildArray.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,859 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +/*
1.10 + * Storage of the children and attributes of a DOM node; storage for
1.11 + * the two is unified to minimize footprint.
1.12 + */
1.13 +
1.14 +#include "nsAttrAndChildArray.h"
1.15 +
1.16 +#include "mozilla/MathAlgorithms.h"
1.17 +#include "mozilla/MemoryReporting.h"
1.18 +
1.19 +#include "nsMappedAttributeElement.h"
1.20 +#include "nsString.h"
1.21 +#include "nsHTMLStyleSheet.h"
1.22 +#include "nsRuleWalker.h"
1.23 +#include "nsMappedAttributes.h"
1.24 +#include "nsUnicharUtils.h"
1.25 +#include "nsAutoPtr.h"
1.26 +#include "nsContentUtils.h" // nsAutoScriptBlocker
1.27 +
1.28 +/*
1.29 +CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer.
1.30 +It should be small enough to not cause collisions between adjecent arrays, and
1.31 +large enough to make sure that all indexes are used. The size below is based
1.32 +on the size of the smallest possible element (currently 24[*] bytes) which is
1.33 +the smallest distance between two nsAttrAndChildArray. 24/(2^_5_) is 0.75.
1.34 +This means that two adjacent nsAttrAndChildArrays will overlap one in 4 times.
1.35 +However not all elements will have enough children to get cached. And any
1.36 +allocator that doesn't return addresses aligned to 64 bytes will ensure that
1.37 +any index will get used.
1.38 +
1.39 +[*] sizeof(Element) + 4 bytes for nsIDOMElement vtable pointer.
1.40 +*/
1.41 +
1.42 +#define CACHE_POINTER_SHIFT 5
1.43 +#define CACHE_NUM_SLOTS 128
1.44 +#define CACHE_CHILD_LIMIT 10
1.45 +
1.46 +#define CACHE_GET_INDEX(_array) \
1.47 + ((NS_PTR_TO_INT32(_array) >> CACHE_POINTER_SHIFT) & \
1.48 + (CACHE_NUM_SLOTS - 1))
1.49 +
1.50 +struct IndexCacheSlot
1.51 +{
1.52 + const nsAttrAndChildArray* array;
1.53 + int32_t index;
1.54 +};
1.55 +
1.56 +// This is inited to all zeroes since it's static. Though even if it wasn't
1.57 +// the worst thing that'd happen is a small inefficency if you'd get a false
1.58 +// positive cachehit.
1.59 +static IndexCacheSlot indexCache[CACHE_NUM_SLOTS];
1.60 +
1.61 +static
1.62 +inline
1.63 +void
1.64 +AddIndexToCache(const nsAttrAndChildArray* aArray, int32_t aIndex)
1.65 +{
1.66 + uint32_t ix = CACHE_GET_INDEX(aArray);
1.67 + indexCache[ix].array = aArray;
1.68 + indexCache[ix].index = aIndex;
1.69 +}
1.70 +
1.71 +static
1.72 +inline
1.73 +int32_t
1.74 +GetIndexFromCache(const nsAttrAndChildArray* aArray)
1.75 +{
1.76 + uint32_t ix = CACHE_GET_INDEX(aArray);
1.77 + return indexCache[ix].array == aArray ? indexCache[ix].index : -1;
1.78 +}
1.79 +
1.80 +
1.81 +/**
1.82 + * Due to a compiler bug in VisualAge C++ for AIX, we need to return the
1.83 + * address of the first index into mBuffer here, instead of simply returning
1.84 + * mBuffer itself.
1.85 + *
1.86 + * See Bug 231104 for more information.
1.87 + */
1.88 +#define ATTRS(_impl) \
1.89 + reinterpret_cast<InternalAttr*>(&((_impl)->mBuffer[0]))
1.90 +
1.91 +
1.92 +#define NS_IMPL_EXTRA_SIZE \
1.93 + ((sizeof(Impl) - sizeof(mImpl->mBuffer)) / sizeof(void*))
1.94 +
1.95 +nsAttrAndChildArray::nsAttrAndChildArray()
1.96 + : mImpl(nullptr)
1.97 +{
1.98 +}
1.99 +
1.100 +nsAttrAndChildArray::~nsAttrAndChildArray()
1.101 +{
1.102 + if (!mImpl) {
1.103 + return;
1.104 + }
1.105 +
1.106 + Clear();
1.107 +
1.108 + moz_free(mImpl);
1.109 +}
1.110 +
1.111 +nsIContent*
1.112 +nsAttrAndChildArray::GetSafeChildAt(uint32_t aPos) const
1.113 +{
1.114 + if (aPos < ChildCount()) {
1.115 + return ChildAt(aPos);
1.116 + }
1.117 +
1.118 + return nullptr;
1.119 +}
1.120 +
1.121 +nsIContent * const *
1.122 +nsAttrAndChildArray::GetChildArray(uint32_t* aChildCount) const
1.123 +{
1.124 + *aChildCount = ChildCount();
1.125 +
1.126 + if (!*aChildCount) {
1.127 + return nullptr;
1.128 + }
1.129 +
1.130 + return reinterpret_cast<nsIContent**>(mImpl->mBuffer + AttrSlotsSize());
1.131 +}
1.132 +
1.133 +nsresult
1.134 +nsAttrAndChildArray::InsertChildAt(nsIContent* aChild, uint32_t aPos)
1.135 +{
1.136 + NS_ASSERTION(aChild, "nullchild");
1.137 + NS_ASSERTION(aPos <= ChildCount(), "out-of-bounds");
1.138 +
1.139 + uint32_t offset = AttrSlotsSize();
1.140 + uint32_t childCount = ChildCount();
1.141 +
1.142 + NS_ENSURE_TRUE(childCount < ATTRCHILD_ARRAY_MAX_CHILD_COUNT,
1.143 + NS_ERROR_FAILURE);
1.144 +
1.145 + // First try to fit new child in existing childlist
1.146 + if (mImpl && offset + childCount < mImpl->mBufferSize) {
1.147 + void** pos = mImpl->mBuffer + offset + aPos;
1.148 + if (childCount != aPos) {
1.149 + memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
1.150 + }
1.151 + SetChildAtPos(pos, aChild, aPos, childCount);
1.152 +
1.153 + SetChildCount(childCount + 1);
1.154 +
1.155 + return NS_OK;
1.156 + }
1.157 +
1.158 + // Try to fit new child in existing buffer by compressing attrslots
1.159 + if (offset && !mImpl->mBuffer[offset - ATTRSIZE]) {
1.160 + // Compress away all empty slots while we're at it. This might not be the
1.161 + // optimal thing to do.
1.162 + uint32_t attrCount = NonMappedAttrCount();
1.163 + void** newStart = mImpl->mBuffer + attrCount * ATTRSIZE;
1.164 + void** oldStart = mImpl->mBuffer + offset;
1.165 + memmove(newStart, oldStart, aPos * sizeof(nsIContent*));
1.166 + memmove(&newStart[aPos + 1], &oldStart[aPos],
1.167 + (childCount - aPos) * sizeof(nsIContent*));
1.168 + SetChildAtPos(newStart + aPos, aChild, aPos, childCount);
1.169 +
1.170 + SetAttrSlotAndChildCount(attrCount, childCount + 1);
1.171 +
1.172 + return NS_OK;
1.173 + }
1.174 +
1.175 + // We can't fit in current buffer, Realloc time!
1.176 + if (!GrowBy(1)) {
1.177 + return NS_ERROR_OUT_OF_MEMORY;
1.178 + }
1.179 +
1.180 + void** pos = mImpl->mBuffer + offset + aPos;
1.181 + if (childCount != aPos) {
1.182 + memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
1.183 + }
1.184 + SetChildAtPos(pos, aChild, aPos, childCount);
1.185 +
1.186 + SetChildCount(childCount + 1);
1.187 +
1.188 + return NS_OK;
1.189 +}
1.190 +
1.191 +void
1.192 +nsAttrAndChildArray::RemoveChildAt(uint32_t aPos)
1.193 +{
1.194 + // Just store the return value of TakeChildAt in an nsCOMPtr to
1.195 + // trigger a release.
1.196 + nsCOMPtr<nsIContent> child = TakeChildAt(aPos);
1.197 +}
1.198 +
1.199 +already_AddRefed<nsIContent>
1.200 +nsAttrAndChildArray::TakeChildAt(uint32_t aPos)
1.201 +{
1.202 + NS_ASSERTION(aPos < ChildCount(), "out-of-bounds");
1.203 +
1.204 + uint32_t childCount = ChildCount();
1.205 + void** pos = mImpl->mBuffer + AttrSlotsSize() + aPos;
1.206 + nsIContent* child = static_cast<nsIContent*>(*pos);
1.207 + if (child->mPreviousSibling) {
1.208 + child->mPreviousSibling->mNextSibling = child->mNextSibling;
1.209 + }
1.210 + if (child->mNextSibling) {
1.211 + child->mNextSibling->mPreviousSibling = child->mPreviousSibling;
1.212 + }
1.213 + child->mPreviousSibling = child->mNextSibling = nullptr;
1.214 +
1.215 + memmove(pos, pos + 1, (childCount - aPos - 1) * sizeof(nsIContent*));
1.216 + SetChildCount(childCount - 1);
1.217 +
1.218 + return dont_AddRef(child);
1.219 +}
1.220 +
1.221 +int32_t
1.222 +nsAttrAndChildArray::IndexOfChild(const nsINode* aPossibleChild) const
1.223 +{
1.224 + if (!mImpl) {
1.225 + return -1;
1.226 + }
1.227 + void** children = mImpl->mBuffer + AttrSlotsSize();
1.228 + // Use signed here since we compare count to cursor which has to be signed
1.229 + int32_t i, count = ChildCount();
1.230 +
1.231 + if (count >= CACHE_CHILD_LIMIT) {
1.232 + int32_t cursor = GetIndexFromCache(this);
1.233 + // Need to compare to count here since we may have removed children since
1.234 + // the index was added to the cache.
1.235 + // We're also relying on that GetIndexFromCache returns -1 if no cached
1.236 + // index was found.
1.237 + if (cursor >= count) {
1.238 + cursor = -1;
1.239 + }
1.240 +
1.241 + // Seek outward from the last found index. |inc| will change sign every
1.242 + // run through the loop. |sign| just exists to make sure the absolute
1.243 + // value of |inc| increases each time through.
1.244 + int32_t inc = 1, sign = 1;
1.245 + while (cursor >= 0 && cursor < count) {
1.246 + if (children[cursor] == aPossibleChild) {
1.247 + AddIndexToCache(this, cursor);
1.248 +
1.249 + return cursor;
1.250 + }
1.251 +
1.252 + cursor += inc;
1.253 + inc = -inc - sign;
1.254 + sign = -sign;
1.255 + }
1.256 +
1.257 + // We ran into one 'edge'. Add inc to cursor once more to get back to
1.258 + // the 'side' where we still need to search, then step in the |sign|
1.259 + // direction.
1.260 + cursor += inc;
1.261 +
1.262 + if (sign > 0) {
1.263 + for (; cursor < count; ++cursor) {
1.264 + if (children[cursor] == aPossibleChild) {
1.265 + AddIndexToCache(this, cursor);
1.266 +
1.267 + return static_cast<int32_t>(cursor);
1.268 + }
1.269 + }
1.270 + }
1.271 + else {
1.272 + for (; cursor >= 0; --cursor) {
1.273 + if (children[cursor] == aPossibleChild) {
1.274 + AddIndexToCache(this, cursor);
1.275 +
1.276 + return static_cast<int32_t>(cursor);
1.277 + }
1.278 + }
1.279 + }
1.280 +
1.281 + // The child wasn't even in the remaining children
1.282 + return -1;
1.283 + }
1.284 +
1.285 + for (i = 0; i < count; ++i) {
1.286 + if (children[i] == aPossibleChild) {
1.287 + return static_cast<int32_t>(i);
1.288 + }
1.289 + }
1.290 +
1.291 + return -1;
1.292 +}
1.293 +
1.294 +uint32_t
1.295 +nsAttrAndChildArray::AttrCount() const
1.296 +{
1.297 + return NonMappedAttrCount() + MappedAttrCount();
1.298 +}
1.299 +
1.300 +const nsAttrValue*
1.301 +nsAttrAndChildArray::GetAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
1.302 +{
1.303 + uint32_t i, slotCount = AttrSlotCount();
1.304 + if (aNamespaceID == kNameSpaceID_None) {
1.305 + // This should be the common case so lets make an optimized loop
1.306 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.307 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
1.308 + return &ATTRS(mImpl)[i].mValue;
1.309 + }
1.310 + }
1.311 +
1.312 + if (mImpl && mImpl->mMappedAttrs) {
1.313 + return mImpl->mMappedAttrs->GetAttr(aLocalName);
1.314 + }
1.315 + }
1.316 + else {
1.317 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.318 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
1.319 + return &ATTRS(mImpl)[i].mValue;
1.320 + }
1.321 + }
1.322 + }
1.323 +
1.324 + return nullptr;
1.325 +}
1.326 +
1.327 +const nsAttrValue*
1.328 +nsAttrAndChildArray::GetAttr(const nsAString& aLocalName) const
1.329 +{
1.330 + uint32_t i, slotCount = AttrSlotCount();
1.331 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.332 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
1.333 + return &ATTRS(mImpl)[i].mValue;
1.334 + }
1.335 + }
1.336 +
1.337 + if (mImpl && mImpl->mMappedAttrs) {
1.338 + return mImpl->mMappedAttrs->GetAttr(aLocalName);
1.339 + }
1.340 +
1.341 + return nullptr;
1.342 +}
1.343 +
1.344 +const nsAttrValue*
1.345 +nsAttrAndChildArray::GetAttr(const nsAString& aName,
1.346 + nsCaseTreatment aCaseSensitive) const
1.347 +{
1.348 + // Check whether someone is being silly and passing non-lowercase
1.349 + // attr names.
1.350 + if (aCaseSensitive == eIgnoreCase &&
1.351 + nsContentUtils::StringContainsASCIIUpper(aName)) {
1.352 + // Try again with a lowercased name, but make sure we can't reenter this
1.353 + // block by passing eCaseSensitive for aCaseSensitive.
1.354 + nsAutoString lowercase;
1.355 + nsContentUtils::ASCIIToLower(aName, lowercase);
1.356 + return GetAttr(lowercase, eCaseMatters);
1.357 + }
1.358 +
1.359 + uint32_t i, slotCount = AttrSlotCount();
1.360 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.361 + if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
1.362 + return &ATTRS(mImpl)[i].mValue;
1.363 + }
1.364 + }
1.365 +
1.366 + if (mImpl && mImpl->mMappedAttrs) {
1.367 + const nsAttrValue* val =
1.368 + mImpl->mMappedAttrs->GetAttr(aName);
1.369 + if (val) {
1.370 + return val;
1.371 + }
1.372 + }
1.373 +
1.374 + return nullptr;
1.375 +}
1.376 +
1.377 +const nsAttrValue*
1.378 +nsAttrAndChildArray::AttrAt(uint32_t aPos) const
1.379 +{
1.380 + NS_ASSERTION(aPos < AttrCount(),
1.381 + "out-of-bounds access in nsAttrAndChildArray");
1.382 +
1.383 + uint32_t mapped = MappedAttrCount();
1.384 + if (aPos < mapped) {
1.385 + return mImpl->mMappedAttrs->AttrAt(aPos);
1.386 + }
1.387 +
1.388 + return &ATTRS(mImpl)[aPos - mapped].mValue;
1.389 +}
1.390 +
1.391 +nsresult
1.392 +nsAttrAndChildArray::SetAndTakeAttr(nsIAtom* aLocalName, nsAttrValue& aValue)
1.393 +{
1.394 + uint32_t i, slotCount = AttrSlotCount();
1.395 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.396 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
1.397 + ATTRS(mImpl)[i].mValue.Reset();
1.398 + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
1.399 +
1.400 + return NS_OK;
1.401 + }
1.402 + }
1.403 +
1.404 + NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
1.405 + NS_ERROR_FAILURE);
1.406 +
1.407 + if (i == slotCount && !AddAttrSlot()) {
1.408 + return NS_ERROR_OUT_OF_MEMORY;
1.409 + }
1.410 +
1.411 + new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName);
1.412 + new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
1.413 + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
1.414 +
1.415 + return NS_OK;
1.416 +}
1.417 +
1.418 +nsresult
1.419 +nsAttrAndChildArray::SetAndTakeAttr(nsINodeInfo* aName, nsAttrValue& aValue)
1.420 +{
1.421 + int32_t namespaceID = aName->NamespaceID();
1.422 + nsIAtom* localName = aName->NameAtom();
1.423 + if (namespaceID == kNameSpaceID_None) {
1.424 + return SetAndTakeAttr(localName, aValue);
1.425 + }
1.426 +
1.427 + uint32_t i, slotCount = AttrSlotCount();
1.428 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.429 + if (ATTRS(mImpl)[i].mName.Equals(localName, namespaceID)) {
1.430 + ATTRS(mImpl)[i].mName.SetTo(aName);
1.431 + ATTRS(mImpl)[i].mValue.Reset();
1.432 + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
1.433 +
1.434 + return NS_OK;
1.435 + }
1.436 + }
1.437 +
1.438 + NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
1.439 + NS_ERROR_FAILURE);
1.440 +
1.441 + if (i == slotCount && !AddAttrSlot()) {
1.442 + return NS_ERROR_OUT_OF_MEMORY;
1.443 + }
1.444 +
1.445 + new (&ATTRS(mImpl)[i].mName) nsAttrName(aName);
1.446 + new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
1.447 + ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
1.448 +
1.449 + return NS_OK;
1.450 +}
1.451 +
1.452 +
1.453 +nsresult
1.454 +nsAttrAndChildArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue)
1.455 +{
1.456 + NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
1.457 +
1.458 + uint32_t mapped = MappedAttrCount();
1.459 + if (aPos < mapped) {
1.460 + if (mapped == 1) {
1.461 + // We're removing the last mapped attribute. Can't swap in this
1.462 + // case; have to copy.
1.463 + aValue.SetTo(*mImpl->mMappedAttrs->AttrAt(0));
1.464 + NS_RELEASE(mImpl->mMappedAttrs);
1.465 +
1.466 + return NS_OK;
1.467 + }
1.468 +
1.469 + nsRefPtr<nsMappedAttributes> mapped =
1.470 + GetModifiableMapped(nullptr, nullptr, false);
1.471 +
1.472 + mapped->RemoveAttrAt(aPos, aValue);
1.473 +
1.474 + return MakeMappedUnique(mapped);
1.475 + }
1.476 +
1.477 + aPos -= mapped;
1.478 + ATTRS(mImpl)[aPos].mValue.SwapValueWith(aValue);
1.479 + ATTRS(mImpl)[aPos].~InternalAttr();
1.480 +
1.481 + uint32_t slotCount = AttrSlotCount();
1.482 + memmove(&ATTRS(mImpl)[aPos],
1.483 + &ATTRS(mImpl)[aPos + 1],
1.484 + (slotCount - aPos - 1) * sizeof(InternalAttr));
1.485 + memset(&ATTRS(mImpl)[slotCount - 1], 0, sizeof(InternalAttr));
1.486 +
1.487 + return NS_OK;
1.488 +}
1.489 +
1.490 +const nsAttrName*
1.491 +nsAttrAndChildArray::AttrNameAt(uint32_t aPos) const
1.492 +{
1.493 + NS_ASSERTION(aPos < AttrCount(),
1.494 + "out-of-bounds access in nsAttrAndChildArray");
1.495 +
1.496 + uint32_t mapped = MappedAttrCount();
1.497 + if (aPos < mapped) {
1.498 + return mImpl->mMappedAttrs->NameAt(aPos);
1.499 + }
1.500 +
1.501 + return &ATTRS(mImpl)[aPos - mapped].mName;
1.502 +}
1.503 +
1.504 +const nsAttrName*
1.505 +nsAttrAndChildArray::GetSafeAttrNameAt(uint32_t aPos) const
1.506 +{
1.507 + uint32_t mapped = MappedAttrCount();
1.508 + if (aPos < mapped) {
1.509 + return mImpl->mMappedAttrs->NameAt(aPos);
1.510 + }
1.511 +
1.512 + aPos -= mapped;
1.513 + if (aPos >= AttrSlotCount()) {
1.514 + return nullptr;
1.515 + }
1.516 +
1.517 + void** pos = mImpl->mBuffer + aPos * ATTRSIZE;
1.518 + if (!*pos) {
1.519 + return nullptr;
1.520 + }
1.521 +
1.522 + return &reinterpret_cast<InternalAttr*>(pos)->mName;
1.523 +}
1.524 +
1.525 +const nsAttrName*
1.526 +nsAttrAndChildArray::GetExistingAttrNameFromQName(const nsAString& aName) const
1.527 +{
1.528 + uint32_t i, slotCount = AttrSlotCount();
1.529 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.530 + if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
1.531 + return &ATTRS(mImpl)[i].mName;
1.532 + }
1.533 + }
1.534 +
1.535 + if (mImpl && mImpl->mMappedAttrs) {
1.536 + return mImpl->mMappedAttrs->GetExistingAttrNameFromQName(aName);
1.537 + }
1.538 +
1.539 + return nullptr;
1.540 +}
1.541 +
1.542 +int32_t
1.543 +nsAttrAndChildArray::IndexOfAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
1.544 +{
1.545 + int32_t idx;
1.546 + if (mImpl && mImpl->mMappedAttrs && aNamespaceID == kNameSpaceID_None) {
1.547 + idx = mImpl->mMappedAttrs->IndexOfAttr(aLocalName);
1.548 + if (idx >= 0) {
1.549 + return idx;
1.550 + }
1.551 + }
1.552 +
1.553 + uint32_t i;
1.554 + uint32_t mapped = MappedAttrCount();
1.555 + uint32_t slotCount = AttrSlotCount();
1.556 + if (aNamespaceID == kNameSpaceID_None) {
1.557 + // This should be the common case so lets make an optimized loop
1.558 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.559 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
1.560 + return i + mapped;
1.561 + }
1.562 + }
1.563 + }
1.564 + else {
1.565 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.566 + if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
1.567 + return i + mapped;
1.568 + }
1.569 + }
1.570 + }
1.571 +
1.572 + return -1;
1.573 +}
1.574 +
1.575 +nsresult
1.576 +nsAttrAndChildArray::SetAndTakeMappedAttr(nsIAtom* aLocalName,
1.577 + nsAttrValue& aValue,
1.578 + nsMappedAttributeElement* aContent,
1.579 + nsHTMLStyleSheet* aSheet)
1.580 +{
1.581 + bool willAdd = true;
1.582 + if (mImpl && mImpl->mMappedAttrs) {
1.583 + willAdd = !mImpl->mMappedAttrs->GetAttr(aLocalName);
1.584 + }
1.585 +
1.586 + nsRefPtr<nsMappedAttributes> mapped =
1.587 + GetModifiableMapped(aContent, aSheet, willAdd);
1.588 +
1.589 + mapped->SetAndTakeAttr(aLocalName, aValue);
1.590 +
1.591 + return MakeMappedUnique(mapped);
1.592 +}
1.593 +
1.594 +nsresult
1.595 +nsAttrAndChildArray::DoSetMappedAttrStyleSheet(nsHTMLStyleSheet* aSheet)
1.596 +{
1.597 + NS_PRECONDITION(mImpl && mImpl->mMappedAttrs,
1.598 + "Should have mapped attrs here!");
1.599 + if (aSheet == mImpl->mMappedAttrs->GetStyleSheet()) {
1.600 + return NS_OK;
1.601 + }
1.602 +
1.603 + nsRefPtr<nsMappedAttributes> mapped =
1.604 + GetModifiableMapped(nullptr, nullptr, false);
1.605 +
1.606 + mapped->SetStyleSheet(aSheet);
1.607 +
1.608 + return MakeMappedUnique(mapped);
1.609 +}
1.610 +
1.611 +void
1.612 +nsAttrAndChildArray::WalkMappedAttributeStyleRules(nsRuleWalker* aRuleWalker)
1.613 +{
1.614 + if (mImpl && mImpl->mMappedAttrs) {
1.615 + aRuleWalker->Forward(mImpl->mMappedAttrs);
1.616 + }
1.617 +}
1.618 +
1.619 +void
1.620 +nsAttrAndChildArray::Compact()
1.621 +{
1.622 + if (!mImpl) {
1.623 + return;
1.624 + }
1.625 +
1.626 + // First compress away empty attrslots
1.627 + uint32_t slotCount = AttrSlotCount();
1.628 + uint32_t attrCount = NonMappedAttrCount();
1.629 + uint32_t childCount = ChildCount();
1.630 +
1.631 + if (attrCount < slotCount) {
1.632 + memmove(mImpl->mBuffer + attrCount * ATTRSIZE,
1.633 + mImpl->mBuffer + slotCount * ATTRSIZE,
1.634 + childCount * sizeof(nsIContent*));
1.635 + SetAttrSlotCount(attrCount);
1.636 + }
1.637 +
1.638 + // Then resize or free buffer
1.639 + uint32_t newSize = attrCount * ATTRSIZE + childCount;
1.640 + if (!newSize && !mImpl->mMappedAttrs) {
1.641 + moz_free(mImpl);
1.642 + mImpl = nullptr;
1.643 + }
1.644 + else if (newSize < mImpl->mBufferSize) {
1.645 + mImpl = static_cast<Impl*>(moz_realloc(mImpl, (newSize + NS_IMPL_EXTRA_SIZE) * sizeof(nsIContent*)));
1.646 + NS_ASSERTION(mImpl, "failed to reallocate to smaller buffer");
1.647 +
1.648 + mImpl->mBufferSize = newSize;
1.649 + }
1.650 +}
1.651 +
1.652 +void
1.653 +nsAttrAndChildArray::Clear()
1.654 +{
1.655 + if (!mImpl) {
1.656 + return;
1.657 + }
1.658 +
1.659 + if (mImpl->mMappedAttrs) {
1.660 + NS_RELEASE(mImpl->mMappedAttrs);
1.661 + }
1.662 +
1.663 + uint32_t i, slotCount = AttrSlotCount();
1.664 + for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.665 + ATTRS(mImpl)[i].~InternalAttr();
1.666 + }
1.667 +
1.668 + nsAutoScriptBlocker scriptBlocker;
1.669 + uint32_t end = slotCount * ATTRSIZE + ChildCount();
1.670 + for (i = slotCount * ATTRSIZE; i < end; ++i) {
1.671 + nsIContent* child = static_cast<nsIContent*>(mImpl->mBuffer[i]);
1.672 + // making this false so tree teardown doesn't end up being
1.673 + // O(N*D) (number of nodes times average depth of tree).
1.674 + child->UnbindFromTree(false); // XXX is it better to let the owner do this?
1.675 + // Make sure to unlink our kids from each other, since someone
1.676 + // else could stil be holding references to some of them.
1.677 +
1.678 + // XXXbz We probably can't push this assignment down into the |aNullParent|
1.679 + // case of UnbindFromTree because we still need the assignment in
1.680 + // RemoveChildAt. In particular, ContentRemoved fires between
1.681 + // RemoveChildAt and UnbindFromTree, and in ContentRemoved the sibling
1.682 + // chain needs to be correct. Though maybe we could set the prev and next
1.683 + // to point to each other but keep the kid being removed pointing to them
1.684 + // through ContentRemoved so consumers can find where it used to be in the
1.685 + // list?
1.686 + child->mPreviousSibling = child->mNextSibling = nullptr;
1.687 + NS_RELEASE(child);
1.688 + }
1.689 +
1.690 + SetAttrSlotAndChildCount(0, 0);
1.691 +}
1.692 +
1.693 +uint32_t
1.694 +nsAttrAndChildArray::NonMappedAttrCount() const
1.695 +{
1.696 + if (!mImpl) {
1.697 + return 0;
1.698 + }
1.699 +
1.700 + uint32_t count = AttrSlotCount();
1.701 + while (count > 0 && !mImpl->mBuffer[(count - 1) * ATTRSIZE]) {
1.702 + --count;
1.703 + }
1.704 +
1.705 + return count;
1.706 +}
1.707 +
1.708 +uint32_t
1.709 +nsAttrAndChildArray::MappedAttrCount() const
1.710 +{
1.711 + return mImpl && mImpl->mMappedAttrs ? (uint32_t)mImpl->mMappedAttrs->Count() : 0;
1.712 +}
1.713 +
1.714 +nsMappedAttributes*
1.715 +nsAttrAndChildArray::GetModifiableMapped(nsMappedAttributeElement* aContent,
1.716 + nsHTMLStyleSheet* aSheet,
1.717 + bool aWillAddAttr)
1.718 +{
1.719 + if (mImpl && mImpl->mMappedAttrs) {
1.720 + return mImpl->mMappedAttrs->Clone(aWillAddAttr);
1.721 + }
1.722 +
1.723 + MOZ_ASSERT(aContent, "Trying to create modifiable without content");
1.724 +
1.725 + nsMapRuleToAttributesFunc mapRuleFunc =
1.726 + aContent->GetAttributeMappingFunction();
1.727 + return new nsMappedAttributes(aSheet, mapRuleFunc);
1.728 +}
1.729 +
1.730 +nsresult
1.731 +nsAttrAndChildArray::MakeMappedUnique(nsMappedAttributes* aAttributes)
1.732 +{
1.733 + NS_ASSERTION(aAttributes, "missing attributes");
1.734 +
1.735 + if (!mImpl && !GrowBy(1)) {
1.736 + return NS_ERROR_OUT_OF_MEMORY;
1.737 + }
1.738 +
1.739 + if (!aAttributes->GetStyleSheet()) {
1.740 + // This doesn't currently happen, but it could if we do loading right
1.741 +
1.742 + nsRefPtr<nsMappedAttributes> mapped(aAttributes);
1.743 + mapped.swap(mImpl->mMappedAttrs);
1.744 +
1.745 + return NS_OK;
1.746 + }
1.747 +
1.748 + nsRefPtr<nsMappedAttributes> mapped =
1.749 + aAttributes->GetStyleSheet()->UniqueMappedAttributes(aAttributes);
1.750 + NS_ENSURE_TRUE(mapped, NS_ERROR_OUT_OF_MEMORY);
1.751 +
1.752 + if (mapped != aAttributes) {
1.753 + // Reset the stylesheet of aAttributes so that it doesn't spend time
1.754 + // trying to remove itself from the hash. There is no risk that aAttributes
1.755 + // is in the hash since it will always have come from GetModifiableMapped,
1.756 + // which never returns maps that are in the hash (such hashes are by
1.757 + // nature not modifiable).
1.758 + aAttributes->DropStyleSheetReference();
1.759 + }
1.760 + mapped.swap(mImpl->mMappedAttrs);
1.761 +
1.762 + return NS_OK;
1.763 +}
1.764 +
1.765 +
1.766 +bool
1.767 +nsAttrAndChildArray::GrowBy(uint32_t aGrowSize)
1.768 +{
1.769 + uint32_t size = mImpl ? mImpl->mBufferSize + NS_IMPL_EXTRA_SIZE : 0;
1.770 + uint32_t minSize = size + aGrowSize;
1.771 +
1.772 + if (minSize <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) {
1.773 + do {
1.774 + size += ATTRCHILD_ARRAY_GROWSIZE;
1.775 + } while (size < minSize);
1.776 + }
1.777 + else {
1.778 + size = 1u << mozilla::CeilingLog2(minSize);
1.779 + }
1.780 +
1.781 + bool needToInitialize = !mImpl;
1.782 + Impl* newImpl = static_cast<Impl*>(moz_realloc(mImpl, size * sizeof(void*)));
1.783 + NS_ENSURE_TRUE(newImpl, false);
1.784 +
1.785 + mImpl = newImpl;
1.786 +
1.787 + // Set initial counts if we didn't have a buffer before
1.788 + if (needToInitialize) {
1.789 + mImpl->mMappedAttrs = nullptr;
1.790 + SetAttrSlotAndChildCount(0, 0);
1.791 + }
1.792 +
1.793 + mImpl->mBufferSize = size - NS_IMPL_EXTRA_SIZE;
1.794 +
1.795 + return true;
1.796 +}
1.797 +
1.798 +bool
1.799 +nsAttrAndChildArray::AddAttrSlot()
1.800 +{
1.801 + uint32_t slotCount = AttrSlotCount();
1.802 + uint32_t childCount = ChildCount();
1.803 +
1.804 + // Grow buffer if needed
1.805 + if (!(mImpl && mImpl->mBufferSize >= (slotCount + 1) * ATTRSIZE + childCount) &&
1.806 + !GrowBy(ATTRSIZE)) {
1.807 + return false;
1.808 + }
1.809 + void** offset = mImpl->mBuffer + slotCount * ATTRSIZE;
1.810 +
1.811 + if (childCount > 0) {
1.812 + memmove(&ATTRS(mImpl)[slotCount + 1], &ATTRS(mImpl)[slotCount],
1.813 + childCount * sizeof(nsIContent*));
1.814 + }
1.815 +
1.816 + SetAttrSlotCount(slotCount + 1);
1.817 + offset[0] = nullptr;
1.818 + offset[1] = nullptr;
1.819 +
1.820 + return true;
1.821 +}
1.822 +
1.823 +inline void
1.824 +nsAttrAndChildArray::SetChildAtPos(void** aPos, nsIContent* aChild,
1.825 + uint32_t aIndex, uint32_t aChildCount)
1.826 +{
1.827 + NS_PRECONDITION(!aChild->GetNextSibling(), "aChild with next sibling?");
1.828 + NS_PRECONDITION(!aChild->GetPreviousSibling(), "aChild with prev sibling?");
1.829 +
1.830 + *aPos = aChild;
1.831 + NS_ADDREF(aChild);
1.832 + if (aIndex != 0) {
1.833 + nsIContent* previous = static_cast<nsIContent*>(*(aPos - 1));
1.834 + aChild->mPreviousSibling = previous;
1.835 + previous->mNextSibling = aChild;
1.836 + }
1.837 + if (aIndex != aChildCount) {
1.838 + nsIContent* next = static_cast<nsIContent*>(*(aPos + 1));
1.839 + aChild->mNextSibling = next;
1.840 + next->mPreviousSibling = aChild;
1.841 + }
1.842 +}
1.843 +
1.844 +size_t
1.845 +nsAttrAndChildArray::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
1.846 +{
1.847 + size_t n = 0;
1.848 + if (mImpl) {
1.849 + // Don't add the size taken by *mMappedAttrs because it's shared.
1.850 +
1.851 + n += aMallocSizeOf(mImpl);
1.852 +
1.853 + uint32_t slotCount = AttrSlotCount();
1.854 + for (uint32_t i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
1.855 + nsAttrValue* value = &ATTRS(mImpl)[i].mValue;
1.856 + n += value->SizeOfExcludingThis(aMallocSizeOf);
1.857 + }
1.858 + }
1.859 +
1.860 + return n;
1.861 +}
1.862 +
