diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | goto.cpp | 55 | ||||
| -rw-r--r-- | rbtree.cpp | 5 | ||||
| -rw-r--r-- | rbtree.h | 273 |
4 files changed, 298 insertions, 37 deletions
@@ -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) @@ -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 |