optimized red-black trees and common base class for string-keyed RB trees

 * the old implementation tried to avoid template programming by
   making the entry comparison function virtual.
 * The new RBTree implementation takes a template argument with the
   implementation of RBEntry. It is now partially conventional
   that the template argument must be actually derived from RBTree::RBEntry
   and must define a "compare" method.
 * As an advantage we now get static polymorphism (avoiding virtual
   calls and allowing for more compiler optimizations) and the
   the RBEntry implementation no longer has to be virtual.
 * The only RB-Trees actually used are string-keyed, though.
   Therefore there's a common base class RBTreeString now which
   defines two synonymous "key" and "name" attributes.
   * The entry base class RBEntryString is virtual again because
     we do not want to propagate the RBEntryType template parameter
     even further and the RBTree base class needs to destroy
     entries.
     This might be avoided by not defining a RBTree::clear() method,
     leaving this task to the implementations.
     At least QRegisters have to be virtual, though.
   * RBTreeString only depends on the strcmp() and strncmp() functions
     used now and only case-sensitive and case-insensitive versions
     are actually required, so we instantiate these templates statically
     in rbtree.cpp.
     This means there are still only two instantiations of the RBTree
     in the binary.
   * RBTreeString defines convenient wrappers for find() and nfind()
     to look up by string.
     This uses the RBEntryString base class, so no allocations whatsover
     are required for lookups and less space is wasted on the call stack.
   * A RBEntryOwnString base class is also provided which frees the
     implementations from memory managing the tree keys.
   * RBTreeString can now be used to add other common functionality
     like auto-completions for Q-Registers, goto labels and help topics.
 * some minor optimizations
 * updated TODO

0 files changed, 0 insertions, 0 deletions