diff options
Diffstat (limited to 'comm/mailnews/db/mork/morkQuickSort.cpp')
| -rw-r--r-- | comm/mailnews/db/mork/morkQuickSort.cpp | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/comm/mailnews/db/mork/morkQuickSort.cpp b/comm/mailnews/db/mork/morkQuickSort.cpp new file mode 100644 index 0000000000..6fd211ee5c --- /dev/null +++ b/comm/mailnews/db/mork/morkQuickSort.cpp @@ -0,0 +1,182 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ + +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef _MDB_ +# include "mdb.h" +#endif + +#ifndef _MORK_ +# include "mork.h" +#endif + +#ifndef _MORKQUICKSORT_ +# include "morkQuickSort.h" +#endif + +#if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc)) +# ifndef INLINE +# define INLINE inline +# endif +#else +# define INLINE +#endif + +static INLINE mork_u1* morkQS_med3(mork_u1*, mork_u1*, mork_u1*, mdbAny_Order, + void*); + +static INLINE void morkQS_swapfunc(mork_u1*, mork_u1*, int, int); + +/* + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + */ +#define morkQS_swapcode(TYPE, parmi, parmj, n) \ + { \ + long i = (n) / sizeof(TYPE); \ + TYPE* pi = (TYPE*)(parmi); \ + TYPE* pj = (TYPE*)(parmj); \ + do { \ + TYPE t = *pi; \ + *pi++ = *pj; \ + *pj++ = t; \ + } while (--i > 0); \ + } + +#define morkQS_SwapInit(a, es) \ + swaptype = (a - (mork_u1*)0) % sizeof(long) || es % sizeof(long) ? 2 \ + : es == sizeof(long) ? 0 \ + : 1; + +static INLINE void morkQS_swapfunc(mork_u1* a, mork_u1* b, int n, + int swaptype) { + if (swaptype <= 1) + morkQS_swapcode(long, a, b, n) else morkQS_swapcode(mork_u1, a, b, n) +} + +#define morkQS_swap(a, b) \ + if (swaptype == 0) { \ + long t = *(long*)(a); \ + *(long*)(a) = *(long*)(b); \ + *(long*)(b) = t; \ + } else \ + morkQS_swapfunc(a, b, (int)inSize, swaptype) + +#define morkQS_vecswap(a, b, n) \ + if ((n) > 0) morkQS_swapfunc(a, b, (int)n, swaptype) + +static INLINE mork_u1* morkQS_med3(mork_u1* a, mork_u1* b, mork_u1* c, + mdbAny_Order cmp, void* closure) { + return (*cmp)(a, b, closure) < 0 + ? ((*cmp)(b, c, closure) < 0 ? b + : ((*cmp)(a, c, closure) < 0 ? c : a)) + : ((*cmp)(b, c, closure) > 0 + ? b + : ((*cmp)(a, c, closure) < 0 ? a : c)); +} + +#define morkQS_MIN(x, y) ((x) < (y) ? (x) : (y)) + +void morkQuickSort(mork_u1* ioVec, mork_u4 inCount, mork_u4 inSize, + mdbAny_Order inOrder, void* ioClosure) { + mork_u1 *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swaptype, swap_cnt; + +tailCall: + morkQS_SwapInit(ioVec, inSize); + swap_cnt = 0; + if (inCount < 7) { + for (pm = ioVec + inSize; pm < ioVec + inCount * inSize; pm += inSize) + for (pl = pm; pl > ioVec && (*inOrder)(pl - inSize, pl, ioClosure) > 0; + pl -= inSize) + morkQS_swap(pl, pl - inSize); + return; + } + pm = ioVec + (inCount / 2) * inSize; + if (inCount > 7) { + pl = ioVec; + pn = ioVec + (inCount - 1) * inSize; + if (inCount > 40) { + d = (inCount / 8) * inSize; + pl = morkQS_med3(pl, pl + d, pl + 2 * d, inOrder, ioClosure); + pm = morkQS_med3(pm - d, pm, pm + d, inOrder, ioClosure); + pn = morkQS_med3(pn - 2 * d, pn - d, pn, inOrder, ioClosure); + } + pm = morkQS_med3(pl, pm, pn, inOrder, ioClosure); + } + morkQS_swap(ioVec, pm); + pa = pb = ioVec + inSize; + + pc = pd = ioVec + (inCount - 1) * inSize; + for (;;) { + while (pb <= pc && (r = (*inOrder)(pb, ioVec, ioClosure)) <= 0) { + if (r == 0) { + swap_cnt = 1; + morkQS_swap(pa, pb); + pa += inSize; + } + pb += inSize; + } + while (pb <= pc && (r = (*inOrder)(pc, ioVec, ioClosure)) >= 0) { + if (r == 0) { + swap_cnt = 1; + morkQS_swap(pc, pd); + pd -= inSize; + } + pc -= inSize; + } + if (pb > pc) break; + morkQS_swap(pb, pc); + swap_cnt = 1; + pb += inSize; + pc -= inSize; + } + if (swap_cnt == 0) { /* Switch to insertion sort */ + for (pm = ioVec + inSize; pm < ioVec + inCount * inSize; pm += inSize) + for (pl = pm; pl > ioVec && (*inOrder)(pl - inSize, pl, ioClosure) > 0; + pl -= inSize) + morkQS_swap(pl, pl - inSize); + return; + } + + pn = ioVec + inCount * inSize; + r = morkQS_MIN(pa - ioVec, pb - pa); + morkQS_vecswap(ioVec, pb - r, r); + r = morkQS_MIN(pd - pc, (int)(pn - pd - inSize)); + morkQS_vecswap(pb, pn - r, r); + if ((r = pb - pa) > (int)inSize) + morkQuickSort(ioVec, r / inSize, inSize, inOrder, ioClosure); + if ((r = pd - pc) > (int)inSize) { + /* Iterate rather than recurse to save stack space */ + ioVec = pn - r; + inCount = r / inSize; + goto tailCall; + } + /* morkQuickSort(pn - r, r / inSize, inSize, inOrder, ioClosure);*/ +} |