SDL_qsort.c File Reference

#include "../SDL_internal.h"
#include "SDL_stdinc.h"
#include "SDL_assert.h"

Include dependency graph for SDL_qsort.c:

Go to the source code of this file.

Data Structures
struct	stack_entry

Macros
#define	assert   SDL_assert
#define	malloc   SDL_malloc
#define	free   SDL_free
#define	memcpy   SDL_memcpy
#define	memmove   SDL_memmove
#define	qsortG   SDL_qsort
#define	WORD_BYTES   sizeof(int)
#define	STACK_SIZE   (8*sizeof(size_t))
#define	TRUNC_nonaligned   12
#define	TRUNC_aligned   12
#define	TRUNC_words   12*WORD_BYTES /* nb different meaning */
#define	PIVOT_THRESHOLD   40
#define	pushLeft   {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}
#define	pushRight   {stack[stacktop].first=first;stack[stacktop++].last=llast;}
#define	doLeft   {first=ffirst;llast=last;continue;}
#define	doRight   {ffirst=first;last=llast;continue;}
#define	pop
#define	Recurse(Trunc)
#define	Pivot(swapper, sz)
#define	Partition(swapper, sz)
#define	PreInsertion(swapper, limit, sz)
#define	Insertion(swapper)
#define	SWAP_nonaligned(a, b)
#define	SWAP_aligned(a, b)
#define	SWAP_words(a, b)

Functions
static char *	pivot_big (char *first, char *mid, char *last, size_t size, int compare(const void *, const void *))
static void	qsort_nonaligned (void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
static void	qsort_aligned (void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))
static void	qsort_words (void *base, size_t nmemb, int(*compare)(const void *, const void *))
void	qsortG (void *base, size_t nmemb, size_t size, int(*compare)(const void *, const void *))

Macro Definition Documentation

assert

#define assert   SDL_assert

Definition at line 43 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

doLeft

#define doLeft   {first=ffirst;llast=last;continue;}

Definition at line 190 of file SDL_qsort.c.

doRight

#define doRight   {ffirst=first;last=llast;continue;}

Definition at line 191 of file SDL_qsort.c.

free

#define free   SDL_free

Definition at line 51 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

Insertion

#define Insertion

(

swapper

)

Value:

last=((char*)base)+nmemb*size;          \
  for (first=((char*)base)+size;first!=last;first+=size) {      \
    char *test;                                 \
    /* Find the right place for |first|.        \
     * My apologies for var reuse. */           \
    for (test=first-size;compare(test,first)>0;test-=size) ;    \
    test+=size;                                 \
    if (test!=first) {                          \
      /* Shift everything in [test,first)       \
       * up by one, and place |first|           \
       * where |test| is. */                    \
      memcpy(pivot,first,size);                 \
      memmove(test+size,test,first-test);       \
      memcpy(test,pivot,size);                  \
    }                                           \
  }

Definition at line 330 of file SDL_qsort.c.

Referenced by qsort_aligned(), and qsort_nonaligned().

malloc

#define malloc   SDL_malloc

Definition at line 47 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

memcpy

#define memcpy   SDL_memcpy

Definition at line 55 of file SDL_qsort.c.

Referenced by qsort_aligned(), and qsort_nonaligned().

memmove

#define memmove   SDL_memmove

Definition at line 59 of file SDL_qsort.c.

Referenced by SDL_memmove().

Partition

#define Partition	(		swapper,
			sz
	)

Value:

{                       \
  do {                                          \
    while (compare(first,pivot)<0) first+=sz;   \
    while (compare(pivot,last)<0) last-=sz;     \
    if (first<last) {                           \
      swapper(first,last);                      \
      first+=sz; last-=sz; }                    \
    else if (first==last) { first+=sz; last-=sz; break; }\
  } while (first<=last);                        \
}

Definition at line 301 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

Pivot

#define Pivot	(		swapper,
			sz
	)

Value:

if ((size_t)(last-first)>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\
  else {        \
    if (compare(first,mid)<0) {                 \
      if (compare(mid,last)>0) {                \
        swapper(mid,last);                      \
        if (compare(first,mid)>0) swapper(first,mid);\
      }                                         \
    }                                           \
    else {                                      \
      if (compare(mid,last)>0) swapper(first,last)\
      else {                                    \
        swapper(first,mid);                     \
        if (compare(mid,last)>0) swapper(mid,last);\
      }                                         \
    }                                           \
    first+=sz; last-=sz;                        \
  }

Definition at line 277 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

PIVOT_THRESHOLD

#define PIVOT_THRESHOLD   40

Definition at line 185 of file SDL_qsort.c.

pop

#define pop

Value:

{if (--stacktop<0) break;\
  first=ffirst=stack[stacktop].first;\
  last=llast=stack[stacktop].last;\
  continue;}

Definition at line 192 of file SDL_qsort.c.

Referenced by CPU_haveCPUID(), SDL_SoftStretch(), and SDL_tolower().

PreInsertion

#define PreInsertion	(		swapper,
			limit,
			sz
	)

Value:

first=base;                                     \
  last=first + ((nmemb>limit ? limit : nmemb)-1)*sz;\
  while (last!=base) {                          \
    if (compare(first,last)>0) first=last;      \
    last-=sz; }                                 \
  if (first!=base) swapper(first,(char*)base);

Definition at line 321 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

pushLeft

#define pushLeft   {stack[stacktop].first=ffirst;stack[stacktop++].last=last;}

Definition at line 188 of file SDL_qsort.c.

pushRight

#define pushRight   {stack[stacktop].first=first;stack[stacktop++].last=llast;}

Definition at line 189 of file SDL_qsort.c.

qsortG

#define qsortG   SDL_qsort

Definition at line 63 of file SDL_qsort.c.

Recurse

#define Recurse

(

Trunc

)

Value:

{ size_t l=last-ffirst,r=llast-first;   \
        if (l<Trunc) {                          \
          if (r>=Trunc) doRight                 \
          else pop                              \
        }                                       \
        else if (l<=r) { pushLeft; doRight }    \
        else if (r>=Trunc) { pushRight; doLeft }\
        else doLeft                             \
      }

Definition at line 265 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

STACK_SIZE

#define STACK_SIZE   (8*sizeof(size_t))

Definition at line 168 of file SDL_qsort.c.

Referenced by qsort_aligned(), qsort_nonaligned(), and qsort_words().

SWAP_aligned

#define SWAP_aligned	(		a,
			b
	)

Value:

{ \
  register int *aa=(int*)(a),*bb=(int*)(b); \
  register size_t sz=size; \
  do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz-=WORD_BYTES); }

Definition at line 353 of file SDL_qsort.c.

Referenced by qsort_aligned().

SWAP_nonaligned

#define SWAP_nonaligned	(		a,
			b
	)

Value:

{ \
  register char *aa=(a),*bb=(b); \
  register size_t sz=size; \
  do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }

Definition at line 348 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

SWAP_words

#define SWAP_words	(		a,
			b
	)

Value:

{ \
  register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }

Definition at line 358 of file SDL_qsort.c.

Referenced by qsort_words().

TRUNC_aligned

#define TRUNC_aligned   12

Definition at line 178 of file SDL_qsort.c.

Referenced by qsort_aligned().

TRUNC_nonaligned

#define TRUNC_nonaligned   12

Definition at line 177 of file SDL_qsort.c.

Referenced by qsort_nonaligned().

TRUNC_words

#define TRUNC_words   12*WORD_BYTES /* nb different meaning */

Definition at line 179 of file SDL_qsort.c.

Referenced by qsort_words().

WORD_BYTES

#define WORD_BYTES   sizeof(int)

Definition at line 163 of file SDL_qsort.c.

Referenced by qsort_words(), and qsortG().

Function Documentation

pivot_big()

static char* pivot_big ( char *  first, char *  mid, char *  last, size_t  size, int   compareconst void *, const void *  )

static

Definition at line 363 of file SDL_qsort.c.

References d.

                                                                 {
  size_t d=(((last-first)/size)>>3)*size;
#ifdef DEBUG_QSORT
fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((last-first+1)/size));
#endif
  char *m1,*m2,*m3;
  { char *a=first, *b=first+d, *c=first+2*d;
#ifdef DEBUG_QSORT
fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m1 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
  { char *a=mid-d, *b=mid, *c=mid+d;
#ifdef DEBUG_QSORT
fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m2 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
  { char *a=last-2*d, *b=last-d, *c=last;
#ifdef DEBUG_QSORT
fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c);
#endif
    m3 = compare(a,b)<0 ?
           (compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a))
         : (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b));
  }
#ifdef DEBUG_QSORT
fprintf(stderr,"-> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3);
#endif
  return compare(m1,m2)<0 ?
           (compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1))
         : (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2));
}

qsort_aligned()

static void qsort_aligned ( void *  base, size_t  nmemb, size_t  size, int(*)(const void *, const void *)  compare  )

static

Definition at line 435 of file SDL_qsort.c.

References assert, free, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_aligned, and TRUNC_aligned.

