Back to index

lightning-sunbird  0.9+nobinonly
Defines | Typedefs | Functions
nsQuickSort.cpp File Reference
#include <stdlib.h>
#include "prtypes.h"
#include "nsQuickSort.h"

Go to the source code of this file.

Defines

#define INLINE
#define swapcode(TYPE, parmi, parmj, n)
#define SWAPINIT(a, es)
#define swap(a, b)
#define vecswap(a, b, n)   if ((n) > 0) swapfunc((char *)a, (char *)b, (int)n, swaptype)

Typedefs

typedef int cmp_t (const void *, const void *, void *)

Functions

static INLINE char * med3 (char *, char *, char *, cmp_t *, void *)
static INLINE void swapfunc (char *, char *, int, int)
void NS_QuickSort (void *a, unsigned int n, unsigned int es, cmp_t *cmp, void *data)

Define Documentation

Definition at line 47 of file nsQuickSort.cpp.

#define swap (   a,
  b 
)
Value:
if (swaptype == 0) {                      \
		long t = *(long *)(a);                  \
              *(long *)(a) = *(long *)(b);              \
              *(long *)(b) = t;                  \
       } else						\
		swapfunc((char *)a, (char*)b, (int)es, swaptype)

Definition at line 80 of file nsQuickSort.cpp.

#define 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 57 of file nsQuickSort.cpp.

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

Definition at line 68 of file nsQuickSort.cpp.

#define vecswap (   a,
  b,
  n 
)    if ((n) > 0) swapfunc((char *)a, (char *)b, (int)n, swaptype)

Definition at line 88 of file nsQuickSort.cpp.


Typedef Documentation

typedef int cmp_t(const void *, const void *, void *)

Definition at line 50 of file nsQuickSort.cpp.


Function Documentation

static INLINE char * med3 ( char *  a,
char *  b,
char *  c,
cmp_t cmp,
void data 
) [static]

Definition at line 91 of file nsQuickSort.cpp.

{
       return cmp(a, b, data) < 0 ?
              (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
              :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
}

Here is the caller graph for this function:

void NS_QuickSort ( void a,
unsigned int  n,
unsigned int  es,
cmp_t cmp,
void data 
)

Definition at line 98 of file nsQuickSort.cpp.

{
       char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
       int d, r, swaptype, swap_cnt;

loop:  SWAPINIT(a, es);
       swap_cnt = 0;
       if (n < 7) {
              for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
                     for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
                          pl -= es)
                            swap(pl, pl - es);
              return;
       }
       pm = (char *)a + (n / 2) * es;
       if (n > 7) {
              pl = (char *)a;
              pn = (char *)a + (n - 1) * es;
              if (n > 40) {
                     d = (n / 8) * es;
                     pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
                     pm = med3(pm - d, pm, pm + d, cmp, data);
                     pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
              }
              pm = med3(pl, pm, pn, cmp, data);
       }
       swap(a, pm);
       pa = pb = (char *)a + es;

       pc = pd = (char *)a + (n - 1) * es;
       for (;;) {
              while (pb <= pc && (r = cmp(pb, a, data)) <= 0) {
                     if (r == 0) {
                            swap_cnt = 1;
                            swap(pa, pb);
                            pa += es;
                     }
                     pb += es;
              }
              while (pb <= pc && (r = cmp(pc, a, data)) >= 0) {
                     if (r == 0) {
                            swap_cnt = 1;
                            swap(pc, pd);
                            pd -= es;
                     }
                     pc -= es;
              }
              if (pb > pc)
                     break;
              swap(pb, pc);
              swap_cnt = 1;
              pb += es;
              pc -= es;
       }
       if (swap_cnt == 0) {  /* Switch to insertion sort */
              for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
                     for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
                          pl -= es)
                            swap(pl, pl - es);
              return;
       }

       pn = (char *)a + n * es;
       r = PR_MIN(pa - (char *)a, pb - pa);
       vecswap(a, pb - r, r);
       r = PR_MIN(pd - pc, (int)(pn - pd - es));
       vecswap(pb, pn - r, r);
       if ((r = pb - pa) > (int)es)
        NS_QuickSort(a, r / es, es, cmp, data);
       if ((r = pd - pc) > (int)es) {
              /* Iterate rather than recurse to save stack space */
              a = pn - r;
              n = r / es;
              goto loop;
       }
/*            NS_QuickSort(pn - r, r / es, es, cmp, data);*/
}

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE void swapfunc ( char *  a,
char *  b,
int  n,
int  swaptype 
) [static]

Definition at line 72 of file nsQuickSort.cpp.

{
       if(swaptype <= 1)
              swapcode(long, a, b, n)
       else
              swapcode(char, a, b, n)
}