author  Ryan C. Gordon <icculus@icculus.org> 
Mon, 01 Aug 2016 00:20:47 0400  
changeset 10214  4f29bb9e19c3 
parent 10116  418691d83f6a 
permissions  rwrr 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

1 
/* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

2 
Simple DirectMedia Layer 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

3 
Copyright (C) 19972016 Sam Lantinga <slouken@libsdl.org> 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

4 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

5 
This software is provided 'asis', without any express or implied 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

6 
warranty. In no event will the authors be held liable for any damages 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

7 
arising from the use of this software. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

8 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

9 
Permission is granted to anyone to use this software for any purpose, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

10 
including commercial applications, and to alter it and redistribute it 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

11 
freely, subject to the following restrictions: 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

12 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

13 
1. The origin of this software must not be misrepresented; you must not 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

14 
claim that you wrote the original software. If you use this software 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

15 
in a product, an acknowledgment in the product documentation would be 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

16 
appreciated but is not required. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

17 
2. Altered source versions must be plainly marked as such, and must not be 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

18 
misrepresented as being the original software. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

19 
3. This notice may not be removed or altered from any source distribution. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

20 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

21 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

22 
#if defined(__clang_analyzer__) && !defined(SDL_DISABLE_ANALYZE_MACROS) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

23 
#define SDL_DISABLE_ANALYZE_MACROS 1 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

24 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

25 

8093
b43765095a6f
Make internal SDL sources include SDL_internal.h instead of SDL_config.h
Ryan C. Gordon <icculus@icculus.org>
parents:
7351
diff
changeset

26 
#include "../SDL_internal.h" 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

27 

1354
22f39393668a
Fixed build problem with SDL_string.c
Sam Lantinga <slouken@libsdl.org>
parents:
1337
diff
changeset

28 
#include "SDL_stdinc.h" 
6281
e46d6f4b469e
Replaced some assert macros with SDL_assert.
Ryan C. Gordon <icculus@icculus.org>
parents:
3616
diff
changeset

29 
#include "SDL_assert.h" 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

30 

7351
668a3dc28361
Removed the inline functions from SDL_stdinc.h
Sam Lantinga <slouken@libsdl.org>
parents:
7003
diff
changeset

31 
#if defined(HAVE_QSORT) 
7003
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

32 
void 
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

33 
SDL_qsort(void *base, size_t nmemb, size_t size, int (*compare) (const void *, const void *)) 
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

34 
{ 
7351
668a3dc28361
Removed the inline functions from SDL_stdinc.h
Sam Lantinga <slouken@libsdl.org>
parents:
7003
diff
changeset

35 
qsort(base, nmemb, size, compare); 
7003
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

36 
} 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

37 

7003
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

38 
#else 
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

39 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

40 
#ifdef assert 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

41 
#undef assert 
3616
0aaa7f52d1c6
Merged r4710:4711 from branches/SDL1.2: Mac OS X SDL_stdlib qsort build fixes.
Ryan C. Gordon <icculus@icculus.org>
parents:
3162
diff
changeset

42 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

43 
#define assert SDL_assert 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

44 
#ifdef malloc 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

45 
#undef malloc 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

46 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

47 
#define malloc SDL_malloc 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

48 
#ifdef free 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

49 
#undef free 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

50 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

51 
#define free SDL_free 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

52 
#ifdef memcpy 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

53 
#undef memcpy 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

54 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

55 
#define memcpy SDL_memcpy 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

56 
#ifdef memmove 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

57 
#undef memmove 
10069
ba33b870b45c
Patched to compile on Visual Studio.
Ryan C. Gordon <icculus@icculus.org>
parents:
10068
diff
changeset

58 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

59 
#define memmove SDL_memmove 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

60 
#ifdef qsortG 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

61 
#undef qsortG 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

62 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

63 
#define qsortG SDL_qsort 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

64 

19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

65 
/* 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

66 
This code came from Gareth McCaughan, under the zlib license. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

67 
Specifically this: https://www.mccaughan.org.uk/software/qsort.c1.14 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

68 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

69 
Everything below this comment until the HAVE_QSORT #endif was from Gareth 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

70 
(any minor changes will be noted inline). 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

71 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

72 
Thank you to Gareth for relicensing this code under the zlib license for our 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

73 
benefit! 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

74 

10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

75 
ryan. 
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

76 
*/ 
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

77 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

