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.

1 files changed, 28 insertions, 16 deletions

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.