1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsQuickSort.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,187 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +
1.6 +/*-
1.7 + * Copyright (c) 1992, 1993
1.8 + * The Regents of the University of California. All rights reserved.
1.9 + *
1.10 + * Redistribution and use in source and binary forms, with or without
1.11 + * modification, are permitted provided that the following conditions
1.12 + * are met:
1.13 + * 1. Redistributions of source code must retain the above copyright
1.14 + * notice, this list of conditions and the following disclaimer.
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + * 3. Neither the name of the University nor the names of its contributors
1.19 + * may be used to endorse or promote products derived from this software
1.20 + * without specific prior written permission.
1.21 + *
1.22 + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1.23 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.24 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.25 + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1.26 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.27 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.28 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.29 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.30 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.31 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.32 + * SUCH DAMAGE.
1.33 + */
1.34 +
1.35 +/* We need this because Solaris' version of qsort is broken and
1.36 + * causes array bounds reads.
1.37 + */
1.38 +
1.39 +#include <stdlib.h>
1.40 +#include "nsAlgorithm.h"
1.41 +#include "nsQuickSort.h"
1.42 +
1.43 +extern "C" {
1.44 +
1.45 +#if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc))
1.46 +# ifndef INLINE
1.47 +# define INLINE inline
1.48 +# endif
1.49 +#else
1.50 +# define INLINE
1.51 +#endif
1.52 +
1.53 +typedef int cmp_t(const void *, const void *, void *);
1.54 +static INLINE char *med3(char *, char *, char *, cmp_t *, void *);
1.55 +static INLINE void swapfunc(char *, char *, int, int);
1.56 +
1.57 +/*
1.58 + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
1.59 + */
1.60 +#define swapcode(TYPE, parmi, parmj, n) { \
1.61 + long i = (n) / sizeof (TYPE); \
1.62 + TYPE *pi = (TYPE *) (parmi); \
1.63 + TYPE *pj = (TYPE *) (parmj); \
1.64 + do { \
1.65 + TYPE t = *pi; \
1.66 + *pi++ = *pj; \
1.67 + *pj++ = t; \
1.68 + } while (--i > 0); \
1.69 +}
1.70 +
1.71 +#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
1.72 + es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
1.73 +
1.74 +static INLINE void
1.75 +swapfunc(char *a, char *b, int n, int swaptype)
1.76 +{
1.77 + if(swaptype <= 1)
1.78 + swapcode(long, a, b, n)
1.79 + else
1.80 + swapcode(char, a, b, n)
1.81 +}
1.82 +
1.83 +#define swap(a, b) \
1.84 + if (swaptype == 0) { \
1.85 + long t = *(long *)(a); \
1.86 + *(long *)(a) = *(long *)(b); \
1.87 + *(long *)(b) = t; \
1.88 + } else \
1.89 + swapfunc((char *)a, (char*)b, (int)es, swaptype)
1.90 +
1.91 +#define vecswap(a, b, n) if ((n) > 0) swapfunc((char *)a, (char *)b, (int)n, swaptype)
1.92 +
1.93 +static INLINE char *
1.94 +med3(char *a, char *b, char *c, cmp_t* cmp, void *data)
1.95 +{
1.96 + return cmp(a, b, data) < 0 ?
1.97 + (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
1.98 + :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
1.99 +}
1.100 +
1.101 +void NS_QuickSort (
1.102 + void *a,
1.103 + unsigned int n,
1.104 + unsigned int es,
1.105 + cmp_t *cmp,
1.106 + void *data
1.107 + )
1.108 +{
1.109 + char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
1.110 + int d, r, swaptype;
1.111 +
1.112 +loop: SWAPINIT(a, es);
1.113 + /* Use insertion sort when input is small */
1.114 + if (n < 7) {
1.115 + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
1.116 + for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
1.117 + pl -= es)
1.118 + swap(pl, pl - es);
1.119 + return;
1.120 + }
1.121 + /* Choose pivot */
1.122 + pm = (char *)a + (n / 2) * es;
1.123 + if (n > 7) {
1.124 + pl = (char *)a;
1.125 + pn = (char *)a + (n - 1) * es;
1.126 + if (n > 40) {
1.127 + d = (n / 8) * es;
1.128 + pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
1.129 + pm = med3(pm - d, pm, pm + d, cmp, data);
1.130 + pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
1.131 + }
1.132 + pm = med3(pl, pm, pn, cmp, data);
1.133 + }
1.134 + swap(a, pm);
1.135 + pa = pb = (char *)a + es;
1.136 +
1.137 + pc = pd = (char *)a + (n - 1) * es;
1.138 + /* loop invariants:
1.139 + * [a, pa) = pivot
1.140 + * [pa, pb) < pivot
1.141 + * [pb, pc + es) unprocessed
1.142 + * [pc + es, pd + es) > pivot
1.143 + * [pd + es, pn) = pivot
1.144 + */
1.145 + for (;;) {
1.146 + while (pb <= pc && (r = cmp(pb, a, data)) <= 0) {
1.147 + if (r == 0) {
1.148 + swap(pa, pb);
1.149 + pa += es;
1.150 + }
1.151 + pb += es;
1.152 + }
1.153 + while (pb <= pc && (r = cmp(pc, a, data)) >= 0) {
1.154 + if (r == 0) {
1.155 + swap(pc, pd);
1.156 + pd -= es;
1.157 + }
1.158 + pc -= es;
1.159 + }
1.160 + if (pb > pc)
1.161 + break;
1.162 + swap(pb, pc);
1.163 + pb += es;
1.164 + pc -= es;
1.165 + }
1.166 + /* Move pivot values */
1.167 + pn = (char *)a + n * es;
1.168 + r = XPCOM_MIN(pa - (char *)a, pb - pa);
1.169 + vecswap(a, pb - r, r);
1.170 + r = XPCOM_MIN<size_t>(pd - pc, pn - pd - es);
1.171 + vecswap(pb, pn - r, r);
1.172 + /* Recursively process partitioned items */
1.173 + if ((r = pb - pa) > (int)es)
1.174 + NS_QuickSort(a, r / es, es, cmp, data);
1.175 + if ((r = pd - pc) > (int)es) {
1.176 + /* Iterate rather than recurse to save stack space */
1.177 + a = pn - r;
1.178 + n = r / es;
1.179 + goto loop;
1.180 + }
1.181 +/* NS_QuickSort(pn - r, r / es, es, cmp, data);*/
1.182 +}
1.183 +
1.184 +}
1.185 +
1.186 +#undef INLINE
1.187 +#undef swapcode
1.188 +#undef SWAPINIT
1.189 +#undef swap
1.190 +#undef vecswap
