Rewrite QMap to use a RB tree

QMap used to use a skiplist in Qt 4.x, which has variable
sized nodes and we can thus not optimise using custom
allocators.

The rewrite now uses a red-black tree, and all allocations
and tree operations happen in the cpp file. This will allow
us to introduce custom allocation schemes in later versions
of Qt.

Added some more tests and a benchmark. Memory consumption
of the new QMap implementation is pretty much the same as before.
Performance of insertion and lookup has increased by 10-30%. iteration
is slower, but still extremely fast and should not matter compared
to the work usually done when iterating.

Change-Id: I8796c0e4b207d01111e2ead7ae55afb464dd88f5
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 5 insertions, 0 deletions

diff --git a/tests/benchmarks/corelib/tools/qmap/qmap.pro b/tests/benchmarks/corelib/tools/qmap/qmap.pro
new file mode 100644
index 0000000000..6a0c8d62bd
--- /dev/null
+++ b/tests/benchmarks/corelib/tools/qmap/qmap.pro
@@ -0,0 +1,5 @@
+TARGET = tst_qmap
+QT = core testlib
+INCLUDEPATH += .
+SOURCES += main.cpp
+CONFIG += release