1/*
2 * taken from https://github.com/swenson/sort
3 * Kept as is for the moment to be able to apply upstream patches for that
4 * code, currently used only to speed up XPath node sorting, see xpath.c
5 */
6
7/*
8 * All code in this header, unless otherwise specified, is hereby licensed under the MIT Public License:
9
10Copyright (c) 2010 Christopher Swenson
11
12Permission 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:
13
14The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
15
16THE 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.
17*/
18
19#include <stdlib.h>
20#include <stdio.h>
21#include <string.h>
22#ifdef HAVE_STDINT_H
23#include <stdint.h>
24#else
25#ifdef HAVE_INTTYPES_H
26#include <inttypes.h>
27#elif defined(WIN32)
28typedef __int64 int64_t;
29typedef unsigned __int64 uint64_t;
30#endif
31#endif
32
33#ifndef MK_UINT64
34#if defined(WIN32) && defined(_MSC_VER) && _MSC_VER < 1300
35#define MK_UINT64(x) ((uint64_t)(x))
36#else
37#define MK_UINT64(x) x##ULL
38#endif
39#endif
40
41#ifndef MAX
42#define MAX(x,y) (((x) > (y) ? (x) : (y)))
43#endif
44#ifndef MIN
45#define MIN(x,y) (((x) < (y) ? (x) : (y)))
46#endif
47
48int compute_minrun(uint64_t);
49
50#ifndef CLZ
51#if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3))
52#define CLZ __builtin_clzll
53#else
54
55int clzll(uint64_t);
56
57/* adapted from Hacker's Delight */
58int clzll(uint64_t x) /* {{{ */
59{
60  int n;
61
62  if (x == 0) return(64);
63  n = 0;
64  if (x <= 0x00000000FFFFFFFFL) {n = n + 32; x = x << 32;}
65  if (x <= 0x0000FFFFFFFFFFFFL) {n = n + 16; x = x << 16;}
66  if (x <= 0x00FFFFFFFFFFFFFFL) {n = n + 8; x = x << 8;}
67  if (x <= 0x0FFFFFFFFFFFFFFFL) {n = n + 4; x = x << 4;}
68  if (x <= 0x3FFFFFFFFFFFFFFFL) {n = n + 2; x = x << 2;}
69  if (x <= 0x7FFFFFFFFFFFFFFFL) {n = n + 1;}
70  return n;
71}
72/* }}} */
73
74#define CLZ clzll
75#endif
76#endif
77
78int compute_minrun(uint64_t size) /* {{{ */
79{
80  const int top_bit = 64 - CLZ(size);
81  const int shift = MAX(top_bit, 6) - 6;
82  const int minrun = size >> shift;
83  const uint64_t mask = (MK_UINT64(1) << shift) - 1;
84  if (mask & size) return minrun + 1;
85  return minrun;
86}
87/* }}} */
88
89#ifndef SORT_NAME
90#error "Must declare SORT_NAME"
91#endif
92
93#ifndef SORT_TYPE
94#error "Must declare SORT_TYPE"
95#endif
96
97#ifndef SORT_CMP
98#define SORT_CMP(x, y)  ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
99#endif
100
101
102#define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
103
104#define SORT_CONCAT(x, y) x ## _ ## y
105#define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
106#define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
107
108#define BINARY_INSERTION_FIND  SORT_MAKE_STR(binary_insertion_find)
109#define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)
110#define BINARY_INSERTION_SORT  SORT_MAKE_STR(binary_insertion_sort)
111#define REVERSE_ELEMENTS       SORT_MAKE_STR(reverse_elements)
112#define COUNT_RUN              SORT_MAKE_STR(count_run)
113#define CHECK_INVARIANT        SORT_MAKE_STR(check_invariant)
114#define TIM_SORT               SORT_MAKE_STR(tim_sort)
115#define TIM_SORT_RESIZE        SORT_MAKE_STR(tim_sort_resize)
116#define TIM_SORT_MERGE         SORT_MAKE_STR(tim_sort_merge)
117#define TIM_SORT_COLLAPSE      SORT_MAKE_STR(tim_sort_collapse)
118
119#define TIM_SORT_RUN_T         SORT_MAKE_STR(tim_sort_run_t)
120#define TEMP_STORAGE_T         SORT_MAKE_STR(temp_storage_t)
121
122typedef struct {
123  int64_t start;
124  int64_t length;
125} TIM_SORT_RUN_T;
126
127void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
128void TIM_SORT(SORT_TYPE *dst, const size_t size);
129
130/* Function used to do a binary search for binary insertion sort */
131static int64_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x, const size_t size)
132{
133  int64_t l, c, r;
134  SORT_TYPE lx;
135  SORT_TYPE cx;
136  l = 0;
137  r = size - 1;
138  c = r >> 1;
139  lx = dst[l];
140
141  /* check for beginning conditions */
142  if (SORT_CMP(x, lx) < 0)
143    return 0;
144  else if (SORT_CMP(x, lx) == 0)
145  {
146    int64_t i = 1;
147    while (SORT_CMP(x, dst[i]) == 0) i++;
148    return i;
149  }
150
151  cx = dst[c];
152  while (1)
153  {
154    const int val = SORT_CMP(x, cx);
155    if (val < 0)
156    {
157      if (c - l <= 1) return c;
158      r = c;
159    }
160    else if (val > 0)
161    {
162      if (r - c <= 1) return c + 1;
163      l = c;
164      lx = cx;
165    }
166    else
167    {
168      do
169      {
170        cx = dst[++c];
171      } while (SORT_CMP(x, cx) == 0);
172      return c;
173    }
174    c = l + ((r - l) >> 1);
175    cx = dst[c];
176  }
177}
178
179/* Binary insertion sort, but knowing that the first "start" entries are sorted.  Used in timsort. */
180static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size)
181{
182  int64_t i;
183  for (i = start; i < (int64_t) size; i++)
184  {
185    int64_t j;
186    SORT_TYPE x;
187    int64_t location;
188    /* If this entry is already correct, just move along */
189    if (SORT_CMP(dst[i - 1], dst[i]) <= 0) continue;
190
191    /* Else we need to find the right place, shift everything over, and squeeze in */
192    x = dst[i];
193    location = BINARY_INSERTION_FIND(dst, x, i);
194    for (j = i - 1; j >= location; j--)
195    {
196      dst[j + 1] = dst[j];
197    }
198    dst[location] = x;
199  }
200}
201
202/* Binary insertion sort */
203void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size)
204{
205  BINARY_INSERTION_SORT_START(dst, 1, size);
206}
207
208/* timsort implementation, based on timsort.txt */
209
210static void REVERSE_ELEMENTS(SORT_TYPE *dst, int64_t start, int64_t end)
211{
212  while (1)
213  {
214    if (start >= end) return;
215    SORT_SWAP(dst[start], dst[end]);
216    start++;
217    end--;
218  }
219}
220
221static int64_t COUNT_RUN(SORT_TYPE *dst, const int64_t start, const size_t size)
222{
223  int64_t curr;
224  if (size - start == 1) return 1;
225  if (start >= (int64_t) size - 2)
226  {
227    if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0)
228      SORT_SWAP(dst[size - 2], dst[size - 1]);
229    return 2;
230  }
231
232  curr = start + 2;
233
234  if (SORT_CMP(dst[start], dst[start + 1]) <= 0)
235  {
236    /* increasing run */
237    while (1)
238    {
239      if (curr == (int64_t) size - 1) break;
240      if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) break;
241      curr++;
242    }
243    return curr - start;
244  }
245  else
246  {
247    /* decreasing run */
248    while (1)
249    {
250      if (curr == (int64_t) size - 1) break;
251      if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) break;
252      curr++;
253    }
254    /* reverse in-place */
255    REVERSE_ELEMENTS(dst, start, curr - 1);
256    return curr - start;
257  }
258}
259
260#define PUSH_NEXT() do {\
261len = COUNT_RUN(dst, curr, size);\
262run = minrun;\
263if (run < minrun) run = minrun;\
264if (run > (int64_t) size - curr) run = size - curr;\
265if (run > len)\
266{\
267  BINARY_INSERTION_SORT_START(&dst[curr], len, run);\
268  len = run;\
269}\
270{\
271run_stack[stack_curr].start = curr;\
272run_stack[stack_curr].length = len;\
273stack_curr++;\
274}\
275curr += len;\
276if (curr == (int64_t) size)\
277{\
278  /* finish up */ \
279  while (stack_curr > 1) \
280  { \
281    TIM_SORT_MERGE(dst, run_stack, stack_curr, store); \
282    run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
283    stack_curr--; \
284  } \
285  if (store->storage != NULL)\
286  {\
287    free(store->storage);\
288    store->storage = NULL;\
289  }\
290  return;\
291}\
292}\
293while (0)
294
295static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr)
296{
297  int64_t A, B, C;
298  if (stack_curr < 2) return 1;
299  if (stack_curr == 2)
300  {
301    const int64_t A1 = stack[stack_curr - 2].length;
302    const int64_t B1 = stack[stack_curr - 1].length;
303    if (A1 <= B1) return 0;
304    return 1;
305  }
306  A = stack[stack_curr - 3].length;
307  B = stack[stack_curr - 2].length;
308  C = stack[stack_curr - 1].length;
309  if ((A <= B + C) || (B <= C)) return 0;
310  return 1;
311}
312
313typedef struct {
314  size_t alloc;
315  SORT_TYPE *storage;
316} TEMP_STORAGE_T;
317
318
319static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size)
320{
321  if (store->alloc < new_size)
322  {
323    SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
324    if (tempstore == NULL)
325    {
326      fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes", sizeof(SORT_TYPE) * new_size);
327      exit(1);
328    }
329    store->storage = tempstore;
330    store->alloc = new_size;
331  }
332}
333
334static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr, TEMP_STORAGE_T *store)
335{
336  const int64_t A = stack[stack_curr - 2].length;
337  const int64_t B = stack[stack_curr - 1].length;
338  const int64_t curr = stack[stack_curr - 2].start;
339  SORT_TYPE *storage;
340  int64_t i, j, k;
341
342  TIM_SORT_RESIZE(store, MIN(A, B));
343  storage = store->storage;
344
345  /* left merge */
346  if (A < B)
347  {
348    memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
349    i = 0;
350    j = curr + A;
351
352    for (k = curr; k < curr + A + B; k++)
353    {
354      if ((i < A) && (j < curr + A + B))
355      {
356        if (SORT_CMP(storage[i], dst[j]) <= 0)
357          dst[k] = storage[i++];
358        else
359          dst[k] = dst[j++];
360      }
361      else if (i < A)
362      {
363        dst[k] = storage[i++];
364      }
365      else
366        dst[k] = dst[j++];
367    }
368  }
369  /* right merge */
370  else
371  {
372    memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
373    i = B - 1;
374    j = curr + A - 1;
375
376    for (k = curr + A + B - 1; k >= curr; k--)
377    {
378      if ((i >= 0) && (j >= curr))
379      {
380          if (SORT_CMP(dst[j], storage[i]) > 0)
381            dst[k] = dst[j--];
382          else
383            dst[k] = storage[i--];
384      }
385      else if (i >= 0)
386        dst[k] = storage[i--];
387      else
388        dst[k] = dst[j--];
389    }
390  }
391}
392
393static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr, TEMP_STORAGE_T *store, const size_t size)
394{
395  while (1)
396  {
397    int64_t A, B, C;
398    /* if the stack only has one thing on it, we are done with the collapse */
399    if (stack_curr <= 1) break;
400    /* if this is the last merge, just do it */
401    if ((stack_curr == 2) &&
402        (stack[0].length + stack[1].length == (int64_t) size))
403    {
404      TIM_SORT_MERGE(dst, stack, stack_curr, store);
405      stack[0].length += stack[1].length;
406      stack_curr--;
407      break;
408    }
409    /* check if the invariant is off for a stack of 2 elements */
410    else if ((stack_curr == 2) && (stack[0].length <= stack[1].length))
411    {
412      TIM_SORT_MERGE(dst, stack, stack_curr, store);
413      stack[0].length += stack[1].length;
414      stack_curr--;
415      break;
416    }
417    else if (stack_curr == 2)
418      break;
419
420    A = stack[stack_curr - 3].length;
421    B = stack[stack_curr - 2].length;
422    C = stack[stack_curr - 1].length;
423
424    /* check first invariant */
425    if (A <= B + C)
426    {
427      if (A < C)
428      {
429        TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
430        stack[stack_curr - 3].length += stack[stack_curr - 2].length;
431        stack[stack_curr - 2] = stack[stack_curr - 1];
432        stack_curr--;
433      }
434      else
435      {
436        TIM_SORT_MERGE(dst, stack, stack_curr, store);
437        stack[stack_curr - 2].length += stack[stack_curr - 1].length;
438        stack_curr--;
439      }
440    }
441    /* check second invariant */
442    else if (B <= C)
443    {
444      TIM_SORT_MERGE(dst, stack, stack_curr, store);
445      stack[stack_curr - 2].length += stack[stack_curr - 1].length;
446      stack_curr--;
447    }
448    else
449      break;
450  }
451  return stack_curr;
452}
453
454void TIM_SORT(SORT_TYPE *dst, const size_t size)
455{
456  int minrun;
457  TEMP_STORAGE_T _store, *store;
458  TIM_SORT_RUN_T run_stack[128];
459  int stack_curr = 0;
460  int64_t len, run;
461  int64_t curr = 0;
462
463  if (size < 64)
464  {
465    BINARY_INSERTION_SORT(dst, size);
466    return;
467  }
468
469  /* compute the minimum run length */
470  minrun = compute_minrun(size);
471
472  /* temporary storage for merges */
473  store = &_store;
474  store->alloc = 0;
475  store->storage = NULL;
476
477  PUSH_NEXT();
478  PUSH_NEXT();
479  PUSH_NEXT();
480
481  while (1)
482  {
483    if (!CHECK_INVARIANT(run_stack, stack_curr))
484    {
485      stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
486      continue;
487    }
488    PUSH_NEXT();
489  }
490}
491
492#undef SORT_CONCAT
493#undef SORT_MAKE_STR1
494#undef SORT_MAKE_STR
495#undef SORT_NAME
496#undef SORT_TYPE
497#undef SORT_CMP
498#undef TEMP_STORAGE_T
499#undef TIM_SORT_RUN_T
500#undef PUSH_NEXT
501#undef SORT_SWAP
502#undef SORT_CONCAT
503#undef SORT_MAKE_STR1
504#undef SORT_MAKE_STR
505#undef BINARY_INSERTION_FIND
506#undef BINARY_INSERTION_SORT_START
507#undef BINARY_INSERTION_SORT
508#undef REVERSE_ELEMENTS
509#undef COUNT_RUN
510#undef TIM_SORT
511#undef TIM_SORT_RESIZE
512#undef TIM_SORT_COLLAPSE
513#undef TIM_SORT_RUN_T
514#undef TEMP_STORAGE_T
515