[kio] src/widgets: Reimplement sibling(), faster than the default impl which goes via parent()

[Mark Gaiser]

On Sun, May 4, 2014 at 1:41 PM, David Faure <faure at kde.org> wrote:
> Git commit 23d81eb86ae45828f8a56d2b0447de0a0f20aa86 by David Faure.
> Committed on 04/05/2014 at 11:40.
> Pushed by dfaure into branch 'master'.
>
> Reimplement sibling(), faster than the default impl which goes via parent()
>
> It wasn't virtual until Qt 5.0.
>
> We should do this for all tree models...
> CCMAIL: kde-frameworks-devel at kde.org
>
> M  +19   -1    src/widgets/kdirmodel.cpp
>
> http://commits.kde.org/kio/23d81eb86ae45828f8a56d2b0447de0a0f20aa86
>
> diff --git a/src/widgets/kdirmodel.cpp b/src/widgets/kdirmodel.cpp
> index d88a169..70d5ee4 100644
> --- a/src/widgets/kdirmodel.cpp
> +++ b/src/widgets/kdirmodel.cpp
> @@ -900,7 +900,6 @@ int KDirModel::rowCount(const QModelIndex &parent) const
>      return count;
>  }
>
> -// sibling() calls parent() and isn't virtual! So parent() should be fast...
>  QModelIndex KDirModel::parent(const QModelIndex &index) const
>  {
>      if (!index.isValid()) {
> @@ -913,6 +912,25 @@ QModelIndex KDirModel::parent(const QModelIndex &index) const
>      return d->indexForNode(parentNode); // O(n)
>  }
>
> +// Reimplemented to avoid the default implementation which calls parent
> +// (O(n) for finding the parent's row number for nothing). This implementation is O(1).
> +QModelIndex KDirModel::sibling(int row, int column, const QModelIndex &index) const
> +{
> +    if (!index.isValid()) {
> +        return QModelIndex();
> +    }
> +    KDirModelNode *oldChildNode = static_cast<KDirModelNode *>(index.internalPointer());
> +    Q_ASSERT(oldChildNode);
> +    KDirModelNode *parentNode = oldChildNode->parent();
> +    Q_ASSERT(parentNode);
> +    Q_ASSERT(d->isDir(parentNode));
> +    KDirModelNode *childNode = static_cast<KDirModelDirNode *>(parentNode)->m_childNodes.value(row); // O(1)
> +    if (childNode) {
> +        return createIndex(row, column, childNode);
> +    }
> +    return QModelIndex();
> +}

Impressive! The docs [1] don't mention much other then: "This method
can optionally be overridden for implementation-specific
optimization."..
How did you figure out that re-implementing this function is more
efficient then the parent function?

Also, just curious. Do you have any before/after numbers?

[1] http://qt-project.org/doc/qt-5/qabstractitemmodel.html#sibling