ReactOS  0.4.13-dev-544-gede3fdd
timsort.h File Reference
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
Include dependency graph for timsort.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  TIM_SORT_RUN_T
 
struct  TEMP_STORAGE_T
 

Macros

#define SORT_CMP(x, y)   ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
 
#define TIM_SORT_STACK_SIZE   128
 
#define SORT_SWAP(x, y)   {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
 
#define SORT_COMMON_H
 
#define MAX(x, y)   (((x) > (y) ? (x) : (y)))
 
#define MIN(x, y)   (((x) < (y) ? (x) : (y)))
 
#define CLZ   clzll
 
#define SORT_CONCAT(x, y)   x ## _ ## y
 
#define SORT_MAKE_STR1(x, y)   SORT_CONCAT(x,y)
 
#define SORT_MAKE_STR(x)   SORT_MAKE_STR1(SORT_NAME,x)
 
#define BINARY_INSERTION_FIND   SORT_MAKE_STR(binary_insertion_find)
 
#define BINARY_INSERTION_SORT_START   SORT_MAKE_STR(binary_insertion_sort_start)
 
#define BINARY_INSERTION_SORT   SORT_MAKE_STR(binary_insertion_sort)
 
#define REVERSE_ELEMENTS   SORT_MAKE_STR(reverse_elements)
 
#define COUNT_RUN   SORT_MAKE_STR(count_run)
 
#define CHECK_INVARIANT   SORT_MAKE_STR(check_invariant)
 
#define TIM_SORT   SORT_MAKE_STR(tim_sort)
 
#define TIM_SORT_RESIZE   SORT_MAKE_STR(tim_sort_resize)
 
#define TIM_SORT_MERGE   SORT_MAKE_STR(tim_sort_merge)
 
#define TIM_SORT_COLLAPSE   SORT_MAKE_STR(tim_sort_collapse)
 

Functions

static int compute_minrun (const uint64_t)
 
static int clzll (uint64_t)
 
void BINARY_INSERTION_SORT (SORT_TYPE *dst, const size_t size)
 
void TIM_SORT (SORT_TYPE *dst, const size_t size)
 
static __inline size_t BINARY_INSERTION_FIND (SORT_TYPE *dst, const SORT_TYPE x, const size_t size)
 
static void BINARY_INSERTION_SORT_START (SORT_TYPE *dst, const size_t start, const size_t size)
 
static __inline void REVERSE_ELEMENTS (SORT_TYPE *dst, size_t start, size_t end)
 
static size_t COUNT_RUN (SORT_TYPE *dst, const size_t start, const size_t size)
 
static int CHECK_INVARIANT (TIM_SORT_RUN_T *stack, const int stack_curr)
 
static void TIM_SORT_RESIZE (TEMP_STORAGE_T *store, const size_t new_size)
 
static void TIM_SORT_MERGE (SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr, TEMP_STORAGE_T *store)
 
static int TIM_SORT_COLLAPSE (SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr, TEMP_STORAGE_T *store, const size_t 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)
 

Macro Definition Documentation

◆ BINARY_INSERTION_FIND

#define BINARY_INSERTION_FIND   SORT_MAKE_STR(binary_insertion_find)

Definition at line 148 of file timsort.h.

◆ BINARY_INSERTION_SORT

#define BINARY_INSERTION_SORT   SORT_MAKE_STR(binary_insertion_sort)

Definition at line 150 of file timsort.h.

◆ BINARY_INSERTION_SORT_START

#define BINARY_INSERTION_SORT_START   SORT_MAKE_STR(binary_insertion_sort_start)

Definition at line 149 of file timsort.h.

◆ CHECK_INVARIANT

#define CHECK_INVARIANT   SORT_MAKE_STR(check_invariant)

Definition at line 153 of file timsort.h.

◆ CLZ

#define CLZ   clzll

Definition at line 125 of file timsort.h.

◆ COUNT_RUN