78 
/* This is a dropin replacement for the C library's qsort() routine. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

79 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

80 
* It is intended for use where you know or suspect that your 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

81 
* platform's qsort is bad. If that isn't the case, then you 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

82 
* should probably use the qsort your system gives you in preference 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

83 
* to mine  it will likely have been tested and tuned better. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

84 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

85 
* Features: 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

86 
*  Medianofthree pivoting (and more) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

87 
*  Truncation and final polishing by a single insertion sort 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

88 
*  Early truncation when no swaps needed in pivoting step 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

89 
*  Explicit recursion, guaranteed not to overflow 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

90 
*  A few little wrinkles stolen from the GNU qsort(). 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

91 
* (For the avoidance of doubt, no code was stolen, only 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

92 
* broad ideas.) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

93 
*  separate code for nonaligned / aligned / wordsize objects 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

94 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

95 
* Earlier releases of this code used an idiosyncratic licence 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

96 
* I wrote myself, because I'm an idiot. The code is now released 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

97 
* under the "zlib/libpng licence"; you will find the actual 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

98 
* terms in the next comment. I request (but do not require) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

99 
* that if you make any changes beyond the name of the exported 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

100 
* routine and reasonable tweaks to the TRUNC_* and 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

101 
* PIVOT_THRESHOLD values, you modify the _ID string so as 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

102 
* to make it clear that you have changed the code. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

103 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

104 
* If you find problems with this code, or find ways of 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

105 
* making it significantly faster, please let me know! 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

106 
* My email address, valid as of early 2016 and for the 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

107 
* foreseeable future, is 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

108 
* gareth.mccaughan@pobox.com 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

109 
* Thanks! 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

110 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

111 
* Gareth McCaughan 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

112 
*/ 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

113 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

114 
/* Copyright (c) 19982016 Gareth McCaughan 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

115 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

116 
* This software is provided 'asis', without any express or implied 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

117 
* warranty. In no event will the authors be held liable for any 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

118 
* damages arising from the use of this software. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

119 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

120 
* Permission is granted to anyone to use this software for any purpose, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

121 
* including commercial applications, and to alter it and redistribute it 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

122 
* freely, subject to the following restrictions: 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

123 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

124 
* 1. The origin of this software must not be misrepresented; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

125 
* you must not claim that you wrote the original software. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

126 
* If you use this software in a product, an acknowledgment 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

127 
* in the product documentation would be appreciated but 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

128 
* is not required. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

129 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

130 
* 2. Altered source versions must be plainly marked as such, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

131 
* and must not be misrepresented as being the original software. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

132 
* 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

133 
* 3. This notice may not be removed or altered from any source 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

134 
* distribution. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

135 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

136 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

137 
/* Revision history since release: 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

138 
* 19980319 v1.12 First release I have any records of. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

139 
* 20070902 v1.13 Fix bug kindly reported by Dan Bodoh 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

140 
* (premature termination of recursion). 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

141 
* Add a few clarifying comments. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

142 
* Minor improvements to debug output. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

143 
* 20160221 v1.14 Replace licence with 2clause BSD, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

144 
* and clarify a couple of things in 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

145 
* comments. No code changes. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

146 
*/ 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

147 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

148 
/* BEGIN SDL CHANGE ... commented this out with an #if 0 block. ryan. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

149 
#if 0 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

150 
#include <assert.h> 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

151 
#include <stdlib.h> 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

152 
#include <string.h> 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

153 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

154 
#define DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

155 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

156 
static char _ID[]="<qsort.c gjm 1.14 20160221>"; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

157 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

158 
/* END SDL CHANGE ... commented this out with an #if 0 block. ryan. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

159 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

160 
/* How many bytes are there per word? (Must be a power of 2, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

161 
* and must in fact equal sizeof(int).) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

162 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

163 
#define WORD_BYTES sizeof(int) 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

164 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

165 
/* How big does our stack need to be? Answer: one entry per 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

166 
* bit in a size_t. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

167 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

168 
#define STACK_SIZE (8*sizeof(size_t)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

169 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

170 
/* Different situations have slightly different requirements, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

171 
* and we make life epsilon easier by using different truncation 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

172 
* points for the three different cases. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

173 
* So far, I have tuned TRUNC_words and guessed that the same 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

174 
* value might work well for the other two cases. Of course 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

175 
* what works well on my machine might work badly on yours. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

176 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

177 
#define TRUNC_nonaligned 12 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

178 
#define TRUNC_aligned 12 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

179 
#define TRUNC_words 12*WORD_BYTES /* nb different meaning */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

