Back to index

lightning-sunbird  0.9+nobinonly
morkQuickSort.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 
00003 /*-
00004  * Copyright (c) 1992, 1993
00005  *  The Regents of the University of California.  All rights reserved.
00006  *
00007  * Redistribution and use in source and binary forms, with or without
00008  * modification, are permitted provided that the following conditions
00009  * are met:
00010  * 1. Redistributions of source code must retain the above copyright
00011  *    notice, this list of conditions and the following disclaimer.
00012  * 2. Redistributions in binary form must reproduce the above copyright
00013  *    notice, this list of conditions and the following disclaimer in the
00014  *    documentation and/or other materials provided with the distribution.
00015  * 3. Neither the name of the University nor the names of its contributors
00016  *    may be used to endorse or promote products derived from this software
00017  *    without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00020  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00021  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00022  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00023  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00024  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00025  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00026  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00027  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00028  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00029  * SUCH DAMAGE.
00030  */
00031 
00032 /* We need this because Solaris' version of qsort is broken and
00033  * causes array bounds reads.
00034  */
00035 
00036 #ifndef _MDB_
00037 #include "mdb.h"
00038 #endif
00039 
00040 #ifndef _MORK_
00041 #include "mork.h"
00042 #endif
00043 
00044 #ifndef _MORKQUICKSORT_
00045 #include "morkQuickSort.h"
00046 #endif
00047 
00048 #if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc))
00049 # ifndef INLINE
00050 #  define INLINE inline
00051 # endif
00052 #else
00053 # define INLINE
00054 #endif
00055 
00056 static INLINE mork_u1*
00057 morkQS_med3(mork_u1 *, mork_u1 *, mork_u1 *, mdbAny_Order, void *);
00058 
00059 static INLINE void
00060 morkQS_swapfunc(mork_u1 *, mork_u1 *, int, int);
00061 
00062 /*
00063  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
00064  */
00065 #define morkQS_swapcode(TYPE, parmi, parmj, n) {     \
00066   long i = (n) / sizeof (TYPE);       \
00067   register TYPE *pi = (TYPE *) (parmi);     \
00068   register TYPE *pj = (TYPE *) (parmj);     \
00069   do {             \
00070     register TYPE  t = *pi;    \
00071     *pi++ = *pj;        \
00072     *pj++ = t;        \
00073         } while (--i > 0);        \
00074 }
00075 
00076 #define morkQS_SwapInit(a, es) swaptype = (a - (mork_u1 *)0) % sizeof(long) || \
00077   es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
00078 
00079 static INLINE void
00080 morkQS_swapfunc(mork_u1* a, mork_u1* b, int n, int swaptype)
00081 {
00082   if(swaptype <= 1)
00083     morkQS_swapcode(long, a, b, n)
00084   else
00085     morkQS_swapcode(mork_u1, a, b, n)
00086 }
00087 
00088 #define morkQS_swap(a, b)          \
00089   if (swaptype == 0) {        \
00090     long t = *(long *)(a);      \
00091     *(long *)(a) = *(long *)(b);    \
00092     *(long *)(b) = t;      \
00093   } else            \
00094     morkQS_swapfunc(a, b, (int)inSize, swaptype)
00095 
00096 #define morkQS_vecswap(a, b, n)   if ((n) > 0) morkQS_swapfunc(a, b, (int)n, swaptype)
00097 
00098 static INLINE mork_u1 *
00099 morkQS_med3(mork_u1* a, mork_u1* b, mork_u1* c, mdbAny_Order cmp, void* closure)
00100 {
00101   return (*cmp)(a, b, closure) < 0 ?
00102     ((*cmp)(b, c, closure) < 0 ? b : ((*cmp)(a, c, closure) < 0 ? c : a ))
00103       :((*cmp)(b, c, closure) > 0 ? b : ((*cmp)(a, c, closure) < 0 ? a : c ));
00104 }
00105 
00106 #define morkQS_MIN(x,y)     ((x)<(y)?(x):(y))
00107 
00108 void
00109 morkQuickSort(mork_u1* ioVec, mork_u4 inCount, mork_u4 inSize,
00110   mdbAny_Order inOrder, void* ioClosure)
00111 {
00112   mork_u1* pa, *pb, *pc, *pd, *pl, *pm, *pn;
00113   int d, r, swaptype, swap_cnt;
00114 
00115 tailCall:  morkQS_SwapInit(ioVec, inSize);
00116   swap_cnt = 0;
00117   if (inCount < 7) {
00118     for (pm = ioVec + inSize; pm < ioVec + inCount * inSize; pm += inSize)
00119       for (pl = pm; pl > ioVec && (*inOrder)(pl - inSize, pl, ioClosure) > 0;
00120            pl -= inSize)
00121         morkQS_swap(pl, pl - inSize);
00122     return;
00123   }
00124   pm = ioVec + (inCount / 2) * inSize;
00125   if (inCount > 7) {
00126     pl = ioVec;
00127     pn = ioVec + (inCount - 1) * inSize;
00128     if (inCount > 40) {
00129       d = (inCount / 8) * inSize;
00130       pl = morkQS_med3(pl, pl + d, pl + 2 * d, inOrder, ioClosure);
00131       pm = morkQS_med3(pm - d, pm, pm + d, inOrder, ioClosure);
00132       pn = morkQS_med3(pn - 2 * d, pn - d, pn, inOrder, ioClosure);
00133     }
00134     pm = morkQS_med3(pl, pm, pn, inOrder, ioClosure);
00135   }
00136   morkQS_swap(ioVec, pm);
00137   pa = pb = ioVec + inSize;
00138 
00139   pc = pd = ioVec + (inCount - 1) * inSize;
00140   for (;;) {
00141     while (pb <= pc && (r = (*inOrder)(pb, ioVec, ioClosure)) <= 0) {
00142       if (r == 0) {
00143         swap_cnt = 1;
00144         morkQS_swap(pa, pb);
00145         pa += inSize;
00146       }
00147       pb += inSize;
00148     }
00149     while (pb <= pc && (r = (*inOrder)(pc, ioVec, ioClosure)) >= 0) {
00150       if (r == 0) {
00151         swap_cnt = 1;
00152         morkQS_swap(pc, pd);
00153         pd -= inSize;
00154       }
00155       pc -= inSize;
00156     }
00157     if (pb > pc)
00158       break;
00159     morkQS_swap(pb, pc);
00160     swap_cnt = 1;
00161     pb += inSize;
00162     pc -= inSize;
00163   }
00164   if (swap_cnt == 0) {  /* Switch to insertion sort */
00165     for (pm = ioVec + inSize; pm < ioVec + inCount * inSize; pm += inSize)
00166       for (pl = pm; pl > ioVec && (*inOrder)(pl - inSize, pl, ioClosure) > 0;
00167            pl -= inSize)
00168         morkQS_swap(pl, pl - inSize);
00169     return;
00170   }
00171 
00172   pn = ioVec + inCount * inSize;
00173   r = morkQS_MIN(pa - ioVec, pb - pa);
00174   morkQS_vecswap(ioVec, pb - r, r);
00175   r = morkQS_MIN(pd - pc, (int)(pn - pd - inSize));
00176   morkQS_vecswap(pb, pn - r, r);
00177   if ((r = pb - pa) > (int)inSize)
00178         morkQuickSort(ioVec, r / inSize, inSize, inOrder, ioClosure);
00179   if ((r = pd - pc) > (int)inSize) {
00180     /* Iterate rather than recurse to save stack space */
00181     ioVec = pn - r;
00182     inCount = r / inSize;
00183     goto tailCall;
00184   }
00185 /*    morkQuickSort(pn - r, r / inSize, inSize, inOrder, ioClosure);*/
00186 }
00187