[libxml2] Upgrade timsort.h to latest revision

[Nick Wellnhofer <nwellnhof src gnome org>]

commit bec3c17fae1610c6e39f982a35b391d9f1c84943
Author: Nick Wellnhofer <wellnhofer aevum de>
Date:   Thu Oct 12 15:15:58 2017 +0200

    Upgrade timsort.h to latest revision
    
    Upgrade timsort.h to revision 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
    from https://github.com/swenson/sort
    
    Removed all code unrelated to Timsort and made minor adjustments for
    cross-platform compatibility.

 timsort.h |  579 +++++++++++++++++++++++++++++++++++--------------------------
 1 files changed, 331 insertions(+), 248 deletions(-)
---
diff --git a/timsort.h b/timsort.h
index 724e066..6772928 100644
--- a/timsort.h
+++ b/timsort.h
@@ -1,312 +1,350 @@
 /*
- * taken from https://github.com/swenson/sort
- * Kept as is for the moment to be able to apply upstream patches for that
- * code, currently used only to speed up XPath node sorting, see xpath.c
+ * Taken from https://github.com/swenson/sort
+ * Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
+ * Removed all code unrelated to Timsort and made minor adjustments for
+ * cross-platform compatibility.
  */
 
 /*
- * All code in this header, unless otherwise specified, is hereby licensed under the MIT Public License:
-
-Copyright (c) 2010 Christopher Swenson
-
-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.
-*/
+ * 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>
-#else
-#ifdef HAVE_INTTYPES_H
-#include <inttypes.h>
 #elif defined(_WIN32)
-typedef __int64 int64_t;
 typedef unsigned __int64 uint64_t;
 #endif
+
+#ifndef SORT_NAME
+#error "Must declare SORT_NAME"
 #endif
 
-#ifndef MK_UINT64
-#if defined(_MSC_VER) && _MSC_VER < 1300
-#define MK_UINT64(x) ((uint64_t)(x))
-#else
-#define MK_UINT64(x) x##ULL
+#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-agnosting 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
 
-int compute_minrun(uint64_t);
+static int compute_minrun(const uint64_t);
 
 #ifndef CLZ
-#if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3))
+#ifdef __GNUC__
 #define CLZ __builtin_clzll
 #else
 
-int clzll(uint64_t);
+static int clzll(uint64_t);
 
 /* adapted from Hacker's Delight */
