path: root/contrib/libs/libxml/timsort.h

/*
 * 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