|
Packit |
f0b94e |
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
|
|
Packit |
f0b94e |
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
|
|
Packit |
f0b94e |
/* This Source Code Form is subject to the terms of the Mozilla Public
|
|
Packit |
f0b94e |
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
Packit |
f0b94e |
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
/* base class for nsCounterList and nsQuoteList */
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
#include "nsGenConList.h"
|
|
Packit |
f0b94e |
#include "nsLayoutUtils.h"
|
|
Packit |
f0b94e |
#include "nsIContent.h"
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
void nsGenConList::Clear() {
|
|
Packit |
f0b94e |
// Delete entire list.
|
|
Packit |
f0b94e |
mNodes.Clear();
|
|
Packit |
f0b94e |
while (nsGenConNode* node = mList.popFirst()) {
|
|
Packit |
f0b94e |
delete node;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
mSize = 0;
|
|
Packit |
f0b94e |
mLastInserted = nullptr;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
bool nsGenConList::DestroyNodesFor(nsIFrame* aFrame) {
|
|
Packit |
f0b94e |
// This algorithm relies on the invariant that nodes of a frame are
|
|
Packit |
f0b94e |
// put contiguously in the linked list. This is guaranteed because
|
|
Packit |
f0b94e |
// each frame is mapped to only one (nsIContent, pseudoType) pair,
|
|
Packit |
f0b94e |
// and the nodes in the linked list are put in the tree order based
|
|
Packit |
f0b94e |
// on that pair and offset inside frame.
|
|
Packit |
f0b94e |
nsGenConNode* node = mNodes.GetAndRemove(aFrame).valueOr(nullptr);
|
|
Packit |
f0b94e |
if (!node) {
|
|
Packit |
f0b94e |
return false;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
MOZ_ASSERT(node->mPseudoFrame == aFrame);
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
while (node && node->mPseudoFrame == aFrame) {
|
|
Packit |
f0b94e |
nsGenConNode* nextNode = Next(node);
|
|
Packit |
f0b94e |
Destroy(node);
|
|
Packit |
f0b94e |
node = nextNode;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
// Modification of the list invalidates the cached pointer.
|
|
Packit |
f0b94e |
mLastInserted = nullptr;
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
return true;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
/**
|
|
Packit |
f0b94e |
* Compute the type of the pseudo and the content for the pseudo that
|
|
Packit |
f0b94e |
* we'll use for comparison purposes.
|
|
Packit |
f0b94e |
* @param aContent the content to use is stored here; it's the element
|
|
Packit |
f0b94e |
* that generated the ::before or ::after content, or (if not for generated
|
|
Packit |
f0b94e |
* content), the frame's own element
|
|
Packit |
f0b94e |
* @return -1 for ::before, +1 for ::after, and 0 otherwise.
|
|
Packit |
f0b94e |
*/
|
|
Packit |
f0b94e |
inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent) {
|
|
Packit |
f0b94e |
nsAtom* pseudo = aFrame->StyleContext()->GetPseudo();
|
|
Packit |
f0b94e |
if (pseudo == nsCSSPseudoElements::before) {
|
|
Packit |
f0b94e |
*aContent = aFrame->GetContent()->GetParent();
|
|
Packit |
f0b94e |
return -1;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
if (pseudo == nsCSSPseudoElements::after) {
|
|
Packit |
f0b94e |
*aContent = aFrame->GetContent()->GetParent();
|
|
Packit |
f0b94e |
return 1;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
*aContent = aFrame->GetContent();
|
|
Packit |
f0b94e |
return 0;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
/* static */ bool nsGenConList::NodeAfter(const nsGenConNode* aNode1,
|
|
Packit |
f0b94e |
const nsGenConNode* aNode2) {
|
|
Packit |
f0b94e |
nsIFrame* frame1 = aNode1->mPseudoFrame;
|
|
Packit |
f0b94e |
nsIFrame* frame2 = aNode2->mPseudoFrame;
|
|
Packit |
f0b94e |
if (frame1 == frame2) {
|
|
Packit |
f0b94e |
NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
|
|
Packit |
f0b94e |
return aNode1->mContentIndex > aNode2->mContentIndex;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
nsIContent* content1;
|
|
Packit |
f0b94e |
nsIContent* content2;
|
|
Packit |
f0b94e |
int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
|
|
Packit |
f0b94e |
int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
|
|
Packit |
f0b94e |
if (pseudoType1 == 0 || pseudoType2 == 0) {
|
|
Packit |
f0b94e |
if (content1 == content2) {
|
|
Packit |
f0b94e |
NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
|
|
Packit |
f0b94e |
return pseudoType2 == 0;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
// We want to treat an element as coming before its :before (preorder
|
|
Packit |
f0b94e |
// traversal), so treating both as :before now works.
|
|
Packit |
f0b94e |
if (pseudoType1 == 0) pseudoType1 = -1;
|
|
Packit |
f0b94e |
if (pseudoType2 == 0) pseudoType2 = -1;
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
if (content1 == content2) {
|
|
Packit |
f0b94e |
NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
|
|
Packit |
f0b94e |
return pseudoType1 == 1;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
// XXX Switch to the frame version of DoCompareTreePosition?
|
|
Packit |
f0b94e |
int32_t cmp = nsLayoutUtils::DoCompareTreePosition(content1, content2,
|
|
Packit |
f0b94e |
pseudoType1, -pseudoType2);
|
|
Packit |
f0b94e |
MOZ_ASSERT(cmp != 0, "same content, different frames");
|
|
Packit |
f0b94e |
return cmp > 0;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
void nsGenConList::Insert(nsGenConNode* aNode) {
|
|
Packit |
f0b94e |
// Check for append.
|
|
Packit |
f0b94e |
if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
|
|
Packit |
f0b94e |
mList.insertBack(aNode);
|
|
Packit |
f0b94e |
} else if (mLastInserted && mLastInserted != mList.getLast() &&
|
|
Packit |
f0b94e |
NodeAfter(aNode, mLastInserted) &&
|
|
Packit |
f0b94e |
NodeAfter(Next(mLastInserted), aNode)) {
|
|
Packit |
f0b94e |
// Fast path for inserting many consecutive nodes in one place
|
|
Packit |
f0b94e |
mLastInserted->setNext(aNode);
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
// Binary search.
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
// the range of indices at which |aNode| could end up.
|
|
Packit |
f0b94e |
// (We already know it can't be at index mSize.)
|
|
Packit |
f0b94e |
uint32_t first = 0, last = mSize - 1;
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
// A cursor to avoid walking more than the length of the list.
|
|
Packit |
f0b94e |
nsGenConNode* curNode = mList.getLast();
|
|
Packit |
f0b94e |
uint32_t curIndex = mSize - 1;
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
while (first != last) {
|
|
Packit |
f0b94e |
uint32_t test = (first + last) / 2;
|
|
Packit |
f0b94e |
if (last == curIndex) {
|
|
Packit |
f0b94e |
for (; curIndex != test; --curIndex) curNode = Prev(curNode);
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
for (; curIndex != test; ++curIndex) curNode = Next(curNode);
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
if (NodeAfter(aNode, curNode)) {
|
|
Packit |
f0b94e |
first = test + 1;
|
|
Packit |
f0b94e |
// if we exit the loop, we need curNode to be right
|
|
Packit |
f0b94e |
++curIndex;
|
|
Packit |
f0b94e |
curNode = Next(curNode);
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
last = test;
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
curNode->setPrevious(aNode);
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
++mSize;
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
mLastInserted = aNode;
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
// Set the mapping only if it is the first node of the frame.
|
|
Packit |
f0b94e |
// The DEBUG blocks below are for ensuring the invariant required by
|
|
Packit |
f0b94e |
// nsGenConList::DestroyNodesFor. See comment there.
|
|
Packit |
f0b94e |
if (IsFirst(aNode) || Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
|
|
Packit |
f0b94e |
#ifdef DEBUG
|
|
Packit |
f0b94e |
if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
|
|
Packit |
f0b94e |
MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
|
|
Packit |
f0b94e |
"oldFrameFirstNode should now be immediately after "
|
|
Packit |
f0b94e |
"the newly-inserted one.");
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
// If the node is not the only node in the list.
|
|
Packit |
f0b94e |
if (!IsFirst(aNode) || !IsLast(aNode)) {
|
|
Packit |
f0b94e |
nsGenConNode* nextNode = Next(aNode);
|
|
Packit |
f0b94e |
MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
|
|
Packit |
f0b94e |
"There shouldn't exist any node for this frame.");
|
|
Packit |
f0b94e |
// If the node is neither the first nor the last node
|
|
Packit |
f0b94e |
if (!IsFirst(aNode) && !IsLast(aNode)) {
|
|
Packit |
f0b94e |
MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
|
|
Packit |
f0b94e |
"New node should not break contiguity of nodes of "
|
|
Packit |
f0b94e |
"the same frame.");
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
#endif
|
|
Packit |
f0b94e |
mNodes.Put(aNode->mPseudoFrame, aNode);
|
|
Packit |
f0b94e |
} else {
|
|
Packit |
f0b94e |
#ifdef DEBUG
|
|
Packit |
f0b94e |
nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
|
|
Packit |
f0b94e |
MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
|
|
Packit |
f0b94e |
for (nsGenConNode* curNode = Prev(aNode); curNode != frameFirstNode;
|
|
Packit |
f0b94e |
curNode = Prev(curNode)) {
|
|
Packit |
f0b94e |
MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
|
|
Packit |
f0b94e |
"Every node between frameFirstNode and the new node inserted "
|
|
Packit |
f0b94e |
"should refer to the same frame.");
|
|
Packit |
f0b94e |
MOZ_ASSERT(!IsFirst(curNode),
|
|
Packit |
f0b94e |
"The newly-inserted node should be in a contiguous run after "
|
|
Packit |
f0b94e |
"frameFirstNode, thus frameFirstNode should be reached before "
|
|
Packit |
f0b94e |
"the first node of mList.");
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
#endif
|
|
Packit |
f0b94e |
}
|
|
Packit |
f0b94e |
|
|
Packit |
f0b94e |
NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
|
|
Packit |
f0b94e |
"sorting error");
|
|
Packit |
f0b94e |
NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode), "sorting error");
|
|
Packit |
f0b94e |
}
|