#include <stdlib.h>
#include <stdio.h>
#include <string.h>

Include dependency graph for timsort.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	TIM_SORT_RUN_T

struct	TEMP_STORAGE_T

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

#define	TIM_SORT_STACK_SIZE 128

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

#define	SORT_COMMON_H

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

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

#define	CLZ clzll

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

Functions
static int	compute_minrun (const uint64_t)

static int	clzll (uint64_t)

void	BINARY_INSERTION_SORT (SORT_TYPE *dst, const size_t size)

void	TIM_SORT (SORT_TYPE *dst, const size_t size)

static __inline size_t	BINARY_INSERTION_FIND (SORT_TYPE *dst, const SORT_TYPE x, const size_t size)

static void	BINARY_INSERTION_SORT_START (SORT_TYPE *dst, const size_t start, const size_t size)

static __inline void	REVERSE_ELEMENTS (SORT_TYPE *dst, size_t start, size_t end)

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

static int	CHECK_INVARIANT (TIM_SORT_RUN_T *stack, const int stack_curr)

static void	TIM_SORT_RESIZE (TEMP_STORAGE_T *store, const size_t new_size)

static void	TIM_SORT_MERGE (SORT_TYPE dst, const TIM_SORT_RUN_T stack, const int stack_curr, TEMP_STORAGE_T *store)

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

Macro Definition Documentation

◆ BINARY_INSERTION_FIND

#define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find)

Definition at line 148 of file timsort.h.

◆ BINARY_INSERTION_SORT

#define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort)

Definition at line 150 of file timsort.h.

◆ BINARY_INSERTION_SORT_START

#define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)

Definition at line 149 of file timsort.h.

◆ CHECK_INVARIANT

#define CHECK_INVARIANT SORT_MAKE_STR(check_invariant)

Definition at line 153 of file timsort.h.

◆ CLZ

#define CLZ clzll

Definition at line 125 of file timsort.h.

◆ COUNT_RUN

#define COUNT_RUN SORT_MAKE_STR(count_run)

Definition at line 152 of file timsort.h.

◆ MAX

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

Definition at line 67 of file timsort.h.

◆ MIN

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

Definition at line 71 of file timsort.h.

◆ REVERSE_ELEMENTS

#define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements)

Definition at line 151 of file timsort.h.

◆ SORT_CMP

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

Definition at line 52 of file timsort.h.

◆ SORT_COMMON_H

#define SORT_COMMON_H

Definition at line 64 of file timsort.h.

◆ SORT_CONCAT

#define SORT_CONCAT	(	x,
		y
	)	x ## _ ## y

Definition at line 144 of file timsort.h.

◆ SORT_MAKE_STR

#define SORT_MAKE_STR ( x ) SORT_MAKE_STR1(SORT_NAME,x)

Definition at line 146 of file timsort.h.

◆ SORT_MAKE_STR1

#define SORT_MAKE_STR1	(	x,
		y
	)	SORT_CONCAT(x,y)

Definition at line 145 of file timsort.h.

◆ SORT_SWAP

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

Definition at line 59 of file timsort.h.

◆ TIM_SORT

#define TIM_SORT SORT_MAKE_STR(tim_sort)

Definition at line 154 of file timsort.h.

◆ TIM_SORT_COLLAPSE

#define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse)

Definition at line 157 of file timsort.h.

◆ TIM_SORT_MERGE

#define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge)

Definition at line 156 of file timsort.h.

◆ TIM_SORT_RESIZE

#define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize)

Definition at line 155 of file timsort.h.

◆ TIM_SORT_STACK_SIZE

#define TIM_SORT_STACK_SIZE 128

Definition at line 56 of file timsort.h.

Function Documentation

◆ BINARY_INSERTION_FIND()

static __inline size_t BINARY_INSERTION_FIND	(	SORT_TYPE *	dst,
		const SORT_TYPE	x,
		const size_t	size
	)

static

