[gimp] Optimized append to make it an O(n) operation (See Sourceforge bug #3400290) From a patch by Doug C

[Kevin Cozens <kcozens src gnome org>]

commit 23978ecec326dff969a6e889a16dff3d3cb0b224
Author: Kevin Cozens <kcozens svn gnome org>
Date:   Fri Sep 23 19:04:32 2011 -0400

    Optimized append to make it an O(n) operation  (See Sourceforge bug #3400290)
    From a patch by Doug Currie. Also some minor whitespace changes.

 plug-ins/script-fu/tinyscheme/scheme.c |   65 +++++++++++++++++--------------
 1 files changed, 36 insertions(+), 29 deletions(-)
---
diff --git a/plug-ins/script-fu/tinyscheme/scheme.c b/plug-ins/script-fu/tinyscheme/scheme.c
index 37d0417..64c4ed4 100644
--- a/plug-ins/script-fu/tinyscheme/scheme.c
+++ b/plug-ins/script-fu/tinyscheme/scheme.c
@@ -416,7 +416,7 @@ static pointer mk_closure(scheme *sc, pointer c, pointer e);
 static pointer mk_continuation(scheme *sc, pointer d);
 static pointer reverse(scheme *sc, pointer a);
 static pointer reverse_in_place(scheme *sc, pointer term, pointer list);
-static pointer append(scheme *sc, pointer a, pointer b);
+static pointer revappend(scheme *sc, pointer a, pointer b);
 int list_length(scheme *sc, pointer a);
 int eqv(pointer a, pointer b);
 
@@ -2268,19 +2268,20 @@ static pointer reverse_in_place(scheme *sc, pointer term, pointer list) {
 }
 
 /* append list -- produce new list */
-static pointer append(scheme *sc, pointer a, pointer b) {
-     pointer p = b, q;
-
-     if (a != sc->NIL) {
-          a = reverse(sc, a);
-          while (a != sc->NIL) {
-               q = cdr(a);
-               cdr(a) = p;
-               p = a;
-               a = q;
-          }
-     }
-     return (p);
+static pointer revappend(scheme *sc, pointer a, pointer b) {
+    pointer result = a;
+    pointer p = b;
+
+    while (is_pair(p)) {
+        result = cons(sc, car(p), result);
+        p = cdr(p);
+    }
+
+    if (p == sc->NIL) {
+        return result;
+    }
+
+    return sc->F;   /* signal an error */
 }
 
 /* equivalence of atoms */
@@ -4003,24 +4004,30 @@ static pointer opexe_4(scheme *sc, enum scheme_opcodes op) {
                }
           }
 
-     case OP_REVERSE:    /* reverse */
+     case OP_REVERSE:   /* reverse */
           s_return(sc,reverse(sc, car(sc->args)));
 
      case OP_LIST_STAR: /* list* */
-       s_return(sc,list_star(sc,sc->args));
+          s_return(sc,list_star(sc,sc->args));
 
-     case OP_APPEND:     /* append */
-          if(sc->args==sc->NIL) {
-               s_return(sc,sc->NIL);
+     case OP_APPEND:    /* append */
+          x = sc->NIL;
+          y = sc->args;
+          if (y == x) {
+              s_return(sc, x);
           }
-          x=car(sc->args);
-          if(cdr(sc->args)==sc->NIL) {
-            s_return(sc,x);
-          }
-          for (y = cdr(sc->args); y != sc->NIL; y = cdr(y)) {
-               x=append(sc,x,car(y));
+
+          /* cdr() in the while condition is not a typo. If car() */
+          /* is used (append '() 'a) will return the wrong result.*/
+          while (cdr(y) != sc->NIL) {
+              x = revappend(sc, x, car(y));
+              y = cdr(y);
+              if (x == sc->F) {
+                  Error_0(sc, "non-list argument to append");
+              }
           }
-          s_return(sc,x);
+
+          s_return(sc, reverse_in_place(sc, car(y), x));
 
 #if USE_PLIST
      case OP_PUT:        /* put */
@@ -4255,8 +4262,8 @@ static pointer opexe_5(scheme *sc, enum scheme_opcodes op) {
      case OP_RDSEXPR:
           switch (sc->tok) {
           case TOK_EOF:
-            s_return(sc,sc->EOF_OBJ);
-            /* NOTREACHED */
+               s_return(sc,sc->EOF_OBJ);
+          /* NOTREACHED */
 /*
  * Commented out because we now skip comments in the scanner
  *
@@ -4394,7 +4401,7 @@ static pointer opexe_5(scheme *sc, enum scheme_opcodes op) {
           s_return(sc,cons(sc, sc->QQUOTE, cons(sc, sc->value, sc->NIL)));
 
      case OP_RDQQUOTEVEC:
-       s_return(sc,cons(sc, mk_symbol(sc,"apply"),
+          s_return(sc,cons(sc, mk_symbol(sc,"apply"),
                         cons(sc, mk_symbol(sc,"vector"),
                              cons(sc,cons(sc, sc->QQUOTE,
                                   cons(sc,sc->value,sc->NIL)),