summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMartin T. H. Sandsmark <martin.sandsmark@kde.org>2016-08-21 19:07:12 (GMT)
committerMartin T. H. Sandsmark <martin.sandsmark@kde.org>2016-08-27 13:03:29 (GMT)
commitee71f61218704248bd77a68c6d3ada9b913ba3d7 (patch)
tree6a77e565002629457342ec51e33a28d0d9c41c8e
parent6175850d0195bccf362d19ea7a874c6a81252c6a (diff)
Port away from homemade data structure
Ports away from and removes the custom linked list implementation, and use QList instead. Both a small performance improvement, and QList is compatible with e. g. std::sort().
-rw-r--r--src/part/fileTree.h201
-rw-r--r--src/part/localLister.cpp19
-rw-r--r--src/part/localLister.h4
-rw-r--r--src/part/radialMap/map.cpp24
-rw-r--r--src/part/scan.cpp14
5 files changed, 39 insertions, 223 deletions
diff --git a/src/part/fileTree.h b/src/part/fileTree.h
index bad4097..da70a3a 100644
--- a/src/part/fileTree.h
+++ b/src/part/fileTree.h
@@ -30,198 +30,10 @@
#include <stdlib.h>
-//TODO these are pointlessly general purpose now, make them incredibly specific
-
typedef quint64 FileSize;
typedef quint64 Dirsize; //**** currently unused
-template <class T> class Iterator;
-template <class T> class ConstIterator;
-template <class T> class Chain;
-
-template <class T>
-class Link
-{
-public:
- Link(T* const t) : prev(this), next(this), data(t) {}
- Link() : prev(this), next(this), data(0) {}
-
-//TODO unlinking is slow and you don't use it very much in this context.
-// ** Perhaps you can make a faster deletion system that doesn't bother tidying up first
-// ** and then you MUST call some kind of detach() function when you remove elements otherwise
- ~Link() {
- delete data;
- unlink();
- }
-
- friend class Iterator<T>;
- friend class ConstIterator<T>;
- friend class Chain<T>;
-
-private:
- void unlink() {
- prev->next = next;
- next->prev = prev;
- prev = next = this;
- }
-
- Link<T>* prev;
- Link<T>* next;
-
- T* data; //ensure only iterators have access to this
-};
-
-
-template <class T>
-class Iterator
-{
-public:
- Iterator() = delete;
-
- Iterator(Link<T> *p) : link(p) { }
-
- bool operator==(const Iterator<T>& it) const {
- return link == it.link;
- }
- bool operator!=(const Iterator<T>& it) const {
- return link != it.link;
- }
- bool operator!=(const Link<T> *p) const {
- return p != link;
- }
-
- //here we have a choice, really I should make two classes one const the other not
- const T* operator*() const {
- return link->data;
- }
- T* operator*() {
- return link->data;
- }
-
- Iterator<T>& operator++() {
- link = link->next; //**** does it waste time returning in places where we don't use the retval?
- return *this;
- }
-
- bool isNull() const {
- return (link == 0); //REMOVE WITH ABOVE REMOVAL you don't want null iterators to be possible
- }
-
- void transferTo(Chain<T> &chain)
- {
- chain.append(remove());
- }
-
- T* remove() //remove from list, delete Link, data is returned NOT deleted
-
- {
- T* const d = link->data;
- Link<T>* const p = link->prev;
-
- link->data = 0;
- delete link;
- link = p; //make iterator point to previous element, YOU must check this points to an element
-
- return d;
- }
-
-private:
- Link<T> *link;
-};
-
-
-template <class T>
-class ConstIterator
-{
-public:
- ConstIterator(Link<T> *p) : link(p) { }
-
- bool operator==(const Iterator<T>& it) const {
- return link == it.link;
- }
- bool operator!=(const Iterator<T>& it) const {
- return link != it.link;
- }
- bool operator!=(const Link<T> *p) const {
- return p != link;
- }
-
- const T* operator*() const {
- return link->data;
- }
-
- ConstIterator<T>& operator++() {
- link = link->next;
- return *this;
- }
-
-private:
- const Link<T> *link;
-};
-
-
-template <class T>
-class Chain
-{
-public:
- virtual ~Chain() {
- empty();
- }
-
- void append(T* const data)
- {
- Link<T>* const link = new Link<T>(data);
-
- link->prev = head.prev;
- link->next = &head;
-
- head.prev->next = link;
- head.prev = link;
- }
-
- void transferTo(Chain &c)
- {
- if (isEmpty()) return;
-
- Link<T>* const first = head.next;
- Link<T>* const last = head.prev;
-
- head.unlink();
-
- first->prev = c.head.prev;
- c.head.prev->next = first;
-
- last->next = &c.head;
- c.head.prev = last;
- }
-
- void empty() {
- while (head.next != &head) {
- delete head.next;
- }
- }
-
- Iterator<T> iterator() const {
- return Iterator<T>(head.next);
- }
- ConstIterator<T> constIterator() const {
- return ConstIterator<T>(head.next);
- }
- const Link<T> *end() const {
- return &head;
- }
- bool isEmpty() const {
- return head.next == &head;
- }
-
-private:
- Link<T> head;
- void operator=(const Chain&);
-};
-
-
class Folder;
-class QString;
class File
{
@@ -269,7 +81,7 @@ private:
};
-class Folder : public Chain<File>, public File
+class Folder : public File
{
public:
Folder(const char *name) : File(name, 0), m_children(0) {} //DON'T pass the full path!
@@ -302,20 +114,21 @@ public:
/// removes a file
void remove(const File *f) {
- for (Iterator<File> it = iterator(); it != end(); ++it)
- if (f == (*it))
- it.remove();
+ files.removeAll(const_cast<File*>(f));
- for (Folder *d = this; d; d = d->parent())
+ for (Folder *d = this; d; d = d->parent()) {
d->m_size -= f->size();
+ }
}
+ QList<File *> files;
+
private:
void append(File *p)
{
m_children++;
m_size += p->size();
- Chain<File>::append(p);
+ files.append(p);
}
uint m_children;
diff --git a/src/part/localLister.cpp b/src/part/localLister.cpp
index 1399ffc..5a9e629 100644
--- a/src/part/localLister.cpp
+++ b/src/part/localLister.cpp
@@ -29,6 +29,7 @@
#include <Solid/StorageAccess>
#include <Solid/Device>
+#include <QElapsedTimer>
#include <QGuiApplication> //postEvent()
#include <QFile>
#include <QByteArray>
@@ -52,7 +53,7 @@ namespace Filelight
QStringList LocalLister::s_remoteMounts;
QStringList LocalLister::s_localMounts;
-LocalLister::LocalLister(const QString &path, Chain<Folder> *cachedTrees, ScanManager *parent)
+LocalLister::LocalLister(const QString &path, QList<Folder *> *cachedTrees, ScanManager *parent)
: QThread()
, m_path(path)
, m_trees(cachedTrees)
@@ -75,9 +76,12 @@ LocalLister::LocalLister(const QString &path, Chain<Folder> *cachedTrees, ScanMa
void
LocalLister::run()
{
+ QElapsedTimer timer;
+ timer.start();
//recursively scan the requested path
const QByteArray path = QFile::encodeName(m_path);
Folder *tree = scan(path, path);
+ qDebug() << "Scan completed in" << (timer.elapsed()/1000);
//delete the list of trees useful for this scan,
//in a sucessful scan the contents would now be transferred to 'tree'
@@ -198,15 +202,14 @@ LocalLister::scan(const QByteArray &path, const QByteArray &dirname)
//check to see if we've scanned this section already
- for (Iterator<Folder> it = m_trees->iterator(); it != m_trees->end(); ++it)
+ for (Folder *folder : *m_trees)
{
- if (new_path == (*it)->name8Bit())
+ if (new_path == folder->name8Bit())
{
- qDebug() << "Tree pre-completed: " << (*it)->name();
- d = it.remove();
- m_parent->m_files += d->children();
- //**** ideally don't have this redundant extra somehow
- cwd->append(d, new_dirname);
+ qDebug() << "Tree pre-completed: " << folder->name();
+ m_trees->removeAll(folder);
+ m_parent->m_files += folder->children();
+ cwd->append(folder, new_dirname);
}
}
diff --git a/src/part/localLister.h b/src/part/localLister.h
index ea5acee..b73c14c 100644
--- a/src/part/localLister.h
+++ b/src/part/localLister.h
@@ -37,7 +37,7 @@ class LocalLister : public QThread
Q_OBJECT
public:
- LocalLister(const QString &path, Chain<Folder> *cachedTrees, ScanManager *parent);
+ LocalLister(const QString &path, QList<Folder*> *cachedTrees, ScanManager *parent);
static void readMounts();
@@ -46,7 +46,7 @@ signals:
private:
QString m_path;
- Chain<Folder> *m_trees;
+ QList<Folder*> *m_trees;
ScanManager *m_parent;
private:
diff --git a/src/part/radialMap/map.cpp b/src/part/radialMap/map.cpp
index 0401692..b1d0985 100644
--- a/src/part/radialMap/map.cpp
+++ b/src/part/radialMap/map.cpp
@@ -139,9 +139,9 @@ void RadialMap::Map::findVisibleDepth(const Folder *dir, uint currentDepth)
if (m_visibleDepth < currentDepth) m_visibleDepth = currentDepth;
if (m_visibleDepth >= stopDepth) return;
- for (ConstIterator<File> it = dir->constIterator(); it != dir->end(); ++it) {
- if ((*it)->isFolder() && (*it)->size() > m_minSize) {
- findVisibleDepth((Folder *)*it, currentDepth + 1); //if no files greater than min size the depth is still recorded
+ for (File *file : dir->files) {
+ if (file->isFolder() && file->size() > m_minSize) {
+ findVisibleDepth((Folder *)file, currentDepth + 1); //if no files greater than min size the depth is still recorded
}
}
}
@@ -157,25 +157,25 @@ bool RadialMap::Map::build(const Folder * const dir, const uint depth, uint a_st
FileSize hiddenSize = 0;
uint hiddenFileCount = 0;
- for (ConstIterator<File> it = dir->constIterator(); it != dir->end(); ++it) {
- if ((*it)->size() < m_limits[depth] * 6) { // limit is half a degree? we want at least 3 degrees
- hiddenSize += (*it)->size();
- if ((*it)->isFolder()) { //**** considered virtual, but dir wouldn't count itself!
- hiddenFileCount += static_cast<const Folder*>(*it)->children(); //need to add one to count the dir as well
+ for (File *file : dir->files) {
+ if (file->size() < m_limits[depth] * 6) { // limit is half a degree? we want at least 3 degrees
+ hiddenSize += file->size();
+ if (file->isFolder()) { //**** considered virtual, but dir wouldn't count itself!
+ hiddenFileCount += static_cast<const Folder*>(file)->children(); //need to add one to count the dir as well
}
++hiddenFileCount;
continue;
}
- unsigned int a_len = (unsigned int)(5760 * ((double)(*it)->size() / (double)m_root->size()));
+ unsigned int a_len = (unsigned int)(5760 * ((double)file->size() / (double)m_root->size()));
- Segment *s = new Segment(*it, a_start, a_len);
+ Segment *s = new Segment(file, a_start, a_len);
m_signature[depth].append(s);
- if ((*it)->isFolder()) {
+ if (file->isFolder()) {
if (depth != m_visibleDepth) {
//recurse
- s->m_hasHiddenChildren = build((Folder*)*it, depth + 1, a_start, a_start + a_len);
+ s->m_hasHiddenChildren = build((Folder*)file, depth + 1, a_start, a_start + a_len);
} else {
s->m_hasHiddenChildren = true;
}
diff --git a/src/part/scan.cpp b/src/part/scan.cpp
index c64ec65..4b8da2b 100644
--- a/src/part/scan.cpp
+++ b/src/part/scan.cpp
@@ -91,7 +91,7 @@ bool ScanManager::start(const QUrl &url)
if (!path.endsWith(QDir::separator())) path += QDir::separator();
- Chain<Folder> *trees = new Chain<Folder>;
+ QList<Folder*> *trees = new QList<Folder*>;
/* CHECK CACHE
* user wants: /usr/local/
@@ -115,17 +115,17 @@ bool ScanManager::start(const QUrl &url)
Folder *d = folder;
while (!split.isEmpty() && d != NULL) { //if NULL we have got lost so abort!!
- Iterator<File> jt = d->iterator();
-
- const Link<File> *end = d->end();
if (split.first().isEmpty()) { //found the dir
break;
}
QString s = split.first() % QLatin1Char('/'); // % is the string concatenation operator for QStringBuilder
- for (d = 0; jt != end; ++jt) {
- if (s == (*jt)->name()) {
- d = (Folder*)*jt;
+ QListIterator<File*> it(d->files);
+ d = nullptr;
+ while (it.hasNext()) {
+ File *subfolder = it.next();
+ if (s == subfolder->name()) {
+ d = (Folder*)subfolder;
break;
}
}