Adding upstream version 9.1.upstream/9.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 156 insertions, 0 deletions

diff --git a/lib/mpsort.c b/lib/mpsort.c
new file mode 100644
index 0000000..459a63c
--- /dev/null
+++ b/lib/mpsort.c
@@ -0,0 +1,156 @@
+/* Sort a vector of pointers to data.
+
+   Copyright (C) 2007, 2009-2022 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Written by Paul Eggert.  */
+
+#include <config.h>
+
+#include "mpsort.h"
+
+#include <string.h>
+
+/* The type of qsort-style comparison functions.  */
+
+typedef int (*comparison_function) (void const *, void const *);
+
+static void mpsort_with_tmp (void const **restrict, size_t,
+                             void const **restrict, comparison_function);
+
+/* Sort a vector BASE containing N pointers, placing the sorted array
+   into TMP.  Compare pointers with CMP.  N must be at least 2.  */
+
+static void
+mpsort_into_tmp (void const **restrict base, size_t n,
+                 void const **restrict tmp,
+                 comparison_function cmp)
+{
+  size_t n1 = n / 2;
+  size_t n2 = n - n1;
+  size_t a = 0;
+  size_t alim = n1;
+  size_t b = n1;
+  size_t blim = n;
+  void const *ba;
+  void const *bb;
+
+  mpsort_with_tmp (base + n1, n2, tmp, cmp);
+  mpsort_with_tmp (base, n1, tmp, cmp);
+
+  ba = base[a];
+  bb = base[b];
+
+  for (;;)
+    if (cmp (ba, bb) <= 0)
+      {
+        *tmp++ = ba;
+        a++;
+        if (a == alim)
+          {
+            a = b;
+            alim = blim;
+            break;
+          }
+        ba = base[a];
+      }
+    else
+      {
+        *tmp++ = bb;
+        b++;
+        if (b == blim)
+          break;
+        bb = base[b];
+      }
+
+  memcpy (tmp, base + a, (alim - a) * sizeof *base);
+}
+
+/* Sort a vector BASE containing N pointers, in place.  Use TMP
+   (containing N / 2 pointers) for temporary storage.  Compare
+   pointers with CMP.  */
+
+static void
+mpsort_with_tmp (void const **restrict base, size_t n,
+                 void const **restrict tmp,
+                 comparison_function cmp)
+{
+  if (n <= 2)
+    {
+      if (n == 2)
+        {
+          void const *p0 = base[0];
+          void const *p1 = base[1];
+          if (! (cmp (p0, p1) <= 0))
+            {
+              base[0] = p1;
+              base[1] = p0;
+            }
+        }
+    }
+  else
+    {
+      size_t n1 = n / 2;
+      size_t n2 = n - n1;
+      size_t i;
+      size_t t = 0;
+      size_t tlim = n1;
+      size_t b = n1;
+      size_t blim = n;
+      void const *bb;
+      void const *tt;
+
+      mpsort_with_tmp (base + n1, n2, tmp, cmp);
+
+      if (n1 < 2)
+        tmp[0] = base[0];
+      else
+        mpsort_into_tmp (base, n1, tmp, cmp);
+
+      tt = tmp[t];
+      bb = base[b];
+
+      for (i = 0; ; )
+        if (cmp (tt, bb) <= 0)
+          {
+            base[i++] = tt;
+            t++;
+            if (t == tlim)
+              break;
+            tt = tmp[t];
+          }
+        else
+          {
+            base[i++] = bb;
+            b++;
+            if (b == blim)
+              {
+                memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
+                break;
+              }
+            bb = base[b];
+          }
+    }
+}
+
+/* Sort a vector BASE containing N pointers, in place.  BASE must
+   contain enough storage to hold N + N / 2 vectors; the trailing
+   vectors are used for temporaries.  Compare pointers with CMP.  */
+
+void
+mpsort (void const **base, size_t n, comparison_function cmp)
+{
+  mpsort_with_tmp (base, n, base + n, cmp);
+}