From f9e6f8630cdb0c6d056154b82e8f94289509f48a Mon Sep 17 00:00:00 2001
From: Robin Haberkorn <robin.haberkorn@googlemail.com>
Date: Sat, 19 Nov 2016 18:34:52 +0100
Subject: 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
---
 src/goto.cpp | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)

(limited to 'src/goto.cpp')

diff --git a/src/goto.cpp b/src/goto.cpp
index c5fda9a..01cf0a9 100644
--- a/src/goto.cpp
+++ b/src/goto.cpp
@@ -42,16 +42,15 @@ namespace Goto {
 }
 
 gint
-GotoTable::remove(gchar *name)
+GotoTable::remove(const gchar *name)
 {
 	gint existing_pc = -1;
 
-	Label label(name);
-	Label *existing = (Label *)RBTree::find(&label);
+	Label *existing = (Label *)RBTreeString::find(name);
 
 	if (existing) {
 		existing_pc = existing->pc;
-		RBTree::remove(existing);
+		RBTreeString::remove(existing);
 		delete existing;
 	}
 
@@ -59,35 +58,29 @@ GotoTable::remove(gchar *name)
 }
 
 gint
-GotoTable::find(gchar *name)
+GotoTable::find(const gchar *name)
 {
-	Label label(name);
-	Label *existing = (Label *)RBTree::find(&label);
+	Label *existing = (Label *)RBTreeString::find(name);
 
 	return existing ? existing->pc : -1;
 }
 
 gint
-GotoTable::set(gchar *name, gint pc)
+GotoTable::set(const gchar *name, gint pc)
 {
 	if (pc < 0)
 		return remove(name);
 
-	Label *label = new Label(name, pc);
-	Label *existing;
 	gint existing_pc = -1;
+	Label *existing = (Label *)RBTreeString::find(name);
 
-	existing = (Label *)RBTree::find(label);
 	if (existing) {
 		existing_pc = existing->pc;
 		g_free(existing->name);
-		existing->name = label->name;
-		existing->pc = label->pc;
-
-		label->name = NULL;
-		delete label;
+		existing->name = g_strdup(name);
+		existing->pc = pc;
 	} else {
-		RBTree::insert(label);
+		RBTree::insert(new Label(name, pc));
 	}
 
 #ifdef DEBUG
@@ -101,7 +94,7 @@ GotoTable::set(gchar *name, gint pc)
 void
 GotoTable::dump(void)
 {
-	for (Label *cur = (Label *)RBTree::min();
+	for (Label *cur = (Label *)min();
 	     cur != NULL;
 	     cur = (Label *)cur->next())
 		g_printf("table[\"%s\"] = %d\n", cur->name, cur->pc);
-- 
cgit v1.2.3