1 /* Unit test for ldconfig string tables.
2 Copyright (C) 2020-2022 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
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
7 by the Free Software Foundation; version 2 of the License, or
8 (at your option) any later version.
9
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.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, see <https://www.gnu.org/licenses/>. */
17
18 #include <array_length.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <stringtable.h>
22 #include <support/check.h>
23 #include <support/support.h>
24
25 static int
do_test(void)26 do_test (void)
27 {
28 /* Empty string table. */
29 {
30 struct stringtable s = { 0, };
31 struct stringtable_finalized f;
32 stringtable_finalize (&s, &f);
33 TEST_COMPARE_STRING (f.strings, "");
34 TEST_COMPARE (f.size, 0);
35 free (f.strings);
36 stringtable_free (&s);
37 }
38
39 /* String table with one empty string. */
40 {
41 struct stringtable s = { 0, };
42 struct stringtable_entry *e = stringtable_add (&s, "");
43 TEST_COMPARE_STRING (e->string, "");
44 TEST_COMPARE (e->length, 0);
45 TEST_COMPARE (s.count, 1);
46
47 struct stringtable_finalized f;
48 stringtable_finalize (&s, &f);
49 TEST_COMPARE (e->offset, 0);
50 TEST_COMPARE_STRING (f.strings, "");
51 TEST_COMPARE (f.size, 1);
52 free (f.strings);
53 stringtable_free (&s);
54 }
55
56 /* String table with one non-empty string. */
57 {
58 struct stringtable s = { 0, };
59 struct stringtable_entry *e = stringtable_add (&s, "name");
60 TEST_COMPARE_STRING (e->string, "name");
61 TEST_COMPARE (e->length, 4);
62 TEST_COMPARE (s.count, 1);
63
64 struct stringtable_finalized f;
65 stringtable_finalize (&s, &f);
66 TEST_COMPARE (e->offset, 0);
67 TEST_COMPARE_STRING (f.strings, "name");
68 TEST_COMPARE (f.size, 5);
69 free (f.strings);
70 stringtable_free (&s);
71 }
72
73 /* Two strings, one is a prefix of the other. Tail-merging can only
74 happen in one way in this case. */
75 {
76 struct stringtable s = { 0, };
77 struct stringtable_entry *suffix = stringtable_add (&s, "suffix");
78 TEST_COMPARE_STRING (suffix->string, "suffix");
79 TEST_COMPARE (suffix->length, 6);
80 TEST_COMPARE (s.count, 1);
81
82 struct stringtable_entry *prefix
83 = stringtable_add (&s, "prefix-suffix");
84 TEST_COMPARE_STRING (prefix->string, "prefix-suffix");
85 TEST_COMPARE (prefix->length, strlen ("prefix-suffix"));
86 TEST_COMPARE (s.count, 2);
87
88 struct stringtable_finalized f;
89 stringtable_finalize (&s, &f);
90 TEST_COMPARE (prefix->offset, 0);
91 TEST_COMPARE (suffix->offset, strlen ("prefix-"));
92 TEST_COMPARE_STRING (f.strings, "prefix-suffix");
93 TEST_COMPARE (f.size, sizeof ("prefix-suffix"));
94 free (f.strings);
95 stringtable_free (&s);
96 }
97
98 /* String table with various shared prefixes. Triggers hash
99 resizing. */
100 {
101 enum { count = 1500 };
102 char *strings[2 * count];
103 struct stringtable_entry *entries[2 * count];
104 struct stringtable s = { 0, };
105 for (int i = 0; i < count; ++i)
106 {
107 strings[i] = xasprintf ("%d", i);
108 entries[i] = stringtable_add (&s, strings[i]);
109 TEST_COMPARE (entries[i]->length, strlen (strings[i]));
110 TEST_COMPARE_STRING (entries[i]->string, strings[i]);
111 strings[i + count] = xasprintf ("prefix/%d", i);
112 entries[i + count] = stringtable_add (&s, strings[i + count]);
113 TEST_COMPARE (entries[i + count]->length, strlen (strings[i + count]));
114 TEST_COMPARE_STRING (entries[i + count]->string, strings[i + count]);
115 }
116
117 struct stringtable_finalized f;
118 stringtable_finalize (&s, &f);
119
120 for (int i = 0; i < 2 * count; ++i)
121 {
122 TEST_COMPARE (entries[i]->length, strlen (strings[i]));
123 TEST_COMPARE_STRING (entries[i]->string, strings[i]);
124 TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
125 free (strings[i]);
126 }
127
128 free (f.strings);
129 stringtable_free (&s);
130 }
131
132 /* Verify that maximum tail merging happens. */
133 {
134 struct stringtable s = { 0, };
135 const char *strings[] = {
136 "",
137 "a",
138 "b",
139 "aa",
140 "aaa",
141 "aa",
142 "bb",
143 "b",
144 "a",
145 "ba",
146 "baa",
147 };
148 struct stringtable_entry *entries[array_length (strings)];
149 for (int i = 0; i < array_length (strings); ++i)
150 entries[i] = stringtable_add (&s, strings[i]);
151 for (int i = 0; i < array_length (strings); ++i)
152 TEST_COMPARE_STRING (entries[i]->string, strings[i]);
153
154 struct stringtable_finalized f;
155 stringtable_finalize (&s, &f);
156
157 /* There are only four different strings, "aaa", "ba", "baa",
158 "bb". The rest is shared in an unspecified fashion. */
159 TEST_COMPARE (f.size, 4 + 3 + 4 + 3);
160
161 for (int i = 0; i < array_length (strings); ++i)
162 {
163 TEST_COMPARE_STRING (entries[i]->string, strings[i]);
164 TEST_COMPARE_STRING (f.strings + entries[i]->offset, strings[i]);
165 }
166
167 free (f.strings);
168 stringtable_free (&s);
169 }
170
171 return 0;
172 }
173
174 #include <support/test-driver.c>
175
176 /* Re-compile the string table implementation here. It is not
177 possible to link against the actual build because it was built for
178 use in ldconfig. */
179 #define _(arg) arg
180 #include "stringtable.c"
181 #include "stringtable_free.c"
182