|
| 1 | +/* |
| 2 | + * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit! |
| 3 | + * |
| 4 | + * This file is included by tuplesort.c, rather than compiled separately. |
| 5 | + */ |
| 6 | + |
| 7 | +/*$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $*/ |
| 8 | + |
| 9 | +/*- |
| 10 | + * Copyright (c) 1992, 1993 |
| 11 | + *The Regents of the University of California. All rights reserved. |
| 12 | + * |
| 13 | + * Redistribution and use in source and binary forms, with or without |
| 14 | + * modification, are permitted provided that the following conditions |
| 15 | + * are met: |
| 16 | + * 1. Redistributions of source code must retain the above copyright |
| 17 | + * notice, this list of conditions and the following disclaimer. |
| 18 | + * 2. Redistributions in binary form must reproduce the above copyright |
| 19 | + * notice, this list of conditions and the following disclaimer in the |
| 20 | + * documentation and/or other materials provided with the distribution. |
| 21 | + * 3. Neither the name of the University nor the names of its contributors |
| 22 | + * may be used to endorse or promote products derived from this software |
| 23 | + * without specific prior written permission. |
| 24 | + * |
| 25 | + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
| 26 | + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 27 | + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 28 | + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
| 29 | + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 30 | + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 31 | + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 32 | + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 33 | + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 34 | + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 35 | + * SUCH DAMAGE. |
| 36 | + */ |
| 37 | + |
| 38 | +/* |
| 39 | + * Qsort routine based on J. L. Bentley and M. D. McIlroy, |
| 40 | + * "Engineering a sort function", |
| 41 | + * Software--Practice and Experience 23 (1993) 1249-1265. |
| 42 | + * |
| 43 | + * We have modified their original by adding a check for already-sorted input, |
| 44 | + * which seems to be a win per discussions on pgsql-hackers around 2006-03-21. |
| 45 | + * |
| 46 | + * Also, we recurse on the smaller partition and iterate on the larger one, |
| 47 | + * which ensures we cannot recurse more than log(N) levels (since the |
| 48 | + * partition recursed to is surely no more than half of the input). Bentley |
| 49 | + * and McIlroy explicitly rejected doing this on the grounds that it's "not |
| 50 | + * worth the effort", but we have seen crashes in the field due to stack |
| 51 | + * overrun, so that judgment seems wrong. |
| 52 | + */ |
| 53 | + |
| 54 | +staticvoid |
| 55 | +swapfunc(SortTuple*a,SortTuple*b,size_tn) |
| 56 | +{ |
| 57 | +do |
| 58 | +{ |
| 59 | +SortTuplet=*a; |
| 60 | +*a++=*b; |
| 61 | +*b++=t; |
| 62 | +}while (--n>0); |
| 63 | +} |
| 64 | + |
| 65 | +#defineswap(a,b)\ |
| 66 | +do { \ |
| 67 | +SortTuple t = *(a);\ |
| 68 | +*(a) = *(b);\ |
| 69 | +*(b) = t;\ |
| 70 | +} while (0) |
| 71 | + |
| 72 | +#definevecswap(a,b,n) if ((n) > 0) swapfunc(a, b, n) |
| 73 | + |
| 74 | +staticSortTuple* |
| 75 | +med3_tuple(SortTuple*a,SortTuple*b,SortTuple*c,SortTupleComparatorcmp_tuple,Tuplesortstate*state) |
| 76 | +{ |
| 77 | +returncmp_tuple(a,b,state)<0 ? |
| 78 | +(cmp_tuple(b,c,state)<0 ?b : |
| 79 | +(cmp_tuple(a,c,state)<0 ?c :a)) |
| 80 | +: (cmp_tuple(b,c,state)>0 ?b : |
| 81 | +(cmp_tuple(a,c,state)<0 ?a :c)); |
| 82 | +} |
| 83 | + |
| 84 | +staticvoid |
| 85 | +qsort_tuple(SortTuple*a,size_tn,SortTupleComparatorcmp_tuple,Tuplesortstate*state) |
| 86 | +{ |
| 87 | +SortTuple*pa, |
| 88 | +*pb, |
| 89 | +*pc, |
| 90 | +*pd, |
| 91 | +*pl, |
| 92 | +*pm, |
| 93 | +*pn; |
| 94 | +size_td1, |
| 95 | +d2; |
| 96 | +intr, |
| 97 | +presorted; |
| 98 | + |
| 99 | +loop: |
| 100 | +CHECK_FOR_INTERRUPTS(); |
| 101 | +if (n<7) |
| 102 | +{ |
| 103 | +for (pm=a+1;pm<a+n;pm++) |
| 104 | +for (pl=pm;pl>a&&cmp_tuple(pl-1,pl,state)>0;pl--) |
| 105 | +swap(pl,pl-1); |
| 106 | +return; |
| 107 | +} |
| 108 | +presorted=1; |
| 109 | +for (pm=a+1;pm<a+n;pm++) |
| 110 | +{ |
| 111 | +CHECK_FOR_INTERRUPTS(); |
| 112 | +if (cmp_tuple(pm-1,pm,state)>0) |
| 113 | +{ |
| 114 | +presorted=0; |
| 115 | +break; |
| 116 | +} |
| 117 | +} |
| 118 | +if (presorted) |
| 119 | +return; |
| 120 | +pm=a+ (n /2); |
| 121 | +if (n>7) |
| 122 | +{ |
| 123 | +pl=a; |
| 124 | +pn=a+ (n-1); |
| 125 | +if (n>40) |
| 126 | +{ |
| 127 | +size_td= (n /8); |
| 128 | + |
| 129 | +pl=med3_tuple(pl,pl+d,pl+2*d,cmp_tuple,state); |
| 130 | +pm=med3_tuple(pm-d,pm,pm+d,cmp_tuple,state); |
| 131 | +pn=med3_tuple(pn-2*d,pn-d,pn,cmp_tuple,state); |
| 132 | +} |
| 133 | +pm=med3_tuple(pl,pm,pn,cmp_tuple,state); |
| 134 | +} |
| 135 | +swap(a,pm); |
| 136 | +pa=pb=a+1; |
| 137 | +pc=pd=a+ (n-1); |
| 138 | +for (;;) |
| 139 | +{ |
| 140 | +while (pb <=pc&& (r=cmp_tuple(pb,a,state)) <=0) |
| 141 | +{ |
| 142 | +if (r==0) |
| 143 | +{ |
| 144 | +swap(pa,pb); |
| 145 | +pa++; |
| 146 | +} |
| 147 | +pb++; |
| 148 | +CHECK_FOR_INTERRUPTS(); |
| 149 | +} |
| 150 | +while (pb <=pc&& (r=cmp_tuple(pc,a,state)) >=0) |
| 151 | +{ |
| 152 | +if (r==0) |
| 153 | +{ |
| 154 | +swap(pc,pd); |
| 155 | +pd--; |
| 156 | +} |
| 157 | +pc--; |
| 158 | +CHECK_FOR_INTERRUPTS(); |
| 159 | +} |
| 160 | +if (pb>pc) |
| 161 | +break; |
| 162 | +swap(pb,pc); |
| 163 | +pb++; |
| 164 | +pc--; |
| 165 | +} |
| 166 | +pn=a+n; |
| 167 | +d1=Min(pa-a,pb-pa); |
| 168 | +vecswap(a,pb-d1,d1); |
| 169 | +d1=Min(pd-pc,pn-pd-1); |
| 170 | +vecswap(pb,pn-d1,d1); |
| 171 | +d1=pb-pa; |
| 172 | +d2=pd-pc; |
| 173 | +if (d1 <=d2) |
| 174 | +{ |
| 175 | +/* Recurse on left partition, then iterate on right partition */ |
| 176 | +if (d1>1) |
| 177 | +qsort_tuple(a,d1,cmp_tuple,state); |
| 178 | +if (d2>1) |
| 179 | +{ |
| 180 | +/* Iterate rather than recurse to save stack space */ |
| 181 | +/* qsort_tuple(pn - d2, d2, cmp_tuple, state); */ |
| 182 | +a=pn-d2; |
| 183 | +n=d2; |
| 184 | +gotoloop; |
| 185 | +} |
| 186 | +} |
| 187 | +else |
| 188 | +{ |
| 189 | +/* Recurse on right partition, then iterate on left partition */ |
| 190 | +if (d2>1) |
| 191 | +qsort_tuple(pn-d2,d2,cmp_tuple,state); |
| 192 | +if (d1>1) |
| 193 | +{ |
| 194 | +/* Iterate rather than recurse to save stack space */ |
| 195 | +/* qsort_tuple(a, d1, cmp_tuple, state); */ |
| 196 | +n=d1; |
| 197 | +gotoloop; |
| 198 | +} |
| 199 | +} |
| 200 | +} |
| 201 | + |
| 202 | +#definecmp_ssup(a,b,ssup) \ |
| 203 | +ApplySortComparator((a)->datum1, (a)->isnull1, \ |
| 204 | +(b)->datum1, (b)->isnull1, ssup) |
| 205 | + |
| 206 | +staticSortTuple* |
| 207 | +med3_ssup(SortTuple*a,SortTuple*b,SortTuple*c,SortSupportssup) |
| 208 | +{ |
| 209 | +returncmp_ssup(a,b,ssup)<0 ? |
| 210 | +(cmp_ssup(b,c,ssup)<0 ?b : |
| 211 | +(cmp_ssup(a,c,ssup)<0 ?c :a)) |
| 212 | +: (cmp_ssup(b,c,ssup)>0 ?b : |
| 213 | +(cmp_ssup(a,c,ssup)<0 ?a :c)); |
| 214 | +} |
| 215 | + |
| 216 | +staticvoid |
| 217 | +qsort_ssup(SortTuple*a,size_tn,SortSupportssup) |
| 218 | +{ |
| 219 | +SortTuple*pa, |
| 220 | +*pb, |
| 221 | +*pc, |
| 222 | +*pd, |
| 223 | +*pl, |
| 224 | +*pm, |
| 225 | +*pn; |
| 226 | +size_td1, |
| 227 | +d2; |
| 228 | +intr, |
| 229 | +presorted; |
| 230 | + |
| 231 | +loop: |
| 232 | +CHECK_FOR_INTERRUPTS(); |
| 233 | +if (n<7) |
| 234 | +{ |
| 235 | +for (pm=a+1;pm<a+n;pm++) |
| 236 | +for (pl=pm;pl>a&&cmp_ssup(pl-1,pl,ssup)>0;pl--) |
| 237 | +swap(pl,pl-1); |
| 238 | +return; |
| 239 | +} |
| 240 | +presorted=1; |
| 241 | +for (pm=a+1;pm<a+n;pm++) |
| 242 | +{ |
| 243 | +CHECK_FOR_INTERRUPTS(); |
| 244 | +if (cmp_ssup(pm-1,pm,ssup)>0) |
| 245 | +{ |
| 246 | +presorted=0; |
| 247 | +break; |
| 248 | +} |
| 249 | +} |
| 250 | +if (presorted) |
| 251 | +return; |
| 252 | +pm=a+ (n /2); |
| 253 | +if (n>7) |
| 254 | +{ |
| 255 | +pl=a; |
| 256 | +pn=a+ (n-1); |
| 257 | +if (n>40) |
| 258 | +{ |
| 259 | +size_td= (n /8); |
| 260 | + |
| 261 | +pl=med3_ssup(pl,pl+d,pl+2*d,ssup); |
| 262 | +pm=med3_ssup(pm-d,pm,pm+d,ssup); |
| 263 | +pn=med3_ssup(pn-2*d,pn-d,pn,ssup); |
| 264 | +} |
| 265 | +pm=med3_ssup(pl,pm,pn,ssup); |
| 266 | +} |
| 267 | +swap(a,pm); |
| 268 | +pa=pb=a+1; |
| 269 | +pc=pd=a+ (n-1); |
| 270 | +for (;;) |
| 271 | +{ |
| 272 | +while (pb <=pc&& (r=cmp_ssup(pb,a,ssup)) <=0) |
| 273 | +{ |
| 274 | +if (r==0) |
| 275 | +{ |
| 276 | +swap(pa,pb); |
| 277 | +pa++; |
| 278 | +} |
| 279 | +pb++; |
| 280 | +CHECK_FOR_INTERRUPTS(); |
| 281 | +} |
| 282 | +while (pb <=pc&& (r=cmp_ssup(pc,a,ssup)) >=0) |
| 283 | +{ |
| 284 | +if (r==0) |
| 285 | +{ |
| 286 | +swap(pc,pd); |
| 287 | +pd--; |
| 288 | +} |
| 289 | +pc--; |
| 290 | +CHECK_FOR_INTERRUPTS(); |
| 291 | +} |
| 292 | +if (pb>pc) |
| 293 | +break; |
| 294 | +swap(pb,pc); |
| 295 | +pb++; |
| 296 | +pc--; |
| 297 | +} |
| 298 | +pn=a+n; |
| 299 | +d1=Min(pa-a,pb-pa); |
| 300 | +vecswap(a,pb-d1,d1); |
| 301 | +d1=Min(pd-pc,pn-pd-1); |
| 302 | +vecswap(pb,pn-d1,d1); |
| 303 | +d1=pb-pa; |
| 304 | +d2=pd-pc; |
| 305 | +if (d1 <=d2) |
| 306 | +{ |
| 307 | +/* Recurse on left partition, then iterate on right partition */ |
| 308 | +if (d1>1) |
| 309 | +qsort_ssup(a,d1,ssup); |
| 310 | +if (d2>1) |
| 311 | +{ |
| 312 | +/* Iterate rather than recurse to save stack space */ |
| 313 | +/* qsort_ssup(pn - d2, d2, ssup); */ |
| 314 | +a=pn-d2; |
| 315 | +n=d2; |
| 316 | +gotoloop; |
| 317 | +} |
| 318 | +} |
| 319 | +else |
| 320 | +{ |
| 321 | +/* Recurse on right partition, then iterate on left partition */ |
| 322 | +if (d2>1) |
| 323 | +qsort_ssup(pn-d2,d2,ssup); |
| 324 | +if (d1>1) |
| 325 | +{ |
| 326 | +/* Iterate rather than recurse to save stack space */ |
| 327 | +/* qsort_ssup(a, d1, ssup); */ |
| 328 | +n=d1; |
| 329 | +gotoloop; |
| 330 | +} |
| 331 | +} |
| 332 | +} |
