/src/libxml2/timsort.h

Source (jump to first uncovered line)
/*
 * Taken from https://github.com/swenson/sort
 * Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
 * Removed all code unrelated to Timsort and made minor adjustments for
 * cross-platform compatibility.
 */

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2010-2017 Christopher Swenson.
 * Copyright (c) 2012 Vojtech Fried.
 * Copyright (c) 2012 Google Inc. All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#elif defined(_WIN32)
typedef unsigned __int64 uint64_t;
#endif

#ifndef SORT_NAME
#error "Must declare SORT_NAME"
#endif

#ifndef SORT_TYPE
#error "Must declare SORT_TYPE"
#endif

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

#ifndef TIM_SORT_STACK_SIZE
#define TIM_SORT_STACK_SIZE 128
#endif

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


/* Common, type-agnostic functions and constants that we don't want to declare twice. */
#ifndef SORT_COMMON_H
#define SORT_COMMON_H

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

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

static int compute_minrun(const uint64_t);

#ifndef CLZ
#if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3))
#define CLZ __builtin_clzll
#else

static int clzll(uint64_t);

/* adapted from Hacker's Delight */
static int clzll(uint64_t x) {
  int n;

  if (x == 0) {
    return 64;
  }

  n = 0;

  if (x <= 0x00000000FFFFFFFFL) {
    n = n + 32;
    x = x << 32;
  }

  if (x <= 0x0000FFFFFFFFFFFFL) {
    n = n + 16;
    x = x << 16;
  }

  if (x <= 0x00FFFFFFFFFFFFFFL) {
    n = n + 8;
    x = x << 8;
  }

  if (x <= 0x0FFFFFFFFFFFFFFFL) {
    n = n + 4;
    x = x << 4;
  }

  if (x <= 0x3FFFFFFFFFFFFFFFL) {
    n = n + 2;
    x = x << 2;
  }

  if (x <= 0x7FFFFFFFFFFFFFFFL) {
    n = n + 1;
  }

  return n;
}

#define CLZ clzll
#endif
#endif

static __inline int compute_minrun(const uint64_t size) {
  const int top_bit = 64 - CLZ(size);
  const int shift = MAX(top_bit, 6) - 6;
  const int minrun = size >> shift;
  const uint64_t mask = (1ULL << shift) - 1;

  if (mask & size) {
    return minrun + 1;
  }

  return minrun;
}

#endif /* SORT_COMMON_H */

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

#ifndef MAX
#define MAX(x,y) (((x) > (y) ? (x) : (y)))
#endif
#ifndef MIN
#define MIN(x,y) (((x) < (y) ? (x) : (y)))
#endif

typedef struct {
  size_t start;
  size_t length;
} TIM_SORT_RUN_T;


void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
void TIM_SORT(SORT_TYPE *dst, const size_t size);


/* Function used to do a binary search for binary insertion sort */
static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
    const size_t size) {
  size_t l, c, r;
  SORT_TYPE cx;
  l = 0;
  r = size - 1;
  c = r >> 1;

  /* check for out of bounds at the beginning. */
  if (SORT_CMP(x, dst[0]) < 0) {
    return 0;
  } else if (SORT_CMP(x, dst[r]) > 0) {
    return r;
  }

  cx = dst[c];

  while (1) {
    const int val = SORT_CMP(x, cx);

    if (val < 0) {
      if (c - l <= 1) {
        return c;
      }

      r = c;
    } else { /* allow = for stability. The binary search favors the right. */
      if (r - c <= 1) {
        return c + 1;
      }

      l = c;
    }

    c = l + ((r - l) >> 1);
    cx = dst[c];
  }
}

/* Binary insertion sort, but knowing that the first "start" entries are sorted.  Used in timsort. */
static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
  size_t i;

  for (i = start; i < size; i++) {
    size_t j;
    SORT_TYPE x;
    size_t location;

    /* If this entry is already correct, just move along */
    if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
      continue;
    }

    /* Else we need to find the right place, shift everything over, and squeeze in */
    x = dst[i];
    location = BINARY_INSERTION_FIND(dst, x, i);

    for (j = i - 1; j >= location; j--) {
      dst[j + 1] = dst[j];

      if (j == 0) { /* check edge case because j is unsigned */
        break;
      }
    }

    dst[location] = x;
  }
}

/* Binary insertion sort */
void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
  /* don't bother sorting an array of size <= 1 */
  if (size <= 1) {
    return;
  }

  BINARY_INSERTION_SORT_START(dst, 1, size);
}

/* timsort implementation, based on timsort.txt */

static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
  while (1) {
    if (start >= end) {
      return;
    }

    SORT_SWAP(dst[start], dst[end]);
    start++;
    end--;
  }
}

static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
  size_t curr;

  if (size - start == 1) {
    return 1;
  }

  if (start >= size - 2) {
    if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
      SORT_SWAP(dst[size - 2], dst[size - 1]);
    }

    return 2;
  }

  curr = start + 2;

  if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
    /* increasing run */
    while (1) {
      if (curr == size - 1) {
        break;
      }

      if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
        break;
      }

      curr++;
    }

    return curr - start;
  } else {
    /* decreasing run */
    while (1) {
      if (curr == size - 1) {
        break;
      }

      if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
        break;
      }

      curr++;
    }

    /* reverse in-place */
    REVERSE_ELEMENTS(dst, start, curr - 1);
    return curr - start;
  }
}

static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
  size_t A, B, C;

  if (stack_curr < 2) {
    return 1;
  }

  if (stack_curr == 2) {
    const size_t A1 = stack[stack_curr - 2].length;
    const size_t B1 = stack[stack_curr - 1].length;

    if (A1 <= B1) {
      return 0;
    }

    return 1;
  }

  A = stack[stack_curr - 3].length;
  B = stack[stack_curr - 2].length;
  C = stack[stack_curr - 1].length;

  if ((A <= B + C) || (B <= C)) {
    return 0;
  }

  return 1;
}

typedef struct {
  size_t alloc;
  SORT_TYPE *storage;
} TEMP_STORAGE_T;

static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
  if (store->alloc < new_size) {
    SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));

    if (tempstore == NULL) {
      fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
              (unsigned long)(sizeof(SORT_TYPE) * new_size));
      exit(1);
    }

    store->storage = tempstore;
    store->alloc = new_size;
  }
}

static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr,
                           TEMP_STORAGE_T *store) {
  const size_t A = stack[stack_curr - 2].length;
  const size_t B = stack[stack_curr - 1].length;
  const size_t curr = stack[stack_curr - 2].start;
  SORT_TYPE *storage;
  size_t i, j, k;
  TIM_SORT_RESIZE(store, MIN(A, B));
  storage = store->storage;

  /* left merge */
  if (A < B) {
    memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
    i = 0;
    j = curr + A;

    for (k = curr; k < curr + A + B; k++) {
      if ((i < A) && (j < curr + A + B)) {
        if (SORT_CMP(storage[i], dst[j]) <= 0) {
          dst[k] = storage[i++];
        } else {
          dst[k] = dst[j++];
        }
      } else if (i < A) {
        dst[k] = storage[i++];
      } else {
        break;
      }
    }
  } else {
    /* right merge */
    memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
    i = B;
    j = curr + A;
    k = curr + A + B;

    while (k > curr) {
      k--;
      if ((i > 0) && (j > curr)) {
        if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
          dst[k] = dst[--j];
        } else {
          dst[k] = storage[--i];
        }
      } else if (i > 0) {
        dst[k] = storage[--i];
      } else {
        break;
      }
    }
  }
}

