[gtk/wip/otte/sortlistmodel: 92/121] Add a timsort() implementation



commit a47ba545c62799d5258084e5e57b6b8ae5db0476
Author: Benjamin Otte <otte redhat com>
Date:   Sat Jul 11 05:37:31 2020 +0200

    Add a timsort() implementation

 gtk/gtktimsort-impl.c     | 944 ++++++++++++++++++++++++++++++++++++++++++++++
 gtk/gtktimsort.c          | 204 ++++++++++
 gtk/gtktimsortprivate.h   | 106 ++++++
 gtk/meson.build           |   1 +
 testsuite/gtk/meson.build |   4 +
 testsuite/gtk/timsort.c   | 208 ++++++++++
 6 files changed, 1467 insertions(+)
---
diff --git a/gtk/gtktimsort-impl.c b/gtk/gtktimsort-impl.c
new file mode 100644
index 0000000000..e6f9f3bba6
--- /dev/null
+++ b/gtk/gtktimsort-impl.c
@@ -0,0 +1,944 @@
+/*
+ * Copyright (C) 2020 Benjamin Otte
+ * Copyright (C) 2011 Patrick O. Perry
+ * Copyright (C) 2008 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef NAME
+#define NAME WIDTH
+#endif
+
+#define DEFINE_TEMP(temp) gpointer temp = g_alloca (WIDTH)
+#define ASSIGN(x, y) memcpy (x, y, WIDTH)
+#define INCPTR(x) ((gpointer) ((char *) (x) + WIDTH))
+#define DECPTR(x) ((gpointer) ((char *) (x) - WIDTH))
+#define ELEM(a, i) ((char *) (a) + (i) * WIDTH)
+#define LEN(n) ((n) * WIDTH)
+
+#define CONCAT(x, y) gtk_tim_sort_ ## x ## _ ## y
+#define MAKE_STR(x, y) CONCAT (x, y)
+#define gtk_tim_sort(x) MAKE_STR (x, NAME)
+
+/*
+ * Reverse the specified range of the specified array.
+ *
+ * @param a the array in which a range is to be reversed
+ * @param hi the index after the last element in the range to be reversed
+ */
+static void gtk_tim_sort(reverse_range) (GtkTimSort *self,
+                                         gpointer    a,
+                                         gsize       hi)
+{
+  DEFINE_TEMP (t);
+  char *front = a;
+  char *back = ELEM (a, hi - 1);
+
+  g_assert (hi > 0);
+
+  while (front < back)
+    {
+      ASSIGN (t, front);
+      ASSIGN (front, back);
+      ASSIGN (back, t);
+      front = INCPTR (front);
+      back = DECPTR (back);
+    }
+}
+
+/*
+ * Returns the length of the run beginning at the specified position in
+ * the specified array and reverses the run if it is descending (ensuring
+ * that the run will always be ascending when the method returns).
+ *
+ * A run is the longest ascending sequence with:
+ *
+ *    a[0] <= a[1] <= a[2] <= ...
+ *
+ * or the longest descending sequence with:
+ *
+ *    a[0] >  a[1] >  a[2] >  ...
+ *
+ * For its intended use in a stable mergesort, the strictness of the
+ * definition of "descending" is needed so that the call can safely
+ * reverse a descending sequence without violating stability.
+ *
+ * @param a the array in which a run is to be counted and possibly reversed
+ * @param hi index after the last element that may be contained in the run.
+ *        It is required that {@code 0 < hi}.
+ * @param compare the comparator to used for the sort
+ * @return  the length of the run beginning at the specified position in
+ *          the specified array
+ */
+static gsize
+gtk_tim_sort(prepare_run) (GtkTimSort *self)
+{
+  gsize run_hi = 1;
+  char *cur;
+  char *next;
+
+  if (self->size <= run_hi)
+    return self->size;
+
+  cur = INCPTR (self->base);
+  next = INCPTR (cur);
+  run_hi++;
+
+  /* Find end of run, and reverse range if descending */
+  if (gtk_tim_sort_compare (self, cur, self->base) < 0)          /* Descending */
+    {
+      while (run_hi < self->size && gtk_tim_sort_compare (self, next, cur) < 0)
+        {
+          run_hi++;
+          cur = next;
+          next = INCPTR (next);
+        }
+      gtk_tim_sort(reverse_range) (self, self->base, run_hi);
+    }
+  else                          /* Ascending */
+    {
+      while (run_hi < self->size && gtk_tim_sort_compare (self, next, cur) >= 0)
+        {
+          run_hi++;
+          cur = next;
+          next = INCPTR (next);
+        }
+    }
+
+  return run_hi;
+}
+
+/*
+ * Sorts the specified portion of the specified array using a binary
+ * insertion sort.  This is the best method for sorting small numbers
+ * of elements.  It requires O(n log n) compares, but O(n^2) data
+ * movement (worst case).
+ *
+ * If the initial part of the specified range is already sorted,
+ * this method can take advantage of it: the method assumes that the
+ * elements from index {@code lo}, inclusive, to {@code start},
+ * exclusive are already sorted.
+ *
+ * @param a the array in which a range is to be sorted
+ * @param hi the index after the last element in the range to be sorted
+ * @param start the index of the first element in the range that is
+ *        not already known to be sorted ({@code lo <= start <= hi})
+ */
+static void gtk_tim_sort(binary_sort) (GtkTimSort *self,
+                                       gpointer    a,
+                                       gsize       hi,
+                                       gsize       start)
+{
+  DEFINE_TEMP (pivot);
+  char *startp;
+
+  g_assert (start <= hi);
+
+  if (start == 0)
+    start++;
+
+  startp = ELEM (a, start);
+
+  for (; start < hi; start++, startp = INCPTR (startp))
+    {
+      /* Set left (and right) to the index where a[start] (pivot) belongs */
+      char *leftp = a;
+      gsize right = start;
+      gsize n;
+
+      /*
+       * Invariants:
+       *   pivot >= all in [0, left).
+       *   pivot <  all in [right, start).
+       */
+      while (0 < right)
+        {
+          gsize mid = right >> 1;
+          gpointer midp = ELEM (leftp, mid);
+          if (gtk_tim_sort_compare (self, startp, midp) < 0)
+            {
+              right = mid;
+            }
+          else
+            {
+              leftp = INCPTR (midp);
+              right -= (mid + 1);
+            }
+        }
+      g_assert (0 == right);
+
+      /*
+       * The invariants still hold: pivot >= all in [lo, left) and
+       * pivot < all in [left, start), so pivot belongs at left.  Note
+       * that if there are elements equal to pivot, left points to the
+       * first slot after them -- that's why this sort is stable.
+       * Slide elements over to make room to make room for pivot.
+       */
+      n = startp - leftp;               /* The number of bytes to move */
+
+      ASSIGN (pivot, startp);
+      memmove (INCPTR (leftp), leftp, n);         /* POP: overlaps */
+
+      /* a[left] = pivot; */
+      ASSIGN (leftp, pivot);
+    }
+}
+
+static gboolean
+gtk_tim_sort(merge_append) (GtkTimSort *self)
+{
+  /* Identify next run */
+  gsize run_len;
+
+  run_len = gtk_tim_sort(prepare_run) (self);
+  if (run_len == 0)
+    return FALSE;
+
+  /* If run is short, extend to min(self->min_run, self->size) */
+  if (run_len < self->min_run)
+    {
+      gsize force = MIN (self->size, self->min_run);
+      gtk_tim_sort(binary_sort) (self, self->base, force, run_len);
+      run_len = force;
+    }
+  /* Push run onto pending-run stack, and maybe merge */
+  gtk_tim_sort_push_run (self, self->base, run_len);
+
+  /* Advance to find next run */
+  self->base = ELEM (self->base, run_len);
+  self->size -= run_len;
+
+  return TRUE;
+}
+
+#if 0
+static int gtk_tim_sort(timsort) (void *a, gsize nel)
+{
+  int err = SUCCESS;
+  GtkTimSort self;
+  gsize self->min_run;
+
+  g_assert (a || !nel || !width);
+  g_assert (c);
+
+  if (nel < 2 || !width)
+    return err;                 /* Arrays of size 0 and 1 are always sorted */
+
+  /* If array is small, do a "mini-TimSort" with no merges */
+  if (nel < MIN_MERGE)
+    {
+      gsize initRunLen =
+        gtk_tim_sort(prepare_run) (a, nel, CMPARGS (c, carg));
+      gtk_tim_sort(binary_sort) (self, a, nel, initRunLen, CMPARGS (c, carg));
+      return err;
+    }
+
+  /*
+   * March over the array once, left to right, finding natural runs,
+   * extending short natural runs to self->min_run elements, and merging runs
+   * to maintain stack invariant.
+   */
+  if ((err = timsort_init (&self, a, nel, CMPARGS (c, carg))))
+    return err;
+
+  do
+    {
+      /* Identify next run */
+      gsize run_len =
+        gtk_tim_sort(prepare_run) (a, nel, CMPARGS (c, carg));
+
+      /* If run is short, extend to min(self->min_run, nel) */
+      if (run_len < self->min_run)
+        {
+          gsize force = nel <= self->min_run ? nel : self->min_run;
+          gtk_tim_sort(binary_sort) (a, force, run_len, CMPARGS (c, carg));
+          run_len = force;
+        }
+      /* Push run onto pending-run stack, and maybe merge */
+      gtk_tim_sort_push_run (&self, a, run_len);
+      if ((err = gtk_tim_sort(mergeCollapse) (&self)))
+        goto out;
+
+      /* Advance to find next run */
+      a = ELEM (a, run_len);
+      nel -= run_len;
+    }
+  while (nel != 0);
+
+  /* Merge all remaining runs to complete sort */
+  if ((err = gtk_tim_sort(merge_force_collapse) (&self)))
+    goto out;
+
+  g_assert (self.pending_runs == 1);
+out:
+  timsort_deinit (&self);
+  return err;
+}
+#endif
+
+/*
+ * Locates the position at which to insert the specified key into the
+ * specified sorted range; if the range contains an element equal to key,
+ * returns the index of the leftmost equal element.
+ *
+ * @param key the key whose insertion point to search for
+ * @param base the array in which to search
+ * @param len the length of the range; must be > 0
+ * @param hint the index at which to begin the search, 0 <= hint < n.
+ *     The closer hint is to the result, the faster this method will run.
+ * @param c the comparator used to order the range, and to search
+ * @return the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
+ *    pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
+ *    In other words, key belongs at index b + k; or in other words,
+ *    the first k elements of a should precede key, and the last n - k
+ *    should follow it.
+ */
+static gsize
+gtk_tim_sort(gallop_left) (GtkTimSort *self,
+                           gpointer    key,
+                           gpointer    base,
+                           gsize       len,
+                           gsize       hint)
+{
+  char *hintp = ELEM (base, hint);
+  gsize last_ofs = 0;
+  gsize ofs = 1;
+
+  g_assert (len > 0 && hint < len);
+  if (gtk_tim_sort_compare (self, key, hintp) > 0)
+    {
+      /* Gallop right until a[hint+last_ofs] < key <= a[hint+ofs] */
+      gsize max_ofs = len - hint;
+      while (ofs < max_ofs
+             && gtk_tim_sort_compare (self, key, ELEM (hintp, ofs)) > 0)
+        {
+          last_ofs = ofs;
+          ofs = (ofs << 1) + 1;                 /* eventually this becomes SIZE_MAX */
+        }
+      if (ofs > max_ofs)
+        ofs = max_ofs;
+
+      /* Make offsets relative to base */
+      last_ofs += hint + 1;              /* POP: we add 1 here so last_ofs stays non-negative */
+      ofs += hint;
+    }
+  else                          /* key <= a[hint] */
+  /* Gallop left until a[hint-ofs] < key <= a[hint-last_ofs] */
+    {
+      const gsize max_ofs = hint + 1;
+      gsize tmp;
+      while (ofs < max_ofs
+             && gtk_tim_sort_compare (self, key, ELEM (hintp, -ofs)) <= 0)
+        {
+          last_ofs = ofs;
+          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
+        }
+      if (ofs > max_ofs)
+        ofs = max_ofs;
+
+      /* Make offsets relative to base */
+      tmp = last_ofs;
+      last_ofs = hint + 1 - ofs;                 /* POP: we add 1 here so last_ofs stays non-negative */
+      ofs = hint - tmp;
+    }
+  g_assert (last_ofs <= ofs && ofs <= len);
+
+  /*
+   * Now a[last_ofs-1] < key <= a[ofs], so key belongs somewhere
+   * to the right of last_ofs but no farther right than ofs.  Do a binary
+   * search, with invariant a[last_ofs - 1] < key <= a[ofs].
+   */
+  /* last_ofs++; POP: we added 1 above to keep last_ofs non-negative */
+  while (last_ofs < ofs)
+    {
+      /*gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
+      /* http://stackoverflow.com/questions/4844165/safe-integer-middle-value-formula */
+      gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
+
+      if (gtk_tim_sort_compare (self, key, ELEM (base, m)) > 0)
+        last_ofs = m + 1;                        /* a[m] < key */
+      else
+        ofs = m;                        /* key <= a[m] */
+    }
+  g_assert (last_ofs == ofs);      /* so a[ofs - 1] < key <= a[ofs] */
+  return ofs;
+}
+
+/*
+ * Like gallop_left, except that if the range contains an element equal to
+ * key, gallop_right returns the index after the rightmost equal element.
+ *
+ * @param key the key whose insertion point to search for
+ * @param base the array in which to search
+ * @param len the length of the range; must be > 0
+ * @param hint the index at which to begin the search, 0 <= hint < n.
+ *     The closer hint is to the result, the faster this method will run.
+ * @param c the comparator used to order the range, and to search
+ * @return the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
+ */
+static gsize
+gtk_tim_sort(gallop_right) (GtkTimSort *self,
+                            gpointer    key,
+                            gpointer    base,
+                            gsize       len,
+                            gsize       hint)
+{
+  char *hintp = ELEM (base, hint);
+  gsize ofs = 1;
+  gsize last_ofs = 0;
+
+  g_assert (len > 0 && hint < len);
+
+  if (gtk_tim_sort_compare (self, key, hintp) < 0)
+    {
+      /* Gallop left until a[hint - ofs] <= key < a[hint - last_ofs] */
+      gsize max_ofs = hint + 1;
+      gsize tmp;
+      while (ofs < max_ofs
+             && gtk_tim_sort_compare (self, key, ELEM (hintp, -ofs)) < 0)
+        {
+          last_ofs = ofs;
+          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
+        }
+      if (ofs > max_ofs)
+        ofs = max_ofs;
+
+      /* Make offsets relative to base */
+      tmp = last_ofs;
+      last_ofs = hint + 1 - ofs;
+      ofs = hint - tmp;
+    }
+  else                          /* a[hint] <= key */
+  /* Gallop right until a[hint + last_ofs] <= key < a[hint + ofs] */
+    {
+      gsize max_ofs = len - hint;
+      while (ofs < max_ofs
+             && gtk_tim_sort_compare (self, key, ELEM (hintp, ofs)) >= 0)
+        {
+          last_ofs = ofs;
+          ofs = (ofs << 1) + 1;                 /* no need to check for overflow */
+        }
+      if (ofs > max_ofs)
+        ofs = max_ofs;
+
+      /* Make offsets relative to base */
+      last_ofs += hint + 1;
+      ofs += hint;
+    }
+  g_assert (last_ofs <= ofs && ofs <= len);
+
+  /*
+   * Now a[last_ofs - 1] <= key < a[ofs], so key belongs somewhere to
+   * the right of last_ofs but no farther right than ofs.  Do a binary
+   * search, with invariant a[last_ofs - 1] <= key < a[ofs].
+   */
+  while (last_ofs < ofs)
+    {
+      /* gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
+      gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
+
+      if (gtk_tim_sort_compare (self, key, ELEM (base, m)) < 0)
+        ofs = m;                        /* key < a[m] */
+      else
+        last_ofs = m + 1;                        /* a[m] <= key */
+    }
+  g_assert (last_ofs == ofs);      /* so a[ofs - 1] <= key < a[ofs] */
+  return ofs;
+}
+
+/*
+ * Merges two adjacent runs in place, in a stable fashion.  The first
+ * element of the first run must be greater than the first element of the
+ * second run (a[base1] > a[base2]), and the last element of the first run
+ * (a[base1 + len1-1]) must be greater than all elements of the second run.
+ *
+ * For performance, this method should be called only when len1 <= len2;
+ * its twin, merge_hi should be called if len1 >= len2.  (Either method
+ * may be called if len1 == len2.)
+ *
+ * @param base1 first element in first run to be merged
+ * @param len1  length of first run to be merged (must be > 0)
+ * @param base2 first element in second run to be merged
+ *        (must be aBase + aLen)
+ * @param len2  length of second run to be merged (must be > 0)
+ */
+static void
+gtk_tim_sort(merge_lo) (GtkTimSort *self,
+                        gpointer    base1,
+                        gsize       len1,
+                        gpointer    base2,
+                        gsize       len2)
+{
+  /* Copy first run into temp array */
+  gpointer tmp = gtk_tim_sort_ensure_capacity (self, len1);
+  char *cursor1;
+  char *cursor2;
+  char *dest;
+  gsize min_gallop;
+
+  g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
+
+  /* System.arraycopy(a, base1, tmp, 0, len1); */
+  memcpy (tmp, base1, LEN (len1));     /* POP: can't overlap */
+
+  cursor1 = tmp;                /* Indexes into tmp array */
+  cursor2 = base2;              /* Indexes int a */
+  dest = base1;                 /* Indexes int a */
+
+  /* Move first element of second run and deal with degenerate cases */
+  /* a[dest++] = a[cursor2++]; */
+  ASSIGN (dest, cursor2);
+  dest = INCPTR (dest);
+  cursor2 = INCPTR (cursor2);
+
+  if (--len2 == 0)
+    {
+      memcpy (dest, cursor1, LEN (len1));         /* POP: can't overlap */
+      return;
+    }
+  if (len1 == 1)
+    {
+      memmove (dest, cursor2, LEN (len2));         /* POP: overlaps */
+
+      /* a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge */
+      ASSIGN (ELEM (dest, len2), cursor1);
+      return;
+    }
+
+  /* Use local variable for performance */
+  min_gallop = self->min_gallop;
+
+  while (TRUE)
+    {
+      gsize count1 = 0;                 /* Number of times in a row that first run won */
+      gsize count2 = 0;                 /* Number of times in a row that second run won */
+
+      /*
+       * Do the straightforward thing until (if ever) one run starts
+       * winning consistently.
+       */
+      do
+        {
+          g_assert (len1 > 1 && len2 > 0);
+          if (gtk_tim_sort_compare (self, cursor2, cursor1) < 0)
+            {
+              ASSIGN (dest, cursor2);
+              dest = INCPTR (dest);
+              cursor2 = INCPTR (cursor2);
+              count2++;
+              count1 = 0;
+              if (--len2 == 0)
+                goto outer;
+              if (count2 >= min_gallop)
+                break;
+            }
+          else
+            {
+              ASSIGN (dest, cursor1);
+              dest = INCPTR (dest);
+              cursor1 = INCPTR (cursor1);
+              count1++;
+              count2 = 0;
+              if (--len1 == 1)
+                goto outer;
+              if (count1 >= min_gallop)
+                break;
+            }
+        }
+      while (TRUE);                /* (count1 | count2) < min_gallop); */
+
+      /*
+       * One run is winning so consistently that galloping may be a
+       * huge win. So try that, and continue galloping until (if ever)
+       * neither run appears to be winning consistently anymore.
+       */
+      do
+        {
+          g_assert (len1 > 1 && len2 > 0);
+          count1 = gtk_tim_sort(gallop_right) (self, cursor2, cursor1, len1, 0);
+          if (count1 != 0)
+            {
+              memcpy (dest, cursor1, LEN (count1));                 /* POP: can't overlap */
+              dest = ELEM (dest, count1);
+              cursor1 = ELEM (cursor1, count1);
+              len1 -= count1;
+              if (len1 <= 1)                    /* len1 == 1 || len1 == 0 */
+                goto outer;
+            }
+          ASSIGN (dest, cursor2);
+          dest = INCPTR (dest);
+          cursor2 = INCPTR (cursor2);
+          if (--len2 == 0)
+            goto outer;
+
+          count2 = gtk_tim_sort(gallop_left) (self, cursor1, cursor2, len2, 0);
+          if (count2 != 0)
+            {
+              memmove (dest, cursor2, LEN (count2));                 /* POP: might overlap */
+              dest = ELEM (dest, count2);
+              cursor2 = ELEM (cursor2, count2);
+              len2 -= count2;
+              if (len2 == 0)
+                goto outer;
+            }
+          ASSIGN (dest, cursor1);
+          dest = INCPTR (dest);
+          cursor1 = INCPTR (cursor1);
+          if (--len1 == 1)
+            goto outer;
+          if (min_gallop > 0)
+            min_gallop--;
+        }
+      while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
+      min_gallop += 2;           /* Penalize for leaving gallop mode */
+    }                           /* End of "outer" loop */
+outer:
+  self->min_gallop = min_gallop < 1 ? 1 : min_gallop;        /* Write back to field */
+
+  if (len1 == 1)
+    {
+      g_assert (len2 > 0);
+      memmove (dest, cursor2, LEN (len2));              /*  POP: might overlap */
+      ASSIGN (ELEM (dest, len2), cursor1);              /*  Last elt of run 1 to end of merge */
+    }
+  else if (len1 == 0)
+    {
+      g_critical ("Comparison method violates its general contract");
+      return;
+    }
+  else
+    {
+      g_assert (len2 == 0);
+      g_assert (len1 > 1);
+      memcpy (dest, cursor1, LEN (len1));         /* POP: can't overlap */
+    }
+}
+
+/*
+ * Like merge_lo, except that this method should be called only if
+ * len1 >= len2; merge_lo should be called if len1 <= len2.  (Either method
+ * may be called if len1 == len2.)
+ *
+ * @param base1 first element in first run to be merged
+ * @param len1  length of first run to be merged (must be > 0)
+ * @param base2 first element in second run to be merged
+ *        (must be aBase + aLen)
+ * @param len2  length of second run to be merged (must be > 0)
+ */
+static void
+gtk_tim_sort(merge_hi) (GtkTimSort *self,
+                        gpointer    base1,
+                        gsize       len1,
+                        gpointer    base2,
+                        gsize       len2)
+{
+  /* Copy second run into temp array */
+  gpointer tmp = gtk_tim_sort_ensure_capacity (self, len2);
+  char *cursor1;        /* Indexes into a */
+  char *cursor2;        /* Indexes into tmp array */
+  char *dest;           /* Indexes into a */
+  gsize min_gallop;
+
+  g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
+
+  memcpy (tmp, base2, LEN (len2));     /* POP: can't overlap */
+
+  cursor1 = ELEM (base1, len1 - 1);     /* Indexes into a */
+  cursor2 = ELEM (tmp, len2 - 1);       /* Indexes into tmp array */
+  dest = ELEM (base2, len2 - 1);        /* Indexes into a */
+
+  /* Move last element of first run and deal with degenerate cases */
+  /* a[dest--] = a[cursor1--]; */
+  ASSIGN (dest, cursor1);
+  dest = DECPTR (dest);
+  cursor1 = DECPTR (cursor1);
+  if (--len1 == 0)
+    {
+      memcpy (ELEM (dest, -(len2 - 1)), tmp, LEN (len2));        /* POP: can't overlap */
+      return;
+    }
+  if (len2 == 1)
+    {
+      dest = ELEM (dest, -len1);
+      cursor1 = ELEM (cursor1, -len1);
+      memmove (ELEM (dest, 1), ELEM (cursor1, 1), LEN (len1));       /* POP: overlaps */
+      /* a[dest] = tmp[cursor2]; */
+      ASSIGN (dest, cursor2);
+      return;
+    }
+
+  /* Use local variable for performance */
+  min_gallop = self->min_gallop;
+
+  while (TRUE)
+    {
+      gsize count1 = 0;                 /* Number of times in a row that first run won */
+      gsize count2 = 0;                 /* Number of times in a row that second run won */
+
+      /*
+       * Do the straightforward thing until (if ever) one run
+       * appears to win consistently.
+       */
+      do
+        {
+          g_assert (len1 > 0 && len2 > 1);
+          if (gtk_tim_sort_compare (self, cursor2, cursor1) < 0)
+            {
+              ASSIGN (dest, cursor1);
+              dest = DECPTR (dest);
+              cursor1 = DECPTR (cursor1);
+              count1++;
+              count2 = 0;
+              if (--len1 == 0)
+                goto outer;
+            }
+          else
+            {
+              ASSIGN (dest, cursor2);
+              dest = DECPTR (dest);
+              cursor2 = DECPTR (cursor2);
+              count2++;
+              count1 = 0;
+              if (--len2 == 1)
+                goto outer;
+            }
+        }
+      while ((count1 | count2) < min_gallop);
+
+      /*
+       * One run is winning so consistently that galloping may be a
+       * huge win. So try that, and continue galloping until (if ever)
+       * neither run appears to be winning consistently anymore.
+       */
+      do
+        {
+          g_assert (len1 > 0 && len2 > 1);
+          count1 = len1 - gtk_tim_sort(gallop_right) (self, cursor2, base1, len1, len1 - 1);
+          if (count1 != 0)
+            {
+              dest = ELEM (dest, -count1);
+              cursor1 = ELEM (cursor1, -count1);
+              len1 -= count1;
+              memmove (INCPTR (dest), INCPTR (cursor1),
+                       LEN (count1));                /* POP: might overlap */
+              if (len1 == 0)
+                goto outer;
+            }
+          ASSIGN (dest, cursor2);
+          dest = DECPTR (dest);
+          cursor2 = DECPTR (cursor2);
+          if (--len2 == 1)
+            goto outer;
+
+          count2 = len2 - gtk_tim_sort(gallop_left) (self, cursor1, tmp, len2, len2 - 1);
+          if (count2 != 0)
+            {
+              dest = ELEM (dest, -count2);
+              cursor2 = ELEM (cursor2, -count2);
+              len2 -= count2;
+              memcpy (INCPTR (dest), INCPTR (cursor2), LEN (count2));               /* POP: can't overlap */
+              if (len2 <= 1)                    /* len2 == 1 || len2 == 0 */
+                goto outer;
+            }
+          ASSIGN (dest, cursor1);
+          dest = DECPTR (dest);
+          cursor1 = DECPTR (cursor1);
+          if (--len1 == 0)
+            goto outer;
+          if (min_gallop > 0)
+            min_gallop--;
+        }
+      while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
+      min_gallop += 2;           /* Penalize for leaving gallop mode */
+    }                           /* End of "outer" loop */
+outer:
+  self->min_gallop = min_gallop < 1 ? 1 : min_gallop;        /* Write back to field */
+
+  if (len2 == 1)
+    {
+      g_assert (len1 > 0);
+      dest = ELEM (dest, -len1);
+      cursor1 = ELEM (cursor1, -len1);
+      memmove (INCPTR (dest), INCPTR (cursor1), LEN (len1));       /* POP: might overlap */
+      /* a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge */
+      ASSIGN (dest, cursor2);
+    }
+  else if (len2 == 0)
+    {
+      g_critical ("Comparison method violates its general contract");
+      return;
+    }
+  else
+    {
+      g_assert (len1 == 0);
+      g_assert (len2 > 0);
+      memcpy (ELEM (dest, -(len2 - 1)), tmp, LEN (len2));        /* POP: can't overlap */
+    }
+}
+
+/*
+ * Merges the two runs at stack indices i and i+1.  Run i must be
+ * the penultimate or antepenultimate run on the stack.  In other words,
+ * i must be equal to pending_runs-2 or pending_runs-3.
+ *
+ * @param i stack index of the first of the two runs to merge
+ */
+static void
+gtk_tim_sort(merge_at) (GtkTimSort *self,
+                        gsize       i)
+{
+  gpointer base1 = self->run[i].base;
+  gsize len1 = self->run[i].len;
+  gpointer base2 = self->run[i + 1].base;
+  gsize len2 = self->run[i + 1].len;
+  gsize k;
+
+  g_assert (self->pending_runs >= 2);
+  g_assert (i == self->pending_runs - 2 || i == self->pending_runs - 3);
+  g_assert (len1 > 0 && len2 > 0);
+  g_assert (ELEM (base1, len1) == base2);
+
+  /*
+   * Record the length of the combined runs; if i is the 3rd-last
+   * run now, also slide over the last run (which isn't involved
+   * in this merge).  The current run (i+1) goes away in any case.
+   */
+  self->run[i].len = len1 + len2;
+  if (i == self->pending_runs - 3)
+    {
+      self->run[i + 1] = self->run[i + 2];
+    }
+  self->pending_runs--;
+
+  /*
+   * Find where the first element of run2 goes in run1. Prior elements
+   * in run1 can be ignored (because they're already in place).
+   */
+  k = gtk_tim_sort(gallop_right) (self, base2, base1, len1, 0);
+  base1 = ELEM (base1, k);
+  len1 -= k;
+  if (len1 == 0)
+    return;
+
+  /*
+   * Find where the last element of run1 goes in run2. Subsequent elements
+   * in run2 can be ignored (because they're already in place).
+   */
+  len2 = gtk_tim_sort(gallop_left) (self,
+                                    ELEM (base1, len1 - 1),
+                                    base2, len2, len2 - 1);
+  if (len2 == 0)
+    return;
+
+  /* Merge remaining runs, using tmp array with min(len1, len2) elements */
+  if (len1 <= len2)
+    gtk_tim_sort(merge_lo) (self, base1, len1, base2, len2);
+  else
+    gtk_tim_sort(merge_hi) (self, base1, len1, base2, len2);
+}
+
+
+/*
+ * Examines the stack of runs waiting to be merged and merges adjacent runs
+ * until the stack invariants are reestablished:
+ *
+ *     1. run_len[i - 3] > run_len[i - 2] + run_len[i - 1]
+ *     2. run_len[i - 2] > run_len[i - 1]
+ *
+ * This method is called each time a new run is pushed onto the stack,
+ * so the invariants are guaranteed to hold for i < pending_runs upon
+ * entry to the method.
+ *
+ * POP:
+ * Modified according to http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf
+ *
+ * and
+ *
+ * https://bugs.openjdk.java.net/browse/JDK-8072909 (suggestion 2)
+ *
+ */
+static gboolean
+gtk_tim_sort(merge_collapse) (GtkTimSort *self)
+{
+  GtkTimSortRun *run = self->run;
+  gsize n;
+
+  if (self->pending_runs <= 1)
+    return FALSE;
+
+  n = self->pending_runs - 2;
+  if ((n > 0 && run[n - 1].len <= run[n].len + run[n + 1].len) ||
+      (n > 1 && run[n - 2].len <= run[n].len + run[n - 1].len))
+    {
+      if (run[n - 1].len < run[n + 1].len)
+        n--;
+    }
+  else if (run[n].len > run[n + 1].len)
+    {
+      return FALSE; /* Invariant is established */
+    }
+  
+  gtk_tim_sort(merge_at) (self, n);
+  return TRUE;
+}
+
+/*
+ * Merges all runs on the stack until only one remains.  This method is
+ * called once, to complete the sort.
+ */
+static gboolean
+gtk_tim_sort(merge_force_collapse) (GtkTimSort *self)
+{
+  gsize n;
+
+  if (self->pending_runs <= 1)
+    return FALSE;
+
+  n = self->pending_runs - 2;
+  if (n > 0 && self->run[n - 1].len < self->run[n + 1].len)
+    n--;
+  gtk_tim_sort(merge_at) (self, n);
+  return TRUE;
+}
+
+static gboolean
+gtk_tim_sort(step) (GtkTimSort * self)
+{
+  g_assert (self);
+
+  if (gtk_tim_sort(merge_collapse) (self))
+    return TRUE;
+
+  if (gtk_tim_sort(merge_append) (self))
+    return TRUE;
+
+  if (gtk_tim_sort(merge_force_collapse) (self))
+    return TRUE;
+
+  return FALSE;
+}
+
+#undef DEFINE_TEMP
+#undef ASSIGN
+#undef INCPTR
+#undef DECPTR
+#undef ELEM
+#undef LEN
+
+#undef CONCAT
+#undef MAKE_STR
+#undef gtk_tim_sort
+
+#undef WIDTH
+#undef NAME
diff --git a/gtk/gtktimsort.c b/gtk/gtktimsort.c
new file mode 100644
index 0000000000..451a63a902
--- /dev/null
+++ b/gtk/gtktimsort.c
@@ -0,0 +1,204 @@
+/* Lots of code for an adaptive, stable, natural mergesort.  There are many
+ * pieces to this algorithm; read listsort.txt for overviews and details.
+ */
+
+#include "config.h"
+
+#include "gtktimsortprivate.h"
+
+/*
+ * This is the minimum sized sequence that will be merged.  Shorter
+ * sequences will be lengthened by calling binarySort.  If the entire
+ * array is less than this length, no merges will be performed.
+ *
+ * This constant should be a power of two.  It was 64 in Tim Peter's C
+ * implementation, but 32 was empirically determined to work better in
+ * [Android's Java] implementation.  In the unlikely event that you set
+ * this constant to be a number that's not a power of two, you'll need
+ * to change the compute_min_run() computation.
+ *
+ * If you decrease this constant, you must change the
+ * GTK_TIM_SORT_MAX_PENDING value, or you risk running out of space.
+ * See Python's listsort.txt for a discussion of the minimum stack
+ * length required as a function of the length of the array being sorted and
+ * the minimum merge sequence length.
+ */
+#define MIN_MERGE 32
+
+
+/*
+ * When we get into galloping mode, we stay there until both runs win less
+ * often than MIN_GALLOP consecutive times.
+ */
+#define MIN_GALLOP 7
+
+/*
+ * Returns the minimum acceptable run length for an array of the specified
+ * length. Natural runs shorter than this will be extended with binary sort.
+ *
+ * Roughly speaking, the computation is:
+ *
+ *  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
+ *  Else if n is an exact power of 2, return MIN_MERGE/2.
+ *  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
+ *   is close to, but strictly less than, an exact power of 2.
+ *
+ * For the rationale, see listsort.txt.
+ *
+ * @param n the length of the array to be sorted
+ * @return the length of the minimum run to be merged
+ */
+static gsize
+compute_min_run (gsize n)
+{
+  gsize r = 0; // Becomes 1 if any 1 bits are shifted off
+
+  while (n >= MIN_MERGE) {
+    r |= (n & 1);
+    n >>= 1;
+  }
+  return n + r;
+}
+
+void
+gtk_tim_sort_init (GtkTimSort       *self,
+                   gpointer          base,
+                   gsize             size,
+                   gsize             element_size,
+                   GCompareDataFunc  compare_func,
+                   gpointer          data)
+{
+  self->element_size = element_size;
+  self->base = base;
+  self->size = size;
+  self->compare_func = compare_func;
+  self->data = data;
+
+  self->min_gallop = MIN_GALLOP;
+  self->min_run = compute_min_run (size);
+
+  self->tmp = NULL;
+  self->tmp_length = 0;
+  self->pending_runs = 0;
+}
+
+void
+gtk_tim_sort_finish (GtkTimSort *self)
+{
+  g_free (self->tmp);
+}
+
+void
+gtk_tim_sort (gpointer         base,
+              gsize            size,
+              gsize            element_size,
+              GCompareDataFunc compare_func,
+              gpointer         user_data)
+{
+  GtkTimSort self;
+
+  gtk_tim_sort_init (&self, base, size, element_size, compare_func, user_data);
+
+  while (gtk_tim_sort_step (&self));
+
+  gtk_tim_sort_finish (&self);
+}
+
+static inline int
+gtk_tim_sort_compare (GtkTimSort *self,
+                      gpointer    a,
+                      gpointer    b)
+{
+  return self->compare_func (a, b, self->data);
+}
+
+
+/**
+ * Pushes the specified run onto the pending-run stack.
+ *
+ * @param runBase index of the first element in the run
+ * @param runLen  the number of elements in the run
+ */
+static void
+gtk_tim_sort_push_run (GtkTimSort *self,
+                       void       *base,
+                       gsize       len)
+{
+  g_assert (self->pending_runs < GTK_TIM_SORT_MAX_PENDING);
+
+  self->run[self->pending_runs].base = base;
+  self->run[self->pending_runs].len = len;
+  self->pending_runs++;
+}
+
+/**
+ * Ensures that the external array tmp has at least the specified
+ * number of elements, increasing its size if necessary.  The size
+ * increases exponentially to ensure amortized linear time complexity.
+ *
+ * @param min_capacity the minimum required capacity of the tmp array
+ * @return tmp, whether or not it grew
+ */
+static gpointer
+gtk_tim_sort_ensure_capacity (GtkTimSort *self,
+                              gsize       min_capacity)
+{
+  if (self->tmp_length < min_capacity)
+    {
+      /* Compute smallest power of 2 > min_capacity */
+      gsize new_size = min_capacity;
+      new_size |= new_size >> 1;
+      new_size |= new_size >> 2;
+      new_size |= new_size >> 4;
+      new_size |= new_size >> 8;
+      new_size |= new_size >> 16;
+      if (sizeof(new_size) > 4)
+        new_size |= new_size >> 32;
+
+      new_size++;
+      if (new_size == 0) /* (overflow) Not bloody likely! */
+        new_size = min_capacity;
+
+      g_free (self->tmp);
+      self->tmp_length = new_size;
+      self->tmp = g_malloc (self->tmp_length * self->element_size);
+  }
+
+  return self->tmp;
+}
+
+#if 1
+#define WIDTH 4
+#include "gtktimsort-impl.c"
+
+#define WIDTH 8
+#include "gtktimsort-impl.c"
+
+#define WIDTH 16
+#include "gtktimsort-impl.c"
+#endif
+
+#define NAME default
+#define WIDTH (self->element_size)
+#include "gtktimsort-impl.c"
+
+gboolean
+gtk_tim_sort_step (GtkTimSort *self)
+{
+  g_assert (self);
+
+  switch (self->element_size)
+  {
+#if 1
+    case 4:
+      return gtk_tim_sort_step_4 (self);
+    case 8:
+      return gtk_tim_sort_step_8 (self);
+    case 16:
+      return gtk_tim_sort_step_16 (self);
+#endif
+    default:
+      return gtk_tim_sort_step_default(self);
+  }
+}
+
diff --git a/gtk/gtktimsortprivate.h b/gtk/gtktimsortprivate.h
new file mode 100644
index 0000000000..d44c74c470
--- /dev/null
+++ b/gtk/gtktimsortprivate.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __GTK_TIMSORT_PRIVATE_H__
+#define __GTK_TIMSORT_PRIVATE_H__
+
+#include <gdk/gdk.h>
+
+/* The maximum number of entries in a GtkTimState's pending-runs stack.
+ * This is enough to sort arrays of size up to about
+ *     32 * phi ** GTK_TIM_SORT_MAX_PENDING
+ * where phi ~= 1.618.  85 is ridiculously large enough, good for an array
+ * with 2**64 elements.
+ */
+#define GTK_TIM_SORT_MAX_PENDING 86
+
+typedef struct _GtkTimSort GtkTimSort;
+typedef struct _GtkTimSortRun GtkTimSortRun;
+
+struct _GtkTimSortRun
+{
+  void *base;
+  gsize len;
+};
+
+struct _GtkTimSort 
+{
+  /*
+   * Size of elements. Used to decide on fast paths.
+   */
+  gsize element_size;
+
+  /* The comparator for this sort.
+   */
+  GCompareDataFunc compare_func;
+  gpointer         data;
+
+  /*
+   * The array being sorted.
+   */
+  gpointer base;
+  gsize size;
+
+  /*
+   * This controls when we get *into* galloping mode.  It is initialized
+   * to MIN_GALLOP.  The mergeLo and mergeHi methods nudge it higher for
+   * random data, and lower for highly structured data.
+   */
+  gsize min_gallop;
+
+  /*
+   * The minimum run length. See compute_min_run() for details.
+   */
+  gsize min_run;
+
+  /*
+   * Temp storage for merges.
+   */
+  void *tmp;
+  gsize tmp_length;
+
+  /*
+   * A stack of pending runs yet to be merged.  Run i starts at
+   * address base[i] and extends for len[i] elements.  It's always
+   * true (so long as the indices are in bounds) that:
+   *
+   *     runBase[i] + runLen[i] == runBase[i + 1]
+   *
+   * so we could cut the storage for this, but it's a minor amount,
+   * and keeping all the info explicit simplifies the code.
+   */
+  gsize pending_runs;  // Number of pending runs on stack
+  GtkTimSortRun run[GTK_TIM_SORT_MAX_PENDING];
+};
+
+void            gtk_tim_sort_init                               (GtkTimSort             *self,
+                                                                 gpointer                base,
+                                                                 gsize                   size,
+                                                                 gsize                   element_size,
+                                                                 GCompareDataFunc        compare_func,
+                                                                 gpointer                data);
+void            gtk_tim_sort_finish                             (GtkTimSort             *self);
+
+gboolean        gtk_tim_sort_step                               (GtkTimSort             *self);
+
+void            gtk_tim_sort                                    (gpointer                base,
+                                                                 gsize                   size,
+                                                                 gsize                   element_size,
+                                                                 GCompareDataFunc        compare_func,
+                                                                 gpointer                user_data);
+
+#endif /* __GTK_TIMSORT_PRIVATE_H__ */
diff --git a/gtk/meson.build b/gtk/meson.build
index cde5e55eea..1e9d038016 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -139,6 +139,7 @@ gtk_private_sources = files([
   'gtktextbtree.c',
   'gtktexthistory.c',
   'gtktextviewchild.c',
+  'gtktimsort.c',
   'gtktrashmonitor.c',
   'gtktreedatalist.c',
 ])
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index 30a1f6b331..4667093a6e 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -99,6 +99,10 @@ tests = [
   { 'name': 'textbuffer' },
   { 'name': 'textiter' },
   { 'name': 'theme-validate' },
+  {
+    'name': 'timsort',
+    'sources': ['timsort.c', '../../gtk/gtktimsort.c'],
+  },
   { 'name': 'tooltips' },
   { 'name': 'treelistmodel' },
   {
diff --git a/testsuite/gtk/timsort.c b/testsuite/gtk/timsort.c
new file mode 100644
index 0000000000..c06ea3b67f
--- /dev/null
+++ b/testsuite/gtk/timsort.c
@@ -0,0 +1,208 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <locale.h>
+
+#include <gtk/gtk.h>
+
+#include "gtk/gtktimsortprivate.h"
+
+#define assert_sort_equal(a, b, size, n) \
+  g_assert_cmpmem (a, sizeof (size) * n, b, sizeof (size) * n)
+
+static int
+compare_int (gconstpointer a,
+             gconstpointer b,
+             gpointer      unused)
+{
+  int ia = *(const int *) a;
+  int ib = *(const int *) b;
+
+  return ia < ib ? -1 : (ia > ib);
+}
+
+static int
+compare_pointer (gconstpointer a,
+                 gconstpointer b,
+                 gpointer      unused)
+{
+  gpointer pa = *(const gpointer *) a;
+  gpointer pb = *(const gpointer *) b;
+
+  return pa < pb ? -1 : (pa > pb);
+}
+G_GNUC_UNUSED static void
+dump (int *a,
+      gsize n)
+{
+  gsize i;
+
+  for (i = 0; i < n; i++)
+    {
+      if (i)
+        g_print(", ");
+      g_print ("%d", a[i]);
+    }
+  g_print ("\n");
+}
+
+static void
+run_comparison (gpointer         a,
+                gsize            n,
+                gsize            element_size,
+                GCompareDataFunc compare_func,
+                gpointer         data)
+{
+  gint64 start, mid, end;
+  gpointer b;
+
+  b = g_memdup (a, element_size * n);
+
+  start = g_get_monotonic_time ();
+  gtk_tim_sort (a, n, element_size, compare_func, data);
+  mid = g_get_monotonic_time ();
+  g_qsort_with_data (b, n, element_size, compare_func, data);
+  end = g_get_monotonic_time ();
+
+  g_test_message ("%zu items in %ldus vs %ldus (%ld%%)", n, mid - start, end - mid, 100 * (mid - start) / 
MAX (1, end - mid));
+  assert_sort_equal (a, b, int, n);
+
+  g_free (b);
+}
+
+static void
+test_integers (void)
+{
+  int *a;
+  gsize i, n, run;
+
+  a = g_new (int, 1000);
+
+  for (run = 0; run < 10; run++)
+    {
+      n = g_test_rand_int_range (0, 1000);
+      for (i = 0; i < n; i++)
+        a[i] = g_test_rand_int ();
+
+      run_comparison (a, n, sizeof (int), compare_int, NULL);
+    }
+
+  g_free (a);
+}
+
+static void
+test_integers_runs (void)
+{
+  int *a;
+  gsize i, j, n, run;
+
+  a = g_new (int, 1000);
+
+  for (run = 0; run < 10; run++)
+    {
+      n = g_test_rand_int_range (0, 1000);
+      for (i = 0; i < n; i++)
+        {
+          a[i] = g_test_rand_int ();
+          j = i + g_test_rand_int_range (0, 20);
+          j = MIN (n, j);
+          if (g_test_rand_bit ())
+            {
+              for (i++; i < j; i++)
+                a[i] = a[i - 1] + 1;
+            }
+          else
+            {
+              for (i++; i < j; i++)
+                a[i] = a[i - 1] - 1;
+            }
+        }
+
+      run_comparison (a, n, sizeof (int), compare_int, NULL);
+    }
+
+  g_free (a);
+}
+
+static void
+test_integers_huge (void)
+{
+  int *a;
+  gsize i, n;
+
+  n = g_test_rand_int_range (2 * 1000 * 1000, 5 * 1000 * 1000);
+
+  a = g_new (int, n);
+  for (i = 0; i < n; i++)
+    a[i] = g_test_rand_int ();
+
+  run_comparison (a, n, sizeof (int), compare_int, NULL);
+
+  g_free (a);
+}
+
+static void
+test_pointers (void)
+{
+  gpointer *a;
+  gsize i, n, run;
+
+  a = g_new (gpointer, 1000);
+
+  for (run = 0; run < 10; run++)
+    {
+      n = g_test_rand_int_range (0, 1000);
+      for (i = 0; i < n; i++)
+        a[i] = GINT_TO_POINTER (g_test_rand_int ());
+
+      run_comparison (a, n, sizeof (gpointer), compare_pointer, NULL);
+    }
+
+  g_free (a);
+}
+
+static void
+test_pointers_huge (void)
+{
+  gpointer *a;
+  gsize i, n;
+
+  n = g_test_rand_int_range (2 * 1000 * 1000, 5 * 1000 * 1000);
+
+  a = g_new (gpointer, n);
+  for (i = 0; i < n; i++)
+    a[i] = GINT_TO_POINTER (g_test_rand_int ());
+
+  run_comparison (a, n, sizeof (gpointer), compare_pointer, NULL);
+
+  g_free (a);
+}
+
+int
+main (int argc, char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "C");
+
+  g_test_add_func ("/timsort/integers", test_integers);
+  g_test_add_func ("/timsort/integers/runs", test_integers_runs);
+  g_test_add_func ("/timsort/integers/huge", test_integers_huge);
+  g_test_add_func ("/timsort/pointers", test_pointers);
+  g_test_add_func ("/timsort/pointers/huge", test_pointers_huge);
+
+  return g_test_run ();
+}



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]