layout/base/nsGenConList.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 // vim:cindent:ts=2:et:sw=2:
   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 /* base class for nsCounterList and nsQuoteList */
   8
   9 #include "nsGenConList.h"
  10 #include "nsLayoutUtils.h"
  11 #include "nsIContent.h"
  12
  13 void
  14 nsGenConList::Clear()
  15 {
  16   //Delete entire list
  17   if (!mFirstNode)
  18     return;
  19   for (nsGenConNode *node = Next(mFirstNode); node != mFirstNode;
  20        node = Next(mFirstNode))
  21   {
  22     Remove(node);
  23     delete node;
  24   }
  25   delete mFirstNode;
  26
  27   mFirstNode = nullptr;
  28   mSize = 0;
  29 }
  30
  31 bool
  32 nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
  33 {
  34   if (!mFirstNode)
  35     return false; // list empty
  36   nsGenConNode* node;
  37   bool destroyed = false;
  38   while (mFirstNode->mPseudoFrame == aFrame) {
  39     destroyed = true;
  40     node = Next(mFirstNode);
  41     bool isLastNode = node == mFirstNode; // before they're dangling
  42     Remove(mFirstNode);
  43     delete mFirstNode;
  44     if (isLastNode) {
  45       mFirstNode = nullptr;
  46       return true;
  47     }
  48     else {
  49       mFirstNode = node;
  50     }
  51   }
  52   node = Next(mFirstNode);
  53   while (node != mFirstNode) {
  54     if (node->mPseudoFrame == aFrame) {
  55       destroyed = true;
  56       nsGenConNode *nextNode = Next(node);
  57       Remove(node);
  58       delete node;
  59       node = nextNode;
  60     } else {
  61       node = Next(node);
  62     }
  63   }
  64   return destroyed;
  65 }
  66
  67 /**
  68  * Compute the type of the pseudo and the content for the pseudo that
  69  * we'll use for comparison purposes.
  70  * @param aContent the content to use is stored here; it's the element
  71  * that generated the ::before or ::after content, or (if not for generated
  72  * content), the frame's own element
  73  * @return -1 for ::before, +1 for ::after, and 0 otherwise.
  74  */
  75 inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent)
  76 {
  77   nsIAtom *pseudo = aFrame->StyleContext()->GetPseudo();
  78   if (pseudo == nsCSSPseudoElements::before) {
  79     *aContent = aFrame->GetContent()->GetParent();
  80     return -1;
  81   }
  82   if (pseudo == nsCSSPseudoElements::after) {
  83     *aContent = aFrame->GetContent()->GetParent();
  84     return 1;
  85   }
  86   *aContent = aFrame->GetContent();
  87   return 0;
  88 }
  89
  90 /* static */ bool
  91 nsGenConList::NodeAfter(const nsGenConNode* aNode1, const nsGenConNode* aNode2)
  92 {
  93   nsIFrame *frame1 = aNode1->mPseudoFrame;
  94   nsIFrame *frame2 = aNode2->mPseudoFrame;
  95   if (frame1 == frame2) {
  96     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
  97     return aNode1->mContentIndex > aNode2->mContentIndex;
  98   }
  99   nsIContent *content1;
 100   nsIContent *content2;
 101   int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
 102   int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
 103   if (pseudoType1 == 0 || pseudoType2 == 0) {
 104     if (content1 == content2) {
 105       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
 106       return pseudoType2 == 0;
 107     }
 108     // We want to treat an element as coming before its :before (preorder
 109     // traversal), so treating both as :before now works.
 110     if (pseudoType1 == 0) pseudoType1 = -1;
 111     if (pseudoType2 == 0) pseudoType2 = -1;
 112   } else {
 113     if (content1 == content2) {
 114       NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
 115       return pseudoType1 == 1;
 116     }
 117   }
 118   // XXX Switch to the frame version of DoCompareTreePosition?
 119   int32_t cmp = nsLayoutUtils::DoCompareTreePosition(content1, content2,
 120                                                      pseudoType1, -pseudoType2);
 121   NS_ASSERTION(cmp != 0, "same content, different frames");
 122   return cmp > 0;
 123 }
 124
 125 void
 126 nsGenConList::Insert(nsGenConNode* aNode)
 127 {
 128   if (mFirstNode) {
 129     // Check for append.
 130     if (NodeAfter(aNode, Prev(mFirstNode))) {
 131       PR_INSERT_BEFORE(aNode, mFirstNode);
 132     }
 133     else {
 134       // Binary search.
 135
 136       // the range of indices at which |aNode| could end up.
 137       // (We already know it can't be at index mSize.)
 138       uint32_t first = 0, last = mSize - 1;
 139
 140       // A cursor to avoid walking more than the length of the list.
 141       nsGenConNode *curNode = Prev(mFirstNode);
 142       uint32_t curIndex = mSize - 1;
 143
 144       while (first != last) {
 145         uint32_t test = (first + last) / 2;
 146         if (last == curIndex) {
 147           for ( ; curIndex != test; --curIndex)
 148             curNode = Prev(curNode);
 149         } else {
 150           for ( ; curIndex != test; ++curIndex)
 151             curNode = Next(curNode);
 152         }
 153
 154         if (NodeAfter(aNode, curNode)) {
 155           first = test + 1;
 156           // if we exit the loop, we need curNode to be right
 157           ++curIndex;
 158           curNode = Next(curNode);
 159         } else {
 160           last = test;
 161         }
 162       }
 163       PR_INSERT_BEFORE(aNode, curNode);
 164       if (curNode == mFirstNode) {
 165         mFirstNode = aNode;
 166       }
 167     }
 168   }
 169   else {
 170     // initialize list with first node
 171     PR_INIT_CLIST(aNode);
 172     mFirstNode = aNode;
 173   }
 174   ++mSize;
 175
 176   NS_ASSERTION(aNode == mFirstNode || NodeAfter(aNode, Prev(aNode)),
 177                "sorting error");
 178   NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode),
 179                "sorting error");
 180 }