undo stack reorganized into a stack of undo token lists

 * in a flat list of undo tokens, we need to store
   the program counter (ie. command line position)
   that the undo token corresponds to.
   Since in general there is more than one undo token per
   input character, this stored PCs redundantly.
 * For input characters with no undo tokens
   (only applies to NOPs like space in the command line
   macro), this needs one more pointer than before.
 * In case of 1 undo token per input character,
   the new implementation uses approx. the same memory.
 * In the most common case of more than one undo token
   per input character, this saves at least 4 bytes per
   undo token.
 * In large macros and long loops the effect is especially
   pronounced. E.g. 500000<%A> will use 8MB less memory
   with the new implementation.

3 files changed, 64 insertions, 41 deletions

diff --git a/TODO b/TODO
index 9748f6f..4f93a5e 100644
--- a/TODO
+++ b/TODO
@@ -84,6 +84,8 @@ Known Bugs:
    Also, auto-completions within string-building constructs
    (except Q-Reg specs) should generally be disabled since
    the result will be unpredictable.
+ * Shutdown seems to hang after generating lots of undo tokens:
+   500000<%A>EX$$
 
 Features:
  * Auto-indention could be implemented via context-sensitive
@@ -289,9 +291,6 @@ Optimizations:
  * RTTI could be disabled (-fno-rtti). It's only still required
    because of StdError() for handling arbitrary C++ exceptions.
    This is probably not required.
- * 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
diff --git a/src/undo.cpp b/src/undo.cpp
index 584883d..468c61a 100644
--- a/src/undo.cpp
+++ b/src/undo.cpp
@@ -50,43 +50,55 @@ UndoStack::push(UndoToken *token)
 #ifdef DEBUG
 	g_printf("UNDO PUSH %p\n", token);
 #endif
-	token->pc = cmdline.pc;
-	SLIST_INSERT_HEAD(&head, token, tokens);
+
+	/*
+	 * There can very well be 0 undo tokens
+	 * per input character (e.g. NOPs like space).
+	 */
+	while (heads->len <= cmdline.pc)
+		g_ptr_array_add(heads, NULL);
+	g_assert(heads->len == cmdline.pc+1);
+
+	SLIST_NEXT(token, tokens) =
+		(UndoToken *)g_ptr_array_index(heads, heads->len-1);
+	g_ptr_array_index(heads, heads->len-1) = token;
 }
 
 void
 UndoStack::pop(gint pc)
 {
-	while (!SLIST_EMPTY(&head) && SLIST_FIRST(&head)->pc >= pc) {
-		UndoToken *top = SLIST_FIRST(&head);
+	while ((gint)heads->len > pc) {
+		UndoToken *top =
+			(UndoToken *)g_ptr_array_remove_index(heads, heads->len-1);
+
+		while (top) {
+			UndoToken *next = SLIST_NEXT(top, tokens);
+
 #ifdef DEBUG
-		g_printf("UNDO POP %p\n", top);
-		fflush(stdout);
+			g_printf("UNDO POP %p\n", top);
+			fflush(stdout);
 #endif
-		top->run();
+			top->run();
 
-		SLIST_REMOVE_HEAD(&head, tokens);
-		delete top;
+			delete top;
+			top = next;
+		}
 	}
 }
 
 void
 UndoStack::clear(void)
 {
-	UndoToken *cur;
-
-	while ((cur = SLIST_FIRST(&head))) {
-		SLIST_REMOVE_HEAD(&head, tokens);
-		delete cur;
+	while (heads->len) {
+		UndoToken *top =
+			(UndoToken *)g_ptr_array_remove_index(heads, heads->len-1);
+
+		while (top) {
+			UndoToken *next = SLIST_NEXT(top, tokens);
+			delete top;
+			top = next;
+		}
 	}
 }
 
-UndoStack::~UndoStack()
-{
-	UndoToken *token, *next;
-
-	SLIST_FOREACH_SAFE(token, &head, tokens, next)
-		delete token;
-}
-
 } /* namespace SciTECO */
diff --git a/src/undo.h b/src/undo.h
index 35991ff..93f68e5 100644
--- a/src/undo.h
+++ b/src/undo.h
@@ -33,22 +33,18 @@
 
 namespace SciTECO {
 
+/**
+ * Undo tokens are generated to revert any
+ * changes to the editor state, ie. they
+ * define an action to take upon rubout.
+ *
+ * Undo tokens are organized into an undo
+ * stack.
+ */
 class UndoToken : public Object {
 public:
 	SLIST_ENTRY(UndoToken) tokens;
 
-	/**
-	 * Command-line character position (program counter)
-	 * corresponding to this token.
-	 *
-	 * @todo This wastes memory in macro calls and loops
-	 *       because all undo tokens will have the same
-	 *       value. It may be better to redesign the undo
-	 *       stack data structure - as a list/array pointing
-	 *       to undo stacks per character.
-	 */
-	gint pc;
-
 	virtual ~UndoToken() {}
 
 	virtual void run(void) = 0;
@@ -123,18 +119,34 @@ public:
 };
 
 extern class UndoStack : public Object {
-	SLIST_HEAD(Head, UndoToken) head;
+	/**
+	 * Stack of UndoToken lists.
+	 *
+	 * Each stack element represents
+	 * a command line character (the UndoTokens
+	 * generated by that character), so it's OK
+	 * to use a data structure that may need
+	 * reallocation but is space efficient.
+	 * This data structure allows us to omit the
+	 * command line program counter from the UndoTokens
+	 * but wastes a few bytes for input characters
+	 * that produce no UndoToken (e.g. NOPs like space).
+	 */
+	GPtrArray *heads;
 
 	void push(UndoToken *token);
 
 public:
 	bool enabled;
 
-	UndoStack(bool _enabled = false) : enabled(_enabled)
+	UndoStack(bool _enabled = false)
+	         : heads(g_ptr_array_new()), enabled(_enabled) {}
+	~UndoStack()
 	{
-		SLIST_INIT(&head);
+		clear();
+		g_ptr_array_free(heads, TRUE);
 	}
-	~UndoStack();
+
 
 	/**
 	 * Allocate and push undo token.