44 #error "Must declare SORT_NAME" 48 #error "Must declare SORT_TYPE" 52 #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1)) 55 #ifndef TIM_SORT_STACK_SIZE 56 #define TIM_SORT_STACK_SIZE 128 59 #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;} 67 #define MAX(x,y) (((x) > (y) ? (x) : (y))) 71 #define MIN(x,y) (((x) < (y) ? (x) : (y))) 77 #if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3)) 78 #define CLZ __builtin_clzll 93 if (
x <= 0x00000000FFFFFFFFL) {
98 if (
x <= 0x0000FFFFFFFFFFFFL) {
103 if (
x <= 0x00FFFFFFFFFFFFFFL) {
108 if (
x <= 0x0FFFFFFFFFFFFFFFL) {
113 if (
x <= 0x3FFFFFFFFFFFFFFFL) {
118 if (
x <= 0x7FFFFFFFFFFFFFFFL) {
130 const int top_bit = 64 -
CLZ(
size);
131 const int shift =
MAX(top_bit, 6) - 6;
144 #define SORT_CONCAT(x, y) x ## _ ## y 145 #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y) 146 #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x) 148 #define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find) 149 #define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start) 150 #define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort) 151 #define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements) 152 #define COUNT_RUN SORT_MAKE_STR(count_run) 153 #define CHECK_INVARIANT SORT_MAKE_STR(check_invariant) 154 #define TIM_SORT SORT_MAKE_STR(tim_sort) 155 #define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize) 156 #define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge) 157 #define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse) 160 #define MAX(x,y) (((x) > (y) ? (x) : (y))) 163 #define MIN(x,y) (((x) < (y) ? (x) : (y))) 211 c =
l + ((
r -
l) >> 1);
290 if (curr ==
size - 1) {
305 if (curr ==
size - 1) {
325 if (stack_curr < 2) {
329 if (stack_curr == 2) {
330 const size_t A1 =
stack[stack_curr - 2].length;
331 const size_t B1 =
stack[stack_curr - 1].length;
340 A =
stack[stack_curr - 3].length;
341 B =
stack[stack_curr - 2].length;
342 C =
stack[stack_curr - 1].length;
344 if ((
A <=
B +
C) || (
B <=
C)) {
357 if (store->
alloc < new_size) {
360 if (tempstore ==
NULL) {
361 fprintf(
stderr,
"Error allocating temporary storage for tim sort: need %lu bytes",
362 (
unsigned long)(
sizeof(
SORT_TYPE) * new_size));
367 store->
alloc = new_size;
373 const size_t A =
stack[stack_curr - 2].length;
374 const size_t B =
stack[stack_curr - 1].length;
375 const size_t curr =
stack[stack_curr - 2].start;
387 for (
k = curr;
k < curr +
A +
B;
k++) {
388 if ((
i <
A) && (
j < curr +
A +
B)) {
390 dst[
k] = storage[
i++];
395 dst[
k] = storage[
i++];
409 if ((
i > 0) && (
j > curr)) {
413 dst[
k] = storage[--
i];
416 dst[
k] = storage[--
i];
431 if (stack_curr <= 1) {
448 }
else if (stack_curr == 2) {
452 B =
stack[stack_curr - 3].length;
453 C =
stack[stack_curr - 2].length;
454 D =
stack[stack_curr - 1].length;
456 if (stack_curr >= 4) {
457 A =
stack[stack_curr - 4].length;
474 stack[stack_curr - 3].length +=
stack[stack_curr - 2].length;
475 stack[stack_curr - 2] =
stack[stack_curr - 1];
480 stack[stack_curr - 2].length +=
stack[stack_curr - 1].length;
498 if (run >
size - *curr) {
507 run_stack[*stack_curr].
start = *curr;
514 while (*stack_curr > 1) {
516 run_stack[*stack_curr - 2].
length += run_stack[*stack_curr - 1].
length;
535 size_t stack_curr = 0;
580 #undef SORT_MAKE_STR1 585 #undef TEMP_STORAGE_T 586 #undef TIM_SORT_RUN_T 590 #undef SORT_MAKE_STR1 592 #undef BINARY_INSERTION_FIND 593 #undef BINARY_INSERTION_SORT_START 594 #undef BINARY_INSERTION_SORT 595 #undef REVERSE_ELEMENTS 598 #undef TIM_SORT_RESIZE 599 #undef TIM_SORT_COLLAPSE 600 #undef TIM_SORT_RUN_T 601 #undef TEMP_STORAGE_T
#define BINARY_INSERTION_SORT
GLdouble GLdouble GLdouble r
GLint GLint GLint GLint GLint x
static int compute_minrun(const uint64_t)
#define BINARY_INSERTION_SORT_START
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
GLenum GLuint GLenum GLsizei length
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
#define TIM_SORT_COLLAPSE
static int clzll(uint64_t)
#define memcpy(s1, s2, n)
#define BINARY_INSERTION_FIND
#define location(file, line)
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
#define TIM_SORT_STACK_SIZE
static __inline int PUSH_NEXT(SORT_TYPE *dst, const size_t size, TEMP_STORAGE_T *store, const size_t minrun, TIM_SORT_RUN_T *run_stack, size_t *stack_curr, size_t *curr)