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

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

     1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

     2 /* This Source Code Form is subject to the terms of the Mozilla Public

     3  * License, v. 2.0. If a copy of the MPL was not distributed with this

     4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     6 #include "nsString.h"

     7 #include "nsTreeRows.h"

     8 #include <algorithm>

    10 nsTreeRows::Subtree*

    11 nsTreeRows::EnsureSubtreeFor(Subtree* aParent,

    12                              int32_t aChildIndex)

    13 {

    14     Subtree* subtree = GetSubtreeFor(aParent, aChildIndex);

    16     if (! subtree) {

    17         subtree = aParent->mRows[aChildIndex].mSubtree = new Subtree(aParent);

    18         InvalidateCachedRow();

    19     }

    21     return subtree;

    22 }

    24 nsTreeRows::Subtree*

    25 nsTreeRows::GetSubtreeFor(const Subtree* aParent,

    26                               int32_t aChildIndex,

    27                               int32_t* aSubtreeSize)

    28 {

    29     NS_PRECONDITION(aParent, "no parent");

    30     NS_PRECONDITION(aChildIndex >= 0, "bad child index");

    32     Subtree* result = nullptr;

    34     if (aChildIndex < aParent->mCount)

    35         result = aParent->mRows[aChildIndex].mSubtree;

    37     if (aSubtreeSize)

    38         *aSubtreeSize = result ? result->mSubtreeSize : 0;

    40     return result;

    41 }

    43 void

    44 nsTreeRows::RemoveSubtreeFor(Subtree* aParent, int32_t aChildIndex)

    45 {

    46     NS_PRECONDITION(aParent, "no parent");

    47     NS_PRECONDITION(aChildIndex >= 0 && aChildIndex < aParent->mCount, "bad child index");

    49     Row& row = aParent->mRows[aChildIndex];

    51     if (row.mSubtree) {

    52         int32_t subtreeSize = row.mSubtree->GetSubtreeSize();

    54         delete row.mSubtree;

    55         row.mSubtree = nullptr;

    57         for (Subtree* subtree = aParent; subtree != nullptr; subtree = subtree->mParent)

    58             subtree->mSubtreeSize -= subtreeSize;

    59     }

    61     InvalidateCachedRow();

    62 }

    64 nsTreeRows::iterator

    65 nsTreeRows::First()

    66 {

    67     iterator result;

    68     result.Append(&mRoot, 0);

    69     result.SetRowIndex(0);

    70     return result;

    71 }

    73 nsTreeRows::iterator

    74 nsTreeRows::Last()

    75 {

    76     iterator result;

    78     // Build up a path along the rightmost edge of the tree

    79     Subtree* current = &mRoot;

    80     int32_t count = current->Count();

    81     do  {

    82         int32_t last = count - 1;

    83         result.Append(current, last);

    84         current = count ? GetSubtreeFor(current, last) : nullptr;

    85     } while (current && ((count = current->Count()) != 0));

    87     // Now, at the bottom rightmost leaf, advance us one off the end.

    88     result.GetTop().mChildIndex++;

    90     // Our row index will be the size of the root subree, plus one.

    91     result.SetRowIndex(mRoot.GetSubtreeSize() + 1);

    93     return result;

    94 }

    96 nsTreeRows::iterator

    97 nsTreeRows::operator[](int32_t aRow)

    98 {

    99     // See if we're just lucky, and end up with something

   100     // nearby. (This tends to happen a lot due to the way that we get

   101     // asked for rows n' stuff.)

   102     int32_t last = mLastRow.GetRowIndex();

   103     if (last != -1) {

   104         if (aRow == last)

   105             return mLastRow;

   106         else if (last + 1 == aRow)

   107             return ++mLastRow;

   108         else if (last - 1 == aRow)

   109             return --mLastRow;

   110     }

   112     // Nope. Construct a path to the specified index. This is a little

   113     // bit better than O(n), because we can skip over subtrees. (So it

   114     // ends up being approximately linear in the subtree size, instead

   115     // of the entire view size. But, most of the time, big views are

   116     // flat. Oh well.)

   117     iterator result;

   118     Subtree* current = &mRoot;

   120     int32_t index = 0;

   121     result.SetRowIndex(aRow);

   123     do {

   124         int32_t subtreeSize;

   125         Subtree* subtree = GetSubtreeFor(current, index, &subtreeSize);

   127         if (subtreeSize >= aRow) {

   128             result.Append(current, index);

   129             current = subtree;

   130             index = 0;

   131             --aRow;

   132         }

   133         else {

   134             ++index;

   135             aRow -= subtreeSize + 1;

   136         }

   137     } while (aRow >= 0);

   139     mLastRow = result;

   140     return result;

   141 }

   143 nsTreeRows::iterator

   144 nsTreeRows::FindByResource(nsIRDFResource* aResource)

   145 {

   146     // XXX Mmm, scan through the rows one-by-one...

   147     iterator last = Last();

   148     iterator iter;

   150     nsresult rv;

   151     nsAutoString resourceid;

   152     bool stringmode = false;

   154     for (iter = First(); iter != last; ++iter) {

   155         if (!stringmode) {

   156             nsCOMPtr<nsIRDFResource> findres;

   157             rv = iter->mMatch->mResult->GetResource(getter_AddRefs(findres));

   158             if (NS_FAILED(rv)) return last;

   160             if (findres == aResource)

   161                 break;

   163             if (! findres) {

   164                 const char *uri;

   165                 aResource->GetValueConst(&uri);

   166                 CopyUTF8toUTF16(uri, resourceid);

   168                 // set stringmode and fall through

   169                 stringmode = true;

   170             }

   171         }

   173         // additional check because previous block could change stringmode

   174         if (stringmode) {

   175             nsAutoString findid;

   176             rv = iter->mMatch->mResult->GetId(findid);

   177             if (NS_FAILED(rv)) return last;

   179             if (resourceid.Equals(findid))

   180                 break;

   181         }

   182     }

   184     return iter;

   185 }

   187 nsTreeRows::iterator

   188 nsTreeRows::Find(nsIXULTemplateResult *aResult)

   189 {

   190     // XXX Mmm, scan through the rows one-by-one...

   191     iterator last = Last();

   192     iterator iter;

   194     for (iter = First(); iter != last; ++iter) {

   195         if (aResult == iter->mMatch->mResult)

   196           break;

   197     }

   199     return iter;

   200 }

   202 void

   203 nsTreeRows::Clear()

   204 {

   205     mRoot.Clear();

   206     InvalidateCachedRow();

   207 }

   209 //----------------------------------------------------------------------

   210 //

   211 // nsTreeRows::Subtree

   212 //

   214 nsTreeRows::Subtree::~Subtree()

   215 {

   216     Clear();

   217 }

   219 void

   220 nsTreeRows::Subtree::Clear()

   221 {

   222     for (int32_t i = mCount - 1; i >= 0; --i)

   223         delete mRows[i].mSubtree;

   225     delete[] mRows;

   227     mRows = nullptr;

   228     mCount = mCapacity = mSubtreeSize = 0;

   229 }

   231 nsTreeRows::iterator

   232 nsTreeRows::Subtree::InsertRowAt(nsTemplateMatch* aMatch, int32_t aIndex)

   233 {

   234     if (mCount >= mCapacity || aIndex >= mCapacity) {

   235         int32_t newCapacity = std::max(mCapacity * 2, aIndex + 1);

   236         Row* newRows = new Row[newCapacity];

   237         if (! newRows)

   238             return iterator();

   240         for (int32_t i = mCount - 1; i >= 0; --i)

   241             newRows[i] = mRows[i];

   243         delete[] mRows;

   245         mRows = newRows;

   246         mCapacity = newCapacity;

   247     }

   249     for (int32_t i = mCount - 1; i >= aIndex; --i)

   250         mRows[i + 1] = mRows[i];

   252     mRows[aIndex].mMatch = aMatch;

   253     mRows[aIndex].mContainerType = eContainerType_Unknown;

   254     mRows[aIndex].mContainerState = eContainerState_Unknown;

   255     mRows[aIndex].mContainerFill = eContainerFill_Unknown;

   256     mRows[aIndex].mSubtree = nullptr;

   257     ++mCount;

   259     // Now build an iterator that points to the newly inserted element.

   260     int32_t rowIndex = 0;

   261     iterator result;

   262     result.Push(this, aIndex);

   264     for ( ; --aIndex >= 0; ++rowIndex) {

   265         // Account for open subtrees in the absolute row index.

   266         const Subtree *subtree = mRows[aIndex].mSubtree;

   267         if (subtree)

   268             rowIndex += subtree->mSubtreeSize;

   269     }

   271     Subtree *subtree = this;

   272     do {

   273         // Note that the subtree's size has expanded.

   274         ++subtree->mSubtreeSize;

   276         Subtree *parent = subtree->mParent;

   277         if (! parent)

   278             break;

   280         // Account for open subtrees in the absolute row index.

   281         int32_t count = parent->Count();

   282         for (aIndex = 0; aIndex < count; ++aIndex, ++rowIndex) {

   283             const Subtree *child = (*parent)[aIndex].mSubtree;

   284             if (subtree == child)

   285                 break;

   287             if (child)

   288                 rowIndex += child->mSubtreeSize;

   289         }

   291         NS_ASSERTION(aIndex < count, "couldn't find subtree in parent");

   293         result.Push(parent, aIndex);

   294         subtree = parent;

   295         ++rowIndex; // One for the parent row.

   296     } while (1);

   298     result.SetRowIndex(rowIndex);

   299     return result;

   300 }

   302 void

   303 nsTreeRows::Subtree::RemoveRowAt(int32_t aIndex)

   304 {

   305     NS_PRECONDITION(aIndex >= 0 && aIndex < Count(), "bad index");

   306     if (aIndex < 0 || aIndex >= Count())

   307         return;

   309     // How big is the subtree we're going to be removing?

   310     int32_t subtreeSize = mRows[aIndex].mSubtree

   311         ? mRows[aIndex].mSubtree->GetSubtreeSize()

   312         : 0;

   314     ++subtreeSize;

   316     delete mRows[aIndex].mSubtree;

   318     for (int32_t i = aIndex + 1; i < mCount; ++i)

   319         mRows[i - 1] = mRows[i];

   321     --mCount;

   323     for (Subtree* subtree = this; subtree != nullptr; subtree = subtree->mParent)

   324         subtree->mSubtreeSize -= subtreeSize;

   325 }

   327 //----------------------------------------------------------------------

   328 //

   329 // nsTreeRows::iterator

   330 //

   332 nsTreeRows::iterator::iterator(const iterator& aIterator)

   333     : mRowIndex(aIterator.mRowIndex),

   334       mLink(aIterator.mLink)

   335 {

   336 }

   338 nsTreeRows::iterator&

   339 nsTreeRows::iterator::operator=(const iterator& aIterator)

   340 {

   341     mRowIndex = aIterator.mRowIndex;

   342     mLink = aIterator.mLink;

   343     return *this;

   344 }

   346 void

   347 nsTreeRows::iterator::Append(Subtree* aParent, int32_t aChildIndex)

   348 {

   349     Link *link = mLink.AppendElement();

   350     if (link) {

   351         link->mParent     = aParent;

   352         link->mChildIndex = aChildIndex;

   353     }

   354     else

   355         NS_ERROR("out of memory");

   356 }

   358 void

   359 nsTreeRows::iterator::Push(Subtree *aParent, int32_t aChildIndex)

   360 {

   361     Link *link = mLink.InsertElementAt(0);

   362     if (link) {

   363         link->mParent     = aParent;

   364         link->mChildIndex = aChildIndex;

   365     }

   366     else

   367         NS_ERROR("out of memory");

   368 }

   370 bool

   371 nsTreeRows::iterator::operator==(const iterator& aIterator) const

   372 {

   373     if (GetDepth() != aIterator.GetDepth())

   374         return false;

   376     if (GetDepth() == 0)

   377         return true;

   379     return GetTop() == aIterator.GetTop();

   380 }

   382 void

   383 nsTreeRows::iterator::Next()

   384 {

   385     NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");

   387     // Increment the absolute row index

   388     ++mRowIndex;

   390     Link& top = GetTop();

   392     // Is there a child subtree? If so, descend into the child

   393     // subtree.

   394     Subtree* subtree = top.GetRow().mSubtree;

   396     if (subtree && subtree->Count()) {

   397         Append(subtree, 0);

   398         return;

   399     }

   401     // Have we exhausted the current subtree?

   402     if (top.mChildIndex >= top.mParent->Count() - 1) {

   403         // Yep. See if we've just iterated path the last element in

   404         // the tree, period. Walk back up the stack, looking for any

   405         // unfinished subtrees.

   406         int32_t unfinished;

   407         for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {

   408             const Link& link = mLink[unfinished];

   409             if (link.mChildIndex < link.mParent->Count() - 1)

   410                 break;

   411         }

   413         // If there are no unfinished subtrees in the stack, then this

   414         // iterator is exhausted. Leave it in the same state that

   415         // Last() does.

   416         if (unfinished < 0) {

   417             top.mChildIndex++;

   418             return;

   419         }

   421         // Otherwise, we ran off the end of one of the inner

   422         // subtrees. Pop up to the next unfinished level in the stack.

   423         mLink.SetLength(unfinished + 1);

   424     }

   426     // Advance to the next child in this subtree

   427     ++(GetTop().mChildIndex);

   428 }

   430 void

   431 nsTreeRows::iterator::Prev()

   432 {

   433     NS_PRECONDITION(GetDepth() > 0, "cannot increment an uninitialized iterator");

   435     // Decrement the absolute row index

   436     --mRowIndex;

   438     // Move to the previous child in this subtree

   439     --(GetTop().mChildIndex);

   441     // Have we exhausted the current subtree?

   442     if (GetTop().mChildIndex < 0) {

   443         // Yep. See if we've just iterated back to the first element

   444         // in the tree, period. Walk back up the stack, looking for

   445         // any unfinished subtrees.

   446         int32_t unfinished;

   447         for (unfinished = GetDepth() - 2; unfinished >= 0; --unfinished) {

   448             const Link& link = mLink[unfinished];

   449             if (link.mChildIndex >= 0)

   450                 break;

   451         }

   453         // If there are no unfinished subtrees in the stack, then this

   454         // iterator is exhausted. Leave it in the same state that

   455         // First() does.

   456         if (unfinished < 0)

   457             return;

   459         // Otherwise, we ran off the end of one of the inner

   460         // subtrees. Pop up to the next unfinished level in the stack.

   461         mLink.SetLength(unfinished + 1);

   462         return;

   463     }

   465     // Is there a child subtree immediately prior to our current

   466     // position? If so, descend into it, grovelling down to the

   467     // deepest, rightmost left edge.

   468     Subtree* parent = GetTop().GetParent();

   469     int32_t index = GetTop().GetChildIndex();

   471     Subtree* subtree = (*parent)[index].mSubtree;

   473     if (subtree && subtree->Count()) {

   474         do {

   475             index = subtree->Count() - 1;

   476             Append(subtree, index);

   478             parent = subtree;

   479             subtree = (*parent)[index].mSubtree;

   480         } while (subtree && subtree->Count());

   481     }

   482 }

The Tor Browser / file revision

content/xul/templates/src/nsTreeRows.cpp@6474c204b198

content/xul/templates/src/nsTreeRows.cpp