From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:55687) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YtH2F-0000zC-RJ for qemu-devel@nongnu.org; Fri, 15 May 2015 10:56:25 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YtH29-0000KQ-DA for qemu-devel@nongnu.org; Fri, 15 May 2015 10:56:23 -0400 Received: from mx1.redhat.com ([209.132.183.28]:36865) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YtH29-0000KG-5B for qemu-devel@nongnu.org; Fri, 15 May 2015 10:56:17 -0400 Message-ID: <5556090E.7070408@redhat.com> Date: Fri, 15 May 2015 08:56:14 -0600 From: Eric Blake MIME-Version: 1.0 References: <1431692725-27656-1-git-send-email-hw.claudio@gmail.com> <1431692725-27656-2-git-send-email-hw.claudio@gmail.com> <5555FB55.5070909@huawei.com> <5555FEBE.5040007@redhat.com> In-Reply-To: <5555FEBE.5040007@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="GqtNGBo0InalO0RL3kutIIPS17G1Ev0al" Subject: Re: [Qemu-devel] [RFC v5 1/2] util: add memmem replacement function List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Paolo Bonzini , Claudio Fontana , hw.claudio@gmail.com, Luiz Capitulino Cc: Peter Maydell , Gonglei , qemu-devel@nongnu.org, karl@freefriends.org This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --GqtNGBo0InalO0RL3kutIIPS17G1Ev0al Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 05/15/2015 08:12 AM, Paolo Bonzini wrote: >=20 >=20 > On 15/05/2015 15:57, Claudio Fontana wrote: >> The header here mentions GPLv2+, but the module data for memmem in gnu= lib mentions LGPLv2+. >> >> Very confusing. >> >> The COPYING file in gnulib mentions: >> >> "The files in here are mostly copyright (C) Free Software Foundation, = and >> are under assorted licenses. Mostly, but not entirely, GPL. >> >> Many modules are provided dual-license, either GPL or LGPL at your >> option. The headers of files in the lib directory (e.g., lib/error.c)= >> state GPL for convenience, since the bulk of current gnulib users are >> GPL'd programs. But the files in the modules directory (e.g., >> modules/error) state the true license of each file, [...] >> " >> >> So if one would want to include the gnulib code without using the gnul= ib esoteric modules mechanisms, what should one do? >=20 > Change it manually, I guess. It's still possible to use gnulib-tool for a one-time export of the modules in question into a temporary project with correct licensing headers written by gnulib-tool, then copy from that temporary project into qemu. It's probably just as fast to do it by hand, but using gnulib-tool in the procedure (and documenting in the commit message what that procedure was, to make it easier for the next guy to copy) is probably friendlier. I'm not sure off-hand what the command line would be, but could help if that's the approach we want to take. Or, since gnulib's memmem is (mostly) sync'd with glibc's memmem (or at least was in sync at one point), and glibc is under LGPLv2+, why not copy straight from glibc instead of from gnulib, and then you don't have to modify any headers? (I haven't looked lately, but glibc may have optimizations that should be backported into gnulib) Historical note: gnulib had this particular implementation of memmem first, as written by me under a dual license; then I got glibc to incorporate it under just LGPLv2+; then since the initial implementation, glibc has been better optimized by others. If you really want to, you could observe that since I released the same original memmem implementation under multiple licenses at the time I first wrote it, you could therefore find and copy an older version under an even looser license in the newlib project (but without glibc's enhancements, as I can't dual-license someone else's follow-up work): https://sourceware.org/git/gitweb.cgi?p=3Dnewlib-cygwin.git;a=3Dblob;f=3D= newlib/libc/string/memmem.c;h=3D25704e46;hb=3DHEAD Or back to the original question - why are we worrying about the O(n) memmem implementation when the naive O(n^2) is MUCH shorter and easier to understand, and where the scaling penalty is only apparent on really long corner case strings? Is our use of memmem going to hit the corner cases where scaling matters? [Personal note: I'm still tickled pink every time I see yet another project adopt my O(n) code - I didn't come up with the algorithm, but merely scraped it from public research, and was shocked to note how many libc still had O(n^2) code at the time. But it is still gratifying to see that my implementation is getting such wide adoption] --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --GqtNGBo0InalO0RL3kutIIPS17G1Ev0al Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJVVgkOAAoJEKeha0olJ0Nq9RMH/3vfJ+a4luCi9foHbl6hvYk/ jIyWwpx2Sj3lVO7m/09j56D9i1ECGjiUmzNE4Av601TLir6T31rXavqLn3GoEi22 K6LXdUEN6a3FINAWan7OFoXXmMG8tS7lfqZRN0Eo2jt9y4rvivCkLvXvpLb0jIlQ CwFCG2qqmBlZALg1rV1AAvdcl58BHFDRNvlq53bL4qFFdg6aiHfEZcMUWtCxqioW oJJdvxq27llKW2EGG0lO6LVEtdKao0sweExccKfdz3Y0BfiZxWbYIoB8xeJEwV7+ sgngNX6pNuVLo3YbmsJKuen+B6Xxy6cmVvIB8E7PGFwSHshKc90xdrncY9zXKVg= =rMNG -----END PGP SIGNATURE----- --GqtNGBo0InalO0RL3kutIIPS17G1Ev0al--