Back to index

lightning-sunbird  0.9+nobinonly
Functions
morkQuickSort.h File Reference
#include "mdb.h"
#include "mork.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void morkQuickSort (mork_u1 *ioVec, mork_u4 inCount, mork_u4 inSize, mdbAny_Order inOrder, void *ioClosure)

Function Documentation

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: