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

1 files changed, 15 insertions, 29 deletions

diff --git a/src/qregisters.h b/src/qregisters.h
index 22fa93d..1ea47ee 100644
--- a/src/qregisters.h
+++ b/src/qregisters.h
@@ -134,30 +134,17 @@ public:
 	friend class QRegisterStack;
 };
 
-class QRegister : public RBTree::RBEntry, public QRegisterData {
+class QRegister : public RBTreeString::RBEntryOwnString, public QRegisterData {
 protected:
 	/**
 	 * The default constructor for subclasses.
 	 * This leaves the name uninitialized.
 	 */
-	QRegister(void) : name(NULL) {}
+	QRegister() {}
 
 public:
-	gchar *name;
-
-	QRegister(const gchar *_name)
-		 : name(g_strdup(_name)) {}
-	virtual
-	~QRegister()
-	{
-		g_free(name);
-	}
-
-	int
-	operator <(RBEntry &entry)
-	{
-		return g_strcmp0(name, ((QRegister &)entry).name);
-	}
+	QRegister(const gchar *name)
+		 : RBTreeString::RBEntryOwnString(name) {}
 
 	virtual void edit(void);
 	virtual void undo_edit(void);
@@ -300,7 +287,7 @@ public:
 	void undo_exchange_string(QRegisterData &reg);
 };
 
-class QRegisterTable : private RBTree {
+class QRegisterTable : private RBTreeString {
 	class UndoTokenRemove : public UndoTokenWithSize<UndoTokenRemove> {
 		QRegisterTable *table;
 		QRegister *reg;
@@ -332,11 +319,7 @@ public:
 	insert(QRegister *reg)
 	{
 		reg->must_undo = must_undo;
-		/* FIXME: Returns already existing regs with the same name.
-		   This could be used to optimize commands that initialize
-		   a register if it does not yet exist (saves one table
-		   lookup): */
-		RBTree::insert(reg);
+		RBTreeString::insert(reg);
 		return reg;
 	}
 	inline QRegister *
@@ -352,30 +335,33 @@ public:
 	}
 
 	inline QRegister *
+	find(const gchar *name)
+	{
+		return (QRegister *)RBTreeString::find(name);
+	}
+	inline QRegister *
 	operator [](const gchar *name)
 	{
-		QRegister reg(name);
-		return (QRegister *)find(&reg);
+		return find(name);
 	}
 	inline QRegister *
 	operator [](gchar chr)
 	{
 		gchar buf[] = {chr, '\0'};
-		return operator [](buf);
+		return find(buf);
 	}
 
 	inline QRegister *
 	nfind(const gchar *name)
 	{
-		QRegister reg(name);
-		return (QRegister *)RBTree::nfind(&reg);
+		return (QRegister *)RBTreeString::nfind(name);
 	}
 
 	void edit(QRegister *reg);
 	inline QRegister *
 	edit(const gchar *name)
 	{
-		QRegister *reg = operator [](name);
+		QRegister *reg = find(name);
 
 		if (!reg)
 			return NULL;