Back to index

lightning-sunbird  0.9+nobinonly
Defines | Functions
morkQuickSort.cpp File Reference
#include "mdb.h"
#include "mork.h"
#include "morkQuickSort.h"

Go to the source code of this file.

Defines

#define INLINE
#define morkQS_swapcode(TYPE, parmi, parmj, n)
#define morkQS_SwapInit(a, es)
#define morkQS_swap(a, b)
#define morkQS_vecswap(a, b, n)   if ((n) > 0) morkQS_swapfunc(a, b, (int)n, swaptype)
#define morkQS_MIN(x, y)   ((x)<(y)?(x):(y))

Functions

static INLINE mork_u1morkQS_med3 (mork_u1 *, mork_u1 *, mork_u1 *, mdbAny_Order, void *)
static INLINE void morkQS_swapfunc (mork_u1 *, mork_u1 *, int, int)
void morkQuickSort (mork_u1 *ioVec, mork_u4 inCount, mork_u4 inSize, mdbAny_Order inOrder, void *ioClosure)

Define Documentation

Definition at line 53 of file morkQuickSort.cpp.

#define morkQS_MIN (   x,
  y 
)    ((x)<(y)?(x):(y))

Definition at line 106 of file morkQuickSort.cpp.

#define morkQS_swap (   a,
  b 
)
Value:
if (swaptype == 0) {        \
    long t = *(long *)(a);      \
    *(long *)(a) = *(long *)(b);    \
    *(long *)(b) = t;      \
  } else            \
    morkQS_swapfunc(a, b, (int)inSize, swaptype)

Definition at line 88 of file morkQuickSort.cpp.

#define morkQS_swapcode (   TYPE,
  parmi,
  parmj,
  n 
)
Value:
{     \
  long i = (n) / sizeof (TYPE);       \
  register TYPE *pi = (TYPE *) (parmi);     \
  register TYPE *pj = (TYPE *) (parmj);     \
  do {             \
    register TYPE  t = *pi;    \
    *pi++ = *pj;        \
    *pj++ = t;        \
        } while (--i > 0);        \
}

Definition at line 65 of file morkQuickSort.cpp.

#define morkQS_SwapInit (   a,
  es 
)
Value:
swaptype = (a - (mork_u1 *)0) % sizeof(long) || \
  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

Definition at line 76 of file morkQuickSort.cpp.

#define morkQS_vecswap (   a,
  b,
  n 
)    if ((n) > 0) morkQS_swapfunc(a, b, (int)n, swaptype)

Definition at line 96 of file morkQuickSort.cpp.


Function Documentation

static INLINE mork_u1 * morkQS_med3 ( mork_u1 a,
mork_u1 b,
mork_u1 c,
mdbAny_Order  cmp,
void closure 
) [static]

Definition at line 99 of file morkQuickSort.cpp.

{
  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 ));
}

Here is the caller graph for this function:

static INLINE void morkQS_swapfunc ( mork_u1 a,
mork_u1 b,
int  n,
int  swaptype 
) [static]

Definition at line 80 of file morkQuickSort.cpp.

{
  if(swaptype <= 1)
    morkQS_swapcode(long, a, b, n)
  else
    morkQS_swapcode(mork_u1, a, b, n)
}
void morkQuickSort ( mork_u1 ioVec,
mork_u4  inCount,
mork_u4  inSize,
mdbAny_Order  inOrder,
void ioClosure 
)

Definition at line 109 of file morkQuickSort.cpp.

{
  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);*/
}

Here is the call graph for this function:

Here is the caller graph for this function: