Back to index

lightning-sunbird  0.9+nobinonly
nsAttrAndChildArray.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * IBM Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * IBM Corporation. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   IBM Corporation
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "nsAttrAndChildArray.h"
00040 #include "nsGenericHTMLElement.h"
00041 #include "prmem.h"
00042 #include "prbit.h"
00043 #include "nsString.h"
00044 #include "nsHTMLStyleSheet.h"
00045 #include "nsRuleWalker.h"
00046 #include "nsMappedAttributes.h"
00047 #include "nsUnicharUtils.h"
00048 #include "nsAutoPtr.h"
00049 
00050 #define NUM_INDEX_CACHE_SLOTS 5
00051 #define INDEX_CACHE_CHILD_LIMIT 15
00052 
00053 struct IndexCacheSlot
00054 {
00055   const nsAttrAndChildArray* array;
00056   PRInt32 index;
00057 };
00058 
00059 // This is inited to all zeroes since it's static. Though even if it wasn't
00060 // the worst thing that'd happen is a small inefficency if you'd get a false
00061 // positive cachehit.
00062 static IndexCacheSlot indexCache[NUM_INDEX_CACHE_SLOTS];
00063 
00064 static
00065 void
00066 AddIndexToCache(const nsAttrAndChildArray* aArray, PRInt32 aIndex)
00067 {
00068   NS_ASSERTION(NUM_INDEX_CACHE_SLOTS > 1, "too few cache slots");
00069 
00070   if (indexCache[0].array != aArray) {
00071     PRUint32 i;
00072     for (i = 1; i < NUM_INDEX_CACHE_SLOTS - 1; ++i) {
00073       if (indexCache[i].array == aArray) {
00074         break;
00075       }
00076     }
00077     memmove(&indexCache[1], &indexCache[0], i * sizeof(IndexCacheSlot));
00078     indexCache[0].array = aArray;
00079   }
00080   
00081   indexCache[0].index = aIndex;
00082 }
00083 
00084 static
00085 PRInt32
00086 GetIndexFromCache(const nsAttrAndChildArray* aArray)
00087 {
00088   PRUint32 i;
00089   for (i = 0; i < NUM_INDEX_CACHE_SLOTS; ++i) {
00090     if (indexCache[i].array == aArray) {
00091       return indexCache[i].index;
00092     }
00093   }
00094   
00095   return -1;
00096 }
00097 
00098 
00106 #define ATTRS(_impl) \
00107   NS_REINTERPRET_CAST(InternalAttr*, &((_impl)->mBuffer[0]))
00108   
00109 
00110 #define NS_IMPL_EXTRA_SIZE \
00111   ((sizeof(Impl) - sizeof(mImpl->mBuffer)) / sizeof(void*))
00112 
00113 nsAttrAndChildArray::nsAttrAndChildArray()
00114   : mImpl(nsnull)
00115 {
00116 }
00117 
00118 nsAttrAndChildArray::~nsAttrAndChildArray()
00119 {
00120   if (!mImpl) {
00121     return;
00122   }
00123 
00124   Clear();
00125 
00126   PR_Free(mImpl);
00127 }
00128 
00129 nsIContent*
00130 nsAttrAndChildArray::GetSafeChildAt(PRUint32 aPos) const
00131 {
00132   if (aPos < ChildCount()) {
00133     return ChildAt(aPos);
00134   }
00135   
00136   return nsnull;
00137 }
00138 
00139 nsresult
00140 nsAttrAndChildArray::InsertChildAt(nsIContent* aChild, PRUint32 aPos)
00141 {
00142   NS_ASSERTION(aChild, "nullchild");
00143   NS_ASSERTION(aPos <= ChildCount(), "out-of-bounds");
00144 
00145   PRUint32 offset = AttrSlotsSize();
00146   PRUint32 childCount = ChildCount();
00147 
00148   NS_ENSURE_TRUE(childCount < ATTRCHILD_ARRAY_MAX_CHILD_COUNT,
00149                  NS_ERROR_FAILURE);
00150 
00151   // First try to fit new child in existing childlist
00152   if (mImpl && offset + childCount < mImpl->mBufferSize) {
00153     void** pos = mImpl->mBuffer + offset + aPos;
00154     if (childCount != aPos) {
00155       memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
00156     }
00157     *pos = aChild;
00158     NS_ADDREF(aChild);
00159 
00160     SetChildCount(childCount + 1);
00161 
00162     return NS_OK;
00163   }
00164 
00165   // Try to fit new child in existing buffer by compressing attrslots
00166   if (offset && !mImpl->mBuffer[offset - ATTRSIZE]) {
00167     // Compress away all empty slots while we're at it. This might not be the
00168     // optimal thing to do.
00169     PRUint32 attrCount = NonMappedAttrCount();
00170     void** newStart = mImpl->mBuffer + attrCount * ATTRSIZE;
00171     void** oldStart = mImpl->mBuffer + offset;
00172     memmove(newStart, oldStart, aPos * sizeof(nsIContent*));
00173     newStart[aPos] = aChild;
00174     memmove(&newStart[aPos + 1], &oldStart[aPos],
00175             (childCount - aPos) * sizeof(nsIContent*));
00176     NS_ADDREF(aChild);
00177 
00178     SetAttrSlotAndChildCount(attrCount, childCount + 1);
00179 
00180     return NS_OK;
00181   }
00182 
00183   // We can't fit in current buffer, Realloc time!
00184   if (!GrowBy(1)) {
00185     return NS_ERROR_OUT_OF_MEMORY;
00186   }
00187 
00188   void** pos = mImpl->mBuffer + offset + aPos;
00189   if (childCount != aPos) {
00190     memmove(pos + 1, pos, (childCount - aPos) * sizeof(nsIContent*));
00191   }
00192   *pos = aChild;
00193   NS_ADDREF(aChild);
00194 
00195   SetChildCount(childCount + 1);
00196   
00197   return NS_OK;
00198 }
00199 
00200 void
00201 nsAttrAndChildArray::RemoveChildAt(PRUint32 aPos)
00202 {
00203   NS_ASSERTION(aPos < ChildCount(), "out-of-bounds");
00204 
00205   PRUint32 childCount = ChildCount();
00206   void** pos = mImpl->mBuffer + AttrSlotsSize() + aPos;
00207   nsIContent* child = NS_STATIC_CAST(nsIContent*, *pos);
00208   NS_RELEASE(child);
00209   memmove(pos, pos + 1, (childCount - aPos - 1) * sizeof(nsIContent*));
00210   SetChildCount(childCount - 1);
00211 }
00212 
00213 PRInt32
00214 nsAttrAndChildArray::IndexOfChild(nsIContent* aPossibleChild) const
00215 {
00216   if (!mImpl) {
00217     return -1;
00218   }
00219   void** children = mImpl->mBuffer + AttrSlotsSize();
00220   // Use signed here since we compare count to cursor which has to be signed
00221   PRInt32 i, count = ChildCount();
00222 
00223   if (count >= INDEX_CACHE_CHILD_LIMIT) {
00224     PRInt32 cursor = GetIndexFromCache(this);
00225     // Need to compare to count here since we may have removed children since
00226     // the index was added to the cache.
00227     // We're also relying on that GetIndexFromCache returns -1 if no cached
00228     // index was found.
00229     if (cursor >= count) {
00230       cursor = -1;
00231     }
00232 
00233     // Seek outward from the last found index. |inc| will change sign every
00234     // run through the loop. |sign| just exists to make sure the absolute
00235     // value of |inc| increases each time through.
00236     PRInt32 inc = 1, sign = 1;
00237     while (cursor >= 0 && cursor < count) {
00238       if (children[cursor] == aPossibleChild) {
00239         AddIndexToCache(this, cursor);
00240 
00241         return cursor;
00242       }
00243 
00244       cursor += inc;
00245       inc = -inc - sign;
00246       sign = -sign;
00247     }
00248 
00249     // We ran into one 'edge'. Add inc to cursor once more to get back to
00250     // the 'side' where we still need to search, then step in the |sign|
00251     // direction.
00252     cursor += inc;
00253 
00254     if (sign > 0) {
00255       for (; cursor < count; ++cursor) {
00256         if (children[cursor] == aPossibleChild) {
00257           AddIndexToCache(this, cursor);
00258 
00259           return NS_STATIC_CAST(PRInt32, cursor);
00260         }
00261       }
00262     }
00263     else {
00264       for (; cursor >= 0; --cursor) {
00265         if (children[cursor] == aPossibleChild) {
00266           AddIndexToCache(this, cursor);
00267 
00268           return NS_STATIC_CAST(PRInt32, cursor);
00269         }
00270       }
00271     }
00272 
00273     // The child wasn't even in the remaining children
00274     return -1;
00275   }
00276 
00277   for (i = 0; i < count; ++i) {
00278     if (children[i] == aPossibleChild) {
00279       return NS_STATIC_CAST(PRInt32, i);
00280     }
00281   }
00282 
00283   return -1;
00284 }
00285 
00286 PRUint32
00287 nsAttrAndChildArray::AttrCount() const
00288 {
00289   return NonMappedAttrCount() + MappedAttrCount();
00290 }
00291 
00292 const nsAttrValue*
00293 nsAttrAndChildArray::GetAttr(nsIAtom* aLocalName, PRInt32 aNamespaceID) const
00294 {
00295   PRUint32 i, slotCount = AttrSlotCount();
00296   if (aNamespaceID == kNameSpaceID_None) {
00297     // This should be the common case so lets make an optimized loop
00298     for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00299       if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
00300         return &ATTRS(mImpl)[i].mValue;
00301       }
00302     }
00303 
00304     if (mImpl && mImpl->mMappedAttrs) {
00305       return mImpl->mMappedAttrs->GetAttr(aLocalName);
00306     }
00307   }
00308   else {
00309     for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00310       if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
00311         return &ATTRS(mImpl)[i].mValue;
00312       }
00313     }
00314   }
00315 
00316   return nsnull;
00317 }
00318 
00319 const nsAttrValue*
00320 nsAttrAndChildArray::AttrAt(PRUint32 aPos) const
00321 {
00322   NS_ASSERTION(aPos < AttrCount(),
00323                "out-of-bounds access in nsAttrAndChildArray");
00324 
00325   PRUint32 mapped = MappedAttrCount();
00326   if (aPos < mapped) {
00327     return mImpl->mMappedAttrs->AttrAt(aPos);
00328   }
00329 
00330   return &ATTRS(mImpl)[aPos - mapped].mValue;
00331 }
00332 
00333 nsresult
00334 nsAttrAndChildArray::SetAttr(nsIAtom* aLocalName, const nsAString& aValue)
00335 {
00336   PRUint32 i, slotCount = AttrSlotCount();
00337   for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00338     if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
00339       ATTRS(mImpl)[i].mValue.SetTo(aValue);
00340 
00341       return NS_OK;
00342     }
00343   }
00344 
00345   NS_ENSURE_TRUE(slotCount < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
00346                  NS_ERROR_FAILURE);
00347 
00348   if (i == slotCount && !AddAttrSlot()) {
00349     return NS_ERROR_OUT_OF_MEMORY;
00350   }
00351 
00352   new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName);
00353   new (&ATTRS(mImpl)[i].mValue) nsAttrValue(aValue);
00354 
00355   return NS_OK;
00356 }
00357 
00358 nsresult
00359 nsAttrAndChildArray::SetAndTakeAttr(nsIAtom* aLocalName, nsAttrValue& aValue)
00360 {
00361   PRUint32 i, slotCount = AttrSlotCount();
00362   for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00363     if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
00364       ATTRS(mImpl)[i].mValue.Reset();
00365       ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
00366 
00367       return NS_OK;
00368     }
00369   }
00370 
00371   NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
00372                  NS_ERROR_FAILURE);
00373 
00374   if (i == slotCount && !AddAttrSlot()) {
00375     return NS_ERROR_OUT_OF_MEMORY;
00376   }
00377 
00378   new (&ATTRS(mImpl)[i].mName) nsAttrName(aLocalName);
00379   new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
00380   ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
00381 
00382   return NS_OK;
00383 }
00384 
00385 nsresult
00386 nsAttrAndChildArray::SetAndTakeAttr(nsINodeInfo* aName, nsAttrValue& aValue)
00387 {
00388   PRInt32 namespaceID = aName->NamespaceID();
00389   nsIAtom* localName = aName->NameAtom();
00390   if (namespaceID == kNameSpaceID_None) {
00391     return SetAndTakeAttr(localName, aValue);
00392   }
00393 
00394   PRUint32 i, slotCount = AttrSlotCount();
00395   for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00396     if (ATTRS(mImpl)[i].mName.Equals(localName, namespaceID)) {
00397       ATTRS(mImpl)[i].mName.SetTo(aName);
00398       ATTRS(mImpl)[i].mValue.Reset();
00399       ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
00400 
00401       return NS_OK;
00402     }
00403   }
00404 
00405   NS_ENSURE_TRUE(i < ATTRCHILD_ARRAY_MAX_ATTR_COUNT,
00406                  NS_ERROR_FAILURE);
00407 
00408   if (i == slotCount && !AddAttrSlot()) {
00409     return NS_ERROR_OUT_OF_MEMORY;
00410   }
00411 
00412   new (&ATTRS(mImpl)[i].mName) nsAttrName(aName);
00413   new (&ATTRS(mImpl)[i].mValue) nsAttrValue();
00414   ATTRS(mImpl)[i].mValue.SwapValueWith(aValue);
00415 
00416   return NS_OK;
00417 }
00418 
00419 
00420 nsresult
00421 nsAttrAndChildArray::RemoveAttrAt(PRUint32 aPos, nsAttrValue& aValue)
00422 {
00423   NS_ASSERTION(aPos < AttrCount(), "out-of-bounds");
00424 
00425   PRUint32 mapped = MappedAttrCount();
00426   if (aPos < mapped) {
00427     if (mapped == 1) {
00428       // We're removing the last mapped attribute.  Can't swap in this
00429       // case; have to copy.
00430       aValue.SetTo(*mImpl->mMappedAttrs->AttrAt(0));
00431       NS_RELEASE(mImpl->mMappedAttrs);
00432 
00433       return NS_OK;
00434     }
00435 
00436     nsRefPtr<nsMappedAttributes> mapped;
00437     nsresult rv = GetModifiableMapped(nsnull, nsnull, PR_FALSE,
00438                                       getter_AddRefs(mapped));
00439     NS_ENSURE_SUCCESS(rv, rv);
00440 
00441     mapped->RemoveAttrAt(aPos, aValue);
00442 
00443     return MakeMappedUnique(mapped);
00444   }
00445 
00446   aPos -= mapped;
00447   ATTRS(mImpl)[aPos].mValue.SwapValueWith(aValue);
00448   ATTRS(mImpl)[aPos].~InternalAttr();
00449 
00450   PRUint32 slotCount = AttrSlotCount();
00451   memmove(&ATTRS(mImpl)[aPos],
00452           &ATTRS(mImpl)[aPos + 1],
00453           (slotCount - aPos - 1) * sizeof(InternalAttr));
00454   memset(&ATTRS(mImpl)[slotCount - 1], nsnull, sizeof(InternalAttr));
00455 
00456   return NS_OK;
00457 }
00458 
00459 const nsAttrName*
00460 nsAttrAndChildArray::GetSafeAttrNameAt(PRUint32 aPos) const
00461 {
00462   PRUint32 mapped = MappedAttrCount();
00463   if (aPos < mapped) {
00464     return mImpl->mMappedAttrs->NameAt(aPos);
00465   }
00466 
00467   // Warn here since we should make this non-bounds safe
00468   aPos -= mapped;
00469   PRUint32 slotCount = AttrSlotCount();
00470   NS_ENSURE_TRUE(aPos < slotCount, nsnull);
00471 
00472   void** pos = mImpl->mBuffer + aPos * ATTRSIZE;
00473   NS_ENSURE_TRUE(*pos, nsnull);
00474 
00475   return &NS_REINTERPRET_CAST(InternalAttr*, pos)->mName;
00476 }
00477 
00478 const nsAttrName*
00479 nsAttrAndChildArray::GetExistingAttrNameFromQName(const nsACString& aName) const
00480 {
00481   PRUint32 i, slotCount = AttrSlotCount();
00482   for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00483     if (ATTRS(mImpl)[i].mName.QualifiedNameEquals(aName)) {
00484       return &ATTRS(mImpl)[i].mName;
00485     }
00486   }
00487 
00488   if (mImpl && mImpl->mMappedAttrs) {
00489     return mImpl->mMappedAttrs->GetExistingAttrNameFromQName(aName);
00490   }
00491 
00492   return nsnull;
00493 }
00494 
00495 PRInt32
00496 nsAttrAndChildArray::IndexOfAttr(nsIAtom* aLocalName, PRInt32 aNamespaceID) const
00497 {
00498   PRInt32 idx;
00499   if (mImpl && mImpl->mMappedAttrs) {
00500     idx = mImpl->mMappedAttrs->IndexOfAttr(aLocalName, aNamespaceID);
00501     if (idx >= 0) {
00502       return idx;
00503     }
00504   }
00505 
00506   PRUint32 i;
00507   PRUint32 mapped = MappedAttrCount();
00508   PRUint32 slotCount = AttrSlotCount();
00509   if (aNamespaceID == kNameSpaceID_None) {
00510     // This should be the common case so lets make an optimized loop
00511     for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00512       if (ATTRS(mImpl)[i].mName.Equals(aLocalName)) {
00513         return i + mapped;
00514       }
00515     }
00516   }
00517   else {
00518     for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00519       if (ATTRS(mImpl)[i].mName.Equals(aLocalName, aNamespaceID)) {
00520         return i + mapped;
00521       }
00522     }
00523   }
00524 
00525   return -1;
00526 }
00527 
00528 nsresult
00529 nsAttrAndChildArray::SetAndTakeMappedAttr(nsIAtom* aLocalName,
00530                                           nsAttrValue& aValue,
00531                                           nsGenericHTMLElement* aContent,
00532                                           nsHTMLStyleSheet* aSheet)
00533 {
00534   nsRefPtr<nsMappedAttributes> mapped;
00535   nsresult rv = GetModifiableMapped(aContent, aSheet, PR_TRUE,
00536                                     getter_AddRefs(mapped));
00537   NS_ENSURE_SUCCESS(rv, rv);
00538 
00539   rv = mapped->SetAndTakeAttr(aLocalName, aValue);
00540   NS_ENSURE_SUCCESS(rv, rv);
00541 
00542   return MakeMappedUnique(mapped);
00543 }
00544 
00545 nsresult
00546 nsAttrAndChildArray::SetMappedAttrStyleSheet(nsHTMLStyleSheet* aSheet)
00547 {
00548   if (!mImpl || !mImpl->mMappedAttrs ||
00549       aSheet == mImpl->mMappedAttrs->GetStyleSheet()) {
00550     return NS_OK;
00551   }
00552 
00553   nsRefPtr<nsMappedAttributes> mapped;
00554   nsresult rv = GetModifiableMapped(nsnull, nsnull, PR_FALSE, 
00555                                     getter_AddRefs(mapped));
00556   NS_ENSURE_SUCCESS(rv, rv);
00557 
00558   mapped->SetStyleSheet(aSheet);
00559 
00560   return MakeMappedUnique(mapped);
00561 }
00562 
00563 void
00564 nsAttrAndChildArray::WalkMappedAttributeStyleRules(nsRuleWalker* aRuleWalker)
00565 {
00566   if (mImpl && mImpl->mMappedAttrs && aRuleWalker) {
00567     aRuleWalker->Forward(mImpl->mMappedAttrs);
00568   }
00569 }
00570 
00571 void
00572 nsAttrAndChildArray::Compact()
00573 {
00574   if (!mImpl) {
00575     return;
00576   }
00577 
00578   // First compress away empty attrslots
00579   PRUint32 slotCount = AttrSlotCount();
00580   PRUint32 attrCount = NonMappedAttrCount();
00581   PRUint32 childCount = ChildCount();
00582 
00583   if (attrCount < slotCount) {
00584     memmove(mImpl->mBuffer + attrCount * ATTRSIZE,
00585             mImpl->mBuffer + slotCount * ATTRSIZE,
00586             childCount * sizeof(nsIContent*));
00587     SetAttrSlotCount(attrCount);
00588   }
00589 
00590   // Then resize or free buffer
00591   PRUint32 newSize = attrCount * ATTRSIZE + childCount;
00592   if (!newSize && !mImpl->mMappedAttrs) {
00593     PR_Free(mImpl);
00594     mImpl = nsnull;
00595   }
00596   else if (newSize < mImpl->mBufferSize) {
00597     mImpl = NS_STATIC_CAST(Impl*, PR_Realloc(mImpl, (newSize + NS_IMPL_EXTRA_SIZE) * sizeof(nsIContent*)));
00598     NS_ASSERTION(mImpl, "failed to reallocate to smaller buffer");
00599 
00600     mImpl->mBufferSize = newSize;
00601   }
00602 }
00603 
00604 void
00605 nsAttrAndChildArray::Clear()
00606 {
00607   if (!mImpl) {
00608     return;
00609   }
00610 
00611   if (mImpl->mMappedAttrs) {
00612     NS_RELEASE(mImpl->mMappedAttrs);
00613   }
00614 
00615   PRUint32 i, slotCount = AttrSlotCount();
00616   for (i = 0; i < slotCount && mImpl->mBuffer[i * ATTRSIZE]; ++i) {
00617     ATTRS(mImpl)[i].~InternalAttr();
00618   }
00619 
00620   PRUint32 end = slotCount * ATTRSIZE + ChildCount();
00621   for (i = slotCount * ATTRSIZE; i < end; ++i) {
00622     nsIContent* child = NS_STATIC_CAST(nsIContent*, mImpl->mBuffer[i]);
00623     // making this PR_FALSE so tree teardown doesn't end up being
00624     // O(N*D) (number of nodes times average depth of tree).
00625     child->UnbindFromTree(PR_FALSE); // XXX is it better to let the owner do this?
00626     NS_RELEASE(child);
00627   }
00628 
00629   SetAttrSlotAndChildCount(0, 0);
00630 }
00631 
00632 PRUint32
00633 nsAttrAndChildArray::NonMappedAttrCount() const
00634 {
00635   if (!mImpl) {
00636     return 0;
00637   }
00638 
00639   PRUint32 count = AttrSlotCount();
00640   while (count > 0 && !mImpl->mBuffer[(count - 1) * ATTRSIZE]) {
00641     --count;
00642   }
00643 
00644   return count;
00645 }
00646 
00647 PRUint32
00648 nsAttrAndChildArray::MappedAttrCount() const
00649 {
00650   return mImpl && mImpl->mMappedAttrs ? (PRUint32)mImpl->mMappedAttrs->Count() : 0;
00651 }
00652 
00653 nsresult
00654 nsAttrAndChildArray::GetModifiableMapped(nsGenericHTMLElement* aContent,
00655                                          nsHTMLStyleSheet* aSheet,
00656                                          PRBool aWillAddAttr,
00657                                          nsMappedAttributes** aModifiable)
00658 {
00659   *aModifiable = nsnull;
00660 
00661   if (mImpl && mImpl->mMappedAttrs) {
00662     *aModifiable = mImpl->mMappedAttrs->Clone(aWillAddAttr);
00663     NS_ENSURE_TRUE(*aModifiable, NS_ERROR_OUT_OF_MEMORY);
00664 
00665     NS_ADDREF(*aModifiable);
00666     
00667     return NS_OK;
00668   }
00669 
00670   NS_ASSERTION(aContent, "Trying to create modifiable without content");
00671 
00672   nsMapRuleToAttributesFunc mapRuleFunc =
00673     aContent->GetAttributeMappingFunction();
00674   *aModifiable = new nsMappedAttributes(aSheet, mapRuleFunc);
00675   NS_ENSURE_TRUE(*aModifiable, NS_ERROR_OUT_OF_MEMORY);
00676 
00677   NS_ADDREF(*aModifiable);
00678 
00679   return NS_OK;
00680 }
00681 
00682 nsresult
00683 nsAttrAndChildArray::MakeMappedUnique(nsMappedAttributes* aAttributes)
00684 {
00685   NS_ASSERTION(aAttributes, "missing attributes");
00686 
00687   if (!mImpl && !GrowBy(1)) {
00688     return NS_ERROR_OUT_OF_MEMORY;
00689   }
00690 
00691   if (!aAttributes->GetStyleSheet()) {
00692     // This doesn't currently happen, but it could if we do loading right
00693 
00694     nsRefPtr<nsMappedAttributes> mapped(aAttributes);
00695     mapped.swap(mImpl->mMappedAttrs);
00696 
00697     return NS_OK;
00698   }
00699 
00700   nsRefPtr<nsMappedAttributes> mapped =
00701     aAttributes->GetStyleSheet()->UniqueMappedAttributes(aAttributes);
00702   NS_ENSURE_TRUE(mapped, NS_ERROR_OUT_OF_MEMORY);
00703 
00704   if (mapped != aAttributes) {
00705     // Reset the stylesheet of aAttributes so that it doesn't spend time
00706     // trying to remove itself from the hash. There is no risk that aAttributes
00707     // is in the hash since it will always have come from GetModifiableMapped,
00708     // which never returns maps that are in the hash (such hashes are by
00709     // nature not modifiable).
00710     aAttributes->DropStyleSheetReference();
00711   }
00712   mapped.swap(mImpl->mMappedAttrs);
00713 
00714   return NS_OK;
00715 }
00716 
00717 
00718 PRBool
00719 nsAttrAndChildArray::GrowBy(PRUint32 aGrowSize)
00720 {
00721   PRUint32 size = mImpl ? mImpl->mBufferSize + NS_IMPL_EXTRA_SIZE : 0;
00722   PRUint32 minSize = size + aGrowSize;
00723 
00724   if (minSize <= ATTRCHILD_ARRAY_LINEAR_THRESHOLD) {
00725     do {
00726       size += ATTRCHILD_ARRAY_GROWSIZE;
00727     } while (size < minSize);
00728   }
00729   else {
00730     size = PR_BIT(PR_CeilingLog2(minSize));
00731   }
00732 
00733   Impl* newImpl = NS_STATIC_CAST(Impl*,
00734       mImpl ? PR_Realloc(mImpl, size * sizeof(void*)) :
00735               PR_Malloc(size * sizeof(void*)));
00736   NS_ENSURE_TRUE(newImpl, PR_FALSE);
00737 
00738   Impl* oldImpl = mImpl;
00739   mImpl = newImpl;
00740 
00741   // Set initial counts if we didn't have a buffer before
00742   if (!oldImpl) {
00743     mImpl->mMappedAttrs = nsnull;
00744     SetAttrSlotAndChildCount(0, 0);
00745   }
00746 
00747   mImpl->mBufferSize = size - NS_IMPL_EXTRA_SIZE;
00748 
00749   return PR_TRUE;
00750 }
00751 
00752 PRBool
00753 nsAttrAndChildArray::AddAttrSlot()
00754 {
00755   PRUint32 slotCount = AttrSlotCount();
00756   PRUint32 childCount = ChildCount();
00757 
00758   // Grow buffer if needed
00759   if (!(mImpl && mImpl->mBufferSize >= (slotCount + 1) * ATTRSIZE + childCount) &&
00760       !GrowBy(ATTRSIZE)) {
00761     return PR_FALSE;
00762   }
00763   void** offset = mImpl->mBuffer + slotCount * ATTRSIZE;
00764 
00765   if (childCount > 0) {
00766     memmove(&ATTRS(mImpl)[slotCount + 1], &ATTRS(mImpl)[slotCount],
00767             childCount * sizeof(nsIContent*));
00768   }
00769 
00770   SetAttrSlotCount(slotCount + 1);
00771   offset[0] = nsnull;
00772   offset[1] = nsnull;
00773 
00774   return PR_TRUE;
00775 }