diff options
author | Robin Haberkorn <robin.haberkorn@googlemail.com> | 2016-11-19 18:34:52 +0100 |
---|---|---|
committer | Robin Haberkorn <robin.haberkorn@googlemail.com> | 2016-11-20 00:24:40 +0100 |
commit | f9e6f8630cdb0c6d056154b82e8f94289509f48a (patch) | |
tree | 43e98e32982c6c9b9a0dfcf38d59792f5efe23d3 /src | |
parent | 660b744c4bef80655c240032bc942920629a0d44 (diff) | |
download | sciteco-f9e6f8630cdb0c6d056154b82e8f94289509f48a.tar.gz |
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
Diffstat (limited to 'src')
-rw-r--r-- | src/goto.cpp | 29 | ||||
-rw-r--r-- | src/goto.h | 39 | ||||
-rw-r--r-- | src/help.cpp | 14 | ||||
-rw-r--r-- | src/help.h | 16 | ||||
-rw-r--r-- | src/qregisters.cpp | 2 | ||||
-rw-r--r-- | src/qregisters.h | 44 | ||||
-rw-r--r-- | src/rbtree.cpp | 6 | ||||
-rw-r--r-- | src/rbtree.h | 138 |
8 files changed, 167 insertions, 121 deletions
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); @@ -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 diff --git a/src/help.cpp b/src/help.cpp index 0205cf1..542a11f 100644 --- a/src/help.cpp +++ b/src/help.cpp @@ -51,6 +51,10 @@ HelpIndex::load(void) GDir *women_dir; const gchar *basename; + if (G_UNLIKELY(min() != NULL)) + /* already loaded */ + return; + lib_path = QRegisters::globals["$SCITECOPATH"]->get_string(); women_path = g_build_filename(lib_path, "women", NIL); g_free(lib_path); @@ -157,10 +161,9 @@ HelpIndex::find(const gchar *name) */ gchar *term = String::canonicalize_ctl(name); - Topic topic(term); - ret = (Topic *)RBTree::find(&topic); - g_free(term); + ret = (Topic *)RBTreeStringCase::find(term); + g_free(term); return ret; } @@ -170,7 +173,7 @@ HelpIndex::set(const gchar *name, const gchar *filename, tecoInt pos) Topic *topic = new Topic(name, filename, pos); Topic *existing; - existing = (Topic *)RBTree::find(topic); + existing = (Topic *)RBTree<RBEntryString>::find(topic); if (existing) { gchar *basename; @@ -279,8 +282,7 @@ StateGetHelp::initial(void) * not depend on the availability of the standard * library. */ - if (G_UNLIKELY(!help_index.min())) - help_index.load(); + help_index.load(); } State * @@ -30,29 +30,21 @@ namespace SciTECO { -class HelpIndex : public RBTree { +class HelpIndex : private RBTreeStringCase { public: - class Topic : public RBTree::RBEntry { + class Topic : public RBEntryOwnString { public: - gchar *name; gchar *filename; tecoInt pos; - Topic(const gchar *_name, const gchar *_filename = NULL, tecoInt _pos = 0) - : name(g_strdup(_name)), + Topic(const gchar *name, const gchar *_filename = NULL, tecoInt _pos = 0) + : RBEntryOwnString(name), filename(_filename ? g_strdup(_filename) : NULL), pos(_pos) {} ~Topic() { - g_free(name); g_free(filename); } - - int - operator <(RBEntry &l2) - { - return g_ascii_strcasecmp(name, ((Topic &)l2).name); - } }; void load(void); diff --git a/src/qregisters.cpp b/src/qregisters.cpp index c4c164f..6ca7990 100644 --- a/src/qregisters.cpp +++ b/src/qregisters.cpp @@ -696,7 +696,7 @@ QRegisterClipboard::undo_exchange_string(QRegisterData ®) reg.undo_set_string(); } -QRegisterTable::QRegisterTable(bool _undo) : RBTree(), must_undo(_undo) +QRegisterTable::QRegisterTable(bool _undo) : must_undo(_undo) { /* general purpose registers */ for (gchar q = 'A'; q <= 'Z'; q++) 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 ®); }; -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(®); + 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(®); + 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; diff --git a/src/rbtree.cpp b/src/rbtree.cpp index e64de96..f1d870d 100644 --- a/src/rbtree.cpp +++ b/src/rbtree.cpp @@ -19,12 +19,14 @@ #include "config.h" #endif -#include <bsd/sys/tree.h> +#include <glib.h> +#include <glib/gprintf.h> #include "rbtree.h" namespace SciTECO { -RB_GENERATE(RBTree::Tree, RBTree::RBEntry, nodes, RBTree::compare_entries); +template class RBTreeStringT<strcmp, strncmp>; +template class RBTreeStringT<g_ascii_strcasecmp, g_ascii_strncasecmp>; } /* namespace SciTECO */ diff --git a/src/rbtree.h b/src/rbtree.h index bc836bd..4a4bbdb 100644 --- a/src/rbtree.h +++ b/src/rbtree.h @@ -18,30 +18,22 @@ #ifndef __RBTREE_H #define __RBTREE_H +#include <string.h> + #include <bsd/sys/tree.h> #include <glib.h> - -#include "undo.h" +#include <glib/gprintf.h> namespace SciTECO { +template <class RBEntryType> class RBTree { public: - class RBEntry; - -private: - RB_HEAD(Tree, RBEntry) head; - - RB_PROTOTYPE_INTERNAL(Tree, RBEntry, nodes, /* unused */, static); - -public: class RBEntry { public: RB_ENTRY(RBEntry) nodes; - virtual ~RBEntry() {} - inline RBEntry * next(void) { @@ -52,17 +44,23 @@ public: { return RBTree::Tree_RB_PREV(this); } - - virtual int operator <(RBEntry &entry) = 0; }; private: + RB_HEAD(Tree, RBEntry) head; + static inline int compare_entries(RBEntry *e1, RBEntry *e2) { - return *e1 < *e2; + return ((RBEntryType *)e1)->compare(*(RBEntryType *)e2); } + /* + * All generated functions are plain-C, so they can be + * static methods. + */ + RB_GENERATE_INTERNAL(Tree, RBEntry, nodes, compare_entries, static); + public: RBTree() { @@ -74,42 +72,47 @@ public: clear(); } - inline RBEntry * - insert(RBEntry *entry) + inline RBEntryType * + insert(RBEntryType *entry) { RB_INSERT(Tree, &head, entry); return entry; } - inline RBEntry * - remove(RBEntry *entry) + inline RBEntryType * + remove(RBEntryType *entry) + { + return (RBEntryType *)RB_REMOVE(Tree, &head, entry); + } + inline RBEntryType * + find(RBEntryType *entry) { - return RB_REMOVE(Tree, &head, entry); + return (RBEntryType *)RB_FIND(Tree, &head, entry); } - inline RBEntry * - find(RBEntry *entry) + inline RBEntryType * + operator [](RBEntryType *entry) { - return RB_FIND(Tree, &head, entry); + return find(entry); } - inline RBEntry * - nfind(RBEntry *entry) + inline RBEntryType * + nfind(RBEntryType *entry) { - return RB_NFIND(Tree, &head, entry); + return (RBEntryType *)RB_NFIND(Tree, &head, entry); } - inline RBEntry * + inline RBEntryType * min(void) { - return RB_MIN(Tree, &head); + return (RBEntryType *)RB_MIN(Tree, &head); } - inline RBEntry * + inline RBEntryType * max(void) { - return RB_MAX(Tree, &head); + return (RBEntryType *)RB_MAX(Tree, &head); } inline void clear(void) { - RBEntry *cur; + RBEntryType *cur; while ((cur = min())) { remove(cur); @@ -118,6 +121,79 @@ public: } }; +typedef gint (*StringCmpFunc)(const gchar *str1, const gchar *str2); +typedef gint (*StringNCmpFunc)(const gchar *str1, const gchar *str2, gsize n); + +template <StringCmpFunc StringCmp> +class RBEntryStringT : public RBTree<RBEntryStringT<StringCmp>>::RBEntry { +public: + /* + * It is convenient to be able to access the string + * key with various attribute names. + */ + union { + gchar *key; + gchar *name; + }; + + RBEntryStringT(gchar *_key) : key(_key) {} + + virtual ~RBEntryStringT() {} + + inline gint + compare(RBEntryStringT &other) + { + return StringCmp(key, other.key); + } +}; + +template <StringCmpFunc StringCmp, StringNCmpFunc StringNCmp> +class RBTreeStringT : public RBTree<RBEntryStringT<StringCmp>> { +public: + typedef RBEntryStringT<StringCmp> RBEntryString; + + class RBEntryOwnString : public RBEntryString { + public: + RBEntryOwnString(const gchar *key = NULL) + : RBEntryString(key ? g_strdup(key) : NULL) {} + + ~RBEntryOwnString() + { + g_free(RBEntryString::key); + } + }; + + inline RBEntryString * + find(const gchar *str) + { + RBEntryString entry((gchar *)str); + return RBTree<RBEntryString>::find(&entry); + } + inline RBEntryString * + operator [](const gchar *name) + { + return find(name); + } + + inline RBEntryString * + nfind(const gchar *str) + { + RBEntryString entry((gchar *)str); + return RBTree<RBEntryString>::nfind(&entry); + } +}; + +typedef RBTreeStringT<strcmp, strncmp> RBTreeString; +typedef RBTreeStringT<g_ascii_strcasecmp, g_ascii_strncasecmp> RBTreeStringCase; + +/* + * Only these two instantiations of RBTreeStringT are ever used, + * so it is more efficient to explicitly instantiate them. + * NOTE: The insane rules of C++ prevent using the typedefs here... + */ +extern template class RBTreeStringT<strcmp, strncmp>; +extern template class RBTreeStringT<g_ascii_strcasecmp, g_ascii_strncasecmp>; + } /* namespace SciTECO */ #endif |