The Tor Browser: content/xul/templates/src/nsTreeRows.cpp@6474c204b198 (annotated)

content/xul/templates/src/nsTreeRows.cpp@6474c204b198 (annotated)

content/xul/templates/src/nsTreeRows.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- 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());
     }
 }

The Tor Browser / annotate

content/xul/templates/src/nsTreeRows.cpp@6474c204b198 (annotated)

content/xul/templates/src/nsTreeRows.cpp