180 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

181 
/* We use a simple pivoting algorithm for shortish subarrays 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

182 
* and a more complicated one for larger ones. The threshold 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

183 
* is PIVOT_THRESHOLD. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

184 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

185 
#define PIVOT_THRESHOLD 40 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

186 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

187 
typedef struct { char * first; char * last; } stack_entry; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

188 
#define pushLeft {stack[stacktop].first=ffirst;stack[stacktop++].last=last;} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

189 
#define pushRight {stack[stacktop].first=first;stack[stacktop++].last=llast;} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

190 
#define doLeft {first=ffirst;llast=last;continue;} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

191 
#define doRight {ffirst=first;last=llast;continue;} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

192 
#define pop {if (stacktop<0) break;\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

193 
first=ffirst=stack[stacktop].first;\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

194 
last=llast=stack[stacktop].last;\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

195 
continue;} 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

196 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

197 
/* Some comments on the implementation. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

198 
* 1. When we finish partitioning the array into "low" 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

199 
* and "high", we forget entirely about short subarrays, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

200 
* because they'll be done later by insertion sort. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

201 
* Doing lots of little insertion sorts might be a win 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

202 
* on large datasets for localityofreference reasons, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

203 
* but it makes the code much nastier and increases 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

204 
* bookkeeping overhead. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

205 
* 2. We always save the shorter and get to work on the 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

206 
* longer. This guarantees that every time we push 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

207 
* an item onto the stack its size is <= 1/2 of that 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

208 
* of its parent; so the stack can't need more than 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

209 
* log_2(maxarraysize) entries. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

210 
* 3. We choose a pivot by looking at the first, last 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

211 
* and middle elements. We arrange them into order 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

212 
* because it's easy to do that in conjunction with 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

213 
* choosing the pivot, and it makes things a little 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

214 
* easier in the partitioning step. Anyway, the pivot 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

215 
* is the middle of these three. It's still possible 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

216 
* to construct datasets where the algorithm takes 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

217 
* time of order n^2, but it simply never happens in 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

218 
* practice. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

219 
* 3' Newsflash: On further investigation I find that 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

220 
* it's easy to construct datasets where medianof3 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

221 
* simply isn't good enough. So on largeish subarrays 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

222 
* we do a more sophisticated pivoting: we take three 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

223 
* sets of 3 elements, find their medians, and then 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

224 
* take the median of those. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

225 
* 4. We copy the pivot element to a separate place 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

226 
* because that way we can always do our comparisons 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

227 
* directly against a pointer to that separate place, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

228 
* and don't have to wonder "did we move the pivot 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

229 
* element?". This makes the inner loop better. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

230 
* 5. It's possible to make the pivoting even more 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

231 
* reliable by looking at more candidates when n 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

232 
* is larger. (Taking this to its logical conclusion 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

233 
* results in a variant of quicksort that doesn't 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

234 
* have that n^2 worst case.) However, the overhead 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

235 
* from the extra bookkeeping means that it's just 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

236 
* not worth while. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

237 
* 6. This is pretty clean and portable code. Here are 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

238 
* all the potential portability pitfalls and problems 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

239 
* I know of: 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

240 
*  In one place (the insertion sort) I construct 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

241 
* a pointer that points just past the end of the 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

242 
* supplied array, and assume that (a) it won't 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

243 
* compare equal to any pointer within the array, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

244 
* and (b) it will compare equal to a pointer 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

245 
* obtained by stepping off the end of the array. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

246 
* These might fail on some segmented architectures. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

247 
*  I assume that there are 8 bits in a char when 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

248 
* computing the size of stack needed. This would 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

249 
* fail on machines with 9bit or 16bit bytes. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

250 
*  I assume that if ((int)base&(sizeof(int)1))==0 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

251 
* and (size&(sizeof(int)1))==0 then it's safe to 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

252 
* get at array elements via int*s, and that if 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

253 
* actually size==sizeof(int) as well then it's 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

254 
* safe to treat the elements as ints. This might 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

255 
* fail on systems that convert pointers to integers 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

256 
* in nonstandard ways. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

257 
*  I assume that 8*sizeof(size_t)<=INT_MAX. This 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

258 
* would be false on a machine with 8bit chars, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

259 
* 16bit ints and 4096bit size_ts. :) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

260 
*/ 
10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