#define COUNT_RUN   SORT_MAKE_STR(count_run)

Definition at line 152 of file timsort.h.

◆ MAX

#define MAX (   x,
  y 
)    (((x) > (y) ? (x) : (y)))

Definition at line 67 of file timsort.h.

◆ MIN

#define MIN (   x,
  y 
)    (((x) < (y) ? (x) : (y)))

Definition at line 71 of file timsort.h.

◆ REVERSE_ELEMENTS

#define REVERSE_ELEMENTS   SORT_MAKE_STR(reverse_elements)

Definition at line 151 of file timsort.h.

◆ SORT_CMP

#define SORT_CMP (   x,
  y 
)    ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))

Definition at line 52 of file timsort.h.

◆ SORT_COMMON_H

#define SORT_COMMON_H

Definition at line 64 of file timsort.h.

◆ SORT_CONCAT

#define SORT_CONCAT (   x,
  y 
)    x ## _ ## y

Definition at line 144 of file timsort.h.

◆ SORT_MAKE_STR

#define SORT_MAKE_STR (   x)    SORT_MAKE_STR1(SORT_NAME,x)

Definition at line 146 of file timsort.h.

◆ SORT_MAKE_STR1

#define SORT_MAKE_STR1 (   x,
  y 
)    SORT_CONCAT(x,y)

Definition at line 145 of file timsort.h.

◆ SORT_SWAP

#define SORT_SWAP (   x,
  y 
)    {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}

Definition at line 59 of file timsort.h.

◆ TIM_SORT

#define TIM_SORT   SORT_MAKE_STR(tim_sort)

Definition at line 154 of file timsort.h.

◆ TIM_SORT_COLLAPSE

#define TIM_SORT_COLLAPSE   SORT_MAKE_STR(tim_sort_collapse)

Definition at line 157 of file timsort.h.

◆ TIM_SORT_MERGE

#define TIM_SORT_MERGE   SORT_MAKE_STR(tim_sort_merge)

Definition at line 156 of file timsort.h.

◆ TIM_SORT_RESIZE

#define TIM_SORT_RESIZE   SORT_MAKE_STR(tim_sort_resize)

Definition at line 155 of file timsort.h.

◆ TIM_SORT_STACK_SIZE

#define TIM_SORT_STACK_SIZE   128

Definition at line 56 of file timsort.h.

Function Documentation

◆ BINARY_INSERTION_FIND()

static __inline size_t BINARY_INSERTION_FIND ( SORT_TYPE dst,
const SORT_TYPE  x,
const size_t  size 
)
static

Definition at line 177 of file timsort.h.

178  {
179  size_t l, c, r;
180  SORT_TYPE cx;
181  l = 0;
182  r = size - 1;
183  c = r >> 1;
184 
185  /* check for out of bounds at the beginning. */
186  if (SORT_CMP(x, dst[0]) < 0) {
187  return 0;
188  } else if (SORT_CMP(x, dst[r]) > 0) {
189  return r;
190  }
191 
192  cx = dst[c];
193 
194  while (1) {
195  const int val = SORT_CMP(x, cx);
196 
197  if (val < 0) {
198  if (c - l <= 1) {
199  return c;
200  }
201 
202  r = c;
203  } else { /* allow = for stability. The binary search favors the right. */
204  if (r - c <= 1) {
205  return c + 1;
206  }
207 
208  l = c;
209  }
210 
211  c = l + ((r - l) >> 1);
212  cx = dst[c];
213  }
214 }
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLuint GLfloat * val
Definition: glext.h:7180
r l[0]
Definition: byte_order.h:167
GLsizeiptr size
Definition: glext.h:5919
const GLubyte * c
Definition: glext.h:8905
#define SORT_TYPE
Definition: xpath.c:442
#define SORT_CMP(x, y)
Definition: timsort.h:52
GLenum GLenum dst
Definition: glext.h:6340
_Out_opt_ int * cx
Definition: commctrl.h:570
#define c
Definition: ke_i.h:80

