Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 27 Oct 2020 13:08:17 -0400
From: Rich Felker <dalias@...c.org>
To: Mark Wielaard <mark@...mp.org>
Cc: Florian Weimer <fweimer@...hat.com>, elfutils-devel@...rceware.org,
	musl@...ts.openwall.com,
	√Črico Rolim <erico.erc@...il.com>,
	Max Rees <maxcrees@...com>
Subject: Re: Re: [QUESTION] Which fnmatch() functionality does
 elfutils depend on?

On Tue, Oct 27, 2020 at 04:04:44PM +0100, Mark Wielaard wrote:
> On Tue, 2020-10-27 at 10:19 +0100, Florian Weimer via Elfutils-devel
> wrote:
> > * Rich Felker:
> > 
> > > As I stated in my other reply, I'm opposed to that because it does not
> > > admit implementation with the same (very desirable) big-O properties,
> > > and the "extmatch" syntax is not widely known or widely used.
> > 
> > The syntax comes from ksh and is used in shell scripts.  (bash requires
> > the extglob option to enable it, which makes it easy to search for
> > instances.)
> 
> Right, it is also adopted by zsh and some other shells. The big-O
> properties don't really matter in this case because fnmatch is used on
> small input strings like file names (or in this case section names).

They do because they're also in space, unless you want
exponential-time which is huge even on small inputs, and greater than
O(1) space requirement means the interface can't satisfy its contract
to return a conclusive result for valid inputs.

Rich

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.