Definition at line 177 of file timsort.h.

                       {
  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()

void BINARY_INSERTION_SORT	(	SORT_TYPE *	dst,
		const size_t	size
	)

Definition at line 247 of file timsort.h.

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

◆ BINARY_INSERTION_SORT_START()

static void BINARY_INSERTION_SORT_START	(	SORT_TYPE *	dst,
		const size_t	start,
		const size_t	size
	)

static

Definition at line 217 of file timsort.h.

                                                                                               {
  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;
  }
}

◆ CHECK_INVARIANT()

static int CHECK_INVARIANT	(	TIM_SORT_RUN_T *	stack,
		const int	stack_curr
	)

static

Definition at line 322 of file timsort.h.

                                                                        {
  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;
}

◆ clzll()

static int clzll ( uint64_t x )

static

Definition at line 84 of file timsort.h.

                             {
  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;
}

◆ compute_minrun()

static __inline int compute_minrun ( const uint64_t size )

static

Definition at line 129 of file timsort.h.

                                                        {
  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;
}

Referenced by TIM_SORT().

◆ COUNT_RUN()

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

static

Definition at line 270 of file timsort.h.

                                                                               {
  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;
  }
}

◆ PUSH_NEXT()

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
	)

static

Definition at line 488 of file timsort.h.

                                            {
  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;
}

Referenced by TIM_SORT().

◆ REVERSE_ELEMENTS()

static __inline void REVERSE_ELEMENTS	(	SORT_TYPE *	dst,
		size_t	start,
		size_t	end
	)

static

Definition at line 258 of file timsort.h.

                                                                                {
  while (1) {
    if (start >= end) {
      return;
    }
 
    SORT_SWAP(dst[start], dst[end]);
    start++;
    end--;
  }
}

◆ TIM_SORT()

void TIM_SORT	(	SORT_TYPE *	dst,
		const size_t	size
	)

Definition at line 531 of file timsort.h.

                                                 {
  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;
    }
  }
}

◆ TIM_SORT_COLLAPSE()

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

Definition at line 424 of file timsort.h.

                                                                       {
  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;
}

◆ TIM_SORT_MERGE()

static void TIM_SORT_MERGE	(	SORT_TYPE *	dst,
		const TIM_SORT_RUN_T *	stack,
		const int	stack_curr,
		TEMP_STORAGE_T *	store
	)

static

Definition at line 371 of file timsort.h.

                                                  {
  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;
      }
    }
  }
}

◆ TIM_SORT_RESIZE()

static void TIM_SORT_RESIZE	(	TEMP_STORAGE_T *	store,
		const size_t	new_size
	)

static

Definition at line 356 of file timsort.h.

                                                                          {
  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;
  }
}

Classes

Macros

Functions

Macro Definition Documentation

◆ BINARY_INSERTION_FIND

◆ BINARY_INSERTION_SORT

◆ BINARY_INSERTION_SORT_START

◆ CHECK_INVARIANT

◆ CLZ

◆ COUNT_RUN

◆ MAX

◆ MIN

◆ REVERSE_ELEMENTS

◆ SORT_CMP

◆ SORT_COMMON_H

◆ SORT_CONCAT

◆ SORT_MAKE_STR

◆ SORT_MAKE_STR1

◆ SORT_SWAP

◆ TIM_SORT

◆ TIM_SORT_COLLAPSE

◆ TIM_SORT_MERGE

◆ TIM_SORT_RESIZE

◆ TIM_SORT_STACK_SIZE

Function Documentation

◆ BINARY_INSERTION_FIND()

◆ BINARY_INSERTION_SORT()

◆ BINARY_INSERTION_SORT_START()

◆ CHECK_INVARIANT()

◆ clzll()

◆ compute_minrun()

◆ COUNT_RUN()

◆ PUSH_NEXT()

◆ REVERSE_ELEMENTS()

◆ TIM_SORT()

◆ TIM_SORT_COLLAPSE()

◆ TIM_SORT_MERGE()

◆ TIM_SORT_RESIZE()