Referenced by qsortG().

                                                       {

  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(size);
  size_t trunc=TRUNC_aligned*size;
  assert(pivot!=0);

  first=(char*)base; last=first+(nmemb-1)*size;

  if ((size_t)(last-first)>=trunc) {
    char *ffirst=first,*llast=last;
    while (1) {
      /* Select pivot */
      { char * mid=first+size*((last-first)/size >> 1);
        Pivot(SWAP_aligned,size);
        memcpy(pivot,mid,size);
      }
      /* Partition. */
      Partition(SWAP_aligned,size);
      /* Prepare to recurse/iterate. */
      Recurse(trunc)
    }
  }
  PreInsertion(SWAP_aligned,TRUNC_aligned,size);
  Insertion(SWAP_aligned);
  free(pivot);
}

qsort_nonaligned()

static void qsort_nonaligned ( void *  base, size_t  nmemb, size_t  size, int(*)(const void *, const void *)  compare  )

static

Definition at line 404 of file SDL_qsort.c.

References assert, free, Insertion, malloc, memcpy, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_nonaligned, and TRUNC_nonaligned.

Referenced by qsortG().

                                                       {

  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(size);
  size_t trunc=TRUNC_nonaligned*size;
  assert(pivot!=0);

  first=(char*)base; last=first+(nmemb-1)*size;

  if ((size_t)(last-first)>=trunc) {
    char *ffirst=first, *llast=last;
    while (1) {
      /* Select pivot */
      { char * mid=first+size*((last-first)/size >> 1);
        Pivot(SWAP_nonaligned,size);
        memcpy(pivot,mid,size);
      }
      /* Partition. */
      Partition(SWAP_nonaligned,size);
      /* Prepare to recurse/iterate. */
      Recurse(trunc)
    }
  }
  PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size);
  Insertion(SWAP_nonaligned);
  free(pivot);
}

qsort_words()

static void qsort_words ( void *  base, size_t  nmemb, int(*)(const void *, const void *)  compare  )

static

Definition at line 466 of file SDL_qsort.c.

References assert, free, malloc, Partition, Pivot, PreInsertion, Recurse, STACK_SIZE, SWAP_words, TRUNC_words, and WORD_BYTES.

Referenced by qsortG().

                                                       {

  stack_entry stack[STACK_SIZE];
  int stacktop=0;
  char *first,*last;
  char *pivot=malloc(WORD_BYTES);
  assert(pivot!=0);

  first=(char*)base; last=first+(nmemb-1)*WORD_BYTES;

  if (last-first>=TRUNC_words) {
    char *ffirst=first, *llast=last;
    while (1) {
#ifdef DEBUG_QSORT
fprintf(stderr,"Doing %d:%d: ",
        (first-(char*)base)/WORD_BYTES,
        (last-(char*)base)/WORD_BYTES);
#endif
      /* Select pivot */
      { char * mid=first+WORD_BYTES*((last-first) / (2*WORD_BYTES));
        Pivot(SWAP_words,WORD_BYTES);
        *(int*)pivot=*(int*)mid;
#ifdef DEBUG_QSORT
fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)-((int*)base)), *(int*)mid);
#endif
      }
      /* Partition. */
      Partition(SWAP_words,WORD_BYTES);
#ifdef DEBUG_QSORT
fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first-(char*)base)/4lu, (last-(char*)base)/4lu);
#endif
      /* Prepare to recurse/iterate. */
      Recurse(TRUNC_words)
    }
  }
  PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES);
  /* Now do insertion sort. */
  last=((char*)base)+nmemb*WORD_BYTES;
  for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) {
    /* Find the right place for |first|. My apologies for var reuse */
    int *pl=(int*)(first-WORD_BYTES),*pr=(int*)first;
    *(int*)pivot=*(int*)first;
    for (;compare(pl,pivot)>0;pr=pl,--pl) {
      *pr=*pl; }
    if (pr!=(int*)first) *pr=*(int*)pivot;
  }
  free(pivot);
}

qsortG()

void qsortG	(	void *	base,
		size_t	nmemb,
		size_t	size,
		int(*)(const void *, const void *)	compare
	)

Definition at line 518 of file SDL_qsort.c.

References qsort_aligned(), qsort_nonaligned(), qsort_words(), and WORD_BYTES.

                                                       {

  if (nmemb<=1) return;
  if (((size_t)base|size)&(WORD_BYTES-1))
    qsort_nonaligned(base,nmemb,size,compare);
  else if (size!=WORD_BYTES)
    qsort_aligned(base,nmemb,size,compare);
  else
    qsort_words(base,nmemb,compare);
}