libcdecl: Simplify sorting in cdecl__normalize_specs.

Rewrite the merge sort helper in a simpler way, which not only
simplifies the source code but also helps reduce the library size.

diff --git a/src/normalize.c b/src/normalize.c
index eac71f3ae12ba6c25c8e67cb7e44349bb8da32e8..8cd002047a4fc5cbabd590b007bbddd01d593d1e 100644 (file)
--- a/src/normalize.c
+++ b/src/normalize.c
@@ -1,6 +1,6 @@
 /*
  *  Normalize C declaration specifier lists.
- *  Copyright © 2011, 2021 Nick Bowler
+ *  Copyright © 2011, 2021, 2023 Nick Bowler
  *
  *  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
@@ -58,82 +58,53 @@ static int order_spec(const struct cdecl_declspec *spec)
        return ret;
 }
 
-static int compare_specs(const struct cdecl_declspec *a,
-                         const struct cdecl_declspec *b)
+static int
+compare_specs(const struct cdecl_declspec *a, const struct cdecl_declspec *b)
 {
        return order_spec(a) - order_spec(b);
 }
 
-/*
- * Merge two sorted specifier lists.  Each list must have at least one element.
- */
+/* Merge two sorted specifier lists, and return the head of the sorted list. */
 static struct cdecl_declspec *
-merge_specs(struct cdecl_declspec *l1, size_t n1,
-            struct cdecl_declspec *l2, size_t n2)
+merge_specs(struct cdecl_declspec *l1, struct cdecl_declspec *l2)
 {
-       struct cdecl_declspec *top = l1, **p = ⊤
-
-       assert(n1 > 0 && n2 > 0);
+       struct cdecl_declspec *head = NULL, **x = &head;
 
-       for (size_t i = 0, j = 0; i < n1 && j < n2;) {
-               int ord = compare_specs(l1, l2);
-               struct cdecl_declspec *tmp;
-
-               if (ord <= 0) {
-                       p = &l1->next;
+       while (l1 && l2) {
+               if (compare_specs(l1, l2) > 0) {
+                       *x = l2;
+                       l2 = l2->next;
+               } else {
+                       *x = l1;
                        l1 = l1->next;
-                       i++;
-               } else if (ord > 0) {
-                       tmp = l2->next;
-                       l2->next = l1;
-                       *p = l2;
-                       p = &l2->next;
-                       l2 = tmp;
-
-                       j++;
                }
-
-               if (!l1)
-                       *p = l2;
+               x = &(*x)->next;
        }
 
-       return top;
+       *x = l1 ? l1 : l2;
+       return head;
 }
-        
 
-/*
- * A simple merge sort.  Set n to the number of elements in the list, or 0
- * to have the sort function count them.
- */
-static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
+/* Merge sort a specifier list, where n is the number of items in the list. */
+static struct cdecl_declspec *
+sort_specs(struct cdecl_declspec *l1, size_t n)
 {
-       struct cdecl_declspec *l2, *c;
-       size_t i;
+       struct cdecl_declspec *l2 = l1, **x = &l1;
+       size_t i, n1;
 
-       /* Find the midpoint of the list. */
-       if (n > 1) {
-               for (i = 0, l2 = l1; i < (n+1)/2; i++)
-                       l2 = l2->next;
-       } else if (n == 0) {
-               for (i = 0, c = l2 = l1; c; i++, c = c->next) {
-                       if (i % 2 == 0)
-                               l2 = l2->next;
-               }
-
-               n = i;
-       }
-
-       assert(n != 0);
-       if (n == 1) {
-               l1->next = NULL;
+       if (n < 2)
                return l1;
-       }
 
-       /* l1 always has the longer "half". */
-       l1 = sort_specs(l1, (n+1)/2);
-       l2 = sort_specs(l2, n/2);
+       n1 = n/2;
+       for (i = 0; i < n1; i++) {
+               x = &l2->next;
+               l2 = *x;
+       }
+       *x = NULL;
 
-       return merge_specs(l1, (n+1)/2, l2, n/2);
+       l1 = sort_specs(l1, n1);
+       l2 = sort_specs(l2, (n+1)/2);
+       return merge_specs(l1, l2);
 }
 
 /*
@@ -145,21 +116,20 @@ static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
 {
        struct cdecl_declspec *c, *l;
+       size_t count = 0;
 
-       if (!specs)
-               return NULL;
-
-       specs = sort_specs(specs, 0);
+       for (c = specs; c; c = c->next)
+               count++;
+       specs = sort_specs(specs, count);
 
        for (c = specs, l = NULL; c; l = c, c = c->next) {
-               switch (cdecl_spec_kind(c)) {
-               case CDECL_SPEC_QUAL:
-               case CDECL_SPEC_FUNC:
-                       if (l && l->type == c->type) {
-                               l->next = c->next;
-                               free(c);
-                               c = l;
-                       }
+               if (!(c->type & (CDECL_SPEC_QUAL|CDECL_SPEC_FUNC)))
+                       continue;
+
+               if (l && l->type == c->type) {
+                       l->next = c->next;
+                       free(c);
+                       c = l;
                }
        }