Revision 874247

Go back to digest for 26th October 2008

Optimization in Development Tools

David Nolden committed changes in /trunk/KDE/kdevplatform/util:

Add a tree system to efficiently manage large sorted lists/arrays with "free" items in between.
The system does the complete logic of telling when the array needs to be reallocated with another size, evenly distributes the free items, builds an embedded tree among them, and uses that tree to efficiently insert and remove items in sub-linear time.
This allows to make the currently plain unsorted value-lists in the persistent symbol-table and in the code-model scale up much better.

This also contains an extensive randomized test that proofs that this works. :-)

File Changes

Added 4 files
  • /trunk/KDE/kdevplatform/util
  •   /embeddedfreetree.h
  •   /tests
  •   /tests/CMakeLists.txt
  •   /tests/test_embeddedfreetree.cpp
Modified 1 files
  • /trunk/KDE/kdevplatform/util/CMakeLists.txt
5 files changed in total