Roll libxml to 2.9.3

third_party/libxml/src/timsort.h

 /*
  * 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
  */
 
 /*
  * All code in this header, unless otherwise specified, is hereby licensed under the MIT Public License:
 
 Copyright (c) 2010 Christopher Swenson
@@ skipping 374 matching lines @@
       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)
 {
-  while (1)
-  {
-    int64_t A, B, C;
+  while (1) {
+    int64_t A, B, C, D;
+    int ABC, BCD, BD, CD;
+
     /* if the stack only has one thing on it, we are done with the collapse */
-    if (stack_curr <= 1) break;
+    if (stack_curr <= 1) {
+      break;
+    }
+
     /* if this is the last merge, just do it */
-    if ((stack_curr == 2) &&
-        (stack[0].length + stack[1].length == (int64_t) size))
-    {
+    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))
-    {
+    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;
     }
-    else if (stack_curr == 2)
+
+    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);
+    BD = (B < D);
+
+    /* Both invariants are good */
+    if (!BCD && !CD) {
       break;
+    }
 
-    A = stack[stack_curr - 3].length;
-    B = stack[stack_curr - 2].length;
-    C = stack[stack_curr - 1].length;
-
-    /* check first invariant */
-    if (A <= B + C)
-    {
-      if (A < C)
-      {
-        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
-      {
-        TIM_SORT_MERGE(dst, stack, stack_curr, store);
-        stack[stack_curr - 2].length += stack[stack_curr - 1].length;
-        stack_curr--;
-      }
-    }
-    /* check second invariant */
-    else if (B <= C)
-    {
+    /* 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--;
     }
-    else
-      break;
   }
+
   return stack_curr;
 }
 
 void TIM_SORT(SORT_TYPE *dst, const size_t size)
 {
   int minrun;
   TEMP_STORAGE_T _store, *store;
   TIM_SORT_RUN_T run_stack[128];
   int stack_curr = 0;
   int64_t len, run;
@@ skipping 44 matching lines @@
 #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