◆ BINARY_INSERTION_SORT()

void BINARY_INSERTION_SORT ( SORT_TYPE dst,
const size_t  size 
)

Definition at line 247 of file timsort.h.

247  {
248  /* don't bother sorting an array of size <= 1 */
249  if (size <= 1) {
250  return;
251  }
252 
254 }
#define BINARY_INSERTION_SORT_START
Definition: timsort.h:149
GLsizeiptr size
Definition: glext.h:5919
GLenum GLenum dst
Definition: glext.h:6340

◆ BINARY_INSERTION_SORT_START()

static void BINARY_INSERTION_SORT_START ( SORT_TYPE dst,
const size_t  start,
const size_t  size 
)
static

Definition at line 217 of file timsort.h.

217  {
218  size_t i;
219 
220  for (i = start; i < size; i++) {
221  size_t j;
222  SORT_TYPE x;
223  size_t location;
224 
225  /* If this entry is already correct, just move along */
226  if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
227  continue;
228  }
229 
230  /* Else we need to find the right place, shift everything over, and squeeze in */
231  x = dst[i];
233 
234  for (j = i - 1; j >= location; j--) {
235  dst[j + 1] = dst[j];
236 
237  if (j == 0) { /* check edge case because j is unsigned */
238  break;
239  }
240  }
241 
242  dst[location] = x;
243  }
244 }
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
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
Definition: glfuncs.h:248
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
Definition: glfuncs.h:250
GLsizeiptr size
Definition: glext.h:5919
#define SORT_TYPE
Definition: xpath.c:442
#define SORT_CMP(x, y)
Definition: timsort.h:52
#define BINARY_INSERTION_FIND
Definition: timsort.h:148
#define location(file, line)
Definition: kmtest.h:18
GLuint start
Definition: gl.h:1545
GLenum GLenum dst
Definition: glext.h:6340

◆ CHECK_INVARIANT()

static int CHECK_INVARIANT ( TIM_SORT_RUN_T stack,
const int  stack_curr 
)
static

Definition at line 322 of file timsort.h.

322  {
323  size_t A, B, C;
324 
325  if (stack_curr < 2) {
326  return 1;
327  }
328 
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;
332 
333  if (A1 <= B1) {
334  return 0;
335  }
336 
337  return 1;
338  }
339 
340  A = stack[stack_curr - 3].length;
341  B = stack[stack_curr - 2].length;
342  C = stack[stack_curr - 1].length;
343 
344  if ((A <= B + C) || (B <= C)) {
345  return 0;
346  }
347 
348  return 1;
349 }
#define C(name, bit)
Definition: cpu.h:208
#define A(row, col)
Definition: _stack.h:47
Definition: ttei1.cpp:12
Definition: ttei6.cpp:27
#define B(row, col)
#define A1

◆ clzll()

static int clzll ( uint64_t  x)
static

Definition at line 84 of file timsort.h.

84  {
85  int n;
86 
87  if (x == 0) {
88  return 64;
89  }
90 
91  n = 0;
92 
93  if (x <= 0x00000000FFFFFFFFL) {
94  n = n + 32;
95  x = x << 32;
96  }
97 
98  if (x <= 0x0000FFFFFFFFFFFFL) {
99  n = n + 16;
100  x = x << 16;
101  }
102 
103  if (x <= 0x00FFFFFFFFFFFFFFL) {
104  n = n + 8;
105  x = x << 8;
106  }
107 
108  if (x <= 0x0FFFFFFFFFFFFFFFL) {
109  n = n + 4;
110  x = x << 4;
111  }
112 
113  if (x <= 0x3FFFFFFFFFFFFFFFL) {
114  n = n + 2;
115  x = x << 2;
116  }
117 
118  if (x <= 0x7FFFFFFFFFFFFFFFL) {
119  n = n + 1;
120  }
121 
122  return n;
123 }
GLdouble n
Definition: glext.h:7729
GLint GLint GLint GLint GLint x
Definition: gl.h:1548

