[Qt-interest] QAbstractItemModel, tree structure and dynamic datas

[Tanguy Krotoff]

On Sat, May 2, 2009 at 7:17 PM, Tanguy Krotoff <tkrotoff at gmail.com> wrote:
> Here what I would like to implement inside my
> QAbstractItemModel::fetchMore() method:
>
> fetchMore(const QModelIndex & parent) {
>        computeInAnotherThread(parent);
>        //emits signal computationDone()
> }
>
> //Catches signal compuationDone()
> slotComputationDoneFromOtherThread(const QStringList & childs) {
>        beginInsertRows(parent, first, last);
>        foreach (QString child, childs) {
>                //Change my internal tree data structure
>        }
>        endInsertRows();
> }
>
> Is it the right way to do it? Am I wrong about the use of
> canFetchMore() and fetchMore()? Is there some examples/projects around
> using QAbstractItemModel this way?

I manage to make it work, I was having some hard times because of
other unrelated errors inside my code.

Why I needed to do that? (everything done using Qt 4.5.1/VC++2005
under Windows XP)
I found QFileSystemModel (and QDirModel) to be slow with big lists of
files/directories.
QFileSystemModel takes ~9 secs (graphically I mean) to list 400
directories and it blocks the GUI.

The best way to test this is to use an external USB harddrive and
unplug/plug it inside another USB port before to run an example using
QFileSystemModel and QTreeView. By unplugging/plugging you are sure
that nothing stay in cache (you can also reboot your PC) otherwise
QFileSystemModel do the listing instantly.

Using my implementation it takes only 2 secs to the list 400
directories. The 9 seconds when using QFileSystemModel wouldn't be a
problem if it was not at the application start.

My first attempt was to profile QFileSystemModel and remove some code
like the computation of files informations (size, last date of
modification...). Using AQTime I didn't get really successful and gave
up.
One thing that I have found is that QFileInfo::isDir() is pretty slow
and I've replaced it by own code.