static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
                             TEMP_STORAGE_T *store, const size_t size) {
  while (1) {
    size_t A, B, C, D;
    int ABC, BCD, CD;

    /* if the stack only has one thing on it, we are done with the collapse */
    if (stack_curr <= 1) {
      break;
    }

    /* if this is the last merge, just do it */
    if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
      TIM_SORT_MERGE(dst, stack, stack_curr, store);
      stack[0].length += stack[1].length;
      stack_curr--;
      break;
    }
    /* check if the invariant is off for a stack of 2 elements */
    else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
      TIM_SORT_MERGE(dst, stack, stack_curr, store);
      stack[0].length += stack[1].length;
      stack_curr--;
      break;
    } else if (stack_curr == 2) {
      break;
    }

    B = stack[stack_curr - 3].length;
    C = stack[stack_curr - 2].length;
    D = stack[stack_curr - 1].length;

    if (stack_curr >= 4) {
      A = stack[stack_curr - 4].length;
      ABC = (A <= B + C);
    } else {
      ABC = 0;
    }

    BCD = (B <= C + D) || ABC;
    CD = (C <= D);

    /* Both invariants are good */
    if (!BCD && !CD) {
      break;
    }

    /* left merge */
    if (BCD && !CD) {
      TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
      stack[stack_curr - 3].length += stack[stack_curr - 2].length;
      stack[stack_curr - 2] = stack[stack_curr - 1];
      stack_curr--;
    } else {
      /* right merge */
      TIM_SORT_MERGE(dst, stack, stack_curr, store);
      stack[stack_curr - 2].length += stack[stack_curr - 1].length;
      stack_curr--;
    }
  }

  return stack_curr;
}

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) {
  size_t len = COUNT_RUN(dst, *curr, size);
  size_t run = minrun;

  if (run > size - *curr) {
    run = size - *curr;
  }

  if (run > len) {
    BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
    len = run;
  }

  run_stack[*stack_curr].start = *curr;
  run_stack[*stack_curr].length = len;
  (*stack_curr)++;
  *curr += len;

  if (*curr == size) {
    /* finish up */
    while (*stack_curr > 1) {
      TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
      run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
      (*stack_curr)--;
    }

    if (store->storage != NULL) {
      free(store->storage);
      store->storage = NULL;
    }

    return 0;
  }

  return 1;
}

void TIM_SORT(SORT_TYPE *dst, const size_t size) {
  size_t minrun;
  TEMP_STORAGE_T _store, *store;
  TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
  size_t stack_curr = 0;
  size_t curr = 0;

  /* don't bother sorting an array of size 1 */
  if (size <= 1) {
    return;
  }

  if (size < 64) {
    BINARY_INSERTION_SORT(dst, size);
    return;
  }

  /* compute the minimum run length */
  minrun = compute_minrun(size);
  /* temporary storage for merges */
  store = &_store;
  store->alloc = 0;
  store->storage = NULL;

  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
    return;
  }

  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
    return;
  }

  if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
    return;
  }

  while (1) {
    if (!CHECK_INVARIANT(run_stack, stack_curr)) {
      stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
      continue;
    }

    if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
      return;
    }
  }
}

#undef SORT_CONCAT
#undef SORT_MAKE_STR1
#undef SORT_MAKE_STR
#undef SORT_NAME
#undef SORT_TYPE
#undef SORT_CMP
#undef TEMP_STORAGE_T
#undef TIM_SORT_RUN_T
#undef PUSH_NEXT
#undef SORT_SWAP
#undef SORT_CONCAT
#undef SORT_MAKE_STR1
#undef SORT_MAKE_STR
#undef BINARY_INSERTION_FIND
#undef BINARY_INSERTION_SORT_START
#undef BINARY_INSERTION_SORT
#undef REVERSE_ELEMENTS
#undef COUNT_RUN
#undef TIM_SORT
#undef TIM_SORT_RESIZE
#undef TIM_SORT_COLLAPSE
#undef TIM_SORT_RUN_T
#undef TEMP_STORAGE_T

Coverage Report

