Back to index

lightning-sunbird  0.9+nobinonly
nsGenConList.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 // vim:cindent:ts=2:et:sw=2:
00003 /* ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is mozilla.org code.
00017  *
00018  * The Initial Developer of the Original Code is
00019  * Esben Mose Hansen.
00020  *
00021  * Contributor(s):
00022  *   Esben Mose Hansen <esben@oek.dk> (original author)
00023  *   L. David Baron <dbaron@dbaron.org>
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 "nsGenConList.h"
00040 #include "nsLayoutUtils.h"
00041 
00042 void
00043 nsGenConList::Clear()
00044 {
00045   //Delete entire list
00046   if (!mFirstNode)
00047     return;
00048   for (nsGenConNode *node = Next(mFirstNode); node != mFirstNode;
00049        node = Next(mFirstNode))
00050   {
00051     Remove(node);
00052     delete node;
00053   }
00054   delete mFirstNode;
00055 
00056   mFirstNode = nsnull;
00057   mSize = 0;
00058 }
00059 
00060 PRBool
00061 nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
00062 {
00063   if (!mFirstNode)
00064     return PR_FALSE; // list empty
00065   nsGenConNode* node;
00066   PRBool destroyed = PR_FALSE;
00067   while (mFirstNode->mPseudoFrame == aFrame) {
00068     destroyed = PR_TRUE;
00069     node = Next(mFirstNode);
00070     if (node == mFirstNode) { // Last link
00071       mFirstNode = nsnull;
00072       delete node;
00073       return PR_TRUE;
00074     }
00075     else {
00076       Remove(mFirstNode);
00077       delete mFirstNode;
00078       mFirstNode = node;
00079     }
00080   }
00081   node = Next(mFirstNode);
00082   while (node != mFirstNode) {
00083     if (node->mPseudoFrame == aFrame) {
00084       destroyed = PR_TRUE;
00085       nsGenConNode *nextNode = Next(node);
00086       Remove(node);
00087       delete node;
00088       node = nextNode;
00089     } else {
00090       node = Next(node);
00091     }
00092   }
00093   return destroyed;
00094 }
00095 
00096 // return -1 for ::before, +1 for ::after, and 0 otherwise.
00097 inline PRBool PseudoCompareType(nsIFrame *aFrame)
00098 {
00099   nsIAtom *pseudo = aFrame->GetStyleContext()->GetPseudoType();
00100   if (pseudo == nsCSSPseudoElements::before)
00101     return -1;
00102   if (pseudo == nsCSSPseudoElements::after)
00103     return 1;
00104   return 0;
00105 }
00106 
00107 /* static */ PRBool
00108 nsGenConList::NodeAfter(const nsGenConNode* aNode1, const nsGenConNode* aNode2)
00109 {
00110   nsIFrame *frame1 = aNode1->mPseudoFrame;
00111   nsIFrame *frame2 = aNode2->mPseudoFrame;
00112   if (frame1 == frame2) {
00113     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
00114     return aNode1->mContentIndex > aNode2->mContentIndex;
00115   }
00116   PRInt32 pseudoType1 = PseudoCompareType(frame1);
00117   PRInt32 pseudoType2 = PseudoCompareType(frame2);
00118   nsIContent *content1 = frame1->GetContent();
00119   nsIContent *content2 = frame2->GetContent();
00120   if (pseudoType1 == 0 || pseudoType2 == 0) {
00121     if (content1 == content2) {
00122       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
00123       return pseudoType2 == 0;
00124     }
00125     // We want to treat an element as coming before its :before (preorder
00126     // traversal), so treating both as :before now works.
00127     if (pseudoType1 == 0) pseudoType1 = -1;
00128     if (pseudoType2 == 0) pseudoType2 = -1;
00129   } else {
00130     if (content1 == content2) {
00131       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
00132       return pseudoType1 == 1;
00133     }
00134   }
00135   PRInt32 cmp = nsLayoutUtils::DoCompareTreePosition(content1, content2,
00136                                                      pseudoType1, -pseudoType2);
00137   NS_ASSERTION(cmp != 0, "same content, different frames");
00138   return cmp > 0;
00139 }
00140 
00141 void
00142 nsGenConList::Insert(nsGenConNode* aNode)
00143 {
00144   if (mFirstNode) {
00145     // Check for append.
00146     if (NodeAfter(aNode, Prev(mFirstNode))) {
00147       PR_INSERT_BEFORE(aNode, mFirstNode);
00148     }
00149     else {
00150       // Binary search.
00151 
00152       // the range of indices at which |aNode| could end up.
00153       PRUint32 first = 0, last = mSize - 1;
00154 
00155       // A cursor to avoid walking more than the length of the list.
00156       nsGenConNode *curNode = Prev(mFirstNode);
00157       PRUint32 curIndex = mSize - 1;
00158 
00159       while (first != last) {
00160         PRUint32 test = (first + last) / 2;
00161         if (last == curIndex) {
00162           for ( ; curIndex != test; --curIndex)
00163             curNode = Prev(curNode);
00164         } else {
00165           for ( ; curIndex != test; ++curIndex)
00166             curNode = Next(curNode);
00167         }
00168 
00169         if (NodeAfter(aNode, curNode)) {
00170           first = test + 1;
00171           // if we exit the loop, we need curNode to be right
00172           ++curIndex;
00173           curNode = Next(curNode);
00174         } else {
00175           last = test;
00176         }
00177       }
00178       PR_INSERT_BEFORE(aNode, curNode);
00179       if (curNode == mFirstNode) {
00180         mFirstNode = aNode;
00181       }
00182     }
00183   }
00184   else {
00185     // initialize list with first node
00186     PR_INIT_CLIST(aNode);
00187     mFirstNode = aNode;
00188   }
00189   ++mSize;
00190 }