openbsd/src/regress/lib/libc/qsort, branch OPENBSD_6_3 A mirror of https://github.com/libressl/openbsd.git https://git.lua4.win/openbsd/atom?h=OPENBSD_6_3 2017-05-27T18:54:09+00:00 Also test arrays of double and long long. 2017-05-27T18:54:09+00:00 millert 2017-05-27T18:54:09+00:00 urn:sha1:4a132d8f30d57d5a6d7ab7747c1a581fe2b95b0a Add timing and test name options. 2017-05-22T17:52:16+00:00 millert 2017-05-22T17:52:16+00:00 urn:sha1:bda66dbfbd399c867174f3c429d4b37e15f908d9 Instead of embedding pre-generated tables from McIlroy's "A Killer 2017-05-22T17:16:43+00:00 millert 2017-05-22T17:16:43+00:00 urn:sha1:c6a610ee008733eeb3365f48f5063d48e0f0825d Adversary for Quicksort", just include the code to generate them. Also allow the number of elements to be specified on the command line. correct a return value test 2017-05-21T11:54:41+00:00 jsg 2017-05-21T11:54:41+00:00 urn:sha1:df4200f0f7b054ce31b6fae98e390149c80f7d39 ok millert@ Add input targeted at the Bentley and McIrlroy quicksort generated 2017-05-19T04:08:00+00:00 millert 2017-05-19T04:08:00+00:00 urn:sha1:ee669a2eb38964d5942ce9191de88cf3654a949f by McIlroy's "A Killer Adversary for Quicksort". This results in quadratic behavior and the test aborts before completion. use mergesort instead of heapsort when comparing results 2017-05-18T14:50:08+00:00 millert 2017-05-18T14:50:08+00:00 urn:sha1:819ce78cb7295e140a7c02b68eeb61caff0655e1 Avoid running the "killer" tests multiple times with the same 2017-05-17T21:40:13+00:00 millert 2017-05-17T21:40:13+00:00 urn:sha1:925427598d664573ecb8e8f20b14f5ff10f0f534 parameters. Add "median of three" killer, as seen in "Introspective Sorting and 2017-05-17T21:24:48+00:00 millert 2017-05-17T21:24:48+00:00 urn:sha1:0bbcaddbe494193e0624899bc6fc248cb71da1b6 Selection Algorithms" by David R Musser. Approximate nlgn instead of using libm. The same approximation may 2017-05-17T20:28:35+00:00 millert 2017-05-17T20:28:35+00:00 urn:sha1:8d603a07f4d3001dcb3dbd41181d29c15d99b605 be used in qsort.c in a later commit. Add "killer" input from "algorithmic complexity attacks and libc 2017-05-17T18:07:03+00:00 millert 2017-05-17T18:07:03+00:00 urn:sha1:a94e19c4919aa8f62a0d1a7eea58ab1fdc3832e3 qsort()". This causes quadratic behavior with the 4.4BSD qsort's "switch to insertion sort" optimization when the input appears to be mostly sorted. That optimization was removed in qsort.c r1.12 but it is worth having in the regress test too.