261 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

262 
/* The recursion logic is the same in each case. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

263 
* We keep chopping up until we reach subarrays of size 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

264 
* strictly less than Trunc; we leave these unsorted. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

265 
#define Recurse(Trunc) \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

266 
{ size_t l=lastffirst,r=llastfirst; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

267 
if (l<Trunc) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

268 
if (r>=Trunc) doRight \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

269 
else pop \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

270 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

271 
else if (l<=r) { pushLeft; doRight } \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

272 
else if (r>=Trunc) { pushRight; doLeft }\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

273 
else doLeft \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

274 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

275 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

276 
/* and so is the pivoting logic (note: last is inclusive): */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

277 
#define Pivot(swapper,sz) \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

278 
if (lastfirst>PIVOT_THRESHOLD*sz) mid=pivot_big(first,mid,last,sz,compare);\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

279 
else { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

280 
if (compare(first,mid)<0) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

281 
if (compare(mid,last)>0) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

282 
swapper(mid,last); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

283 
if (compare(first,mid)>0) swapper(first,mid);\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

284 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

285 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

286 
else { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

287 
if (compare(mid,last)>0) swapper(first,last)\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

288 
else { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

289 
swapper(first,mid); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

290 
if (compare(mid,last)>0) swapper(mid,last);\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

291 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

292 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

293 
first+=sz; last=sz; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

294 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

295 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

296 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

297 
#include <stdio.h> 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

298 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

299 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

300 
/* and so is the partitioning logic: */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

301 
#define Partition(swapper,sz) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

302 
do { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

303 
while (compare(first,pivot)<0) first+=sz; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

304 
while (compare(pivot,last)<0) last=sz; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

305 
if (first<last) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

306 
swapper(first,last); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

307 
first+=sz; last=sz; } \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

308 
else if (first==last) { first+=sz; last=sz; break; }\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

309 
} while (first<=last); \ 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

310 
} 
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

311 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

312 
/* and so is the preinsertionsort operation of putting 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

313 
* the smallest element into place as a sentinel. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

314 
* Doing this makes the inner loop nicer. I got this 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

315 
* idea from the GNU implementation of qsort(). 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

316 
* We find the smallest element from the first nmemb, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

317 
* or the first limit, whichever is smaller; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

318 
* therefore we must have ensured that the globally smallest 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

319 
* element is in the first limit. 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

320 
*/ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

321 
#define PreInsertion(swapper,limit,sz) \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

322 
first=base; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

323 
last=first + ((nmemb>limit ? limit : nmemb)1)*sz;\ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

324 
while (last!=base) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

325 
if (compare(first,last)>0) first=last; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

326 
last=sz; } \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

327 
if (first!=base) swapper(first,(char*)base); 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

328 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

329 
/* and so is the insertion sort, in the first two cases: */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

330 
#define Insertion(swapper) \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

331 
last=((char*)base)+nmemb*size; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

332 
for (first=((char*)base)+size;first!=last;first+=size) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

333 
char *test; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

334 
/* Find the right place for first. \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

335 
* My apologies for var reuse. */ \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

336 
for (test=firstsize;compare(test,first)>0;test=size) ; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

337 
test+=size; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

338 
if (test!=first) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

339 
/* Shift everything in [test,first) \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

340 
* up by one, and place first \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

341 
* where test is. */ \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

342 
memcpy(pivot,first,size); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

343 
memmove(test+size,test,firsttest); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

344 
memcpy(test,pivot,size); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

345 
} \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

346 
} 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

347 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

348 
#define SWAP_nonaligned(a,b) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

349 
register char *aa=(a),*bb=(b); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

350 
register size_t sz=size; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

351 
do { register char t=*aa; *aa++=*bb; *bb++=t; } while (sz); } 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

352 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

353 
#define SWAP_aligned(a,b) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

354 
register int *aa=(int*)(a),*bb=(int*)(b); \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

355 
register size_t sz=size; \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

356 
do { register int t=*aa;*aa++=*bb; *bb++=t; } while (sz=WORD_BYTES); } 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

357 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

358 
#define SWAP_words(a,b) { \ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

359 
register int t=*((int*)a); *((int*)a)=*((int*)b); *((int*)b)=t; } 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

360 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

361 
/*  */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

362 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

363 
static char * pivot_big(char *first, char *mid, char *last, size_t size, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

364 
int compare(const void *, const void *)) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

