diff options
author | Tomasz Konojacki <me@xenu.pl> | 2020-03-02 06:04:10 +0000 |
---|---|---|
committer | Karl Williamson <khw@cpan.org> | 2020-03-02 09:30:47 -0700 |
commit | 23a85c2202bcf4c9608c464b55ce80c4bc91f2bb (patch) | |
tree | d6246c8b63e02b1e40b833150861c09e6404d4e6 /pp_sort.c | |
parent | 125e1a36a9395a6da73708bbeb316350fdfe2722 (diff) | |
download | perl-23a85c2202bcf4c9608c464b55ce80c4bc91f2bb.tar.gz |
pp_sort.c: remove the remains of quicksort
e2091bb6ea87111c32936c9170405a44995be338 removed most of it but
some dead code remained.
Diffstat (limited to 'pp_sort.c')
-rw-r--r-- | pp_sort.c | 198 |
1 files changed, 1 insertions, 197 deletions
@@ -37,7 +37,7 @@ #define SMALLSORT (200) #endif -/* Flags for qsortsv and mergesortsv */ +/* Flags for sortsv_flags */ #define SORTf_DESC 1 #define SORTf_STABLE 2 #define SORTf_UNSTABLE 8 @@ -570,202 +570,6 @@ Perl_sortsv_flags(pTHX_ gptr *base, size_t nmemb, SVCOMPARE_t cmp, U32 flags) } /* - * The quicksort implementation was derived from source code contributed - * by Tom Horsley. - * - * NOTE: this code was derived from Tom Horsley's qsort replacement - * and should not be confused with the original code. - */ - -/* Copyright (C) Tom Horsley, 1997. All rights reserved. - - Permission granted to distribute under the same terms as perl which are - (briefly): - - This program is free software; you can redistribute it and/or modify - it under the terms of either: - - a) the GNU General Public License as published by the Free - Software Foundation; either version 1, or (at your option) any - later version, or - - b) the "Artistic License" which comes with this Kit. - - Details on the perl license can be found in the perl source code which - may be located via the www.perl.com web page. - - This is the most wonderfulest possible qsort I can come up with (and - still be mostly portable) My (limited) tests indicate it consistently - does about 20% fewer calls to compare than does the qsort in the Visual - C++ library, other vendors may vary. - - Some of the ideas in here can be found in "Algorithms" by Sedgewick, - others I invented myself (or more likely re-invented since they seemed - pretty obvious once I watched the algorithm operate for a while). - - Most of this code was written while watching the Marlins sweep the Giants - in the 1997 National League Playoffs - no Braves fans allowed to use this - code (just kidding :-). - - I realize that if I wanted to be true to the perl tradition, the only - comment in this file would be something like: - - ...they shuffled back towards the rear of the line. 'No, not at the - rear!' the slave-driver shouted. 'Three files up. And stay there... - - However, I really needed to violate that tradition just so I could keep - track of what happens myself, not to mention some poor fool trying to - understand this years from now :-). -*/ - -/* ********************************************************** Configuration */ - -#ifndef QSORT_ORDER_GUESS -#define QSORT_ORDER_GUESS 2 /* Select doubling version of the netBSD trick */ -#endif - -/* QSORT_MAX_STACK is the largest number of partitions that can be stacked up for - future processing - a good max upper bound is log base 2 of memory size - (32 on 32 bit machines, 64 on 64 bit machines, etc). In reality can - safely be smaller than that since the program is taking up some space and - most operating systems only let you grab some subset of contiguous - memory (not to mention that you are normally sorting data larger than - 1 byte element size :-). -*/ -#ifndef QSORT_MAX_STACK -#define QSORT_MAX_STACK 32 -#endif - -/* QSORT_BREAK_EVEN is the size of the largest partition we should insertion sort. - Anything bigger and we use qsort. If you make this too small, the qsort - will probably break (or become less efficient), because it doesn't expect - the middle element of a partition to be the same as the right or left - - you have been warned). -*/ -#ifndef QSORT_BREAK_EVEN -#define QSORT_BREAK_EVEN 6 -#endif - -/* QSORT_PLAY_SAFE is the size of the largest partition we're willing - to go quadratic on. We innoculate larger partitions against - quadratic behavior by shuffling them before sorting. This is not - an absolute guarantee of non-quadratic behavior, but it would take - staggeringly bad luck to pick extreme elements as the pivot - from randomized data. -*/ -#ifndef QSORT_PLAY_SAFE -#define QSORT_PLAY_SAFE 255 -#endif - -/* ************************************************************* Data Types */ - -/* hold left and right index values of a partition waiting to be sorted (the - partition includes both left and right - right is NOT one past the end or - anything like that). -*/ -struct partition_stack_entry { - int left; - int right; -#ifdef QSORT_ORDER_GUESS - int qsort_break_even; -#endif -}; - -/* ******************************************************* Shorthand Macros */ - -/* Note that these macros will be used from inside the qsort function where - we happen to know that the variable 'elt_size' contains the size of an - array element and the variable 'temp' points to enough space to hold a - temp element and the variable 'array' points to the array being sorted - and 'compare' is the pointer to the compare routine. - - Also note that there are very many highly architecture specific ways - these might be sped up, but this is simply the most generally portable - code I could think of. -*/ - -/* Return < 0 == 0 or > 0 as the value of elt1 is < elt2, == elt2, > elt2 -*/ -#define qsort_cmp(elt1, elt2) \ - ((*compare)(aTHX_ array[elt1], array[elt2])) - -#ifdef QSORT_ORDER_GUESS -#define QSORT_NOTICE_SWAP swapped++; -#else -#define QSORT_NOTICE_SWAP -#endif - -/* swaps contents of array elements elt1, elt2. -*/ -#define qsort_swap(elt1, elt2) \ - STMT_START { \ - QSORT_NOTICE_SWAP \ - temp = array[elt1]; \ - array[elt1] = array[elt2]; \ - array[elt2] = temp; \ - } STMT_END - -/* rotate contents of elt1, elt2, elt3 such that elt1 gets elt2, elt2 gets - elt3 and elt3 gets elt1. -*/ -#define qsort_rotate(elt1, elt2, elt3) \ - STMT_START { \ - QSORT_NOTICE_SWAP \ - temp = array[elt1]; \ - array[elt1] = array[elt2]; \ - array[elt2] = array[elt3]; \ - array[elt3] = temp; \ - } STMT_END - -/* ************************************************************ Debug stuff */ - -#ifdef QSORT_DEBUG - -static void -break_here() -{ - return; /* good place to set a breakpoint */ -} - -#define qsort_assert(t) (void)( (t) || (break_here(), 0) ) - -static void -doqsort_all_asserts( - void * array, - size_t num_elts, - size_t elt_size, - int (*compare)(const void * elt1, const void * elt2), - int pc_left, int pc_right, int u_left, int u_right) -{ - int i; - - qsort_assert(pc_left <= pc_right); - qsort_assert(u_right < pc_left); - qsort_assert(pc_right < u_left); - for (i = u_right + 1; i < pc_left; ++i) { - qsort_assert(qsort_cmp(i, pc_left) < 0); - } - for (i = pc_left; i < pc_right; ++i) { - qsort_assert(qsort_cmp(i, pc_right) == 0); - } - for (i = pc_right + 1; i < u_left; ++i) { - qsort_assert(qsort_cmp(pc_right, i) < 0); - } -} - -#define qsort_all_asserts(PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT) \ - doqsort_all_asserts(array, num_elts, elt_size, compare, \ - PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT) - -#else - -#define qsort_assert(t) ((void)0) - -#define qsort_all_asserts(PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT) ((void)0) - -#endif - -/* =head1 Array Manipulation Functions =for apidoc sortsv |