◆ compute_minrun()

static __inline int compute_minrun ( const uint64_t  size)
static

Definition at line 129 of file timsort.h.

129  {
130  const int top_bit = 64 - CLZ(size);
131  const int shift = MAX(top_bit, 6) - 6;
132  const int minrun = size >> shift;
133  const uint64_t mask = (1ULL << shift) - 1;
134 
135  if (mask & size) {
136  return minrun + 1;
137  }
138 
139  return minrun;
140 }
#define shift
Definition: input.c:1668
GLenum GLint GLuint mask
Definition: glext.h:6028
#define ULL(a, b)
Definition: format_msg.c:27
GLsizeiptr size
Definition: glext.h:5919
#define MAX(x, y)
Definition: timsort.h:67
UINT64 uint64_t
Definition: types.h:77
#define CLZ
Definition: timsort.h:125

Referenced by TIM_SORT().

◆ COUNT_RUN()

static size_t COUNT_RUN ( SORT_TYPE dst,
const size_t  start,
const size_t  size 
)
static

Definition at line 270 of file timsort.h.

270  {
271  size_t curr;
272 
273  if (size - start == 1) {
274  return 1;
275  }
276 
277  if (start >= size - 2) {
278  if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
279  SORT_SWAP(dst[size - 2], dst[size - 1]);
280  }
281 
282  return 2;
283  }
284 
285  curr = start + 2;
286 
287  if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
288  /* increasing run */
289  while (1) {
290  if (curr == size - 1) {
291  break;
292  }
293 
294  if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
295  break;
296  }
297 
298  curr++;
299  }
300 
301  return curr - start;
302  } else {
303  /* decreasing run */
304  while (1) {
305  if (curr == size - 1) {
306  break;
307  }
308 
309  if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
310  break;
311  }
312 
313  curr++;
314  }
315 
316  /* reverse in-place */
317  REVERSE_ELEMENTS(dst, start, curr - 1);
318  return curr - start;
319  }
320 }
#define REVERSE_ELEMENTS
Definition: timsort.h:151
GLsizeiptr size
Definition: glext.h:5919
#define SORT_SWAP(x, y)
Definition: timsort.h:59
#define SORT_CMP(x, y)
Definition: timsort.h:52
GLuint start
Definition: gl.h:1545
GLenum GLenum dst
Definition: glext.h:6340

◆ PUSH_NEXT()

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 
)
static

Definition at line 487 of file timsort.h.

493  {
494  size_t len = COUNT_RUN(dst, *curr, size);
495  size_t run = minrun;
496 
497  if (run > size - *curr) {
498  run = size - *curr;
499  }
500 
501  if (run > len) {
502  BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
503  len = run;
504  }
505 
506  run_stack[*stack_curr].start = *curr;
507  run_stack[*stack_curr].length = len;
508  (*stack_curr)++;
509  *curr += len;
510 
511  if (*curr == size) {
512  /* finish up */
513  while (*stack_curr > 1) {
514  TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
515  run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
516  (*stack_curr)--;
517  }
518 
519  if (store->storage != NULL) {
520  free(store->storage);
521  store->storage = NULL;
522  }
523 
524  return 0;
525  }
526 
527  return 1;
528 }
#define COUNT_RUN
Definition: timsort.h:152
SORT_TYPE * storage
Definition: timsort.h:353
#define free
Definition: debug_ros.c:5
#define TIM_SORT_MERGE
Definition: timsort.h:156
size_t start
Definition: timsort.h:167
#define BINARY_INSERTION_SORT_START
Definition: timsort.h:149
smooth NULL
Definition: ftsmooth.c:416
size_t length
Definition: timsort.h:168
GLsizeiptr size
Definition: glext.h:5919
GLenum GLsizei len
Definition: glext.h:6722
GLenum GLenum dst
Definition: glext.h:6340

