X-Recipient: archive-cygwin AT delorie DOT com
X-Spam-Check-By: sourceware.org
To: cygwin AT cygwin DOT com
From: Eric Blake <ebb9 AT byu DOT net>
Subject:  memmem issues
Date: Wed, 19 Dec 2007 21:22:17 +0000 (UTC)
Lines: 23
Message-ID:  <loom.20071219T210928-910@post.gmane.org>
Mime-Version:  1.0
Content-Type:  text/plain; charset=us-ascii
Content-Transfer-Encoding:  7bit
User-Agent: Loom/3.14 (http://gmane.org/)
X-IsSubscribed: yes
Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
List-Id: <cygwin.cygwin.com>
List-Subscribe: <mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive: <http://sourceware.org/ml/cygwin/>
List-Post: <mailto:cygwin AT cygwin DOT com>
List-Help: <mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Delivered-To: mailing list cygwin AT cygwin DOT com

memmem isn't standardized, but even so, it has some bugs based on comparison 
with strstr.

memmem(haystack,len,"",0) should return haystack, not NULL.  This should be an 
easy one-line fix.

memmem currently has O(m*n) worst-case complexity (quadratic, when haystack and 
needle are both long).  But with the Knuth-Morris-Pratt algorithm and a memory 
allocation of size n, this could be trimmed to O(m+n) (linear).  Gnulib 
provides an example of KMP that is only invoked after several unsuccessful 
iterations of the naive algorithm, in order to avoid memory allocations, and 
which falls back on the naive algorithm if memory allocation fails; however, 
the gnulib example is LGPL, so it can't be lifted verbatim into cygwin.  
Newlib's strstr could use the same algorithmic speedup.  Since I don't have 
copyright on file yet, and at any rate have been potentially tainted by reading 
the gnulib implementation, I won't be contributing the patch; so I'm less 
worried about whether this improvement ever gets added to cygwin.  But I can 
always wish that someone else could be inspired by this description to write 
the improvement from scratch.

-- 
Eric Blake



--
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple
Problem reports:       http://cygwin.com/problems.html
Documentation:         http://cygwin.com/docs.html
FAQ:                   http://cygwin.com/faq/