My quick and dirty implementation does not have all the features from
QFileSystemModel (and I don't need them), it's buggy and I'm still
working on it.

Here the most interesting parts of the code:
The model that inherits from QAbstractItemModel:
http://code.google.com/p/phonon-vlc-mplayer/source/browse/trunk/quarkplayer-plugins/filebrowser/FileSearchModel.cpp
An item/node inside FileSearchModel:
http://code.google.com/p/phonon-vlc-mplayer/source/browse/trunk/quarkplayer-plugins/filebrowser/FileSearchItem.cpp
Search files and directories as quickly as possible:
http://code.google.com/p/phonon-vlc-mplayer/source/browse/trunk/libs/tkutil/FindFiles.cpp
Re-implementation of QFileInfo::isDir():
http://code.google.com/p/phonon-vlc-mplayer/source/browse/trunk/libs/tkutil/TkFile.cpp


I copy-paste in this mail simplified versions (won't compile) of the
main classes for historical reason:



#include "FileSearchModel.h"

#include "FileSearchItem.h"

#include <tkutil/FindFiles.h>

#include <QtGui/QtGui>

#include <QtCore/QDebug>
#include <QtCore/QCoreApplication>

//For INT_MAX
#include <climits>

const int FileSearchModel::COLUMN_FILENAME = 0;
const int FileSearchModel::COLUMN_FIRST = COLUMN_FILENAME;
const int FileSearchModel::COLUMN_LAST = COLUMN_FILENAME;

static const int COLUMN_COUNT = 1;

QHash<QString, QIcon> FileSearchModel::_iconsCache;

FileSearchModel::FileSearchModel(QObject * parent)
	: QAbstractItemModel(parent) {

	_rootItem = NULL;
	_currentParentItem = NULL;

	reset();

	_findFiles = NULL;
}

FileSearchModel::~FileSearchModel() {
	reset();
}

void FileSearchModel::setSearchExtensions(const QStringList & extensions) {
	_searchExtensions = extensions;
}

int FileSearchModel::columnCount(const QModelIndex & parent) const {
	Q_UNUSED(parent);
	return COLUMN_COUNT;
}

QVariant FileSearchModel::headerData(int section, Qt::Orientation
orientation, int role) const {
	QVariant tmp;

	if (orientation == Qt::Horizontal && role == Qt::DisplayRole) {
		switch (section) {
		case COLUMN_FILENAME:
			tmp = tr("Name");
			break;
		}
	}

	return tmp;
}

QVariant FileSearchModel::data(const QModelIndex & index, int role) const {
	QVariant tmp;

	if (!index.isValid() || index.model() != this) {
		return tmp;
	}

	int row = index.row();
	int column = index.column();

	FileSearchItem * item = static_cast<FileSearchItem *>(index.internalPointer());
	if (!item) {
		qWarning() << __FUNCTION__ << "Error: item is NULL";
		return tmp;
	}
	const MediaInfo & mediaInfo(item->mediaInfo());
	QString filename(mediaInfo.fileName());

	switch (role) {
	case Qt::DisplayRole: {
		switch (column) {
		case COLUMN_FILENAME:
			tmp = QFileInfo(filename).fileName();
			break;
		}
		break;
	}

	case Qt::DecorationRole: {
		switch (column) {
		case COLUMN_FILENAME:
			//This is too slow:
			//re-creates an icon for each file
			//We want a cache system -> way faster!
			//tmp = _iconProvider.icon(QFileInfo(filename));

			QFileInfo fileInfo(filename);
			QString ext(fileInfo.suffix());
			if (!_iconsCache.contains(ext)) {
				_iconsCache[ext] = _iconProvider.icon(fileInfo);
			}
			tmp = _iconsCache.value(ext);
			break;
		}
		break;
	}

	}

	return tmp;
}

QModelIndex FileSearchModel::index(int row, int column, const
QModelIndex & parent) const {
	if (!hasIndex(row, column, parent)) {
		return QModelIndex();
	}

	FileSearchItem * parentItem = NULL;
	if (!parent.isValid()) {
		parentItem = _rootItem;
	} else {
		parentItem = static_cast<FileSearchItem *>(parent.internalPointer());
	}

	FileSearchItem * childItem = parentItem->child(row);
	if (childItem) {
		return createIndex(row, column, childItem);
	} else {
		return QModelIndex();
	}
}

QModelIndex FileSearchModel::parent(const QModelIndex & index) const {
	if (!index.isValid()) {
		return QModelIndex();
	}

	FileSearchItem * childItem = static_cast<FileSearchItem
*>(index.internalPointer());
	FileSearchItem * parentItem = childItem->parent();

	if (parentItem == _rootItem) {
		return QModelIndex();
	}

	return createIndex(parentItem->row(), COLUMN_FILENAME, parentItem);
}

int FileSearchModel::rowCount(const QModelIndex & parent) const {
	FileSearchItem * parentItem = NULL;
	if (!parent.isValid()) {
		parentItem = _rootItem;
	} else {
		parentItem = static_cast<FileSearchItem *>(parent.internalPointer());
	}

	int childCount = 0;
	if (parentItem) {
		childCount = parentItem->childCount();
	}
	return childCount;
}

Qt::ItemFlags FileSearchModel::flags(const QModelIndex & index) const {
	if (!index.isValid()) {
		return 0;
	}

	return Qt::ItemIsEnabled | Qt::ItemIsSelectable | Qt::ItemIsDragEnabled;
}

bool FileSearchModel::hasChildren(const QModelIndex & parent) const {
	if (!parent.isValid()) {
		return false;
	}

	bool tmp = false;
	FileSearchItem * item = static_cast<FileSearchItem
*>(parent.internalPointer());
	if (!item) {
		qWarning() << __FUNCTION__ << "Error: item is NULL";
	} else {
		//Optimization: QFileInfo::isDir() is too slow, replaced by TkFile::isDir()
		tmp = item->isDir();
	}

	return tmp;
}

bool FileSearchModel::canFetchMore(const QModelIndex & parent) const {
	FileSearchItem * item = static_cast<FileSearchItem
*>(parent.internalPointer());
	if (item && hasChildren(parent)) {
		return !(item->populatedChildren());
	} else {
		return false;
	}
}

void FileSearchModel::fetchMore(const QModelIndex & parent) {
	_currentParentItem = static_cast<FileSearchItem *>(parent.internalPointer());

	//_currentParentQModelIndex is a hack because of beginInsertRows()
	_currentParentQModelIndex = parent;

	QString path = fileInfo(parent).absoluteFilePath();
	search(path, QRegExp(QString(), Qt::CaseInsensitive,
QRegExp::RegExp2), INT_MAX, false);
}

QFileInfo FileSearchModel::fileInfo(const QModelIndex & index) const {
	QFileInfo tmp;

	FileSearchItem * item = static_cast<FileSearchItem *>(index.internalPointer());
	if (!item) {
		qWarning() << __FUNCTION__ << "Error: item is NULL";
	} else {
		tmp = QFileInfo(item->fileName());
	}
	return tmp;
}

void FileSearchModel::reset() {
	if (_rootItem) {
		//Deteles _rootItem + all its childs
		//so everything is deleted
		delete _rootItem;
		_rootItem = NULL;
	}

	//No need to delete _currentParentItem since "delete _rootItem" will do it
	_currentParentItem = NULL;
	_currentParentQModelIndex = QModelIndex();

	_mediaInfoFetcherIndex = QModelIndex();

	//Resets the model
	QAbstractItemModel::reset();
}

void FileSearchModel::search(const QString & path, const QRegExp &
pattern, int filesFoundLimit, bool recursiveSearch) {
	qDebug() << __FUNCTION__ << path;

	if (!_currentParentItem) {
		if (!_rootItem) {
			//Lazy initialization of _rootItem
			_rootItem = new FileSearchItem(path, NULL);
		}
		_currentParentItem = _rootItem;
	}

	//Item is going to be populated, let's say it is already
	//because population of an item is threaded
	_currentParentItem->setPopulatedChildren(true);

	if (_findFiles) {
		//Uninitialize/remove/disconnect... previous _findFiles
		disconnect(_findFiles, SIGNAL(filesFound(const QStringList &)),
			this, SLOT(filesFound(const QStringList &)));
		disconnect(_findFiles, SIGNAL(finished(int)),
			this, SIGNAL(searchFinished(int)));
	}

	//Stops the previous search
	//Do it first (i.e before setPattern(), setExtensions()...) otherwise
it can crash
	//inside FindFiles since there is no mutex
	stop();

	//Starts a new search
	delete _findFiles;
	_findFiles = new FindFiles(this);

	//Starts a new file search
	_findFiles->setSearchPath(path);

	//_findFiles->setFilesFoundLimit(INT_MAX);
	//This was true with Qt 4.4.3
	//Way faster with INT_MAX because beginInsertRows() is slow
	//It's better to call only once thus INT_MAX instead of 1 for example
	//Now with Qt 4.5.1, speed is really good :-)
	//_findFiles->setFilesFoundLimit(1);
	_findFiles->setFilesFoundLimit(filesFoundLimit);

	_findFiles->setPattern(pattern);
	_findFiles->setExtensions(_searchExtensions);
	_findFiles->setFindDirs(true);
	_findFiles->setRecursiveSearch(recursiveSearch);
	connect(_findFiles, SIGNAL(filesFound(const QStringList &)),
		SLOT(filesFound(const QStringList &)), Qt::QueuedConnection);
	connect(_findFiles, SIGNAL(finished(int)),
		SIGNAL(searchFinished(int)), Qt::QueuedConnection);
	_findFiles->start();
}

void FileSearchModel::stop() {
	if (_findFiles) {
		_findFiles->stop();
	}
}

void FileSearchModel::filesFound(const QStringList & files) {
	if (sender() != _findFiles) {
		//filesFound() signal from a previous _findFiles,
		//let's discards it
		return;
	}

	//Append the files
	int first = _currentParentItem->childCount();
	int last = first + files.size() - 1;

	beginInsertRows(_currentParentQModelIndex, first, last);
	foreach (QString filename, files) {
		_currentParentItem->appendChild(new FileSearchItem(filename,
_currentParentItem));
	}
	endInsertRows();
}





#include "FileSearchItem.h"

#include <tkutil/TkFile.h>

#include <QtCore/QStringList>
#include <QtCore/QDebug>

FileSearchItem::FileSearchItem(const QString & filename,
FileSearchItem * parent) {
	_mediaInfo = MediaInfo(filename);
	_parentItem = parent;
	_populatedChildren = false;
	_isDir = -1;
	_firstFileItemAdded = -1;
}

FileSearchItem::~FileSearchItem() {
	qDeleteAll(_childItems);
}

void FileSearchItem::setPopulatedChildren(bool populatedChildren) {
	_populatedChildren = populatedChildren;
}

bool FileSearchItem::populatedChildren() const {
	return _populatedChildren;
}

void FileSearchItem::appendChild(FileSearchItem * newItem) {
	_childItems.append(newItem);
}

FileSearchItem * FileSearchItem::child(int row) {
	return _childItems.value(row);
}

int FileSearchItem::childCount() const {
	return _childItems.count();
}

FileSearchItem * FileSearchItem::parent() {
	return _parentItem;
}

int FileSearchItem::row() const {
	if (_parentItem) {
		return _parentItem->_childItems.indexOf(const_cast<FileSearchItem *>(this));
	}

	return 0;
}

QString FileSearchItem::fileName() const {
	return _mediaInfo.fileName();
}

const MediaInfo & FileSearchItem::mediaInfo() const {
	return _mediaInfo;
}

void FileSearchItem::setMediaInfo(const MediaInfo & mediaInfo) {
	_mediaInfo = mediaInfo;
}

bool FileSearchItem::isDir() {
	if (_isDir == -1) {
		//Avoid some computations
		//since _isDir is an attribute of this class
		_isDir = TkFile::isDir(_mediaInfo.fileName());
	}
	return _isDir;
}




#include "FindFiles.h"

#include "TkFile.h"

#include <QtCore/QDir>
#include <QtCore/QFileInfo>
#include <QtCore/QTime>
#include <QtCore/QDebug>

#ifdef Q_OS_WIN
	#include <windows.h>
#else
	#include <dirent.h>
#endif	//Q_OS_WIN

static const int DEFAULT_FILES_FOUND_LIMIT = 500;

FindFiles::FindFiles(QObject * parent)
	: QThread(parent) {

	_findDirs = false;
	_recursiveSearch = true;
	_filesFoundLimit = DEFAULT_FILES_FOUND_LIMIT;
	_stop = false;
}

FindFiles::~FindFiles() {
	stop();
}

void FindFiles::setSearchPath(const QString & path) {
	_path = path;
}

void FindFiles::setFilesFoundLimit(int filesFoundLimit) {
	_filesFoundLimit = filesFoundLimit;
}

void FindFiles::setPattern(const QRegExp & pattern) {
	_pattern = pattern;
}

void FindFiles::setExtensions(const QStringList & extensions) {
	_extensions = extensions;
}

void FindFiles::setFindDirs(bool findDirs) {
	_findDirs = findDirs;
}

void FindFiles::setRecursiveSearch(bool recursiveSearch) {
	_recursiveSearch = recursiveSearch;
}

void FindFiles::stop() {
	_stop = true;
	wait();
}

void FindFiles::run() {
	_stop = false;

	if (_path.isEmpty()) {
		qCritical() << __FUNCTION__ << "Error: empty path";
		return;
	}

	QTime timeElapsed;
	timeElapsed.start();

#ifdef Q_OS_WIN
	findAllFilesWin32(_path);
#else
	findAllFilesUNIX(_path);
#endif	//Q_OS_WIN
	//findAllFilesQt(_path);

	if (!_stop) {
		//Emits the signal for the remaining files found
		if (!_files.isEmpty()) {
			emit filesFound(_files);
			_files.clear();
		}

		//Emits the last signal
		emit finished(timeElapsed.elapsed());
	}
}

void FindFiles::findAllFilesQt(const QString & path) {
	if (_stop) {
		return;
	}

	QDir dir(path);

	//QDir::setNameFilters() is too slow :/
	dir.setFilter(QDir::AllDirs | QDir::Files | QDir::NoSymLinks |
QDir::NoDotAndDotDot);
	foreach (QString name, dir.entryList()) {
		if (_stop) {
			break;
		}

		QString filename(path + QDir::separator() + name);

		if (TkFile::isDir(filename)) {
			//Filter directory matching the given pattern
			if (_findDirs && patternMatches(name)) {
				_files << filename;
			}

			if (_recursiveSearch) {
				//Recurse
				findAllFilesQt(filename);
			}
		}

		else {
			//Filter file matching the given pattern and extensions
			if (extensionMatches(name) && patternMatches(name)) {
				_files << filename;
			}

			if (_files.size() > _filesFoundLimit) {
				//Emits the signal every _filesFoundLimit files found
				if (!_stop) {
					emit filesFound(_files);
				}
				_files.clear();
			}
		}
	}
}

void FindFiles::findAllFilesWin32(const QString & path) {
#ifdef Q_OS_WIN
	//See http://msdn.microsoft.com/en-us/library/ms811896.aspx
	//See http://msdn.microsoft.com/en-us/library/aa364418.aspx
	//See http://msdn.microsoft.com/en-us/library/aa365247.aspx

	if (_stop) {
		return;
	}

	QString longPath("\\\\?\\" + path + "\\*");

	//Converts to native separator, otherwise FindFirstFileW()
	//won't work if '/' separators are found
	longPath = QDir::toNativeSeparators(longPath);

	WIN32_FIND_DATAW fileData;
	//LPCWSTR = wchar_t *
	//LPCSTR = char *
	//TCHAR = char or wchar_t
	//WCHAR = wchar_t

	//Get the first file
	HANDLE hList = FindFirstFileW((TCHAR *) longPath.utf16(), &fileData);
	if (hList == INVALID_HANDLE_VALUE) {
		qCritical() << __FUNCTION__ << "Error: no files found, path:" <<
path << " error code:" << GetLastError();
	}

	else {
		//Traverse through the directory structure
		bool finished = false;
		while (!finished) {
			if (_stop) {
				break;
			}

			QString name(QString::fromUtf16((unsigned short *) fileData.cFileName));
			QString filename(path + QDir::separator() + name);

			//Check if the object is a directory or not
			if (fileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {

				//Avoid '.', '..' and other hidden files
				if (!name.startsWith('.')) {
					//Filter directory matching the given pattern
					if (_findDirs && patternMatches(name)) {
						_files << filename;
					}

					if (_recursiveSearch) {
						//Recurse
						findAllFilesWin32(filename);
					}
				}
			}

			else {
				//Filter file matching the given pattern and extensions
				if (extensionMatches(name) && patternMatches(name)) {
					_files << filename;
				}

				if (_files.size() > _filesFoundLimit) {
					//Emits the signal every _filesFoundLimit files found
					if (!_stop) {
						emit filesFound(_files);
					}
					_files.clear();
				}
			}

			if (!FindNextFileW(hList, &fileData)) {
				if (GetLastError() == ERROR_NO_MORE_FILES) {
					finished = true;
				}
			}
		}
	}

	FindClose(hList);
#else
	Q_UNUSED(path);
#endif	//Q_OS_WIN
}

void FindFiles::findAllFilesUNIX(const QString & path) {
#ifndef Q_OS_WIN
	//http://www.commentcamarche.net/forum/affich-1699952-langage-c-recuperer-un-dir

	if (_stop) {
		return;
	}

	//Warning: opendir() is limited to PATH_MAX
	//See http://insanecoding.blogspot.com/2007/11/pathmax-simply-isnt.html
	DIR * dir = opendir(path.toUtf8().constData());
	if (!dir) {
		qCritical() << __FUNCTION__ << "Error: opendir() failed";
		perror(path.toUtf8().constData());
	} else {
		struct dirent * entry = NULL;
		while ((entry = readdir(dir))) {
			if (_stop) {
				break;
			}
			QString name(entry->d_name);

			//Avoid '.', '..' and other hidden files
			if (!name.startsWith('.')) {

				QString filename(path + QDir::separator() + name);

				if (TkFile::isDir(filename)) {
					//Filter directory matching the given pattern
					if (_findDirs && patternMatches(name)) {
						_files << filename;
					}

					if (_recursiveSearch) {
						//Recurse
						findAllFilesUNIX(filename);
					}
				}

				else {
					//Filter file matching the given pattern and extensions
					if (extensionMatches(name) && patternMatches(name)) {
						_files << filename;
					}

					if (_files.size() > _filesFoundLimit) {
						//Emits the signal every _filesFoundLimit files found
						if (!_stop) {
							emit filesFound(_files);
						}
						_files.clear();
					}
				}
			}
		}

		int ret = closedir(dir);
		if (ret != 0) {
			qCritical() << __FUNCTION__ << "Error: closedir() failed";
			perror(path.toUtf8().constData());
		}
	}
#else
	Q_UNUSED(path);
#endif	//Q_OS_WIN
}

bool FindFiles::patternMatches(const QString & filename) const {
	bool tmp = false;

	if (_pattern.isEmpty()) {
		tmp = true;
	} else if (filename.contains(_pattern)) {
		tmp = true;
	}

	return tmp;
}

bool FindFiles::extensionMatches(const QString & filename) const {
	bool tmp = false;

	if (_extensions.isEmpty()) {
		tmp = true;
	} else if (_extensions.contains(QFileInfo(filename).suffix(),
Qt::CaseInsensitive)) {
		tmp = true;
	}

	return tmp;
}




#include "TkFile.h"

#include <QtCore/QDebug>

#include <sys/types.h>
#include <sys/stat.h>

#ifndef S_ISDIR
	#ifdef S_IFDIR
		//Using MSVC
		#define S_ISDIR(mode) (((mode) & S_IFMT) == S_IFDIR)
	#else
		#define S_ISDIR(mode) 0
	#endif	//S_IFDIR
#endif	//!S_ISDIR

#ifndef lstat
	//Using MSVC
	#define lstat _wstat
#endif	//!lstat

#ifndef _stat
	//Using MSVC
	#define _stat stat
#endif	//!_stat

bool TkFile::isDir(const QString & path) {
	struct _stat statbuf;

	const wchar_t * encodedName = reinterpret_cast<const wchar_t *>(path.utf16());

	lstat(encodedName, &statbuf);

	return S_ISDIR(statbuf.st_mode);
}



-- 
Tanguy Krotoff <tkrotoff at gmail.com>
+33 6 68 42 70 24