Created: 2023-06-07 06:14

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Taken from https://github.com/swenson/sort
3		* Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
4		* Removed all code unrelated to Timsort and made minor adjustments for
5		* cross-platform compatibility.
6		*/
7
8		/*
9		* The MIT License (MIT)
10		*
11		* Copyright (c) 2010-2017 Christopher Swenson.
12		* Copyright (c) 2012 Vojtech Fried.
13		* Copyright (c) 2012 Google Inc. All Rights Reserved.
14		*
15		* Permission is hereby granted, free of charge, to any person obtaining a
16		* copy of this software and associated documentation files (the "Software"),
17		* to deal in the Software without restriction, including without limitation
18		* the rights to use, copy, modify, merge, publish, distribute, sublicense,
19		* and/or sell copies of the Software, and to permit persons to whom the
20		* Software is furnished to do so, subject to the following conditions:
21		*
22		* The above copyright notice and this permission notice shall be included in
23		* all copies or substantial portions of the Software.
24		*
25		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28		* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
30		* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31		* DEALINGS IN THE SOFTWARE.
32		*/
33
34		#include <stdlib.h>
35		#include <stdio.h>
36		#include <string.h>
37		#ifdef HAVE_STDINT_H
38		#include <stdint.h>
39		#elif defined(_WIN32)
40		typedef unsigned __int64 uint64_t;
41		#endif
42
43		#ifndef SORT_NAME
44		#error "Must declare SORT_NAME"
45		#endif
46
47		#ifndef SORT_TYPE
48		#error "Must declare SORT_TYPE"
49		#endif
50
51		#ifndef SORT_CMP
52		#define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
53		#endif
54
55		#ifndef TIM_SORT_STACK_SIZE
56		#define TIM_SORT_STACK_SIZE 128
57		#endif
58
59	799k	#define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
60
61
62		/* Common, type-agnostic functions and constants that we don't want to declare twice. */
63		#ifndef SORT_COMMON_H
64		#define SORT_COMMON_H
65
66		#ifndef MAX
67	32.1k	#define MAX(x,y) (((x) > (y) ? (x) : (y)))
68		#endif
69
70		#ifndef MIN
71	59.2k	#define MIN(x,y) (((x) < (y) ? (x) : (y)))
72		#endif
73
74		static int compute_minrun(const uint64_t);
75
76		#ifndef CLZ
77		#if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) \|\| (__GNUC__ > 3))
78	32.1k	#define CLZ __builtin_clzll
79		#else
80
81		static int clzll(uint64_t);
82
83		/* adapted from Hacker's Delight */
84		static int clzll(uint64_t x) {
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		}
124
125		#define CLZ clzll
126		#endif
127		#endif
128
129	32.1k	static __inline int compute_minrun(const uint64_t size) {
130	32.1k	const int top_bit = 64 - CLZ(size);
131	32.1k	const int shift = MAX(top_bit, 6) - 6;
132	32.1k	const int minrun = size >> shift;
133	32.1k	const uint64_t mask = (1ULL << shift) - 1;
134
135	32.1k	if (mask & size) {
136	22.8k	return minrun + 1;
137	22.8k	}
138
139	9.28k	return minrun;
140	32.1k	}
141
142		#endif /* SORT_COMMON_H */
143
144	6.64M	#define SORT_CONCAT(x, y) x ## _ ## y
145	6.64M	#define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
146	6.64M	#define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
147
148	4.09M	#define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find)
149	1.15M	#define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)
150	1.11M	#define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort)
151	13.2k	#define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements)
152	91.3k	#define COUNT_RUN SORT_MAKE_STR(count_run)
153	34.7k	#define CHECK_INVARIANT SORT_MAKE_STR(check_invariant)
154		#define TIM_SORT SORT_MAKE_STR(tim_sort)
155	59.2k	#define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize)
156	59.2k	#define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge)
157	13.8k	#define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse)
158
159		#ifndef MAX
160		#define MAX(x,y) (((x) > (y) ? (x) : (y)))
161		#endif
162		#ifndef MIN
163		#define MIN(x,y) (((x) < (y) ? (x) : (y)))
164		#endif
165
166		typedef struct {
167		size_t start;
168		size_t length;
169		} TIM_SORT_RUN_T;
170
171
172		void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
173		void TIM_SORT(SORT_TYPE *dst, const size_t size);
174
175
176		/* Function used to do a binary search for binary insertion sort */
177		static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
178	4.09M	const size_t size) {
179	4.09M	size_t l, c, r;
180	4.09M	SORT_TYPE cx;
181	4.09M	l = 0;
182	4.09M	r = size - 1;
183	4.09M	c = r >> 1;
184
185		/* check for out of bounds at the beginning. */
186	4.09M	if (SORT_CMP(x, dst[0]) < 0) {
187	875k	return 0;
188	3.22M	} else if (SORT_CMP(x, dst[r]) > 0) {
189	0	return r;
190	0	}
191
192	3.22M	cx = dst[c];
193
194	8.24M	while (1) {
195	8.24M	const int val = SORT_CMP(x, cx);
196
197	8.24M	if (val < 0) {
198	560k	if (c - l <= 1) {
199	258k	return c;
200	258k	}
201
202	301k	r = c;
203	7.68M	} else { /* allow = for stability. The binary search favors the right. */
204	7.68M	if (r - c <= 1) {
205	2.96M	return c + 1;
206	2.96M	}
207
208	4.72M	l = c;
209	4.72M	}
210
211	5.02M	c = l + ((r - l) >> 1);
212	5.02M	cx = dst[c];
213	5.02M	}
214	3.22M	}
215
216		/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
217	1.15M	static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
218	1.15M	size_t i;
219
220	17.3M	for (i = start; i < size; i++) {
221	16.1M	size_t j;
222	16.1M	SORT_TYPE x;
223	16.1M	size_t location;
224
225		/* If this entry is already correct, just move along */
226	16.1M	if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
227	12.0M	continue;
228	12.0M	}
229
230		/* Else we need to find the right place, shift everything over, and squeeze in */
231	4.09M	x = dst[i];
232	4.09M	location = BINARY_INSERTION_FIND(dst, x, i);
233
234	16.2M	for (j = i - 1; j >= location; j--) {
235	13.0M	dst[j + 1] = dst[j];
236
237	13.0M	if (j == 0) { /* check edge case because j is unsigned */
238	875k	break;
239	875k	}
240	13.0M	}
241
242	4.09M	dst[location] = x;
243	4.09M	}
244	1.15M	}
245
246		/* Binary insertion sort */
247	1.11M	void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
248		/* don't bother sorting an array of size <= 1 */
249	1.11M	if (size <= 1) {
250	0	return;
251	0	}
252
253	1.11M	BINARY_INSERTION_SORT_START(dst, 1, size);
254	1.11M	}
255
256		/* timsort implementation, based on timsort.txt */
257
258	13.2k	static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
259	813k	while (1) {
260	813k	if (start >= end) {
261	13.2k	return;
262	13.2k	}
263
264	799k	SORT_SWAP(dst[start], dst[end]);
265	799k	start++;
266	799k	end--;
267	799k	}
268	13.2k	}
269
270	91.3k	static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
271	91.3k	size_t curr;
272
273	91.3k	if (size - start == 1) {
274	24.0k	return 1;
275	24.0k	}
276
277	67.3k	if (start >= size - 2) {
278	349	if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
279	1	SORT_SWAP(dst[size - 2], dst[size - 1]);
280	1	}
281
282	349	return 2;
283	349	}
284
285	66.9k	curr = start + 2;
286
287	66.9k	if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
288		/* increasing run */
289	31.5M	while (1) {
290	31.5M	if (curr == size - 1) {
291	29.8k	break;
292	29.8k	}
293
294	31.4M	if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
295	23.8k	break;
296	23.8k	}
297
298	31.4M	curr++;
299	31.4M	}
300
301	53.6k	return curr - start;
302	53.6k	} else {
303		/* decreasing run */
304	1.59M	while (1) {
305	1.59M	if (curr == size - 1) {
306	12	break;
307	12	}
308
309	1.59M	if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
310	13.2k	break;
311	13.2k	}
312
313	1.57M	curr++;
314	1.57M	}
315
316		/* reverse in-place */
317	13.2k	REVERSE_ELEMENTS(dst, start, curr - 1);
318	13.2k	return curr - start;
319	13.2k	}
320	66.9k	}
321
322	34.7k	static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
323	34.7k	size_t A, B, C;
324
325	34.7k	if (stack_curr < 2) {
326	3.39k	return 1;
327	3.39k	}
328
329	31.3k	if (stack_curr == 2) {
330	9.48k	const size_t A1 = stack[stack_curr - 2].length;
331	9.48k	const size_t B1 = stack[stack_curr - 1].length;
332
333	9.48k	if (A1 <= B1) {
334	148	return 0;
335	148	}
336
337	9.34k	return 1;
338	9.48k	}
339
340	21.8k	A = stack[stack_curr - 3].length;
341	21.8k	B = stack[stack_curr - 2].length;
342	21.8k	C = stack[stack_curr - 1].length;
343
344	21.8k	if ((A <= B + C) \|\| (B <= C)) {
345	13.6k	return 0;
346	13.6k	}
347
348	8.19k	return 1;
349	21.8k	}
350
351		typedef struct {
352		size_t alloc;
353		SORT_TYPE *storage;
354		} TEMP_STORAGE_T;
355
356	59.2k	static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
357	59.2k	if (store->alloc < new_size) {
358	40.0k	SORT_TYPE tempstore = (SORT_TYPE )realloc(store->storage, new_size * sizeof(SORT_TYPE));
359
360	40.0k	if (tempstore == NULL) {
361	0	fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
362	0	(unsigned long)(sizeof(SORT_TYPE) * new_size));
363	0	exit(1);
364	0	}
365
366	40.0k	store->storage = tempstore;
367	40.0k	store->alloc = new_size;
368	40.0k	}
369	59.2k	}
370
371		static void TIM_SORT_MERGE(SORT_TYPE dst, const TIM_SORT_RUN_T stack, const int stack_curr,
372	59.2k	TEMP_STORAGE_T *store) {
373	59.2k	const size_t A = stack[stack_curr - 2].length;
374	59.2k	const size_t B = stack[stack_curr - 1].length;
375	59.2k	const size_t curr = stack[stack_curr - 2].start;
376	59.2k	SORT_TYPE *storage;
377	59.2k	size_t i, j, k;
378	59.2k	TIM_SORT_RESIZE(store, MIN(A, B));
379	59.2k	storage = store->storage;
380
381		/* left merge */
382	59.2k	if (A < B) {
383	9.11k	memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
384	9.11k	i = 0;
385	9.11k	j = curr + A;
386
387	2.93M	for (k = curr; k < curr + A + B; k++) {
388	2.93M	if ((i < A) && (j < curr + A + B)) {
389	2.91M	if (SORT_CMP(storage[i], dst[j]) <= 0) {
390	1.13M	dst[k] = storage[i++];
391	1.78M	} else {
392	1.78M	dst[k] = dst[j++];
393	1.78M	}
394	2.91M	} else if (i < A) {
395	6.44k	dst[k] = storage[i++];
396	8.58k	} else {
397	8.58k	break;
398	8.58k	}
399	2.93M	}
400	50.1k	} else {
401		/* right merge */
402	50.1k	memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
403	50.1k	i = B;
404	50.1k	j = curr + A;
405	50.1k	k = curr + A + B;
406
407	3.67M	while (k > curr) {
408	3.67M	k--;
409	3.67M	if ((i > 0) && (j > curr)) {
410	3.62M	if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
411	133k	dst[k] = dst[--j];
412	3.48M	} else {
413	3.48M	dst[k] = storage[--i];
414	3.48M	}
415	3.62M	} else if (i > 0) {
416	177	dst[k] = storage[--i];
417	49.9k	} else {
418	49.9k	break;
419	49.9k	}
420	3.67M	}
421	50.1k	}
422	59.2k	}
423
424		static int TIM_SORT_COLLAPSE(SORT_TYPE dst, TIM_SORT_RUN_T stack, int stack_curr,
425	13.8k	TEMP_STORAGE_T *store, const size_t size) {
426	31.1k	while (1) {
427	31.1k	size_t A, B, C, D;
428	31.1k	int ABC, BCD, CD;
429
430		/* if the stack only has one thing on it, we are done with the collapse */
431	31.1k	if (stack_curr <= 1) {
432	0	break;
433	0	}
434
435		/* if this is the last merge, just do it */
436	31.1k	if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
437	0	TIM_SORT_MERGE(dst, stack, stack_curr, store);
438	0	stack[0].length += stack[1].length;
439	0	stack_curr--;
440	0	break;
441	0	}
442		/* check if the invariant is off for a stack of 2 elements */
443	31.1k	else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
444	3.39k	TIM_SORT_MERGE(dst, stack, stack_curr, store);
445	3.39k	stack[0].length += stack[1].length;
446	3.39k	stack_curr--;
447	3.39k	break;
448	27.7k	} else if (stack_curr == 2) {
449	7.28k	break;
450	7.28k	}
451
452	20.4k	B = stack[stack_curr - 3].length;
453	20.4k	C = stack[stack_curr - 2].length;
454	20.4k	D = stack[stack_curr - 1].length;
455
456	20.4k	if (stack_curr >= 4) {
457	8.33k	A = stack[stack_curr - 4].length;
458	8.33k	ABC = (A <= B + C);
459	12.1k	} else {
460	12.1k	ABC = 0;
461	12.1k	}
462
463	20.4k	BCD = (B <= C + D) \|\| ABC;
464	20.4k	CD = (C <= D);
465
466		/* Both invariants are good */
467	20.4k	if (!BCD && !CD) {
468	3.14k	break;
469	3.14k	}
470
471		/* left merge */
472	17.3k	if (BCD && !CD) {
473	3.07k	TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
474	3.07k	stack[stack_curr - 3].length += stack[stack_curr - 2].length;
475	3.07k	stack[stack_curr - 2] = stack[stack_curr - 1];
476	3.07k	stack_curr--;
477	14.2k	} else {
478		/* right merge */
479	14.2k	TIM_SORT_MERGE(dst, stack, stack_curr, store);
480	14.2k	stack[stack_curr - 2].length += stack[stack_curr - 1].length;
481	14.2k	stack_curr--;
482	14.2k	}
483	17.3k	}
484
485	13.8k	return stack_curr;
486	13.8k	}
487
488		static __inline int PUSH_NEXT(SORT_TYPE *dst,
489		const size_t size,
490		TEMP_STORAGE_T *store,
491		const size_t minrun,
492		TIM_SORT_RUN_T *run_stack,
493		size_t *stack_curr,
494	91.3k	size_t *curr) {
495	91.3k	size_t len = COUNT_RUN(dst, *curr, size);
496	91.3k	size_t run = minrun;
497
498	91.3k	if (run > size - *curr) {
499	28.7k	run = size - *curr;
500	28.7k	}
501
502	91.3k	if (run > len) {
503	36.7k	BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
504	36.7k	len = run;
505	36.7k	}
506
507	91.3k	run_stack[stack_curr].start = curr;
508	91.3k	run_stack[*stack_curr].length = len;
509	91.3k	(*stack_curr)++;
510	91.3k	*curr += len;
511
512	91.3k	if (*curr == size) {
513		/* finish up */
514	70.5k	while (*stack_curr > 1) {
515	38.4k	TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
516	38.4k	run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length;
517	38.4k	(*stack_curr)--;
518	38.4k	}
519
520	32.1k	if (store->storage != NULL) {
521	32.1k	free(store->storage);
522	32.1k	store->storage = NULL;
523	32.1k	}
524
525	32.1k	return 0;
526	32.1k	}
527
528	59.2k	return 1;
529	91.3k	}
530
531	1.39M	void TIM_SORT(SORT_TYPE *dst, const size_t size) {
532	1.39M	size_t minrun;
533	1.39M	TEMP_STORAGE_T _store, *store;
534	1.39M	TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
535	1.39M	size_t stack_curr = 0;
536	1.39M	size_t curr = 0;
537
538		/* don't bother sorting an array of size 1 */
539	1.39M	if (size <= 1) {
540	245k	return;
541	245k	}
542
543	1.15M	if (size < 64) {
544	1.11M	BINARY_INSERTION_SORT(dst, size);
545	1.11M	return;
546	1.11M	}
547
548		/* compute the minimum run length */
549	32.1k	minrun = compute_minrun(size);
550		/* temporary storage for merges */
551	32.1k	store = &_store;
552	32.1k	store->alloc = 0;
553	32.1k	store->storage = NULL;
554
555	32.1k	if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
556	0	return;
557	0	}
558
559	32.1k	if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
560	25.9k	return;
561	25.9k	}
562
563	6.19k	if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
564	2.70k	return;
565	2.70k	}
566
567	34.7k	while (1) {
568	34.7k	if (!CHECK_INVARIANT(run_stack, stack_curr)) {
569	13.8k	stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
570	13.8k	continue;
571	13.8k	}
572
573	20.9k	if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
574	3.48k	return;
575	3.48k	}
576	20.9k	}
577	3.48k	}
578
579		#undef SORT_CONCAT
580		#undef SORT_MAKE_STR1
581		#undef SORT_MAKE_STR
582		#undef SORT_NAME
583		#undef SORT_TYPE
584		#undef SORT_CMP
585		#undef TEMP_STORAGE_T
586		#undef TIM_SORT_RUN_T
587		#undef PUSH_NEXT
588		#undef SORT_SWAP
589		#undef SORT_CONCAT
590		#undef SORT_MAKE_STR1
591		#undef SORT_MAKE_STR
592		#undef BINARY_INSERTION_FIND
593		#undef BINARY_INSERTION_SORT_START
594		#undef BINARY_INSERTION_SORT
595		#undef REVERSE_ELEMENTS
596		#undef COUNT_RUN
597		#undef TIM_SORT
598		#undef TIM_SORT_RESIZE
599		#undef TIM_SORT_COLLAPSE
600		#undef TIM_SORT_RUN_T
601		#undef TEMP_STORAGE_T