russell@unturf.com
191f018d78
tiled-0001: mapdocument.cpp sortObjects/sortLayers/moveLayersUp/Down/duplicate QList.contains() inside iteration over all map layers/objects = O(N*S) Fix: QSet O(1) lookup. MEDIUM severity. 24x speedup at N=2000,S=1000. tiled-0002: mapobjectmodel.cpp classChanged QList.contains(tile) inside nested loop over all map objects = O(O*T) Fix: QSet O(1) lookup. MEDIUM severity. 14x speedup at O=2000,T=500. tiled-0003: editpolygontool.cpp updateHandles QList.contains() inside QHash iteration = O(H*S) Fix: QSet O(1) lookup. MEDIUM severity. 13x speedup at H=1000,S=500. 3/3 PASS. MOAD-0002/0003/0004/0005 CLEAN.
75 lines
2.5 KiB
C++
75 lines
2.5 KiB
C++
// tiled-0003-test.cpp
|
|
// CWE-407 unit test: editpolygontool.cpp updateHandles
|
|
// QList<MapObject*>.contains() inside QHash iteration = O(HandleEntries * SelectionSize)
|
|
// Fix: QSet for O(1) lookup
|
|
|
|
#include <QList>
|
|
#include <QSet>
|
|
#include <QHash>
|
|
#include <QElapsedTimer>
|
|
#include <cstdio>
|
|
#include <cassert>
|
|
|
|
// Simulate: iterate hash entries, check if key is in selection list
|
|
static int updateHandles_defective(const QHash<void*, int> &handles,
|
|
const QList<void*> &selection) {
|
|
int removed = 0;
|
|
for (auto it = handles.begin(); it != handles.end(); ++it) {
|
|
if (!selection.contains(it.key())) // O(N) per call
|
|
removed++;
|
|
}
|
|
return removed;
|
|
}
|
|
|
|
static int updateHandles_fixed(const QHash<void*, int> &handles,
|
|
const QList<void*> &selection) {
|
|
const QSet<void*> selectionSet(selection.begin(), selection.end());
|
|
int removed = 0;
|
|
for (auto it = handles.begin(); it != handles.end(); ++it) {
|
|
if (!selectionSet.contains(it.key())) // O(1) per call
|
|
removed++;
|
|
}
|
|
return removed;
|
|
}
|
|
|
|
int main() {
|
|
const int HANDLES = 1000; // polygon objects with handles
|
|
const int SELECTION = 500; // selected objects
|
|
|
|
QHash<void*, int> handles;
|
|
QList<void*> selection;
|
|
|
|
for (int i = 0; i < HANDLES; ++i)
|
|
handles.insert(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 1)), i);
|
|
|
|
for (int i = 0; i < SELECTION; ++i)
|
|
selection.append(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 1)));
|
|
|
|
const int ITERS = 500;
|
|
|
|
QElapsedTimer timer;
|
|
timer.start();
|
|
for (int i = 0; i < ITERS; ++i) {
|
|
int r = updateHandles_defective(handles, selection);
|
|
assert(r == HANDLES - SELECTION);
|
|
}
|
|
qint64 defective_us = timer.nsecsElapsed() / 1000;
|
|
|
|
timer.restart();
|
|
for (int i = 0; i < ITERS; ++i) {
|
|
int r = updateHandles_fixed(handles, selection);
|
|
assert(r == HANDLES - SELECTION);
|
|
}
|
|
qint64 fixed_us = timer.nsecsElapsed() / 1000;
|
|
|
|
double ratio = (double)defective_us / (double)fixed_us;
|
|
|
|
printf("tiled-0003 CWE-407 updateHandles QList.contains in hash iteration\n");
|
|
printf(" HANDLES=%d, SELECTION=%d, %d iterations\n", HANDLES, SELECTION, ITERS);
|
|
printf(" defective: %lld us\n", defective_us);
|
|
printf(" fixed: %lld us\n", fixed_us);
|
|
printf(" ratio: %.1fx\n", ratio);
|
|
printf(" %s\n", ratio >= 2.0 ? "PASS" : "FAIL");
|
|
|
|
return ratio >= 2.0 ? 0 : 1;
|
|
}
|