summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/SDL2/src/stdlib/SDL_qsort.c
diff options
context:
space:
mode:
author Miodrag Milanović <mmicko@gmail.com>2023-02-26 19:40:37 +0100
committer GitHub <noreply@github.com>2023-02-27 05:40:37 +1100
commitbd59a0d447b861982429905f186dee8b12f2e777 (patch)
treedc6341c8fb098818039127f758cf3eb0fade986a /3rdparty/SDL2/src/stdlib/SDL_qsort.c
parent28b03e92a84daf79eb3cef75c51c014b2f57807b (diff)
Removed local copy of SDL source and update Android build support. (#10899)
* Removed SDL2 source. * Updated gradle. * Updated SDL2 Java support glue code. * Increased minimum supported Android API version to 24. * Updated required asset files for Android app. * Added proper tag for Android logging. * Added SDL2 hint to make BGFX work on Android.
Diffstat (limited to '3rdparty/SDL2/src/stdlib/SDL_qsort.c')
-rw-r--r--3rdparty/SDL2/src/stdlib/SDL_qsort.c534
1 files changed, 0 insertions, 534 deletions
diff --git a/3rdparty/SDL2/src/stdlib/SDL_qsort.c b/3rdparty/SDL2/src/stdlib/SDL_qsort.c
deleted file mode 100644
index 2ef33b15ea1..00000000000
--- a/3rdparty/SDL2/src/stdlib/SDL_qsort.c
+++ /dev/null
@@ -1,534 +0,0 @@
-/*
- Simple DirectMedia Layer
- Copyright (C) 1997-2016 Sam Lantinga <slouken@libsdl.org>
-
- This software is provided 'as-is', without any express or implied
- warranty. In no event will the authors be held liable for any damages
- arising from the use of this software.
-
- Permission is granted to anyone to use this software for any purpose,
- including commercial applications, and to alter it and redistribute it
- freely, subject to the following restrictions:
-
- 1. The origin of this software must not be misrepresented; you must not
- claim that you wrote the original software. If you use this software
- in a product, an acknowledgment in the product documentation would be
- appreciated but is not required.
- 2. Altered source versions must be plainly marked as such, and must not be
- misrepresented as being the original software.
- 3. This notice may not be removed or altered from any source distribution.
-*/
-
-#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS)
-#define SDL_DISABLE_ANALYZE_MACROS 1
-#endif
-
-#include "../SDL_internal.h"
-
-#include "SDL_stdinc.h"
-#include "SDL_assert.h"
-
-#if defined(HAVE_QSORT)
-void
-SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *))
-{
- qsort(base, nmemb, size, compare);
-}
-
-#else
-
-#ifdef assert
-#undef assert
-#endif
-#define assert SDL_assert
-#ifdef malloc
-#undef malloc
-#endif
-#define malloc SDL_malloc
-#ifdef free
-#undef free
-#endif
-#define free SDL_free
-#ifdef memcpy
-#undef memcpy
-#endif
-#define memcpy SDL_memcpy
-#ifdef memmove
-#undef memmove
-#endif
-#define memmove SDL_memmove
-#ifdef qsortG
-#undef qsortG
-#endif
-#define qsortG SDL_qsort
-
-/*
-This code came from Gareth McCaughan, under the zlib license.
-Specifically this: https://www.mccaughan.org.uk/software/qsort.c-1.14
-
-Everything below this comment until the HAVE_QSORT #endif was from Gareth
-(any minor changes will be noted inline).
-
-Thank you to Gareth for relicensing this code under the zlib license for our
-benefit!
-
---ryan.
-*/
-
-/* This is a drop-in replacement for the C library's |qsort()| routine.
- *
- * It is intended for use where you know or suspect that your
- * platform's qsort is bad. If that isn't the case, then you
- * should probably use the qsort your system gives you in preference
- * to mine -- it will likely have been tested and tuned better.
- *
- * Features:
- * - Median-of-three pivoting (and more)
- * - Truncation and final polishing by a single insertion sort
- * - Early truncation when no swaps needed in pivoting step
- * - Explicit recursion, guaranteed not to overflow
- * - A few little wrinkles stolen from the GNU |qsort()|.
- * (For the avoidance of doubt, no code was stolen, only
- * broad ideas.)
- * - separate code for non-aligned / aligned / word-size objects
- *
- * Earlier releases of this code used an idiosyncratic licence
- * I wrote myself, because I'm an idiot. The code is now released
- * under the "zlib/libpng licence"; you will find the actual
- * terms in the next comment. I request (but do not require)
- * that if you make any changes beyond the name of the exported
- * routine and reasonable tweaks to the TRUNC_* and
- * PIVOT_THRESHOLD values, you modify the _ID string so as
- * to make it clear that you have changed the code.
- *
- * If you find problems with this code, or find ways of
- * making it significantly faster, please let me know!
- * My e-mail address, valid as of early 2016 and for the
- * foreseeable future, is
- * gareth.mccaughan@pobox.com
- * Thanks!
- *
- * Gareth McCaughan
- */
-
-/* Copyright (c) 1998-2016 Gareth McCaughan
- *
- * This software is provided 'as-is', without any express or implied
- * warranty. In no event will the authors be held liable for any
- * damages arising from the use of this software.
- *
- * Permission is granted to anyone to use this software for any purpose,
- * including commercial applications, and to alter it and redistribute it
- * freely, subject to the following restrictions:
- *
- * 1. The origin of this software must not be misrepresented;
- * you must not claim that you wrote the original software.
- * If you use this software in a product, an acknowledgment
- * in the product documentation would be appreciated but
- * is not required.
- *
- * 2. Altered source versions must be plainly marked as such,
- * and must not be misrepresented as being the original software.
- *
- * 3. This notice may not be removed or altered from any source
- * distribution.
- */
-
-/* Revision history since release:
- * 1998-03-19 v1.12 First release I have any records of.
- * 2007-09-02 v1.13 Fix bug kindly reported by Dan Bodoh
- * (premature termination of recursion).
- * Add a few clarifying comments.
- * Minor improvements to debug output.
- * 2016-02-21 v1.14 Replace licence with 2-clause BSD,
- * and clarify a couple of things in
- * comments. No code changes.
- */
-
-/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
-#if 0
-#include <assert.h>
-#include <stdlib.h>
-#include <string.h>
-
-#define DEBUG_QSORT
-
-static char _ID[]="<qsort.c gjm 1.14 2016-02-21>";
-#endif
-/* END SDL CHANGE ... commented this out with an #if 0 block. --ryan. */
-
-/* How many bytes are there per word? (Must be a power of 2,
- * and must in fact equal sizeof(int).)
- */
-#define WORD_BYTES sizeof(int)
-
-/* How big does our stack need to be? Answer: one entry per
- * bit in a |size_t|.
- */
-#define STACK_SIZE (8*sizeof(size_t))
-
-/* Different situations have slightly different requirements,
- * and we make life epsilon easier by using different truncation
- * points for the three different cases.
- * So far, I have tuned TRUNC_words and guessed that the same
- * value might work well for the other two cases. Of course
- * what works well on my machine might work badly on yours.
- */
-#define TRUNC_nonaligned 12
-#define TRUNC_aligned 12
-#define TRUNC_words 12*WORD_BYTES /* nb different meaning */
-
-/* We use a simple pivoting algorithm for shortish sub-arrays
- * and a more complicated one for larger ones. The threshold
- * is PIVOT_THRESHOLD.
- */
-#define PIVOT_THRESHOLD 40
-
-typedef struct { char * first; char * last; } stack_entry;
-#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 {if (--stacktop<0) break;\
- first=ffirst=stack[stacktop].first;\
- last=llast=stack[stacktop].last;\
- continue;}
-
-/* Some comments on the implementation.
- * 1. When we finish partitioning the array into "low"
- * and "high", we forget entirely about short subarrays,
- * because they'll be done later by insertion sort.
- * Doing lots of little insertion sorts might be a win
- * on large datasets for locality-of-reference reasons,
- * but it makes the code much nastier and increases
- * bookkeeping overhead.
- * 2. We always save the shorter and get to work on the
- * longer. This guarantees that every time we push
- * an item onto the stack its size is <= 1/2 of that
- * of its parent; so the stack can't need more than
- * log_2(max-array-size) entries.
- * 3. We choose a pivot by looking at the first, last
- * and middle elements. We arrange them into order
- * because it's easy to do that in conjunction with
- * choosing the pivot, and it makes things a little
- * easier in the partitioning step. Anyway, the pivot
- * is the middle of these three. It's still possible
- * to construct datasets where the algorithm takes
- * time of order n^2, but it simply never happens in
- * practice.
- * 3' Newsflash: On further investigation I find that
- * it's easy to construct datasets where median-of-3
- * simply isn't good enough. So on large-ish subarrays
- * we do a more sophisticated pivoting: we take three
- * sets of 3 elements, find their medians, and then
- * take the median of those.
- * 4. We copy the pivot element to a separate place
- * because that way we can always do our comparisons
- * directly against a pointer to that separate place,
- * and don't have to wonder "did we move the pivot
- * element?". This makes the inner loop better.
- * 5. It's possible to make the pivoting even more
- * reliable by looking at more candidates when n
- * is larger. (Taking this to its logical conclusion
- * results in a variant of quicksort that doesn't
- * have that n^2 worst case.) However, the overhead
- * from the extra bookkeeping means that it's just
- * not worth while.
- * 6. This is pretty clean and portable code. Here are
- * all the potential portability pitfalls and problems
- * I know of:
- * - In one place (the insertion sort) I construct
- * a pointer that points just past the end of the
- * supplied array, and assume that (a) it won't
- * compare equal to any pointer within the array,
- * and (b) it will compare equal to a pointer
- * obtained by stepping off the end of the array.
- * These might fail on some segmented architectures.
- * - I assume that there are 8 bits in a |char| when
- * computing the size of stack needed. This would
- * fail on machines with 9-bit or 16-bit bytes.
- * - I assume that if |((int)base&(sizeof(int)-1))==0|
- * and |(size&(sizeof(int)-1))==0| then it's safe to
- * get at array elements via |int*|s, and that if
- * actually |size==sizeof(int)| as well then it's
- * safe to treat the elements as |int|s. This might
- * fail on systems that convert pointers to integers
- * in non-standard ways.
- * - I assume that |8*sizeof(size_t)<=INT_MAX|. This
- * would be false on a machine with 8-bit |char|s,
- * 16-bit |int|s and 4096-bit |size_t|s. :-)
- */
-
-/* The recursion logic is the same in each case.
- * We keep chopping up until we reach subarrays of size
- * strictly less than Trunc; we leave these unsorted. */
-#define Recurse(Trunc) \
- { 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 \
- }
-
-/* and so is the pivoting logic (note: last is inclusive): */
-#define Pivot(swapper,sz) \
- if (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; \
- }
-
-#ifdef DEBUG_QSORT
-#include <stdio.h>
-#endif
-
-/* and so is the partitioning logic: */
-#define Partition(swapper,sz) { \
- 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); \
-}
-
-/* and so is the pre-insertion-sort operation of putting
- * the smallest element into place as a sentinel.
- * Doing this makes the inner loop nicer. I got this
- * idea from the GNU implementation of qsort().
- * We find the smallest element from the first |nmemb|,
- * or the first |limit|, whichever is smaller;
- * therefore we must have ensured that the globally smallest
- * element is in the first |limit|.
- */
-#define PreInsertion(swapper,limit,sz) \
- 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);
-
-/* and so is the insertion sort, in the first two cases: */
-#define Insertion(swapper) \
- 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); \
- } \
- }
-
-#define SWAP_nonaligned(a,b) { \
- register char *aa=(a),*bb=(b); \
- register size_t sz=size; \
- do { register char t=*aa; *aa++=*bb; *bb++=t; } while (--sz); }
-
-#define SWAP_aligned(a,b) { \
- 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); }
-
-#define SWAP_words(a,b) { \
- register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; }
-
-/* ---------------------------------------------------------------------- */
-
-static char * pivot_big(char *first, char *mid, char *last, size_t size,
- int compare(const void *, const void *)) {
- int 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));
-}
-
-/* ---------------------------------------------------------------------- */
-
-static void qsort_nonaligned(void *base, size_t nmemb, size_t size,
- int (*compare)(const void *, const void *)) {
-
- 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 (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);
-}
-
-static void qsort_aligned(void *base, size_t nmemb, size_t size,
- int (*compare)(const void *, const void *)) {
-
- 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 (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);
-}
-
-static void qsort_words(void *base, size_t nmemb,
- int (*compare)(const void *, const void *)) {
-
- 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);
-}
-
-/* ---------------------------------------------------------------------- */
-
-extern void qsortG(void *base, size_t nmemb, size_t size,
- int (*compare)(const void *, const void *)) {
-
- if (nmemb<=1) return;
- if (((int)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);
-}
-
-
-#endif /* HAVE_QSORT */
-
-/* vi: set ts=4 sw=4 expandtab: */
-