michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: // vim:cindent:ts=2:et:sw=2:
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* base class for nsCounterList and nsQuoteList */
michael@0: 
michael@0: #include "nsGenConList.h"
michael@0: #include "nsLayoutUtils.h"
michael@0: #include "nsIContent.h"
michael@0: 
michael@0: void
michael@0: nsGenConList::Clear()
michael@0: {
michael@0:   //Delete entire list
michael@0:   if (!mFirstNode)
michael@0:     return;
michael@0:   for (nsGenConNode *node = Next(mFirstNode); node != mFirstNode;
michael@0:        node = Next(mFirstNode))
michael@0:   {
michael@0:     Remove(node);
michael@0:     delete node;
michael@0:   }
michael@0:   delete mFirstNode;
michael@0: 
michael@0:   mFirstNode = nullptr;
michael@0:   mSize = 0;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
michael@0: {
michael@0:   if (!mFirstNode)
michael@0:     return false; // list empty
michael@0:   nsGenConNode* node;
michael@0:   bool destroyed = false;
michael@0:   while (mFirstNode->mPseudoFrame == aFrame) {
michael@0:     destroyed = true;
michael@0:     node = Next(mFirstNode);
michael@0:     bool isLastNode = node == mFirstNode; // before they're dangling
michael@0:     Remove(mFirstNode);
michael@0:     delete mFirstNode;
michael@0:     if (isLastNode) {
michael@0:       mFirstNode = nullptr;
michael@0:       return true;
michael@0:     }
michael@0:     else {
michael@0:       mFirstNode = node;
michael@0:     }
michael@0:   }
michael@0:   node = Next(mFirstNode);
michael@0:   while (node != mFirstNode) {
michael@0:     if (node->mPseudoFrame == aFrame) {
michael@0:       destroyed = true;
michael@0:       nsGenConNode *nextNode = Next(node);
michael@0:       Remove(node);
michael@0:       delete node;
michael@0:       node = nextNode;
michael@0:     } else {
michael@0:       node = Next(node);
michael@0:     }
michael@0:   }
michael@0:   return destroyed;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Compute the type of the pseudo and the content for the pseudo that
michael@0:  * we'll use for comparison purposes.
michael@0:  * @param aContent the content to use is stored here; it's the element
michael@0:  * that generated the ::before or ::after content, or (if not for generated
michael@0:  * content), the frame's own element
michael@0:  * @return -1 for ::before, +1 for ::after, and 0 otherwise.
michael@0:  */
michael@0: inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent)
michael@0: {
michael@0:   nsIAtom *pseudo = aFrame->StyleContext()->GetPseudo();
michael@0:   if (pseudo == nsCSSPseudoElements::before) {
michael@0:     *aContent = aFrame->GetContent()->GetParent();
michael@0:     return -1;
michael@0:   }
michael@0:   if (pseudo == nsCSSPseudoElements::after) {
michael@0:     *aContent = aFrame->GetContent()->GetParent();
michael@0:     return 1;
michael@0:   }
michael@0:   *aContent = aFrame->GetContent();
michael@0:   return 0;
michael@0: }
michael@0: 
michael@0: /* static */ bool
michael@0: nsGenConList::NodeAfter(const nsGenConNode* aNode1, const nsGenConNode* aNode2)
michael@0: {
michael@0:   nsIFrame *frame1 = aNode1->mPseudoFrame;
michael@0:   nsIFrame *frame2 = aNode2->mPseudoFrame;
michael@0:   if (frame1 == frame2) {
michael@0:     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
michael@0:     return aNode1->mContentIndex > aNode2->mContentIndex;
michael@0:   }
michael@0:   nsIContent *content1;
michael@0:   nsIContent *content2;
michael@0:   int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
michael@0:   int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
michael@0:   if (pseudoType1 == 0 || pseudoType2 == 0) {
michael@0:     if (content1 == content2) {
michael@0:       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
michael@0:       return pseudoType2 == 0;
michael@0:     }
michael@0:     // We want to treat an element as coming before its :before (preorder
michael@0:     // traversal), so treating both as :before now works.
michael@0:     if (pseudoType1 == 0) pseudoType1 = -1;
michael@0:     if (pseudoType2 == 0) pseudoType2 = -1;
michael@0:   } else {
michael@0:     if (content1 == content2) {
michael@0:       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
michael@0:       return pseudoType1 == 1;
michael@0:     }
michael@0:   }
michael@0:   // XXX Switch to the frame version of DoCompareTreePosition?
michael@0:   int32_t cmp = nsLayoutUtils::DoCompareTreePosition(content1, content2,
michael@0:                                                      pseudoType1, -pseudoType2);
michael@0:   NS_ASSERTION(cmp != 0, "same content, different frames");
michael@0:   return cmp > 0;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsGenConList::Insert(nsGenConNode* aNode)
michael@0: {
michael@0:   if (mFirstNode) {
michael@0:     // Check for append.
michael@0:     if (NodeAfter(aNode, Prev(mFirstNode))) {
michael@0:       PR_INSERT_BEFORE(aNode, mFirstNode);
michael@0:     }
michael@0:     else {
michael@0:       // Binary search.
michael@0: 
michael@0:       // the range of indices at which |aNode| could end up.
michael@0:       // (We already know it can't be at index mSize.)
michael@0:       uint32_t first = 0, last = mSize - 1;
michael@0: 
michael@0:       // A cursor to avoid walking more than the length of the list.
michael@0:       nsGenConNode *curNode = Prev(mFirstNode);
michael@0:       uint32_t curIndex = mSize - 1;
michael@0: 
michael@0:       while (first != last) {
michael@0:         uint32_t test = (first + last) / 2;
michael@0:         if (last == curIndex) {
michael@0:           for ( ; curIndex != test; --curIndex)
michael@0:             curNode = Prev(curNode);
michael@0:         } else {
michael@0:           for ( ; curIndex != test; ++curIndex)
michael@0:             curNode = Next(curNode);
michael@0:         }
michael@0: 
michael@0:         if (NodeAfter(aNode, curNode)) {
michael@0:           first = test + 1;
michael@0:           // if we exit the loop, we need curNode to be right
michael@0:           ++curIndex;
michael@0:           curNode = Next(curNode);
michael@0:         } else {
michael@0:           last = test;
michael@0:         }
michael@0:       }
michael@0:       PR_INSERT_BEFORE(aNode, curNode);
michael@0:       if (curNode == mFirstNode) {
michael@0:         mFirstNode = aNode;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0:   else {
michael@0:     // initialize list with first node
michael@0:     PR_INIT_CLIST(aNode);
michael@0:     mFirstNode = aNode;
michael@0:   }
michael@0:   ++mSize;
michael@0: 
michael@0:   NS_ASSERTION(aNode == mFirstNode || NodeAfter(aNode, Prev(aNode)),
michael@0:                "sorting error");
michael@0:   NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode),
michael@0:                "sorting error");
michael@0: }