From owner-freebsd-current@freebsd.org  Mon Apr 18 12:17:31 2016
Return-Path: <owner-freebsd-current@freebsd.org>
Delivered-To: freebsd-current@mailman.ysv.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org
 [IPv6:2001:1900:2254:206a::19:1])
 by mailman.ysv.freebsd.org (Postfix) with ESMTP id C0F74B11899
 for <freebsd-current@mailman.ysv.freebsd.org>;
 Mon, 18 Apr 2016 12:17:31 +0000 (UTC)
 (envelope-from afiskon@devzen.ru)
Received: from relay11.nicmail.ru (relay11.nicmail.ru [195.208.3.7])
 (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
 (Client did not present a certificate)
 by mx1.freebsd.org (Postfix) with ESMTPS id 792A21DD2
 for <freebsd-current@freebsd.org>; Mon, 18 Apr 2016 12:17:30 +0000 (UTC)
 (envelope-from afiskon@devzen.ru)
Received: from [109.70.25.215] (port=51051 helo=fujitsu)
 by f06.mail.nic.ru with esmtp (Exim 5.55)
 (envelope-from <afiskon@devzen.ru>)
 id 1as87U-000HCn-0d; Mon, 18 Apr 2016 15:17:36 +0300
Received: from [93.174.131.138] (account afiskon@devzen.ru HELO fujitsu)
 by proxy02.mail.nic.ru (Exim 5.55)
 with id 1as87D-0000Da-7E; Mon, 18 Apr 2016 15:17:19 +0300
Date: Mon, 18 Apr 2016 15:16:39 +0300
From: Aleksander Alekseev <afiskon@devzen.ru>
To: Hans Petter Selasky <hps@selasky.org>
Cc: FreeBSD Current <freebsd-current@freebsd.org>
Subject: Re: qsort() documentation
Message-ID: <20160418151639.634d571d@fujitsu>
In-Reply-To: <5714C86A.8050204@selasky.org>
References: <5714C86A.8050204@selasky.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.21
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
 <freebsd-current.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-current>, 
 <mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current/>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-current>, 
 <mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Mon, 18 Apr 2016 12:17:31 -0000

Hello.

I suggest also add a short description of how it was achieved
(randomization?).

On Mon, 18 Apr 2016 13:43:38 +0200
Hans Petter Selasky <hps@selasky.org> wrote:

> Hi,
> 
> Are there any objections adding the following as part of documenting
> our kernel's qsort function?
> 
> Index: sys/libkern/qsort.c
> ===================================================================
> --- sys/libkern/qsort.c (revision 298202)
> +++ sys/libkern/qsort.c (working copy)
> @@ -45,6 +45,10 @@
> 
>   /*
>    * Qsort routine from Bentley & McIlroy's "Engineering a Sort
> Function".
> + *
> + * NOTE: This implementation of qsort() was designed to not have the
> + * worst case complexity of N**2, as seen with the regular quick sort
> + * functions as described by Wikipedia.
>    */
> 
> 
> --HPS
> _______________________________________________
> freebsd-current@freebsd.org mailing list
> https://lists.freebsd.org/mailman/listinfo/freebsd-current
> To unsubscribe, send any mail to
> "freebsd-current-unsubscribe@freebsd.org"
> 



-- 
Best regards,
Aleksander Alekseev
http://eax.me/