RBTree class (wrapper around BSD macros) - use for Goto table

 * the other classes (Table, StringTable, StringTableUndo) do not yet work

4 files changed, 298 insertions, 37 deletions

diff --git a/Makefile b/Makefile
index 5d7787a..7742afd 100644
--- a/Makefile
+++ b/Makefile
@@ -14,7 +14,7 @@ LDFLAGS:=$(GTK_LDFLAGS) $(SCI_LDFLAGS)
 all : sciteco
 
 sciteco : main.o cmdline.o undo.o expressions.o qbuffers.o \
-	  parser.o goto.o \
+	  parser.o goto.o rbtree.o \
 	  gtk-info-popup.o
 	$(CXX) -o $@ $^ $(LDFLAGS)
 
diff --git a/goto.cpp b/goto.cpp
index fd47bcc..6deac96 100644
--- a/goto.cpp
+++ b/goto.cpp
@@ -6,6 +6,7 @@
 #include "sciteco.h"
 #include "parser.h"
 #include "undo.h"
+#include "rbtree.h"
 #include "goto.h"
 
 namespace States {
@@ -14,7 +15,7 @@ namespace States {
 
 static gchar *skip_label = NULL;
 
-class GotoTable {
+class GotoTable : public RBTree {
 	class UndoTokenSet : public UndoToken {
 		GotoTable *table;
 
@@ -35,16 +36,13 @@ class GotoTable {
 			table->set(name, pc);
 			g_free(name);
 			name = NULL;
-#if 0
+
 			table->dump();
-#endif
 		}
 	};
 
-	class Label {
+	class Label : public RBEntry {
 	public:
-		RB_ENTRY(Label) nodes;
-
 		gchar	*name;
 		gint	pc;
 
@@ -55,27 +53,15 @@ class GotoTable {
 			g_free(name);
 		}
 
-		static inline int
-		cmp(Label *l1, Label *l2)
+		int
+		operator <(RBEntry &l2)
 		{
-			return g_strcmp0(l1->name, l2->name);
+			return g_strcmp0(name, ((Label &)l2).name);
 		}
 	};
 
-	RB_HEAD(Table, Label) head;
-
-	RB_GENERATE(Table, Label, nodes, Label::cmp);
-
 public:
-	GotoTable()
-	{
-		RB_INIT(&head);
-	}
-
-	~GotoTable()
-	{
-		clear();
-	}
+	GotoTable() : RBTree() {}
 
 	gint
 	remove(gchar *name)
@@ -83,11 +69,11 @@ public:
 		gint existing_pc = -1;
 
 		Label label(name);
-		Label *existing = RB_FIND(Table, &head, &label);
+		Label *existing = (Label *)RBTree::find(&label);
 
 		if (existing) {
 			existing_pc = existing->pc;
-			RB_REMOVE(Table, &head, existing);
+			RBTree::remove(existing);
 			delete existing;
 		}
 
@@ -98,7 +84,7 @@ public:
 	find(gchar *name)
 	{
 		Label label(name);
-		Label *existing = RB_FIND(Table, &head, &label);
+		Label *existing = (Label *)RBTree::find(&label);
 
 		return existing ? existing->pc : -1;
 	}
@@ -113,7 +99,7 @@ public:
 		Label *existing;
 		gint existing_pc = -1;
 
-		existing = RB_FIND(Table, &head, label);
+		existing = (Label *)RBTree::find(label);
 		if (existing) {
 			existing_pc = existing->pc;
 			g_free(existing->name);
@@ -123,12 +109,11 @@ public:
 			label->name = NULL;
 			delete label;
 		} else {
-			RB_INSERT(Table, &head, label);
+			RBTree::insert(label);
 		}
 
-#if 0
 		dump();
-#endif
+
 		return existing_pc;
 	}
 
@@ -143,23 +128,21 @@ public:
 	{
 		Label *cur;
 
-		while ((cur = RB_MIN(Table, &head))) {
-			RB_REMOVE(Table, &head, cur);
+		while ((cur = (Label *)RBTree::min())) {
+			RBTree::remove(cur);
 			delete cur;
 		}
 	}
 
-#if 0
 	void
 	dump(void)
 	{
-		Label *cur;
-
-		RB_FOREACH(cur, Table, &head)
+		for (Label *cur = (Label *)RBTree::min();
+		     cur != NULL;
+		     cur = (Label *)cur->next())
 			g_printf("table[\"%s\"] = %d\n", cur->name, cur->pc);
 		g_printf("---END---\n");
 	}
-#endif
 };
 
 static GotoTable table;
diff --git a/rbtree.cpp b/rbtree.cpp
new file mode 100644
index 0000000..28df67b
--- /dev/null
+++ b/rbtree.cpp
@@ -0,0 +1,5 @@
+#include <bsd/sys/tree.h>
+
+#include "rbtree.h"
+
+RB_GENERATE(RBTree::Tree, RBTree::RBEntry, nodes, RBTree::compare_entries);
diff --git a/rbtree.h b/rbtree.h
new file mode 100644
index 0000000..6c54f92
--- /dev/null
+++ b/rbtree.h
@@ -0,0 +1,273 @@
+#ifndef __RBTREE_H
+#define __RBTREE_H
+
+#include <bsd/sys/tree.h>
+
+#include <glib.h>
+
+#include "undo.h"
+
+class RBTree {
+protected:
+	class RBEntry;
+
+private:
+	RB_HEAD(Tree, RBEntry) head;
+
+	RB_PROTOTYPE_INTERNAL(Tree, RBEntry, nodes, /* unused */, static);
+
+protected:
+	class RBEntry {
+	public:
+		RB_ENTRY(RBEntry) nodes;
+
+		inline RBEntry *
+		next(void)
+		{
+			return RBTree::Tree_RB_NEXT(this);
+		}
+		inline RBEntry *
+		prev(void)
+		{
+			return RBTree::Tree_RB_PREV(this);
+		}
+
+		virtual int operator <(RBEntry &entry) = 0;
+	};
+
+private:
+	static inline int
+	compare_entries(RBEntry *e1, RBEntry *e2)
+	{
+		return *e1 < *e2;
+	}
+
+public:
+	RBTree()
+	{
+		RB_INIT(&head);
+	}
+
+	virtual
+	~RBTree()
+	{
+		RBEntry *cur, *next;
+
+		RB_FOREACH_SAFE(cur, Tree, &head, next)
+			delete cur;
+	}
+
+	inline RBEntry *
+	insert(RBEntry *entry)
+	{
+		RB_INSERT(Tree, &head, entry);
+		return entry;
+	}
+	inline RBEntry *
+	remove(RBEntry *entry)
+	{
+		return RB_REMOVE(Tree, &head, entry);
+	}
+	inline RBEntry *
+	find(RBEntry *entry)
+	{
+		return RB_FIND(Tree, &head, entry);
+	}
+	inline RBEntry *
+	nfind(RBEntry *entry)
+	{
+		return RB_NFIND(Tree, &head, entry);
+	}
+	inline RBEntry *
+	min(void)
+	{
+		return RB_MIN(Tree, &head);
+	}
+	inline RBEntry *
+	max(void)
+	{
+		return RB_MAX(Tree, &head);
+	}
+};
+
+template <typename KeyType, typename ValueType>
+class Table : public RBTree {
+	class TableEntry : public RBEntry {
+	public:
+		KeyType		key;
+		ValueType	value;
+
+		TableEntry(KeyType &_key, ValueType &_value)
+			  : key(_key), value(_value) {}
+
+		int
+		operator <(RBEntry &entry)
+		{
+			return key < ((TableEntry &)entry).key;
+		}
+	};
+
+public:
+	ValueType nil;
+
+	Table(ValueType &_nil) : RBTree(), nil(_nil) {}
+
+	inline bool
+	hasEntry(KeyType &key)
+	{
+		return find(&TableEntry(key, nil)) != NULL;
+	}
+
+	ValueType &
+	operator [](KeyType &key)
+	{
+		TableEntry *entry = new TableEntry(key, nil);
+		TableEntry *existing = (TableEntry *)find(entry);
+
+		if (existing)
+			delete entry;
+		else
+			existing = (TableEntry *)insert(entry);
+
+		return existing->value;
+	}
+
+	inline void
+	remove(KeyType &key)
+	{
+		TableEntry entry(key, nil);
+		TableEntry *existing = (TableEntry *)find(&entry);
+
+		if (existing)
+			RBTree::remove(existing);
+	}
+
+#if 0
+	void
+	dump(void)
+	{
+		RBEntry *cur;
+
+		RB_FOREACH(cur, Tree, &head)
+			g_printf("tree[\"%s\"] = %d\n", cur->name, cur->pc);
+		g_printf("---END---\n");
+	}
+#endif
+
+	void
+	clear(void)
+	{
+		RBEntry *cur;
+
+		while ((cur = min())) {
+			RBTree::remove(cur);
+			delete cur;
+		}
+	}
+};
+
+class CString {
+public:
+	gchar *str;
+
+	CString(const gchar *_str) : str(g_strdup(_str)) {}
+	~CString()
+	{
+		g_free(str);
+	}
+
+	inline int
+	operator <(CString &obj)
+	{
+		return (int)g_strcmp0(str, obj.str);
+	}
+};
+
+template <typename ValueType>
+class StringTable : public Table<CString, ValueType> {
+public:
+	StringTable(ValueType &nil) : Table<CString, ValueType>(nil) {}
+
+	inline bool
+	hasEntry(const gchar *key)
+	{
+		CString str(key);
+		return Table<CString, ValueType>::hasEntry(str);
+	}
+
+	inline ValueType &
+	operator [](const gchar *key)
+	{
+		CString str(key);
+		return (Table<CString, ValueType>::operator [])(str);
+	}
+
+	inline void
+	remove(const gchar *key)
+	{
+		CString str(key);
+		Table<CString, ValueType>::remove(str);
+	}
+};
+
+template <typename ValueType>
+class StringTableUndo : public StringTable<ValueType> {
+	class UndoTokenSet : public UndoToken {
+		StringTableUndo *table;
+
+		CString		name;
+		ValueType	value;
+
+	public:
+		UndoTokenSet(StringTableUndo *_table, CString &_name, ValueType &_value)
+			    : table(_table), name(_name), value(_value) {}
+
+		void
+		run(void)
+		{
+			table->Table<CString, ValueType>::operator [](name) = value;
+			name.str = NULL;
+#if 0
+			table->dump();
+#endif
+		}
+	};
+
+	class UndoTokenRemove : public UndoToken {
+		StringTableUndo *table;
+
+		CString name;
+
+	public:
+		UndoTokenRemove(StringTableUndo *_table, CString &_name)
+			       : table(_table), name(_name) {}
+
+		void
+		run(void)
+		{
+			table->Table<CString, ValueType>::remove(name);
+#if 0
+			table->dump();
+#endif
+		}
+	};
+
+public:
+	StringTableUndo(ValueType &nil) : StringTable<ValueType>(nil) {}
+
+	void
+	set(const gchar *key, ValueType &value)
+	{
+		ValueType &old = (StringTable<ValueType>::operator [])(key);
+		CString str(key);
+
+		if (old == StringTable<ValueType>::nil)
+			undo.push(new UndoTokenRemove(this, str));
+		else
+			undo.push(new UndoTokenSet(this, str, old));
+
+		old = value;
+	}
+};
+
+#endif