Re: [PATCH v2] compat: Add simplified merge sort implementation from glibc

From: Brian Downing <bdowning-ou/tddhfglreowh0uzbu5w@public.gmane.org>
Date: Feb 6, 2008, 02:47 UTC
Message-ID: <20080206024732.GR26392@lavos.net>
In-Reply-To: <alpine.LSU.1.00.0802052220500.8543-OGWIkrnhIhzN0uC3ymp8PA@public.gmane.org>

On Tue, Feb 05, 2008 at 10:21:58PM +0000, Johannes Schindelin wrote:

Show 13 quoted lines

> On Tue, 5 Feb 2008, Brian Downing wrote:
> > diff --git a/compat/qsort.c b/compat/qsort.c
> > new file mode 100644
> > index 0000000..8663889
> > --- /dev/null
> > +++ b/compat/qsort.c
> > @@ -0,0 +1,60 @@
> > +#include "../git-compat-util.h"
> > +
> > +/* This merge sort implementation is simplified from glibc's. */
> > +static void msort_with_tmp(void *b, size_t n, size_t s,
> 
> Didn't you forget to include the original copyright, as well as yours?

I (perhaps naïvely) assumed the "from glibc" would be enough. If not, the original is:

/* An alternative to qsort, with an identical interface.
   This file is part of the GNU C Library.
   Copyright (C) 1992,95-97,99,2000,01,02,04 Free Software Foundation, Inc.
   Written by Mike Haertel, September 1988.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

(That was from glibc-2.3.6/stdlib/msort.c. I'm not sure of the exact version I referenced for the implementation, but it was a lot closer to 2.3.6 than the current 2.7.)

As far as my copyleft, I was just planning on it being under Git's blanket copyleft. I really only pruned and reformatted code; there's really nothing substantial to claim ownership of.

> BTW if these 60 lines have code that is really faster than Microsoft's 
> implementation of a sort, it is really fascinating to me.

Well, it's faster for us, but I bet our (usually mostly-sorted) tree input is just better for a sort like a merge sort rather than a quicksort.

-bcd