Patch to make word_list_split O(n) instead of O(n^2)

[Michal Marek]

Configuration Information [Automatically generated, do not change]:
Machine: i686
OS: linux-gnu
Compiler: gcc
Compilation CFLAGS:  -DPROGRAM='bash' -DCONF_HOSTTYPE='i686' 
-DCONF_OSTYPE='linux-gnu' -DCONF_MACHTYPE='i686-pc-linux-gnu' 
-DCONF_VENDOR='pc' -DLOCALEDIR='/usr/local/share/locale' -DPACKAGE='bash' 
-DSHELL -DHAVE_CONFIG_H  -I.  -I. -I./include -I./lib   -g -O2
uname output: Linux klokan 2.6.10-1.770_FC3 #1 Thu Feb 24 14:00:06 EST 2005 
i686 i686 i386 GNU/Linux
Machine Type: i686-pc-linux-gnu

Bash Version: 3.0
Patch Level: 0
Release Status: release

Description:
        word_list_split () from subst.c (and probably other functions)
        superfluously takes O(n^2) time, since it operates on a single
        linked list in a inefficient way.  Namely, it calls an O(n)
        function list_append () from list.c for each word added. This
        doesn't cause problems for most scripts etc., since the command
        line is usually short, but it's for example annoying when using
        certain functions of bash completion <http://www.caliban.org/bash/>.
        

Repeat-By:
        a) install bash completion and type
        
             $ man <tab>
        
           It will take a while until the "Display all X possibilities"
           prompt is displayed.
        
        b)
        #!/bin/bash
        a=( `perl -e "print \"abcdefghijkl \"x$1"` )
        echo "${a[@]}" >/dev/null  # this is slow

        running time ./test 5000; time ./test 10000; time ./test 15000;
        etc.  shows that the time is +- quadratic.

Fix:

list.c externs.h
        - new function list_tail(GENERIC_LIST *), returning list tail or 0

subst.c
        - Make word_list_split O(n) instead of O(n^2). It was slowing down
          bash completion <http://www.caliban.org/bash/> for instance.
          From Michal Marek <michal.marek@matfyz.cz>

diff -rc bash-3.0/externs.h bash-3.0.new/externs.h
*** bash-3.0/externs.h  Tue Apr 13 05:30:08 2004
--- bash-3.0.new/externs.h      Thu Apr 28 23:09:46 2005
***************
*** 124,129 ****
--- 124,130 ----
  extern int list_length ();
  extern GENERIC_LIST *list_append ();
  extern GENERIC_LIST *list_remove ();
+ extern GENERIC_LIST *list_tail ();
  
  /* Declarations for functions defined in stringlib.c */
  extern int find_string_in_alist __P((char *, STRING_INT_ALIST *, int));
diff -rc bash-3.0/list.c bash-3.0.new/list.c
*** bash-3.0/list.c     Mon Mar 18 19:13:54 2002
--- bash-3.0.new/list.c Thu Apr 28 23:14:10 2005
***************
*** 103,108 ****
--- 103,123 ----
    return (head);
  }
  
+ /* When appending multiple times, make the O(n) walk only once.
+  * Ideally, we should have some more efficient structure, storing tail and
+  * length at least...
+  */
+ GENERIC_LIST *
+ list_tail (head)
+      GENERIC_LIST *head;
+ {
+   if (!head)
+     return NULL;
+   for (; head->next; head = head->next)
+     ;
+   return head;
+ }
+ 
  #ifdef INCLUDE_UNUSED
  /* Delete the element of LIST which satisfies the predicate function COMPARER.
     Returns the element that was deleted, so you can dispose of it, or -1 if
diff -rc bash-3.0/subst.c bash-3.0.new/subst.c
*** bash-3.0/subst.c    Sun Jul  4 19:56:13 2004
--- bash-3.0.new/subst.c        Thu Apr 28 23:56:47 2005
***************
*** 6834,6845 ****
  word_list_split (list)
       WORD_LIST *list;
  {
!   WORD_LIST *result, *t, *tresult;
  
!   for (t = list, result = (WORD_LIST *)NULL; t; t = t->next)
      {
        tresult = word_split (t->word, ifs_value);
!       result = (WORD_LIST *) list_append (result, tresult);
      }
    return (result);
  }
--- 6834,6848 ----
  word_list_split (list)
       WORD_LIST *list;
  {
!   WORD_LIST *result, *t, *tresult, *tail;
  
!   for (t = list, tail = result = (WORD_LIST *)NULL; t; t = t->next)
      {
        tresult = word_split (t->word, ifs_value);
!       if (!result)
!         result = tresult;
!       list_append(tail, tresult);
!       tail = (WORD_LIST *)list_tail(tresult);
      }
    return (result);
  }