Referenced by TIM_SORT().

◆ REVERSE_ELEMENTS()

static __inline void REVERSE_ELEMENTS ( SORT_TYPE dst,
size_t  start,
size_t  end 
)
static

Definition at line 258 of file timsort.h.

258  {
259  while (1) {
260  if (start >= end) {
261  return;
262  }
263 
264  SORT_SWAP(dst[start], dst[end]);
265  start++;
266  end--;
267  }
268 }
GLuint GLuint end
Definition: gl.h:1545
#define SORT_SWAP(x, y)
Definition: timsort.h:59
GLuint start
Definition: gl.h:1545
GLenum GLenum dst
Definition: glext.h:6340

◆ TIM_SORT()

void TIM_SORT ( SORT_TYPE dst,
const size_t  size 
)

Definition at line 530 of file timsort.h.

530  {
531  size_t minrun;
532  TEMP_STORAGE_T _store, *store;
534  size_t stack_curr = 0;
535  size_t curr = 0;
536 
537  /* don't bother sorting an array of size 1 */
538  if (size <= 1) {
539  return;
540  }
541 
542  if (size < 64) {
544  return;
545  }
546 
547  /* compute the minimum run length */
548  minrun = compute_minrun(size);
549  /* temporary storage for merges */
550  store = &_store;
551  store->alloc = 0;
552  store->storage = NULL;
553 
554  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
555  return;
556  }
557 
558  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
559  return;
560  }
561 
562  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
563  return;
564  }
565 
566  while (1) {
567  if (!CHECK_INVARIANT(run_stack, stack_curr)) {
568  stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
569  continue;
570  }
571 
572  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
573  return;
574  }
575  }
576 }
SORT_TYPE * storage
Definition: timsort.h:353
#define BINARY_INSERTION_SORT
Definition: timsort.h:150
static int compute_minrun(const uint64_t)
Definition: timsort.h:129
smooth NULL
Definition: ftsmooth.c:416
size_t alloc
Definition: timsort.h:352
GLsizeiptr size
Definition: glext.h:5919
#define TIM_SORT_COLLAPSE
Definition: timsort.h:157
GLenum GLenum dst
Definition: glext.h:6340
#define TIM_SORT_STACK_SIZE
Definition: timsort.h:56
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)
Definition: timsort.h:487
#define CHECK_INVARIANT
Definition: timsort.h:153

◆ TIM_SORT_COLLAPSE()

static int TIM_SORT_COLLAPSE ( SORT_TYPE dst,
TIM_SORT_RUN_T stack,
int  stack_curr,
TEMP_STORAGE_T store,
const size_t  size 
)
static

Definition at line 423 of file timsort.h.

424  {
425  while (1) {
426  size_t A, B, C, D;
427  int ABC, BCD, CD;
428 
429  /* if the stack only has one thing on it, we are done with the collapse */
430  if (stack_curr <= 1) {
431  break;
432  }
433 
434  /* if this is the last merge, just do it */
435  if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
436  TIM_SORT_MERGE(dst, stack, stack_curr, store);
437  stack[0].length += stack[1].length;
438  stack_curr--;
439  break;
440  }
441  /* check if the invariant is off for a stack of 2 elements */
442  else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
443  TIM_SORT_MERGE(dst, stack, stack_curr, store);
444  stack[0].length += stack[1].length;
445  stack_curr--;
446  break;
447  } else if (stack_curr == 2) {
448  break;
449  }
450 
451  B = stack[stack_curr - 3].length;
452  C = stack[stack_curr - 2].length;
453  D = stack[stack_curr - 1].length;
454 
455  if (stack_curr >= 4) {
456  A = stack[stack_curr - 4].length;
457  ABC = (A <= B + C);
458  } else {
459  ABC = 0;
460  }
461 
462  BCD = (B <= C + D) || ABC;
463  CD = (C <= D);
464 
465  /* Both invariants are good */
466  if (!BCD && !CD) {
467  break;
468  }
469 
470  /* left merge */
471  if (BCD && !CD) {
472  TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
473  stack[stack_curr - 3].length += stack[stack_curr - 2].length;
474  stack[stack_curr - 2] = stack[stack_curr - 1];
475  stack_curr--;
476  } else {
477  /* right merge */
478  TIM_SORT_MERGE(dst, stack, stack_curr, store);
479  stack[stack_curr - 2].length += stack[stack_curr - 1].length;
480  stack_curr--;
481  }
482  }
483 
484  return stack_curr;
485 }
struct _ABC ABC
#define C(name, bit)
Definition: cpu.h:208
Definition: wingdi.h:1388
static const WCHAR BCD[]
Definition: reginf.c:61
#define TIM_SORT_MERGE
Definition: timsort.h:156
#define A(row, col)
Definition: _stack.h:47
GLsizeiptr size
Definition: glext.h:5919
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
Definition: ttei1.cpp:12
#define D(name, bit)
GLenum GLenum dst
Definition: glext.h:6340
Definition: ttei6.cpp:27
#define B(row, col)

