bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: strstr speedup


From: Bruno Haible
Subject: Re: strstr speedup
Date: Sat, 12 Jan 2008 01:06:42 +0100
User-agent: KMail/1.5.4

Eric Blake wrote:
> --- a/doc/functions/strstr.texi
> +++ b/doc/functions/strstr.texi
> @@ -4,10 +4,14 @@
>  
>  POSIX specification: @url{http://www.opengroup.org/susv3xsh/strstr.html}
>  
> -Gnulib module: ---
> +Gnulib module: strstr
>  
>  Portability problems fixed by Gnulib:
> address@hidden
> address@hidden
> +This function has quadratic instead of linear complexity on some
> +platforms:
> +glibc <= 2.6.1, cygwin 1.5.x, OpenBSD 4.0, Solaris 9, mingw
> address@hidden itemize
>  
>  Portability problems not fixed by Gnulib:

After testing it on more platforms, I can confirm the quadratic complexity
of strstr and memmem on all the tested platforms. I add a note to the doc:


2008-01-10  Bruno Haible  <address@hidden>

        * doc/functions/memmem.texi: Add more precisions about platforms.
        * doc/functions/strstr.texi: Likewise.

*** doc/functions/memmem.texi.orig      2008-01-12 01:03:04.000000000 +0100
--- doc/functions/memmem.texi   2008-01-12 00:58:14.000000000 +0100
***************
*** 11,17 ****
  @itemize
  @item
  This function is missing on some platforms:
! Mingw, OpenBSD 4.0
  
  @item
  This function has reversed arguments on some older platforms:
--- 11,17 ----
  @itemize
  @item
  This function is missing on some platforms:
! MacOS X 10.3, FreeBSD 5.2.1, OpenBSD 4.0, AIX 4.3.2, HP-UX 11, IRIX 6.5, 
OSF/1 5.1, Solaris 10, mingw, Interix 3.5, BeOS.
  
  @item
  This function has reversed arguments on some older platforms:
***************
*** 23,34 ****
  @item
  This function returns incorrect values in some cases, such as when
  given an empty needle:
! glibc <= 2.0, cygwin 1.5.x
  
  @item
! This function has quadratic instead of linear complexity on some
  platforms:
! glibc <= 2.6.1, cygwin 1.5.x
  @end itemize
  
  Portability problems not fixed by Gnulib:
--- 23,34 ----
  @item
  This function returns incorrect values in some cases, such as when
  given an empty needle:
! glibc <= 2.0, Cygwin 1.5.x.
  
  @item
! This function has quadratic instead of linear worst-case complexity on some
  platforms:
! glibc 2.6.1, FreeBSD 6.2, NetBSD 3.0, AIX 5.1, Cygwin 1.5.x.
  @end itemize
  
  Portability problems not fixed by Gnulib:
*** doc/functions/strstr.texi.orig      2008-01-12 01:03:04.000000000 +0100
--- doc/functions/strstr.texi   2008-01-12 00:50:35.000000000 +0100
***************
*** 9,17 ****
  Portability problems fixed by Gnulib:
  @itemize
  @item
! This function has quadratic instead of linear complexity on some
  platforms:
! glibc <= 2.6.1, cygwin 1.5.x, OpenBSD 4.0, Solaris 9, mingw
  @end itemize
  
  Portability problems not fixed by Gnulib:
--- 9,17 ----
  Portability problems fixed by Gnulib:
  @itemize
  @item
! This function has quadratic instead of linear worst-case complexity on some
  platforms:
! glibc 2.6.1, MacOS X 10.3, FreeBSD 6.2, NetBSD 3.0, OpenBSD 4.0, AIX 5.1, 
HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin 1.5.x, mingw.
  @end itemize
  
  Portability problems not fixed by Gnulib:





reply via email to

[Prev in Thread] Current Thread [Next in Thread]