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

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 */