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, 17 insertions, 22 deletions

diff --git a/src/goto.h b/src/goto.h
index 1621acd..4fa5766 100644
--- a/src/goto.h
+++ b/src/goto.h
@@ -30,7 +30,7 @@
 
 namespace SciTECO {
 
-class GotoTable : public RBTree {
+class GotoTable : private RBTreeString {
 	class UndoTokenSet : public UndoToken {
 		GotoTable *table;
 
@@ -38,7 +38,7 @@ class GotoTable : public RBTree {
 		gint	pc;
 
 	public:
-		UndoTokenSet(GotoTable *_table, gchar *_name, gint _pc = -1)
+		UndoTokenSet(GotoTable *_table, const gchar *_name, gint _pc = -1)
 			    : table(_table), name(g_strdup(_name)), pc(_pc) {}
 		~UndoTokenSet()
 		{
@@ -61,23 +61,12 @@ class GotoTable : public RBTree {
 		}
 	};
 
-	class Label : public RBTree::RBEntry {
+	class Label : public RBEntryOwnString {
 	public:
-		gchar	*name;
-		gint	pc;
-
-		Label(gchar *_name, gint _pc = -1)
-		     : name(g_strdup(_name)), pc(_pc) {}
-		~Label()
-		{
-			g_free(name);
-		}
+		gint pc;
 
-		int
-		operator <(RBEntry &l2)
-		{
-			return g_strcmp0(name, ((Label &)l2).name);
-		}
+		Label(const gchar *name, gint _pc = -1)
+		     : RBEntryOwnString(name), pc(_pc) {}
 	};
 
 	/*
@@ -86,19 +75,25 @@ class GotoTable : public RBTree {
 	bool must_undo;
 
 public:
-	GotoTable(bool _undo = true) : RBTree(), must_undo(_undo) {}
+	GotoTable(bool _undo = true) : must_undo(_undo) {}
 
-	gint remove(gchar *name);
-	gint find(gchar *name);
+	gint remove(const gchar *name);
+	gint find(const gchar *name);
 
-	gint set(gchar *name, gint pc);
+	gint set(const gchar *name, gint pc);
 	inline void
-	undo_set(gchar *name, gint pc = -1)
+	undo_set(const gchar *name, gint pc = -1)
 	{
 		if (must_undo)
 			undo.push<UndoTokenSet>(this, name, pc);
 	}
 
+	inline void
+	clear(void)
+	{
+		RBTreeString::clear();
+	}
+
 #ifdef DEBUG
 	void dump(void);
 #endif