Line data Source code
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 : * Storage of the children and attributes of a DOM node; storage for
9 : * the two is unified to minimize footprint.
10 : */
11 :
12 : #include "nsAttrAndChildArray.h"
13 :
14 : #include "mozilla/CheckedInt.h"
15 : #include "mozilla/MathAlgorithms.h"
16 : #include "mozilla/MemoryReporting.h"
17 :
18 : #include "nsMappedAttributeElement.h"
19 : #include "nsString.h"
20 : #include "nsHTMLStyleSheet.h"
21 : #include "nsRuleWalker.h"
22 : #include "nsMappedAttributes.h"
23 : #include "nsUnicharUtils.h"
24 : #include "nsContentUtils.h" // nsAutoScriptBlocker
25 :
26 : using mozilla::CheckedUint32;
27 :
28 : /*
29 : CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer.
30 : It should be small enough to not cause collisions between adjecent arrays, and
31 : large enough to make sure that all indexes are used. The size below is based
32 : on the size of the smallest possible element (currently 24[*] bytes) which is
33 : the smallest distance between two nsAttrAndChildArray. 24/(2^_5_) is 0.75.
34 : This means that two adjacent nsAttrAndChildArrays will overlap one in 4 times.
35 : However not all elements will have enough children to get cached. And any
36 : allocator that doesn't return addresses aligned to 64 bytes will ensure that
37 : any index will get used.
38 :
39 : [*] sizeof(Element) + 4 bytes for nsIDOMElement vtable pointer.
40 : */
41 :
42 : #define CACHE_POINTER_SHIFT 5
43 : #define CACHE_NUM_SLOTS 128
44 : #define CACHE_CHILD_LIMIT 10
45 :
46 : #define CACHE_GET_INDEX(_array) \
47 : ((NS_PTR_TO_INT32(_array) >> CACHE_POINTER_SHIFT) & \
48 : (CACHE_NUM_SLOTS - 1))
49 :
50 : struct IndexCacheSlot
51 : {
52 : const nsAttrAndChildArray* array;
53 : int32_t index;
54 : };
55 :
56 : // This is inited to all zeroes since it's static. Though even if it wasn't
57 : // the worst thing that'd happen is a small inefficency if you'd get a false
58 : // positive cachehit.
59 : static IndexCacheSlot indexCache[CACHE_NUM_SLOTS];
60 :
61 : static
62 : inline
63 : void
64 71 : AddIndexToCache(const nsAttrAndChildArray* aArray, int32_t aIndex)
65 : {
66 71 : uint32_t ix = CACHE_GET_INDEX(aArray);
67 71 : indexCache[ix].array = aArray;
68 71 : indexCache[ix].index = aIndex;
69 71 : }
70 :
71 : static
72 : inline
73 : int32_t
74 71 : GetIndexFromCache(const nsAttrAndChildArray* aArray)
75 : {
76 71 : uint32_t ix = CACHE_GET_INDEX(aArray);
77 71 : return indexCache[ix].array == aArray ? indexCache[ix].index : -1;
78 : }
79 :
80 :
81 : /**
82 : * Due to a compiler bug in VisualAge C++ for AIX, we need to return the
83 : * address of the first index into mBuffer here, instead of simply returning
84 : * mBuffer itself.
85 : *
86 : * See Bug 231104 for more information.
87 : */
88 : #define ATTRS(_impl) \
89 : reinterpret_cast<InternalAttr*>(&((_impl)->mBuffer[0]))
90 :
91 :
92 : #define NS_IMPL_EXTRA_SIZE \
93 : ((sizeof(Impl) - sizeof(mImpl->mBuffer)) / sizeof(void*))
94 :
95 3227 : nsAttrAndChildArray::nsAttrAndChildArray()
96 3227 : : mImpl(nullptr)
97 : {
98 3227 : }
99 :
100 64 : nsAttrAndChildArray::~nsAttrAndChildArray()
101 : {
102 32 : if (!mImpl) {
103 0 : return;
104 : }
105 :
106 32 : Clear();
107 :
108 32 : free(mImpl);
109 32 : }
110 :
111 : nsIContent*
112 2067 : nsAttrAndChildArray::GetSafeChildAt(uint32_t aPos) const
113 : {
114 2067 : if (aPos < ChildCount()) {
115 2041 : return ChildAt(aPos);
116 : }
117 :
118 26 : return nullptr;
119 : }
120 :
121 : nsIContent * const *
122 1023 : nsAttrAndChildArray::GetChildArray(uint32_t* aChildCount) const
123 : {
124 1023 : *aChildCount = ChildCount();
125 :
126 1023 : if (!*aChildCount) {
127 753 : return nullptr;
128 : }
129 :
130 270 : return reinterpret_cast<nsIContent**>(mImpl->mBuffer + AttrSlotsSize());
131 : }
132 :
133 : nsresult
134 3418 : nsAttrAndChildArray::InsertChildAt(nsIContent* aChild, uint32_t aPos)
135 : {
136 3418 : NS_ASSERTION(aChild, "nullchild");
137 3418 : NS_ASSERTION(aPos <= ChildCount(), "out-of-bounds");
138 :
139 3418 : uint32_t offset = AttrSlotsSize();
140 3418 : uint32_t childCount = ChildCount();
141 :
142 3418 : NS_ENSURE_TRUE(childCount < ATTRCHILD_ARRAY_MAX_CHILD_COUNT,
143 : NS_ERROR_FAILURE);
144 :
145 : // First try to fit new child in existing childlist
146 3418 : if (mImpl && offset + childCount < mImpl->mBufferSize) {
147 2855 : void** pos = mImpl->mBuffer + offset + aPos;
148 2855 : if (childCount != aPos) {
149 18 : memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
150 : }
151 2855 : SetChildAtPos(pos, aChild, aPos, childCount);
152 :
153 2855 : SetChildCount(childCount + 1);
154 :
155 2855 : return NS_OK;
156 : }
157 :
158 : // Try to fit new child in existing buffer by compressing attrslots
159 563 : if (offset && !mImpl->mBuffer[offset - ATTRSIZE]) {
160 : // Compress away all empty slots while we're at it. This might not be the
161 : // optimal thing to do.
162 1 : uint32_t attrCount = NonMappedAttrCount();
163 1 : void** newStart = mImpl->mBuffer + attrCount * ATTRSIZE;
164 1 : void** oldStart = mImpl->mBuffer + offset;
165 1 : memmove(newStart, oldStart, aPos * sizeof(nsIContent*));
166 1 : memmove(&newStart[aPos + 1], &oldStart[aPos],
167 2 : (childCount - aPos) * sizeof(nsIContent*));
168 1 : SetChildAtPos(newStart + aPos, aChild, aPos, childCount);
169 :
170 1 : SetAttrSlotAndChildCount(attrCount, childCount + 1);
171 :
172 1 : return NS_OK;
173 : }
174 :
175 : // We can't fit in current buffer, Realloc time!
176 562 : if (!GrowBy(1)) {
177 0 : return NS_ERROR_OUT_OF_MEMORY;
178 : }
179 :
180 562 : void** pos = mImpl->mBuffer + offset + aPos;
181 562 : if (childCount != aPos) {
182 3 : memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
183 : }
184 562 : SetChildAtPos(pos, aChild, aPos, childCount);
185 :
186 562 : SetChildCount(childCount + 1);
187 :
188 562 : return NS_OK;
189 : }
190 :
191 : void
192 109 : nsAttrAndChildArray::RemoveChildAt(uint32_t aPos)
193 : {
194 : // Just store the return value of TakeChildAt in an nsCOMPtr to
195 : // trigger a release.
196 109 : nsCOMPtr<nsIContent> child = TakeChildAt(aPos);
197 109 : }
198 :
199 : already_AddRefed<nsIContent>
200 109 : nsAttrAndChildArray::TakeChildAt(uint32_t aPos)
201 : {
202 109 : NS_ASSERTION(aPos < ChildCount(), "out-of-bounds");
203 :
204 109 : uint32_t childCount = ChildCount();
205 109 : void** pos = mImpl->mBuffer + AttrSlotsSize() + aPos;
206 109 : nsIContent* child = static_cast<nsIContent*>(*pos);
207 109 : if (child->mPreviousSibling) {
208 35 : child->mPreviousSibling->mNextSibling = child->mNextSibling;
209 : }
210 109 : if (child->mNextSibling) {
211 55 : child->mNextSibling->mPreviousSibling = child->mPreviousSibling;
212 : }
213 109 : child->mPreviousSibling = child->mNextSibling = nullptr;
214 :
215 109 : memmove(pos, pos + 1, (childCount - aPos - 1) * sizeof(nsIContent*));
216 109 : SetChildCount(childCount - 1);
217 :
218 109 : return dont_AddRef(child);
219 : }
220 :
221 : int32_t
222 739 : nsAttrAndChildArray::IndexOfChild(const nsINode* aPossibleChild) const
223 : {
224 739 : if (!mImpl) {
225 0 : return -1;
226 : }
227 739 : void** children = mImpl->mBuffer + AttrSlotsSize();
228 : // Use signed here since we compare count to cursor which has to be signed
229 739 : int32_t i, count = ChildCount();
230 :
231 739 : if (count >= CACHE_CHILD_LIMIT) {
232 71 : int32_t cursor = GetIndexFromCache(this);
233 : // Need to compare to count here since we may have removed children since
234 : // the index was added to the cache.
235 : // We're also relying on that GetIndexFromCache returns -1 if no cached
236 : // index was found.
237 71 : if (cursor >= count) {
238 4 : cursor = -1;
239 : }
240 :
241 : // Seek outward from the last found index. |inc| will change sign every
242 : // run through the loop. |sign| just exists to make sure the absolute
243 : // value of |inc| increases each time through.
244 71 : int32_t inc = 1, sign = 1;
245 117 : while (cursor >= 0 && cursor < count) {
246 78 : if (children[cursor] == aPossibleChild) {
247 55 : AddIndexToCache(this, cursor);
248 :
249 55 : return cursor;
250 : }
251 :
252 23 : cursor += inc;
253 23 : inc = -inc - sign;
254 23 : sign = -sign;
255 : }
256 :
257 : // We ran into one 'edge'. Add inc to cursor once more to get back to
258 : // the 'side' where we still need to search, then step in the |sign|
259 : // direction.
260 16 : cursor += inc;
261 :
262 16 : if (sign > 0) {
263 273 : for (; cursor < count; ++cursor) {
264 144 : if (children[cursor] == aPossibleChild) {
265 15 : AddIndexToCache(this, cursor);
266 :
267 15 : return static_cast<int32_t>(cursor);
268 : }
269 : }
270 : }
271 : else {
272 17 : for (; cursor >= 0; --cursor) {
273 9 : if (children[cursor] == aPossibleChild) {
274 1 : AddIndexToCache(this, cursor);
275 :
276 1 : return static_cast<int32_t>(cursor);
277 : }
278 : }
279 : }
280 :
281 : // The child wasn't even in the remaining children
282 0 : return -1;
283 : }
284 :
285 1391 : for (i = 0; i < count; ++i) {
286 1385 : if (children[i] == aPossibleChild) {
287 662 : return static_cast<int32_t>(i);
288 : }
289 : }
290 :
291 6 : return -1;
292 : }
293 :
294 : uint32_t
295 8035 : nsAttrAndChildArray::AttrCount() const
296 : {
297 8035 : return NonMappedAttrCount() + MappedAttrCount();
298 : }
299 :
300 : const nsAttrValue*
301 169770 : nsAttrAndChildArray::GetAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
302 : {
303 169770 : uint32_t i, slotCount = AttrSlotCount();
304 169770 : if (aNamespaceID == kNameSpaceID_None) {
305 : // This should be the common case so lets make an optimized loop
306 520710 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
307 454026 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
308 99354 : return &ATTRS(mImpl)[i].mValue;
309 : }
310 : }
311 :
312 66684 : if (mImpl && mImpl->mMappedAttrs) {
313 286 : return mImpl->mMappedAttrs->GetAttr(aLocalName);
314 : }
315 : }
316 : else {
317 17840 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
318 14138 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
319 30 : return &ATTRS(mImpl)[i].mValue;
320 : }
321 : }
322 : }
323 :
324 70100 : return nullptr;
325 : }
326 :
327 : const nsAttrValue*
328 0 : nsAttrAndChildArray::GetAttr(const nsAString& aLocalName) const
329 : {
330 0 : uint32_t i, slotCount = AttrSlotCount();
331 0 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
332 0 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
333 0 : return &ATTRS(mImpl)[i].mValue;
334 : }
335 : }
336 :
337 0 : if (mImpl && mImpl->mMappedAttrs) {
338 0 : return mImpl->mMappedAttrs->GetAttr(aLocalName);
339 : }
340 :
341 0 : return nullptr;
342 : }
343 :
344 : const nsAttrValue*
345 253 : nsAttrAndChildArray::GetAttr(const nsAString& aName,
346 : nsCaseTreatment aCaseSensitive) const
347 : {
348 : // Check whether someone is being silly and passing non-lowercase
349 : // attr names.
350 260 : if (aCaseSensitive == eIgnoreCase &&
351 7 : nsContentUtils::StringContainsASCIIUpper(aName)) {
352 : // Try again with a lowercased name, but make sure we can't reenter this
353 : // block by passing eCaseSensitive for aCaseSensitive.
354 0 : nsAutoString lowercase;
355 0 : nsContentUtils::ASCIIToLower(aName, lowercase);
356 0 : return GetAttr(lowercase, eCaseMatters);
357 : }
358 :
359 253 : uint32_t i, slotCount = AttrSlotCount();
360 2252 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
361 2133 : if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
362 134 : return &ATTRS(mImpl)[i].mValue;
363 : }
364 : }
365 :
366 119 : if (mImpl && mImpl->mMappedAttrs) {
367 : const nsAttrValue* val =
368 0 : mImpl->mMappedAttrs->GetAttr(aName);
369 0 : if (val) {
370 0 : return val;
371 : }
372 : }
373 :
374 119 : return nullptr;
375 : }
376 :
377 : const nsAttrValue*
378 1879 : nsAttrAndChildArray::AttrAt(uint32_t aPos) const
379 : {
380 1879 : NS_ASSERTION(aPos < AttrCount(),
381 : "out-of-bounds access in nsAttrAndChildArray");
382 :
383 1879 : uint32_t nonmapped = NonMappedAttrCount();
384 1879 : if (aPos < nonmapped) {
385 1879 : return &ATTRS(mImpl)[aPos].mValue;
386 : }
387 :
388 0 : return mImpl->mMappedAttrs->AttrAt(aPos - nonmapped);
389 : }
390 :
391 : nsresult
392 7710 : nsAttrAndChildArray::SetAndSwapAttr(nsIAtom* aLocalName, nsAttrValue& aValue,
393 : bool* aHadValue)
394 : {
395 7710 : *aHadValue = false;
396 7710 : uint32_t i, slotCount = AttrSlotCount();
397 21775 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
398 14147 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
399 82 : ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
400 82 : *aHadValue = true;
401 82 : return NS_OK;
402 : }
403 : }
404 :
405 7628 : NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
406 : NS_ERROR_FAILURE);
407 :
408 7628 : if (i == slotCount && !AddAttrSlot()) {
409 0 : return NS_ERROR_OUT_OF_MEMORY;
410 : }
411 :
412 7628 : new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName);
413 7628 : new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
414 7628 : ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
415 :
416 7628 : return NS_OK;
417 : }
418 :
419 : nsresult
420 654 : nsAttrAndChildArray::SetAndSwapAttr(mozilla::dom::NodeInfo* aName,
421 : nsAttrValue& aValue, bool* aHadValue)
422 : {
423 654 : int32_t namespaceID = aName->NamespaceID();
424 654 : nsIAtom* localName = aName->NameAtom();
425 654 : if (namespaceID == kNameSpaceID_None) {
426 0 : return SetAndSwapAttr(localName, aValue, aHadValue);
427 : }
428 :
429 654 : *aHadValue = false;
430 654 : uint32_t i, slotCount = AttrSlotCount();
431 1775 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
432 1122 : if (ATTRS(mImpl)[i].mName.Equals(localName, namespaceID)) {
433 1 : ATTRS(mImpl)[i].mName.SetTo(aName);
434 1 : ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
435 1 : *aHadValue = true;
436 1 : return NS_OK;
437 : }
438 : }
439 :
440 653 : NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
441 : NS_ERROR_FAILURE);
442 :
443 653 : if (i == slotCount && !AddAttrSlot()) {
444 0 : return NS_ERROR_OUT_OF_MEMORY;
445 : }
446 :
447 653 : new (&ATTRS(mImpl)[i].mName) nsAttrName(aName);
448 653 : new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
449 653 : ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
450 :
451 653 : return NS_OK;
452 : }
453 :
454 :
455 : nsresult
456 136 : nsAttrAndChildArray::RemoveAttrAt(uint32_t aPos, nsAttrValue& aValue)
457 : {
458 136 : NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
459 :
460 136 : uint32_t nonmapped = NonMappedAttrCount();
461 136 : if (aPos < nonmapped) {
462 136 : ATTRS(mImpl)[aPos].mValue.SwapValueWith(aValue);
463 136 : ATTRS(mImpl)[aPos].~InternalAttr();
464 :
465 136 : uint32_t slotCount = AttrSlotCount();
466 272 : memmove(&ATTRS(mImpl)[aPos],
467 136 : &ATTRS(mImpl)[aPos + 1],
468 272 : (slotCount - aPos - 1) * sizeof(InternalAttr));
469 136 : memset(&ATTRS(mImpl)[slotCount - 1], 0, sizeof(InternalAttr));
470 :
471 136 : return NS_OK;
472 : }
473 :
474 0 : if (MappedAttrCount() == 1) {
475 : // We're removing the last mapped attribute. Can't swap in this
476 : // case; have to copy.
477 0 : aValue.SetTo(*mImpl->mMappedAttrs->AttrAt(0));
478 0 : NS_RELEASE(mImpl->mMappedAttrs);
479 :
480 0 : return NS_OK;
481 : }
482 :
483 : RefPtr<nsMappedAttributes> mapped =
484 0 : GetModifiableMapped(nullptr, nullptr, false);
485 :
486 0 : mapped->RemoveAttrAt(aPos - nonmapped, aValue);
487 :
488 0 : return MakeMappedUnique(mapped);
489 : }
490 :
491 : mozilla::dom::BorrowedAttrInfo
492 235 : nsAttrAndChildArray::AttrInfoAt(uint32_t aPos) const
493 : {
494 235 : NS_ASSERTION(aPos < AttrCount(),
495 : "out-of-bounds access in nsAttrAndChildArray");
496 :
497 235 : uint32_t nonmapped = NonMappedAttrCount();
498 235 : if (aPos < nonmapped) {
499 235 : return BorrowedAttrInfo(&ATTRS(mImpl)[aPos].mName, &ATTRS(mImpl)[aPos].mValue);
500 : }
501 :
502 0 : return BorrowedAttrInfo(mImpl->mMappedAttrs->NameAt(aPos - nonmapped),
503 0 : mImpl->mMappedAttrs->AttrAt(aPos - nonmapped));
504 : }
505 :
506 : const nsAttrName*
507 3874 : nsAttrAndChildArray::AttrNameAt(uint32_t aPos) const
508 : {
509 3874 : NS_ASSERTION(aPos < AttrCount(),
510 : "out-of-bounds access in nsAttrAndChildArray");
511 :
512 3874 : uint32_t nonmapped = NonMappedAttrCount();
513 3874 : if (aPos < nonmapped) {
514 3873 : return &ATTRS(mImpl)[aPos].mName;
515 : }
516 :
517 1 : return mImpl->mMappedAttrs->NameAt(aPos - nonmapped);
518 : }
519 :
520 : const nsAttrName*
521 322 : nsAttrAndChildArray::GetSafeAttrNameAt(uint32_t aPos) const
522 : {
523 322 : uint32_t nonmapped = NonMappedAttrCount();
524 322 : if (aPos < nonmapped) {
525 303 : void** pos = mImpl->mBuffer + aPos * ATTRSIZE;
526 303 : if (!*pos) {
527 0 : return nullptr;
528 : }
529 :
530 303 : return &reinterpret_cast<InternalAttr*>(pos)->mName;
531 : }
532 :
533 19 : if (aPos >= AttrCount()) {
534 19 : return nullptr;
535 : }
536 :
537 0 : return mImpl->mMappedAttrs->NameAt(aPos - nonmapped);
538 : }
539 :
540 : const nsAttrName*
541 502 : nsAttrAndChildArray::GetExistingAttrNameFromQName(const nsAString& aName) const
542 : {
543 502 : uint32_t i, slotCount = AttrSlotCount();
544 2959 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
545 2573 : if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
546 116 : return &ATTRS(mImpl)[i].mName;
547 : }
548 : }
549 :
550 386 : if (mImpl && mImpl->mMappedAttrs) {
551 0 : return mImpl->mMappedAttrs->GetExistingAttrNameFromQName(aName);
552 : }
553 :
554 386 : return nullptr;
555 : }
556 :
557 : int32_t
558 20508 : nsAttrAndChildArray::IndexOfAttr(nsIAtom* aLocalName, int32_t aNamespaceID) const
559 : {
560 : int32_t idx;
561 20508 : if (mImpl && mImpl->mMappedAttrs && aNamespaceID == kNameSpaceID_None) {
562 102 : idx = mImpl->mMappedAttrs->IndexOfAttr(aLocalName);
563 102 : if (idx >= 0) {
564 8 : return NonMappedAttrCount() + idx;
565 : }
566 : }
567 :
568 : uint32_t i;
569 20500 : uint32_t slotCount = AttrSlotCount();
570 20500 : if (aNamespaceID == kNameSpaceID_None) {
571 : // This should be the common case so lets make an optimized loop
572 : // Note that here we don't check for AttrSlotIsTaken() in the loop
573 : // condition for the sake of performance because comparing aLocalName
574 : // against null would fail in the loop body (since Equals() just compares
575 : // the raw pointer value of aLocalName to what AttrSlotIsTaken() would be
576 : // checking.
577 116993 : for (i = 0; i < slotCount; ++i) {
578 97604 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
579 1107 : MOZ_ASSERT(AttrSlotIsTaken(i), "sanity check");
580 1107 : return i;
581 : }
582 : }
583 : }
584 : else {
585 20 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
586 17 : if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
587 1 : return i;
588 : }
589 : }
590 : }
591 :
592 19392 : return -1;
593 : }
594 :
595 : nsresult
596 26 : nsAttrAndChildArray::SetAndSwapMappedAttr(nsIAtom* aLocalName,
597 : nsAttrValue& aValue,
598 : nsMappedAttributeElement* aContent,
599 : nsHTMLStyleSheet* aSheet,
600 : bool* aHadValue)
601 : {
602 26 : bool willAdd = true;
603 26 : if (mImpl && mImpl->mMappedAttrs) {
604 0 : willAdd = !mImpl->mMappedAttrs->GetAttr(aLocalName);
605 : }
606 :
607 : RefPtr<nsMappedAttributes> mapped =
608 52 : GetModifiableMapped(aContent, aSheet, willAdd);
609 :
610 26 : mapped->SetAndSwapAttr(aLocalName, aValue, aHadValue);
611 :
612 52 : return MakeMappedUnique(mapped);
613 : }
614 :
615 : nsresult
616 0 : nsAttrAndChildArray::DoSetMappedAttrStyleSheet(nsHTMLStyleSheet* aSheet)
617 : {
618 0 : NS_PRECONDITION(mImpl && mImpl->mMappedAttrs,
619 : "Should have mapped attrs here!");
620 0 : if (aSheet == mImpl->mMappedAttrs->GetStyleSheet()) {
621 0 : return NS_OK;
622 : }
623 :
624 : RefPtr<nsMappedAttributes> mapped =
625 0 : GetModifiableMapped(nullptr, nullptr, false);
626 :
627 0 : mapped->SetStyleSheet(aSheet);
628 :
629 0 : return MakeMappedUnique(mapped);
630 : }
631 :
632 : void
633 79 : nsAttrAndChildArray::WalkMappedAttributeStyleRules(nsRuleWalker* aRuleWalker)
634 : {
635 79 : if (mImpl && mImpl->mMappedAttrs) {
636 46 : aRuleWalker->Forward(mImpl->mMappedAttrs);
637 : }
638 79 : }
639 :
640 : void
641 1 : nsAttrAndChildArray::Compact()
642 : {
643 1 : if (!mImpl) {
644 0 : return;
645 : }
646 :
647 : // First compress away empty attrslots
648 1 : uint32_t slotCount = AttrSlotCount();
649 1 : uint32_t attrCount = NonMappedAttrCount();
650 1 : uint32_t childCount = ChildCount();
651 :
652 1 : if (attrCount < slotCount) {
653 0 : memmove(mImpl->mBuffer + attrCount * ATTRSIZE,
654 0 : mImpl->mBuffer + slotCount * ATTRSIZE,
655 0 : childCount * sizeof(nsIContent*));
656 0 : SetAttrSlotCount(attrCount);
657 : }
658 :
659 : // Then resize or free buffer
660 1 : uint32_t newSize = attrCount * ATTRSIZE + childCount;
661 1 : if (!newSize && !mImpl->mMappedAttrs) {
662 0 : free(mImpl);
663 0 : mImpl = nullptr;
664 : }
665 1 : else if (newSize < mImpl->mBufferSize) {
666 1 : mImpl = static_cast<Impl*>(realloc(mImpl, (newSize + NS_IMPL_EXTRA_SIZE) * sizeof(nsIContent*)));
667 1 : NS_ASSERTION(mImpl, "failed to reallocate to smaller buffer");
668 :
669 1 : mImpl->mBufferSize = newSize;
670 : }
671 : }
672 :
673 : void
674 32 : nsAttrAndChildArray::Clear()
675 : {
676 32 : if (!mImpl) {
677 0 : return;
678 : }
679 :
680 32 : if (mImpl->mMappedAttrs) {
681 0 : NS_RELEASE(mImpl->mMappedAttrs);
682 : }
683 :
684 32 : uint32_t i, slotCount = AttrSlotCount();
685 144 : for (i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
686 112 : ATTRS(mImpl)[i].~InternalAttr();
687 : }
688 :
689 64 : nsAutoScriptBlocker scriptBlocker;
690 32 : uint32_t end = slotCount * ATTRSIZE + ChildCount();
691 37 : for (i = slotCount * ATTRSIZE; i < end; ++i) {
692 5 : nsIContent* child = static_cast<nsIContent*>(mImpl->mBuffer[i]);
693 : // making this false so tree teardown doesn't end up being
694 : // O(N*D) (number of nodes times average depth of tree).
695 5 : child->UnbindFromTree(false); // XXX is it better to let the owner do this?
696 : // Make sure to unlink our kids from each other, since someone
697 : // else could stil be holding references to some of them.
698 :
699 : // XXXbz We probably can't push this assignment down into the |aNullParent|
700 : // case of UnbindFromTree because we still need the assignment in
701 : // RemoveChildAt. In particular, ContentRemoved fires between
702 : // RemoveChildAt and UnbindFromTree, and in ContentRemoved the sibling
703 : // chain needs to be correct. Though maybe we could set the prev and next
704 : // to point to each other but keep the kid being removed pointing to them
705 : // through ContentRemoved so consumers can find where it used to be in the
706 : // list?
707 5 : child->mPreviousSibling = child->mNextSibling = nullptr;
708 5 : NS_RELEASE(child);
709 : }
710 :
711 32 : SetAttrSlotAndChildCount(0, 0);
712 : }
713 :
714 : uint32_t
715 15374 : nsAttrAndChildArray::NonMappedAttrCount() const
716 : {
717 15374 : if (!mImpl) {
718 221 : return 0;
719 : }
720 :
721 15153 : uint32_t count = AttrSlotCount();
722 15609 : while (count > 0 && !mImpl->mBuffer[(count - 1) * ATTRSIZE]) {
723 228 : --count;
724 : }
725 :
726 15153 : return count;
727 : }
728 :
729 : uint32_t
730 64479 : nsAttrAndChildArray::MappedAttrCount() const
731 : {
732 64479 : return mImpl && mImpl->mMappedAttrs ? (uint32_t)mImpl->mMappedAttrs->Count() : 0;
733 : }
734 :
735 : nsresult
736 7 : nsAttrAndChildArray::ForceMapped(nsMappedAttributeElement* aContent, nsIDocument* aDocument)
737 : {
738 7 : nsHTMLStyleSheet* sheet = aDocument->GetAttributeStyleSheet();
739 14 : RefPtr<nsMappedAttributes> mapped = GetModifiableMapped(aContent, sheet, false, 0);
740 14 : return MakeMappedUnique(mapped);
741 : }
742 :
743 : void
744 0 : nsAttrAndChildArray::ClearMappedServoStyle() {
745 0 : if (mImpl && mImpl->mMappedAttrs) {
746 0 : mImpl->mMappedAttrs->ClearServoStyle();
747 : }
748 0 : }
749 :
750 : nsMappedAttributes*
751 33 : nsAttrAndChildArray::GetModifiableMapped(nsMappedAttributeElement* aContent,
752 : nsHTMLStyleSheet* aSheet,
753 : bool aWillAddAttr,
754 : int32_t aAttrCount)
755 : {
756 33 : if (mImpl && mImpl->mMappedAttrs) {
757 0 : return mImpl->mMappedAttrs->Clone(aWillAddAttr);
758 : }
759 :
760 33 : MOZ_ASSERT(aContent, "Trying to create modifiable without content");
761 :
762 : nsMapRuleToAttributesFunc mapRuleFunc =
763 33 : aContent->GetAttributeMappingFunction();
764 33 : return new (aAttrCount) nsMappedAttributes(aSheet, mapRuleFunc);
765 : }
766 :
767 : nsresult
768 33 : nsAttrAndChildArray::MakeMappedUnique(nsMappedAttributes* aAttributes)
769 : {
770 33 : NS_ASSERTION(aAttributes, "missing attributes");
771 :
772 33 : if (!mImpl && !GrowBy(1)) {
773 0 : return NS_ERROR_OUT_OF_MEMORY;
774 : }
775 :
776 33 : if (!aAttributes->GetStyleSheet()) {
777 : // This doesn't currently happen, but it could if we do loading right
778 :
779 0 : RefPtr<nsMappedAttributes> mapped(aAttributes);
780 0 : mapped.swap(mImpl->mMappedAttrs);
781 :
782 0 : return NS_OK;
783 : }
784 :
785 : RefPtr<nsMappedAttributes> mapped =
786 66 : aAttributes->GetStyleSheet()->UniqueMappedAttributes(aAttributes);
787 33 : NS_ENSURE_TRUE(mapped, NS_ERROR_OUT_OF_MEMORY);
788 :
789 33 : if (mapped != aAttributes) {
790 : // Reset the stylesheet of aAttributes so that it doesn't spend time
791 : // trying to remove itself from the hash. There is no risk that aAttributes
792 : // is in the hash since it will always have come from GetModifiableMapped,
793 : // which never returns maps that are in the hash (such hashes are by
794 : // nature not modifiable).
795 1 : aAttributes->DropStyleSheetReference();
796 : }
797 33 : mapped.swap(mImpl->mMappedAttrs);
798 :
799 33 : return NS_OK;
800 : }
801 :
802 : const nsMappedAttributes*
803 0 : nsAttrAndChildArray::GetMapped() const
804 : {
805 0 : return mImpl ? mImpl->mMappedAttrs : nullptr;
806 : }
807 :
808 883 : nsresult nsAttrAndChildArray::EnsureCapacityToClone(const nsAttrAndChildArray& aOther,
809 : bool aAllocateChildren)
810 : {
811 883 : NS_PRECONDITION(!mImpl, "nsAttrAndChildArray::EnsureCapacityToClone requires the array be empty when called");
812 :
813 883 : uint32_t attrCount = aOther.NonMappedAttrCount();
814 883 : uint32_t childCount = 0;
815 883 : if (aAllocateChildren) {
816 883 : childCount = aOther.ChildCount();
817 : }
818 :
819 883 : if (attrCount == 0 && childCount == 0) {
820 77 : return NS_OK;
821 : }
822 :
823 : // No need to use a CheckedUint32 because we are cloning. We know that we
824 : // have already allocated an nsAttrAndChildArray of this size.
825 806 : uint32_t size = attrCount;
826 806 : size *= ATTRSIZE;
827 806 : size += childCount;
828 806 : uint32_t totalSize = size;
829 806 : totalSize += NS_IMPL_EXTRA_SIZE;
830 :
831 806 : mImpl = static_cast<Impl*>(malloc(totalSize * sizeof(void*)));
832 806 : NS_ENSURE_TRUE(mImpl, NS_ERROR_OUT_OF_MEMORY);
833 :
834 806 : mImpl->mMappedAttrs = nullptr;
835 806 : mImpl->mBufferSize = size;
836 :
837 : // The array is now the right size, but we should reserve the correct
838 : // number of slots for attributes so that children don't get written into
839 : // that part of the array (which will then need to be moved later).
840 806 : memset(static_cast<void*>(mImpl->mBuffer), 0, sizeof(InternalAttr) * attrCount);
841 806 : SetAttrSlotAndChildCount(attrCount, 0);
842 :
843 806 : return NS_OK;
844 : }
845 :
846 : bool
847 3504 : nsAttrAndChildArray::GrowBy(uint32_t aGrowSize)
848 : {
849 3504 : CheckedUint32 size = 0;
850 3504 : if (mImpl) {
851 1306 : size += mImpl->mBufferSize;
852 1306 : size += NS_IMPL_EXTRA_SIZE;
853 1306 : if (!size.isValid()) {
854 0 : return false;
855 : }
856 : }
857 :
858 3504 : CheckedUint32 minSize = size.value();
859 3504 : minSize += aGrowSize;
860 3504 : if (!minSize.isValid()) {
861 0 : return false;
862 : }
863 :
864 3504 : if (minSize.value() <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) {
865 3488 : do {
866 3488 : size += ATTRCHILD_ARRAY_GROWSIZE;
867 3488 : if (!size.isValid()) {
868 0 : return false;
869 : }
870 3488 : } while (size.value() < minSize.value());
871 : }
872 : else {
873 16 : uint32_t shift = mozilla::CeilingLog2(minSize.value());
874 16 : if (shift >= 32) {
875 0 : return false;
876 : }
877 :
878 16 : size = 1u << shift;
879 : }
880 :
881 3504 : bool needToInitialize = !mImpl;
882 3504 : CheckedUint32 neededSize = size;
883 3504 : neededSize *= sizeof(void*);
884 3504 : if (!neededSize.isValid()) {
885 0 : return false;
886 : }
887 :
888 3504 : Impl* newImpl = static_cast<Impl*>(realloc(mImpl, neededSize.value()));
889 3504 : NS_ENSURE_TRUE(newImpl, false);
890 :
891 3504 : mImpl = newImpl;
892 :
893 : // Set initial counts if we didn't have a buffer before
894 3504 : if (needToInitialize) {
895 2198 : mImpl->mMappedAttrs = nullptr;
896 2198 : SetAttrSlotAndChildCount(0, 0);
897 : }
898 :
899 3504 : mImpl->mBufferSize = size.value() - NS_IMPL_EXTRA_SIZE;
900 :
901 3504 : return true;
902 : }
903 :
904 : bool
905 6489 : nsAttrAndChildArray::AddAttrSlot()
906 : {
907 6489 : uint32_t slotCount = AttrSlotCount();
908 6489 : uint32_t childCount = ChildCount();
909 :
910 6489 : CheckedUint32 size = slotCount;
911 6489 : size += 1;
912 6489 : size *= ATTRSIZE;
913 6489 : size += childCount;
914 6489 : if (!size.isValid()) {
915 0 : return false;
916 : }
917 :
918 : // Grow buffer if needed
919 9424 : if (!(mImpl && mImpl->mBufferSize >= size.value()) &&
920 2935 : !GrowBy(ATTRSIZE)) {
921 0 : return false;
922 : }
923 :
924 6489 : void** offset = mImpl->mBuffer + slotCount * ATTRSIZE;
925 :
926 6489 : if (childCount > 0) {
927 205 : memmove(&ATTRS(mImpl)[slotCount + 1], &ATTRS(mImpl)[slotCount],
928 205 : childCount * sizeof(nsIContent*));
929 : }
930 :
931 6489 : SetAttrSlotCount(slotCount + 1);
932 6489 : memset(static_cast<void*>(offset), 0, sizeof(InternalAttr));
933 :
934 6489 : return true;
935 : }
936 :
937 : inline void
938 3418 : nsAttrAndChildArray::SetChildAtPos(void** aPos, nsIContent* aChild,
939 : uint32_t aIndex, uint32_t aChildCount)
940 : {
941 3418 : NS_PRECONDITION(!aChild->GetNextSibling(), "aChild with next sibling?");
942 3418 : NS_PRECONDITION(!aChild->GetPreviousSibling(), "aChild with prev sibling?");
943 :
944 3418 : *aPos = aChild;
945 3418 : NS_ADDREF(aChild);
946 3418 : if (aIndex != 0) {
947 2163 : nsIContent* previous = static_cast<nsIContent*>(*(aPos - 1));
948 2163 : aChild->mPreviousSibling = previous;
949 2163 : previous->mNextSibling = aChild;
950 : }
951 3418 : if (aIndex != aChildCount) {
952 21 : nsIContent* next = static_cast<nsIContent*>(*(aPos + 1));
953 21 : aChild->mNextSibling = next;
954 21 : next->mPreviousSibling = aChild;
955 : }
956 3418 : }
957 :
958 : size_t
959 130 : nsAttrAndChildArray::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
960 : {
961 130 : size_t n = 0;
962 130 : if (mImpl) {
963 : // Don't add the size taken by *mMappedAttrs because it's shared.
964 :
965 130 : n += aMallocSizeOf(mImpl);
966 :
967 130 : uint32_t slotCount = AttrSlotCount();
968 447 : for (uint32_t i = 0; i < slotCount && AttrSlotIsTaken(i); ++i) {
969 317 : nsAttrValue* value = &ATTRS(mImpl)[i].mValue;
970 317 : n += value->SizeOfExcludingThis(aMallocSizeOf);
971 : }
972 : }
973 :
974 130 : return n;
975 : }
976 :
|
