+/*
+ * Normalize C declaration specifier lists.
+ * Copyright © 2011 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
+ * 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 <http://www.gnu.org/licenses/>.
+ */
+#include <config.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include "cdecl.h"
+#include "normalize.h"
+
+/*
+ * Totally order the declaration specifier types by defining an injection into
+ * the natural numbers.
+ */
+static unsigned order_spec(struct cdecl_declspec *spec)
+{
+ switch (spec->type) {
+# include "ordspecs.h"
+ default:
+ assert(0);
+ }
+}
+
+static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
+{
+ return order_spec(a) - order_spec(b);
+}
+
+/*
+ * Merge two sorted specifier lists. Each list must have at least one element.
+ */
+static struct cdecl_declspec *
+merge_specs(struct cdecl_declspec *l1, size_t n1,
+ struct cdecl_declspec *l2, size_t n2)
+{
+ struct cdecl_declspec *top = l1, **p = ⊤
+
+ assert(n1 > 0 && n2 > 0);
+
+ 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;
+ 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;
+ }
+
+ return top;
+}
+
+
+/*
+ * 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)
+{
+ struct cdecl_declspec *l2, *c;
+ size_t i;
+
+ /* 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;
+ return l1;
+ }
+
+ /* l1 always has the longer "half". */
+ l1 = sort_specs(l1, (n+1)/2);
+ l2 = sort_specs(l2, n/2);
+
+ return merge_specs(l1, (n+1)/2, l2, n/2);
+}
+
+/*
+ * C allows declaration specifiers to appear in any order, and allows arbitrary
+ * repetition of some kinds of specifiers. Normalize the specifier lists by
+ * sorting the specifiers and removing repeated function specifiers and type
+ * qualifiers.
+ */
+struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
+{
+ struct cdecl_declspec *c, *l;
+
+ if (!specs)
+ return NULL;
+
+ specs = sort_specs(specs, 0);
+
+ 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;
+ }
+ }
+ }
+
+ return specs;
+}