365 
int d=(((lastfirst)/size)>>3)*size; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

366 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

367 
fprintf(stderr, "pivot_big: first=%p last=%p size=%lu n=%lu\n", first, (unsigned long)last, size, (unsigned long)((lastfirst+1)/size)); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

368 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

369 
char *m1,*m2,*m3; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

370 
{ char *a=first, *b=first+d, *c=first+2*d; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

371 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

372 
fprintf(stderr,"< %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

373 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

374 
m1 = compare(a,b)<0 ? 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

375 
(compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

376 
: (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

377 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

378 
{ char *a=midd, *b=mid, *c=mid+d; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

379 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

380 
fprintf(stderr,". %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

381 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

382 
m2 = compare(a,b)<0 ? 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

383 
(compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

384 
: (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

385 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

386 
{ char *a=last2*d, *b=lastd, *c=last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

387 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

388 
fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)a,*(int*)b,*(int*)c, a,b,c); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

389 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

390 
m3 = compare(a,b)<0 ? 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

391 
(compare(b,c)<0 ? b : (compare(a,c)<0 ? c : a)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

392 
: (compare(a,c)<0 ? a : (compare(b,c)<0 ? c : b)); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

393 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

394 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

395 
fprintf(stderr,"> %d %d %d @ %p %p %p\n",*(int*)m1,*(int*)m2,*(int*)m3, m1,m2,m3); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

396 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

397 
return compare(m1,m2)<0 ? 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

398 
(compare(m2,m3)<0 ? m2 : (compare(m1,m3)<0 ? m3 : m1)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

399 
: (compare(m1,m3)<0 ? m1 : (compare(m2,m3)<0 ? m3 : m2)); 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

400 
} 
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

401 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

402 
/*  */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

403 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

404 
static void qsort_nonaligned(void *base, size_t nmemb, size_t size, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

405 
int (*compare)(const void *, const void *)) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

406 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

407 
stack_entry stack[STACK_SIZE]; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

408 
int stacktop=0; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

409 
char *first,*last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

410 
char *pivot=malloc(size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

411 
size_t trunc=TRUNC_nonaligned*size; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

412 
assert(pivot!=0); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

413 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

414 
first=(char*)base; last=first+(nmemb1)*size; 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

415 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

416 
if (lastfirst>=trunc) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

417 
char *ffirst=first, *llast=last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

418 
while (1) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

419 
/* Select pivot */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

420 
{ char * mid=first+size*((lastfirst)/size >> 1); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

421 
Pivot(SWAP_nonaligned,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

422 
memcpy(pivot,mid,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

423 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

424 
/* Partition. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

425 
Partition(SWAP_nonaligned,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

426 
/* Prepare to recurse/iterate. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

427 
Recurse(trunc) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

428 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

429 
} 
10116
418691d83f6a
Quick fix for qsort offbyone error.
Sam Lantinga <slouken@libsdl.org>
parents:
10085
diff
changeset

430 
PreInsertion(SWAP_nonaligned,TRUNC_nonaligned,size); 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

431 
Insertion(SWAP_nonaligned); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

432 
free(pivot); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

433 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

434 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

435 
static void qsort_aligned(void *base, size_t nmemb, size_t size, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

436 
int (*compare)(const void *, const void *)) { 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

437 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

438 
stack_entry stack[STACK_SIZE]; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

439 
int stacktop=0; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

440 
char *first,*last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

441 
char *pivot=malloc(size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

442 
size_t trunc=TRUNC_aligned*size; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

443 
assert(pivot!=0); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

444 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

445 
first=(char*)base; last=first+(nmemb1)*size; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

446 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

447 
if (lastfirst>=trunc) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

448 
char *ffirst=first,*llast=last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

449 
while (1) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

450 
/* Select pivot */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

451 
{ char * mid=first+size*((lastfirst)/size >> 1); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

452 
Pivot(SWAP_aligned,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

453 
memcpy(pivot,mid,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

454 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

455 
/* Partition. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

456 
Partition(SWAP_aligned,size); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

457 
/* Prepare to recurse/iterate. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

458 
Recurse(trunc) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

459 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

460 
} 
10116
418691d83f6a
Quick fix for qsort offbyone error.
Sam Lantinga <slouken@libsdl.org>
parents:
10085
diff
changeset

461 
PreInsertion(SWAP_aligned,TRUNC_aligned,size); 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

462 
Insertion(SWAP_aligned); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

463 
free(pivot); 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

464 
} 
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

465 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

466 
static void qsort_words(void *base, size_t nmemb, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

467 
int (*compare)(const void *, const void *)) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

468 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

469 
stack_entry stack[STACK_SIZE]; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

470 
int stacktop=0; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

471 
char *first,*last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

472 
char *pivot=malloc(WORD_BYTES); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

473 
assert(pivot!=0); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

474 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

475 
first=(char*)base; last=first+(nmemb1)*WORD_BYTES; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

476 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

477 
if (lastfirst>=TRUNC_words) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

478 
char *ffirst=first, *llast=last; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

479 
while (1) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

480 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

481 
fprintf(stderr,"Doing %d:%d: ", 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

482 
(first(char*)base)/WORD_BYTES, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

483 
(last(char*)base)/WORD_BYTES); 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

484 
#endif 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

485 
/* Select pivot */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

486 
{ char * mid=first+WORD_BYTES*((lastfirst) / (2*WORD_BYTES)); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

487 
Pivot(SWAP_words,WORD_BYTES); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

488 
*(int*)pivot=*(int*)mid; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

489 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

490 
fprintf(stderr,"pivot = %p = #%lu = %d\n", mid, (unsigned long)(((int*)mid)((int*)base)), *(int*)mid); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

491 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

492 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

493 
/* Partition. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

494 
Partition(SWAP_words,WORD_BYTES); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

495 
#ifdef DEBUG_QSORT 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

496 
fprintf(stderr, "after partitioning first=#%lu last=#%lu\n", (first(char*)base)/4lu, (last(char*)base)/4lu); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

497 
#endif 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

498 
/* Prepare to recurse/iterate. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

499 
Recurse(TRUNC_words) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

500 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

501 
} 
10116
418691d83f6a
Quick fix for qsort offbyone error.
Sam Lantinga <slouken@libsdl.org>
parents:
10085
diff
changeset

502 
PreInsertion(SWAP_words,(TRUNC_words/WORD_BYTES),WORD_BYTES); 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

503 
/* Now do insertion sort. */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

504 
last=((char*)base)+nmemb*WORD_BYTES; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

505 
for (first=((char*)base)+WORD_BYTES;first!=last;first+=WORD_BYTES) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

506 
/* Find the right place for first. My apologies for var reuse */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

507 
int *pl=(int*)(firstWORD_BYTES),*pr=(int*)first; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

508 
*(int*)pivot=*(int*)first; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

509 
for (;compare(pl,pivot)>0;pr=pl,pl) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

510 
*pr=*pl; } 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

511 
if (pr!=(int*)first) *pr=*(int*)pivot; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

512 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

513 
free(pivot); 
1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

514 
} 
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

515 

10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

516 
/*  */ 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

517 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

518 
extern void qsortG(void *base, size_t nmemb, size_t size, 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

519 
int (*compare)(const void *, const void *)) { 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

520 

a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

521 
if (nmemb<=1) return; 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

522 
if (((int)basesize)&(WORD_BYTES1)) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

523 
qsort_nonaligned(base,nmemb,size,compare); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

524 
else if (size!=WORD_BYTES) 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

525 
qsort_aligned(base,nmemb,size,compare); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

526 
else 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

527 
qsort_words(base,nmemb,compare); 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

528 
} 
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

529 

1330
450721ad5436
It's now possible to build SDL without any C runtime at all on Windows,
Sam Lantinga <slouken@libsdl.org>
parents:
diff
changeset

530 

10068
19998f9082dc
Replaced SDL_qsort with public domain code from PDCLib: http://pdclib.e43.eu/
Ryan C. Gordon <icculus@icculus.org>
parents:
9306
diff
changeset

531 
#endif /* HAVE_QSORT */ 
7003
eeaf77005c30
Improvements to stdlib.
Ryan C. Gordon <icculus@icculus.org>
parents:
6281
diff
changeset

532 

1895
c121d94672cb
SDL 1.2 is moving to a branch, and SDL 1.3 is becoming the head.
Sam Lantinga <slouken@libsdl.org>
parents:
1456
diff
changeset

533 
/* vi: set ts=4 sw=4 expandtab: */ 
10085
a8e53dc3c5a1
stdlib: Restored previous qsort() implementation; the licensing is resolved.
Ryan C. Gordon <icculus@icculus.org>
parents:
10070
diff
changeset

534 