◆ TIM_SORT_MERGE()

static void TIM_SORT_MERGE ( SORT_TYPE dst,
const TIM_SORT_RUN_T stack,
const int  stack_curr,
TEMP_STORAGE_T store 
)
static

Definition at line 371 of file timsort.h.

372  {
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;
376  SORT_TYPE *storage;
377  size_t i, j, k;
378  TIM_SORT_RESIZE(store, MIN(A, B));
379  storage = store->storage;
380 
381  /* left merge */
382  if (A < B) {
383  memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
384  i = 0;
385  j = curr + A;
386 
387  for (k = curr; k < curr + A + B; k++) {
388  if ((i < A) && (j < curr + A + B)) {
389  if (SORT_CMP(storage[i], dst[j]) <= 0) {
390  dst[k] = storage[i++];
391  } else {
392  dst[k] = dst[j++];
393  }
394  } else if (i < A) {
395  dst[k] = storage[i++];
396  } else {
397  break;
398  }
399  }
400  } else {
401  /* right merge */
402  memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
403  i = B;
404  j = curr + A;
405  k = curr + A + B;
406 
407  while (k-- > curr) {
408  if ((i > 0) && (j > curr)) {
409  if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
410  dst[k] = dst[--j];
411  } else {
412  dst[k] = storage[--i];
413  }
414  } else if (i > 0) {
415  dst[k] = storage[--i];
416  } else {
417  break;
418  }
419  }
420  }
421 }
SORT_TYPE * storage
Definition: timsort.h:353
#define MIN(x, y)
Definition: timsort.h:71
#define A(row, col)
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
Definition: glfuncs.h:248
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
Definition: glfuncs.h:250
Definition: _stack.h:47
#define TIM_SORT_RESIZE
Definition: timsort.h:155
#define SORT_TYPE
Definition: xpath.c:442
Definition: ttei1.cpp:12
#define SORT_CMP(x, y)
Definition: timsort.h:52
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum GLenum dst
Definition: glext.h:6340
#define B(row, col)
int k
Definition: mpi.c:3369

◆ TIM_SORT_RESIZE()

static void TIM_SORT_RESIZE ( TEMP_STORAGE_T store,
const size_t  new_size 
)
static

Definition at line 356 of file timsort.h.

356  {
357  if (store->alloc < new_size) {
358  SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
359 
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));
363  exit(1);
364  }
365 
366  store->storage = tempstore;
367  store->alloc = new_size;
368  }
369 }
#define realloc
Definition: debug_ros.c:6
SORT_TYPE * storage
Definition: timsort.h:353
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
smooth NULL
Definition: ftsmooth.c:416
size_t alloc
Definition: timsort.h:352
#define SORT_TYPE
Definition: xpath.c:442
FILE * stderr
void exit(int exitcode)
Definition: _exit.c:33