Add m-esr52 at 52.6.0

1 files changed, 482 insertions, 0 deletions

diff --git a/dom/xul/templates/nsTreeRows.cpp b/dom/xul/templates/nsTreeRows.cpp
new file mode 100644
index 000000000..b77a97213
--- /dev/null
+++ b/dom/xul/templates/nsTreeRows.cpp
@@ -0,0 +1,482 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "nsString.h"
+#include "nsTreeRows.h"
+#include <algorithm>
+
+nsTreeRows::Subtree*
+nsTreeRows::EnsureSubtreeFor(Subtree* aParent,
+                             int32_t aChildIndex)
+{
+    Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);
+
+    if (! subtree) {
+        subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);
+        InvalidateCachedRow();
+    }
+
+    return subtree;
+}
+
+nsTreeRows::Subtree*
+nsTreeRows::GetSubtreeFor(const Subtree* aParent,
+                              int32_t aChildIndex,
+                              int32_t* aSubtreeSize)
+{
+    NS_PRECONDITION(aParent, "no parent");
+    NS_PRECONDITION(aChildIndex >= 0, "bad child index");
+
+    Subtree* result = nullptr;
+
+    if (aChildIndex < aParent->mCount)
+        result = aParent->mRows[aChildIndex].mSubtree;
+
+    if (aSubtreeSize)
+        *aSubtreeSize = result ? result->mSubtreeSize : 0;
+
+    return result;
+}
+
+void
+nsTreeRows::RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex)
+{
+    NS_PRECONDITION(aParent, "no parent");
+    NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");
+
+    Row& row = aParent->mRows[aChildIndex];
+
+    if (row.mSubtree) {
+        int32_t subtreeSize = row.mSubtree->GetSubtreeSize();
+
+        delete row.mSubtree;
+        row.mSubtree = nullptr;
+
+        for (Subtree* subtree = aParent; subtree != nullptr; subtree = subtree->mParent)
+            subtree->mSubtreeSize -= subtreeSize;
+    }
+
+    InvalidateCachedRow();
+}
+
+nsTreeRows::iterator
+nsTreeRows::First()
+{
+    iterator result;
+    result.Append(&mRoot, 0);
+    result.SetRowIndex(0);
+    return result;
+}
+
+nsTreeRows::iterator
+nsTreeRows::Last()
+{
+    iterator result;
+
+    // Build up a path along the rightmost edge of the tree
+    Subtree* current = &mRoot;
+    int32_t count = current->Count();
+    do  {
+        int32_t last = count - 1;
+        result.Append(current, last);
+        current = count ? GetSubtreeFor(current, last) : nullptr;
+    } while (current && ((count = current->Count()) != 0));
+
+    // Now, at the bottom rightmost leaf, advance us one off the end.
+    result.GetTop().mChildIndex++;
+
+    // Our row index will be the size of the root subree, plus one.
+    result.SetRowIndex(mRoot.GetSubtreeSize() + 1);
+
+    return result;
+}
+
+nsTreeRows::iterator
+nsTreeRows::operator[](int32_t aRow)
+{
+    // See if we're just lucky, and end up with something
+    // nearby. (This tends to happen a lot due to the way that we get
+    // asked for rows n' stuff.)
+    int32_t last = mLastRow.GetRowIndex();
+    if (last != -1) {
+        if (aRow == last)
+            return mLastRow;
+        else if (last + 1 == aRow)
+            return ++mLastRow;
+        else if (last - 1 == aRow)
+            return --mLastRow;
+    }
+
+    // Nope. Construct a path to the specified index. This is a little
+    // bit better than O(n), because we can skip over subtrees. (So it
+    // ends up being approximately linear in the subtree size, instead
+    // of the entire view size. But, most of the time, big views are
+    // flat. Oh well.)
+    iterator result;
+    Subtree* current = &mRoot;
+
+    int32_t index = 0;
+    result.SetRowIndex(aRow);
+
+    do {
+        int32_t subtreeSize;
+        Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);
+
+        if (subtreeSize >= aRow) {
+            result.Append(current, index);
+            current = subtree;
+            index = 0;
+            --aRow;
+        }
+        else {
+            ++index;
+            aRow -= subtreeSize + 1;
+        }
+    } while (aRow >= 0);
+
+    mLastRow = result;
+    return result;
+}
+
+nsTreeRows::iterator
+nsTreeRows::FindByResource(nsIRDFResource* aResource)
+{
+    // XXX Mmm, scan through the rows one-by-one...
+    iterator last = Last();
+    iterator iter;
+
+    nsresult rv;
+    nsAutoString resourceid;
+    bool stringmode = false;
+
+    for (iter = First(); iter != last; ++iter) {
+        if (!stringmode) {
+            nsCOMPtr<nsIRDFResource> findres;
+            rv = iter->mMatch->mResult->GetResource(getter_AddRefs(findres));
+            if (NS_FAILED(rv)) return last;
+
+            if (findres == aResource)
+                break;
+
+            if (! findres) {
+                const char *uri;
+                aResource->GetValueConst(&uri);
+                CopyUTF8toUTF16(uri, resourceid);
+
+                // set stringmode and fall through
+                stringmode = true;
+            }
+        }
+
+        // additional check because previous block could change stringmode
+        if (stringmode) {
+            nsAutoString findid;
+            rv = iter->mMatch->mResult->GetId(findid);
+            if (NS_FAILED(rv)) return last;
+
+            if (resourceid.Equals(findid))
+                break;
+        }
+    }
+
+    return iter;
+}
+
+nsTreeRows::iterator
+nsTreeRows::Find(nsIXULTemplateResult *aResult)
+{
+    // XXX Mmm, scan through the rows one-by-one...
+    iterator last = Last();
+    iterator iter;
+
+    for (iter = First(); iter != last; ++iter) {
+        if (aResult == iter->mMatch->mResult)
+          break;
+    }
+
+    return iter;
+}
+
+void
+nsTreeRows::Clear()
+{
+    mRoot.Clear();
+    InvalidateCachedRow();
+}
+
+//----------------------------------------------------------------------
+//
+// nsTreeRows::Subtree
+//
+
+nsTreeRows::Subtree::~Subtree()
+{
+    Clear();
+}
+
+void
+nsTreeRows::Subtree::Clear()
+{
+    for (int32_t i = mCount - 1; i >= 0; --i)
+        delete mRows[i].mSubtree;
+
+    delete[] mRows;
+
+    mRows = nullptr;
+    mCount = mCapacity = mSubtreeSize = 0;
+}
+
+nsTreeRows::iterator
+nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex)
+{
+    if (mCount >= mCapacity || aIndex >= mCapacity) {
+        int32_t newCapacity = std::max(mCapacity * 2, aIndex + 1);
+        Row* newRows = new Row[newCapacity];
+        if (! newRows)
+            return iterator();
+
+        for (int32_t i = mCount - 1; i >= 0; --i)
+            newRows[i] = mRows[i];
+
+        delete[] mRows;
+
+        mRows = newRows;
+        mCapacity = newCapacity;
+    }
+
+    for (int32_t i = mCount - 1; i >= aIndex; --i)
+        mRows[i + 1] = mRows[i];
+
+    mRows[aIndex].mMatch = aMatch;
+    mRows[aIndex].mContainerType = eContainerType_Unknown;
+    mRows[aIndex].mContainerState = eContainerState_Unknown;
+    mRows[aIndex].mContainerFill = eContainerFill_Unknown;
+    mRows[aIndex].mSubtree = nullptr;
+    ++mCount;
+
+    // Now build an iterator that points to the newly inserted element.
+    int32_t rowIndex = 0;
+    iterator result;
+    result.Push(this, aIndex);
+
+    for ( ; --aIndex >= 0; ++rowIndex) {
+        // Account for open subtrees in the absolute row index.
+        const Subtree *subtree = mRows[aIndex].mSubtree;
+        if (subtree)
+            rowIndex += subtree->mSubtreeSize;
+    }
+
+    Subtree *subtree = this;
+    do {
+        // Note that the subtree's size has expanded.
+        ++subtree->mSubtreeSize;
+
+        Subtree *parent = subtree->mParent;
+        if (! parent)
+            break;
+
+        // Account for open subtrees in the absolute row index.
+        int32_t count = parent->Count();
+        for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {
+            const Subtree *child = (*parent)[aIndex].mSubtree;
+            if (subtree == child)
+                break;
+
+            if (child)
+                rowIndex += child->mSubtreeSize;
+        }
+
+        NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");
+
+        result.Push(parent, aIndex);
+        subtree = parent;
+        ++rowIndex; // One for the parent row.
+    } while (1);
+
+    result.SetRowIndex(rowIndex);
+    return result;
+}
+
+void
+nsTreeRows::Subtree::RemoveRowAt(int32_t aIndex)
+{
+    NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");
+    if (aIndex < 0 || aIndex >= Count())
+        return;
+
+    // How big is the subtree we're going to be removing?
+    int32_t subtreeSize = mRows[aIndex].mSubtree
+        ? mRows[aIndex].mSubtree->GetSubtreeSize()
+        : 0;
+
+    ++subtreeSize;
+
+    delete mRows[aIndex].mSubtree;
+
+    for (int32_t i = aIndex + 1; i < mCount; ++i)
+        mRows[i - 1] = mRows[i];
+
+    --mCount;
+
+    for (Subtree* subtree = this; subtree != nullptr; subtree = subtree->mParent)
+        subtree->mSubtreeSize -= subtreeSize;
+}
+
+//----------------------------------------------------------------------
+//
+// nsTreeRows::iterator
+//
+
+nsTreeRows::iterator::iterator(const iterator& aIterator)
+    : mRowIndex(aIterator.mRowIndex),
+      mLink(aIterator.mLink)
+{
+}
+
+nsTreeRows::iterator&
+nsTreeRows::iterator::operator=(const iterator& aIterator)
+{
+    mRowIndex = aIterator.mRowIndex;
+    mLink = aIterator.mLink;
+    return *this;
+}
+
+void
+nsTreeRows::iterator::Append(Subtree* aParent, int32_t aChildIndex)
+{
+    Link *link = mLink.AppendElement();
+    if (link) {
+        link->mParent     = aParent;
+        link->mChildIndex = aChildIndex;
+    }
+    else
+        NS_ERROR("out of memory");
+}
+
+void
+nsTreeRows::iterator::Push(Subtree *aParent, int32_t aChildIndex)
+{
+    Link *link = mLink.InsertElementAt(0);
+    if (link) {
+        link->mParent     = aParent;
+        link->mChildIndex = aChildIndex;
+    }
+    else
+        NS_ERROR("out of memory");
+}
+
+bool
+nsTreeRows::iterator::operator==(const iterator& aIterator) const
+{
+    if (GetDepth() != aIterator.GetDepth())
+        return false;
+
+    if (GetDepth() == 0)
+        return true;
+
+    return GetTop() == aIterator.GetTop();
+}
+
+void
+nsTreeRows::iterator::Next()
+{
+    NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
+
+    // Increment the absolute row index
+    ++mRowIndex;
+
+    Link& top = GetTop();
+
+    // Is there a child subtree? If so, descend into the child
+    // subtree.
+    Subtree* subtree = top.GetRow().mSubtree;
+
+    if (subtree && subtree->Count()) {
+        Append(subtree, 0);
+        return;
+    }
+
+    // Have we exhausted the current subtree?
+    if (top.mChildIndex >= top.mParent->Count() - 1) {
+        // Yep. See if we've just iterated path the last element in
+        // the tree, period. Walk back up the stack, looking for any
+        // unfinished subtrees.
+        int32_t unfinished;
+        for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
+            const Link& link = mLink[unfinished];
+            if (link.mChildIndex < link.mParent->Count() - 1)
+                break;
+        }
+
+        // If there are no unfinished subtrees in the stack, then this
+        // iterator is exhausted. Leave it in the same state that
+        // Last() does.
+        if (unfinished < 0) {
+            top.mChildIndex++;
+            return;
+        }
+
+        // Otherwise, we ran off the end of one of the inner
+        // subtrees. Pop up to the next unfinished level in the stack.
+        mLink.SetLength(unfinished + 1);
+    }
+
+    // Advance to the next child in this subtree
+    ++(GetTop().mChildIndex);
+}
+
+void
+nsTreeRows::iterator::Prev()
+{
+    NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");
+
+    // Decrement the absolute row index
+    --mRowIndex;
+
+    // Move to the previous child in this subtree
+    --(GetTop().mChildIndex);
+
+    // Have we exhausted the current subtree?
+    if (GetTop().mChildIndex < 0) {
+        // Yep. See if we've just iterated back to the first element
+        // in the tree, period. Walk back up the stack, looking for
+        // any unfinished subtrees.
+        int32_t unfinished;
+        for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {
+            const Link& link = mLink[unfinished];
+            if (link.mChildIndex >= 0)
+                break;
+        }
+
+        // If there are no unfinished subtrees in the stack, then this
+        // iterator is exhausted. Leave it in the same state that
+        // First() does.
+        if (unfinished < 0)
+            return;
+
+        // Otherwise, we ran off the end of one of the inner
+        // subtrees. Pop up to the next unfinished level in the stack.
+        mLink.SetLength(unfinished + 1);
+        return;
+    }
+
+    // Is there a child subtree immediately prior to our current
+    // position? If so, descend into it, grovelling down to the
+    // deepest, rightmost left edge.
+    Subtree* parent = GetTop().GetParent();
+    int32_t index = GetTop().GetChildIndex();
+
+    Subtree* subtree = (*parent)[index].mSubtree;
+
+    if (subtree && subtree->Count()) {
+        do {
+            index = subtree->Count() - 1;
+            Append(subtree, index);
+
+            parent = subtree;
+            subtree = (*parent)[index].mSubtree;
+        } while (subtree && subtree->Count());
+    }
+}