1/* Sort a vector of pointers to data. 2 3 Copyright (C) 2007, 2009, 2010 Free Software Foundation, Inc. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18/* Written by Paul Eggert. */ 19 20#include <config.h> 21 22#include "mpsort.h" 23 24#include <string.h> 25 26/* The type of qsort-style comparison functions. */ 27 28typedef int (*comparison_function) (void const *, void const *); 29 30static void mpsort_with_tmp (void const **restrict, size_t, 31 void const **restrict, comparison_function); 32 33/* Sort a vector BASE containing N pointers, placing the sorted array 34 into TMP. Compare pointers with CMP. N must be at least 2. */ 35 36static void 37mpsort_into_tmp (void const **restrict base, size_t n, 38 void const **restrict tmp, 39 comparison_function cmp) 40{ 41 size_t n1 = n / 2; 42 size_t n2 = n - n1; 43 size_t a = 0; 44 size_t alim = n1; 45 size_t b = n1; 46 size_t blim = n; 47 void const *ba; 48 void const *bb; 49 50 mpsort_with_tmp (base + n1, n2, tmp, cmp); 51 mpsort_with_tmp (base, n1, tmp, cmp); 52 53 ba = base[a]; 54 bb = base[b]; 55 56 for (;;) 57 if (cmp (ba, bb) <= 0) 58 { 59 *tmp++ = ba; 60 a++; 61 if (a == alim) 62 { 63 a = b; 64 alim = blim; 65 break; 66 } 67 ba = base[a]; 68 } 69 else 70 { 71 *tmp++ = bb; 72 b++; 73 if (b == blim) 74 break; 75 bb = base[b]; 76 } 77 78 memcpy (tmp, base + a, (alim - a) * sizeof *base); 79} 80 81/* Sort a vector BASE containing N pointers, in place. Use TMP 82 (containing N / 2 pointers) for temporary storage. Compare 83 pointers with CMP. */ 84 85static void 86mpsort_with_tmp (void const **restrict base, size_t n, 87 void const **restrict tmp, 88 comparison_function cmp) 89{ 90 if (n <= 2) 91 { 92 if (n == 2) 93 { 94 void const *p0 = base[0]; 95 void const *p1 = base[1]; 96 if (! (cmp (p0, p1) <= 0)) 97 { 98 base[0] = p1; 99 base[1] = p0; 100 } 101 } 102 } 103 else 104 { 105 size_t n1 = n / 2; 106 size_t n2 = n - n1; 107 size_t i; 108 size_t t = 0; 109 size_t tlim = n1; 110 size_t b = n1; 111 size_t blim = n; 112 void const *bb; 113 void const *tt; 114 115 mpsort_with_tmp (base + n1, n2, tmp, cmp); 116 117 if (n1 < 2) 118 tmp[0] = base[0]; 119 else 120 mpsort_into_tmp (base, n1, tmp, cmp); 121 122 tt = tmp[t]; 123 bb = base[b]; 124 125 for (i = 0; ; ) 126 if (cmp (tt, bb) <= 0) 127 { 128 base[i++] = tt; 129 t++; 130 if (t == tlim) 131 break; 132 tt = tmp[t]; 133 } 134 else 135 { 136 base[i++] = bb; 137 b++; 138 if (b == blim) 139 { 140 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base); 141 break; 142 } 143 bb = base[b]; 144 } 145 } 146} 147 148/* Sort a vector BASE containing N pointers, in place. BASE must 149 contain enough storage to hold N + N / 2 vectors; the trailing 150 vectors are used for temporaries. Compare pointers with CMP. */ 151 152void 153mpsort (void const **base, size_t n, comparison_function cmp) 154{ 155 mpsort_with_tmp (base, n, base + n, cmp); 156} 157