-int clzll(uint64_t x) /* {{{ */
-{
+static int clzll(uint64_t x) {
   int n;
 
-  if (x == 0) return(64);
+  if (x == 0) {
+    return 64;
+  }
+
   n = 0;
-  if (x <= MK_UINT64(0x00000000FFFFFFFF)) {n = n + 32; x = x << 32;}
-  if (x <= MK_UINT64(0x0000FFFFFFFFFFFF)) {n = n + 16; x = x << 16;}
-  if (x <= MK_UINT64(0x00FFFFFFFFFFFFFF)) {n = n + 8; x = x << 8;}
-  if (x <= MK_UINT64(0x0FFFFFFFFFFFFFFF)) {n = n + 4; x = x << 4;}
-  if (x <= MK_UINT64(0x3FFFFFFFFFFFFFFF)) {n = n + 2; x = x << 2;}
-  if (x <= MK_UINT64(0x7FFFFFFFFFFFFFFF)) {n = n + 1;}
+
+  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
 
-int compute_minrun(uint64_t size) /* {{{ */
-{
+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 = (MK_UINT64(1) << shift) - 1;
-  if (mask & size) return minrun + 1;
-  return minrun;
-}
-/* }}} */
-
-#ifndef SORT_NAME
-#error "Must declare SORT_NAME"
-#endif
+  const uint64_t mask = (1ULL << shift) - 1;
 
-#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
+  if (mask & size) {
+    return minrun + 1;
+  }
 
+  return minrun;
+}
 
-#define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
+#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)
+#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)
 
-#define TIM_SORT_RUN_T         SORT_MAKE_STR(tim_sort_run_t)
-#define TEMP_STORAGE_T         SORT_MAKE_STR(temp_storage_t)
+#ifndef MAX
+#define MAX(x,y) (((x) > (y) ? (x) : (y)))
+#endif
+#ifndef MIN
+#define MIN(x,y) (((x) < (y) ? (x) : (y)))
+#endif
 
 typedef struct {
-  int64_t start;
-  int64_t length;
+  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 int64_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x, const size_t size)
-{
-  int64_t l, c, r;
-  SORT_TYPE lx;
+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;
-  lx = dst[l];
 
-  /* check for beginning conditions */
-  if (SORT_CMP(x, lx) < 0)
+  /* check for out of bounds at the beginning. */
+  if (SORT_CMP(x, dst[0]) < 0) {
     return 0;
-  else if (SORT_CMP(x, lx) == 0)
-  {
-    int64_t i = 1;
-    while (SORT_CMP(x, dst[i]) == 0) i++;
-    return i;
+  } else if (SORT_CMP(x, dst[r]) > 0) {
+    return r;
   }
 
   cx = dst[c];
-  while (1)
-  {
+
+  while (1) {
     const int val = SORT_CMP(x, cx);
-    if (val < 0)
-    {
-      if (c - l <= 1) return c;
+
+    if (val < 0) {
+      if (c - l <= 1) {
+        return c;
+      }
+
       r = c;
-    }
-    else if (val > 0)
-    {
-      if (r - c <= 1) return c + 1;
+    } else { /* allow = for stability. The binary search favors the right. */
+      if (r - c <= 1) {
+        return c + 1;
+      }
+
       l = c;
-      lx = cx;
-    }
-    else
-    {
-      do
-      {
-        cx = dst[++c];
-      } while (SORT_CMP(x, cx) == 0);
-      return 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)
-{
-  int64_t i;
-  for (i = start; i < (int64_t) size; i++)
-  {
-    int64_t j;
+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;
-    int64_t location;
+    size_t location;
+
     /* If this entry is already correct, just move along */
-    if (SORT_CMP(dst[i - 1], dst[i]) <= 0) continue;
+    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--)
-    {
+
+    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)
-{
+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 void REVERSE_ELEMENTS(SORT_TYPE *dst, int64_t start, int64_t end)
-{
-  while (1)
-  {
-    if (start >= end) return;
+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 int64_t COUNT_RUN(SORT_TYPE *dst, const int64_t start, const size_t size)
-{
-  int64_t curr;
-  if (size - start == 1) return 1;
-  if (start >= (int64_t) size - 2)
-  {
-    if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0)
+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)
-  {
+  if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
     /* increasing run */
-    while (1)
-    {
-      if (curr == (int64_t) size - 1) break;
-      if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) break;
+    while (1) {
+      if (curr == size - 1) {
+        break;
+      }
+
+      if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
+        break;
+      }
+
       curr++;
     }
+
     return curr - start;
-  }
-  else
-  {
+  } else {
     /* decreasing run */
-    while (1)
-    {
-      if (curr == (int64_t) size - 1) break;
-      if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) break;
+    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;
   }
 }
 
-#define PUSH_NEXT() do {\
-len = COUNT_RUN(dst, curr, size);\
-run = minrun;\
-if (run < minrun) run = minrun;\
-if (run > (int64_t) 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 == (int64_t) 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;\
-}\
-}\
-while (0)
-
-static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr)
-{
-  int64_t A, B, C;
-  if (stack_curr < 2) return 1;
-  if (stack_curr == 2)
-  {
-    const int64_t A1 = stack[stack_curr - 2].length;
-    const int64_t B1 = stack[stack_curr - 1].length;
-    if (A1 <= B1) return 0;
+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;
+
+  if ((A <= B + C) || (B <= C)) {
+    return 0;
+  }
+
   return 1;
 }
 
@@ -315,85 +353,77 @@ typedef struct {
   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)
-  {
+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));
+
+    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 int64_t A = stack[stack_curr - 2].length;
-  const int64_t B = stack[stack_curr - 1].length;
-  const int64_t curr = stack[stack_curr - 2].start;
+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;
-  int64_t i, j, k;
-
+  size_t i, j, k;
   TIM_SORT_RESIZE(store, MIN(A, B));
   storage = store->storage;
 
   /* left merge */
-  if (A < B)
-  {
+  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)
+    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
+        } else {
           dst[k] = dst[j++];
-      }
-      else if (i < A)
-      {
+        }
+      } else if (i < A) {
         dst[k] = storage[i++];
+      } else {
+        break;
       }
-      else
-        dst[k] = dst[j++];
     }
-  }
-  /* right merge */
-  else
-  {
+  } else {
+    /* right merge */
     memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
-    i = B - 1;
-    j = curr + A - 1;
-
-    for (k = curr + A + B - 1; k >= curr; k--)
-    {
-      if ((i >= 0) && (j >= curr))
-      {
-          if (SORT_CMP(dst[j], storage[i]) > 0)
-            dst[k] = dst[j--];
-          else
-            dst[k] = storage[i--];
+    i = B;
+    j = curr + A;
+    k = curr + A + B;
+
+    while (k-- > curr) {
+      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;
       }
-      else if (i >= 0)
-        dst[k] = storage[i--];
-      else
-        dst[k] = dst[j--];
     }
   }
 }
 
-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 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) {
-    int64_t A, B, C, D;
+    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 */
@@ -454,41 +484,94 @@ static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_cu
   return stack_curr;
 }
 
-void TIM_SORT(SORT_TYPE *dst, const size_t size)
-{
-  int minrun;
+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) {
+  /* don't bother sorting an array of size 1 */
+  if (size <= 1) {
+    return;
+  }
+
+  size_t minrun;
   TEMP_STORAGE_T _store, *store;
-  TIM_SORT_RUN_T run_stack[128];
-  int stack_curr = 0;
-  int64_t len, run;
-  int64_t curr = 0;
+  TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
+  size_t stack_curr = 0;
+  size_t curr = 0;
 
-  if (size < 64)
-  {
+  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;
 
-  PUSH_NEXT();
-  PUSH_NEXT();
-  PUSH_NEXT();
+  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))
-    {
+  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;
     }
-    PUSH_NEXT();
+
+    if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
+      return;
+    }
   }
 }