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

diff --git a/TODO b/TODO
index e37de87..2585efb 100644
--- a/TODO
+++ b/TODO
@@ -25,6 +25,7 @@ Known Bugs:
    current macro invocation frame and guarantee ^R == 10 at the beginning
    of macros.
  * Null-byte in strings not always handled transparently
+   (SciTECO is not 8-bit clean.)
  * Saving another user's file will only preserve the user when run as root.
    Generally, it is hard to ensure that a) save point files can be created
    and b) the file mode and ownership of re-created files can be preserved.
@@ -42,6 +43,15 @@ Known Bugs:
    throwing exceptions is unsafe from C-linkage callbacks.
    We should abandon the custom allocators and rely on
    SciTECO's memory limiting.
+   All C++ allocations could be based on g_malloc/g_slice so we
+   assert on OOM. Instead we improve memory limiting using platform-specific
+   API like malloc_info(). Since the remaining platforms are only obscure
+   ones, the overloaded C++ operators should be sufficient to count the
+   bulk of memory used. Since the necessary sized delete operators are
+   only available beginning with C++14, there'd have to be yet another
+   fallback that stores the memory chunk size at the beginning of the
+   heap object.
+   The UndoToken::get_size() workaround can be removed.
  * It is still possible to crash SciTECO using recursive functions,
    since they map to the C++ program's call stack.
    It is perhaps best to use another ValueStack as a stack of
@@ -52,6 +62,9 @@ Known Bugs:
    savepoint restoration.
    On Windows we could work around this using
    MoveFileEx(file, NULL, MOVEFILE_DELAY_UNTIL_REBOOT)
+   This should only happen on abnormal program termination
+   since SciTECO's destructors should clean up everything
+   (test whether this holds true for assertions...).
  * Clipboard registers are prone to race conditions if the
    contents change between get_size() and get_string() calls.
    Also it's a common idiom to query a string and its size,
@@ -59,6 +72,8 @@ Known Bugs:
  * Setting window title is broken on ncurses/XTerm.
    Perhaps do some XTerm magic here. We can also restore
    window titles on exit using XTerm.
+ * Glib (error) messages are not integrated with SciTECO's
+   logging system.
 
 Features:
  * Auto-indention could be implemented via context-sensitive
@@ -128,10 +143,12 @@ Features:
  * Support loading from stdin (--stdin) and writing to
    the current buffer to stdout on exit (--stdout).
    This will make it easy to write command line filters,
-   This also means we need something like --ed to set the
-   ED flags before everything else and --quiet.
+   We will need flags like --8-bit-clean and --quiet with
+   single-letter forms to make it possible to write hash-bang
+   lines like #!...sciteco-wrapper -q8iom
    Command line arguments should then also be handled
-   differently.
+   differently, passing them in an array or single string
+   register, so they no longer affect the unnamed buffer.
  * For third-party macro authors, it is useful to know
    the standard library path (e.g. to install new lexers).
    There could be a --print-path option, or with the --quiet
@@ -149,18 +166,8 @@ Features:
    * EF with buffer id
    * ER command: read file into current buffer at dot
    * nEW to save a buffer by id
- * use CRTP for RBTrees to avoid unnecessary virtual method calls.
-   This means that like the original BSD headers, implementations
-   of the rbtree ops will be generated for every usage.
-   Since currently, only QRegister tables and goto tables are
-   RBTrees, the binary size overhead should be minimal.
-   There's another possible optimization: RBTrees define an entry
-   field for storing node color. This can be avoided on most
-   platforms where G_MEM_ALIGN > 1 by encoding the color in the
-   lowest bit of one of the pointers.
-   The parent pointer is not required for RBTrees in general,
-   but we do use the PREV/NEXT ops to iterate prefixes which requires
-   the parent pointer to be maintained.
+   * ^A and stdio in general
+ * autocompletion of long Q-Reg names
  * Buffer ids should be "circular", i.e. interpreted modulo the
    number of buffers in the ring. This allows "%*" to wrap at the
    end of the buffer list.
@@ -176,17 +183,16 @@ Features:
  * Command to free Q-Register (remove from table).
    e.g. FQ (free Q). :FQ could free by QRegister prefix name for
    the common use case of Q-Register subtables and lists.
- * autocompletion of long Q-Reg names
  * TECO syntax highlighting
  * multiline commandline
    * perhaps use Scintilla view as mini buffer.
      This means patching Scintilla, so it does not break lines
      on new line characters.
    * A Scintilla view will allow syntax highlighting
- * command line could highlight dead branches (e.g. gray them out)
  * improve GTK interface
    * proper command-line widget (best would be a Scintilla view, s.a.)
    * speed improvements
+ * command line could highlight dead branches (e.g. gray them out)
  * backup files, or even better Journal files:
    could write a Macro file for each modified file containing
    only basic commands (no loops etc.). it is removed when the file is
@@ -222,6 +228,13 @@ Features:
    Each Scintilla view could then be associated with at most
    one curses screen.
    GTK+ would simply manage a list of windows.
+ * Error handling in SciTECO macros: Allow throwing errors with
+   e.g. [n]EE<description>$ where n is an error code, defaulting
+   to 0 and description is the error string - there could be code-specific
+   defaults. All internal error classes use defined codes.
+   Errors could be catched using a structured try-catch-like construct
+   or by defining an error handling label.
+   Macros may retrieve the code and string of the last error.
 
 Optimizations:
  * Add G_UNLIKELY to all error throws.
@@ -243,9 +256,10 @@ Optimizations:
    C++11 already allows sized allocators in a class.
    Testing shows that this does not speed up things on Linux
    and prevents freeing memory on command line termination
-   (it would be glibc-specific).
-   We should test whether it brings any benefit on Windows
-   and implement with a build-time option.
+   (it would be glibc-specific), so it should probably depend on
+   HAVE_MALLOC_TRIM. On all other platforms, it could be assumed
+   to be beneficial or at least not hurt.
+   Best is to test its effect on MSVCRT.
  * String::append() could be optimized by ORing a padding
    into the realloc() size (e.g. 0xFF).
    However, this has not proven effective on Linux/glibc
@@ -253,7 +267,9 @@ Optimizations:
    roughly the same size.
    Should be tested on Windows, though.
  * Scintilla: SETDOCPOINTER resets representations, so we
-   have to set SciTECO representations up again often.
+   have to set SciTECO representations up again often when
+   working with Q-Registers. Has been benchmarked to be a
+   major slow-down.
    This should be patched in Scintilla.
  * commonly used (special) Q-Registers could be cached,
    saving the q-reg table lookup
@@ -272,7 +288,20 @@ Optimizations:
    use a custom error reporting system similar to GError.
    This makes error handling and forwarding explicit as in
    plain C code. RTTI can be used to discern different
-   exception types.
+   exception types. By adding an error code to the error object
+   (which we will need anyway for supporting error handling in SciTECO
+   macros), we may even avoid RTTI.
+ * The position can be eliminated from UndoTokens by
+   rewriting the UndoStack into a stack of UndoToken lists.
+   Should be a significant memory reduction in interactive mode.
+ * RBTrees define an entry field for storing node color.
+   This can be avoided on most
+   platforms where G_MEM_ALIGN > 1 by encoding the color in the
+   lowest bit of one of the pointers.
+   The parent pointer is not required for RBTrees in general,
+   but we do use the PREV/NEXT ops to iterate prefixes which requires
+   the parent pointer to be maintained.
+ * Add a configure-switch for LTO (--enable-lto).
 
 Documentation:
  * Code docs (Doxygen). It's slowly getting better...