2 * Normalize C declaration specifier lists.
3 * Copyright © 2011, 2021 Nick Bowler
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
24 #include "cdecl-internal.h"
27 * Totally order the declaration specifier types by defining an injection into
28 * the natural numbers.
30 static unsigned order_spec(struct cdecl_declspec *spec)
33 # include "ordspecs.h"
39 static int compare_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
41 return order_spec(a) - order_spec(b);
45 * Merge two sorted specifier lists. Each list must have at least one element.
47 static struct cdecl_declspec *
48 merge_specs(struct cdecl_declspec *l1, size_t n1,
49 struct cdecl_declspec *l2, size_t n2)
51 struct cdecl_declspec *top = l1, **p = ⊤
53 assert(n1 > 0 && n2 > 0);
55 for (size_t i = 0, j = 0; i < n1 && j < n2;) {
56 int ord = compare_specs(l1, l2);
57 struct cdecl_declspec *tmp;
82 * A simple merge sort. Set n to the number of elements in the list, or 0
83 * to have the sort function count them.
85 static struct cdecl_declspec *sort_specs(struct cdecl_declspec *l1, size_t n)
87 struct cdecl_declspec *l2, *c;
90 /* Find the midpoint of the list. */
92 for (i = 0, l2 = l1; i < (n+1)/2; i++)
95 for (i = 0, c = l2 = l1; c; i++, c = c->next) {
109 /* l1 always has the longer "half". */
110 l1 = sort_specs(l1, (n+1)/2);
111 l2 = sort_specs(l2, n/2);
113 return merge_specs(l1, (n+1)/2, l2, n/2);
117 * C allows declaration specifiers to appear in any order, and allows arbitrary
118 * repetition of some kinds of specifiers. Normalize the specifier lists by
119 * sorting the specifiers and removing repeated function specifiers and type
122 struct cdecl_declspec *cdecl__normalize_specs(struct cdecl_declspec *specs)
124 struct cdecl_declspec *c, *l;
129 specs = sort_specs(specs, 0);
131 for (c = specs, l = NULL; c; l = c, c = c->next) {
132 switch (cdecl_spec_kind(c)) {
133 case CDECL_SPEC_QUAL:
134 case CDECL_SPEC_FUNC:
135 if (l && l->type == c->type) {