1 /* C string table handling.
2 Copyright (C) 2000-2023 Free Software Foundation, Inc.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
7 any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, see <https://www.gnu.org/licenses/>. */
16
17 #ifdef HAVE_CONFIG_H
18 # include <config.h>
19 #endif
20
21 #include <assert.h>
22 #include <inttypes.h>
23 #include <stddef.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <unistd.h>
27 #include <sys/cdefs.h>
28 #include <sys/param.h>
29
30
31 struct Strent
32 {
33 const char *string;
34 size_t len;
35 struct Strent *next;
36 struct Strent *left;
37 struct Strent *right;
38 size_t offset;
39 char reverse[0];
40 };
41
42
43 struct memoryblock
44 {
45 struct memoryblock *next;
46 char memory[0];
47 };
48
49
50 struct Strtab
51 {
52 struct Strent *root;
53 struct memoryblock *memory;
54 char *backp;
55 size_t left;
56 size_t total;
57
58 struct Strent null;
59 };
60
61
62 /* Cache for the pagesize. We correct this value a bit so that `malloc'
63 is not allocating more than a page. */
64 static size_t ps;
65
66
67 #include <programs/xmalloc.h>
68
69 /* Prototypes for our functions that are used from iconvconfig.c. If
70 you change these, change also iconvconfig.c. */
71 /* Create new C string table object in memory. */
72 extern struct Strtab *strtabinit (void);
73
74 /* Free resources allocated for C string table ST. */
75 extern void strtabfree (struct Strtab *st);
76
77 /* Add string STR (length LEN is != 0) to C string table ST. */
78 extern struct Strent *strtabadd (struct Strtab *st, const char *str,
79 size_t len);
80
81 /* Finalize string table ST and store size in *SIZE and return a pointer. */
82 extern void *strtabfinalize (struct Strtab *st, size_t *size);
83
84 /* Get offset in string table for string associated with SE. */
85 extern size_t strtaboffset (struct Strent *se);
86
87
88 struct Strtab *
89 strtabinit (void)
90 {
91 struct Strtab *ret;
92
93 if (ps == 0)
94 {
95 ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
96 assert (sizeof (struct memoryblock) < ps);
97 }
98
99 ret = (struct Strtab *) calloc (1, sizeof (struct Strtab));
100 if (ret != NULL)
101 {
102 ret->null.len = 1;
103 ret->null.string = "";
104 }
105 return ret;
106 }
107
108
109 static void
110 morememory (struct Strtab *st, size_t len)
111 {
112 struct memoryblock *newmem;
113
114 if (len < ps)
115 len = ps;
116 newmem = (struct memoryblock *) malloc (len);
117 if (newmem == NULL)
118 abort ();
119
120 newmem->next = st->memory;
121 st->memory = newmem;
122 st->backp = newmem->memory;
123 st->left = len - offsetof (struct memoryblock, memory);
124 }
125
126
127 void
128 strtabfree (struct Strtab *st)
129 {
130 struct memoryblock *mb = st->memory;
131
132 while (mb != NULL)
133 {
134 void *old = mb;
135 mb = mb->next;
136 free (old);
137 }
138
139 free (st);
140 }
141
142
143 static struct Strent *
144 newstring (struct Strtab *st, const char *str, size_t len)
145 {
146 struct Strent *newstr;
147 size_t align;
148 int i;
149
150 /* Compute the amount of padding needed to make the structure aligned. */
151 align = ((__alignof__ (struct Strent)
152 - (((uintptr_t) st->backp)
153 & (__alignof__ (struct Strent) - 1)))
154 & (__alignof__ (struct Strent) - 1));
155
156 /* Make sure there is enough room in the memory block. */
157 if (st->left < align + sizeof (struct Strent) + len)
158 {
159 morememory (st, sizeof (struct Strent) + len);
160 align = 0;
161 }
162
163 /* Create the reserved string. */
164 newstr = (struct Strent *) (st->backp + align);
165 newstr->string = str;
166 newstr->len = len;
167 newstr->next = NULL;
168 newstr->left = NULL;
169 newstr->right = NULL;
170 newstr->offset = 0;
171 for (i = len - 2; i >= 0; --i)
172 newstr->reverse[i] = str[len - 2 - i];
173 newstr->reverse[len - 1] = '\0';
174 st->backp += align + sizeof (struct Strent) + len;
175 st->left -= align + sizeof (struct Strent) + len;
176
177 return newstr;
178 }
179
180
181 /* XXX This function should definitely be rewritten to use a balancing
182 tree algorithm (AVL, red-black trees). For now a simple, correct
183 implementation is enough. */
184 static struct Strent **
185 searchstring (struct Strent **sep, struct Strent *newstr)
186 {
187 int cmpres;
188
189 /* More strings? */
190 if (*sep == NULL)
191 {
192 *sep = newstr;
193 return sep;
194 }
195
196 /* Compare the strings. */
197 cmpres = memcmp ((*sep)->reverse, newstr->reverse,
198 MIN ((*sep)->len, newstr->len) - 1);
199 if (cmpres == 0)
200 /* We found a matching string. */
201 return sep;
202 else if (cmpres > 0)
203 return searchstring (&(*sep)->left, newstr);
204 else
205 return searchstring (&(*sep)->right, newstr);
206 }
207
208
209 /* Add new string. The actual string is assumed to be permanent. */
210 struct Strent *
211 strtabadd (struct Strtab *st, const char *str, size_t len)
212 {
213 struct Strent *newstr;
214 struct Strent **sep;
215
216 /* Compute the string length if the caller doesn't know it. */
217 if (len == 0)
218 len = strlen (str) + 1;
219
220 /* Make sure all "" strings get offset 0. */
221 if (len == 1)
222 return &st->null;
223
224 /* Allocate memory for the new string and its associated information. */
225 newstr = newstring (st, str, len);
226
227 /* Search in the array for the place to insert the string. If there
228 is no string with matching prefix and no string with matching
229 leading substring, create a new entry. */
230 sep = searchstring (&st->root, newstr);
231 if (*sep != newstr)
232 {
233 /* This is not the same entry. This means we have a prefix match. */
234 if ((*sep)->len > newstr->len)
235 {
236 struct Strent *subs;
237
238 for (subs = (*sep)->next; subs; subs = subs->next)
239 if (subs->len == newstr->len)
240 {
241 /* We have an exact match with a substring. Free the memory
242 we allocated. */
243 st->left += st->backp - (char *) newstr;
244 st->backp = (char *) newstr;
245
246 return subs;
247 }
248
249 /* We have a new substring. This means we don't need the reverse
250 string of this entry anymore. */
251 st->backp -= newstr->len;
252 st->left += newstr->len;
253
254 newstr->next = (*sep)->next;
255 (*sep)->next = newstr;
256 }
257 else if ((*sep)->len != newstr->len)
258 {
259 /* When we get here it means that the string we are about to
260 add has a common prefix with a string we already have but
261 it is longer. In this case we have to put it first. */
262 st->total += newstr->len - (*sep)->len;
263 newstr->next = *sep;
264 newstr->left = (*sep)->left;
265 newstr->right = (*sep)->right;
266 *sep = newstr;
267 }
268 else
269 {
270 /* We have an exact match. Free the memory we allocated. */
271 st->left += st->backp - (char *) newstr;
272 st->backp = (char *) newstr;
273
274 newstr = *sep;
275 }
276 }
277 else
278 st->total += newstr->len;
279
280 return newstr;
281 }
282
283
284 static void
285 copystrings (struct Strent *nodep, char **freep, size_t *offsetp)
286 {
287 struct Strent *subs;
288
289 if (nodep->left != NULL)
290 copystrings (nodep->left, freep, offsetp);
291
292 /* Process the current node. */
293 nodep->offset = *offsetp;
294 *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
295 *offsetp += nodep->len;
296
297 for (subs = nodep->next; subs != NULL; subs = subs->next)
298 {
299 assert (subs->len < nodep->len);
300 subs->offset = nodep->offset + nodep->len - subs->len;
301 }
302
303 if (nodep->right != NULL)
304 copystrings (nodep->right, freep, offsetp);
305 }
306
307
308 void *
309 strtabfinalize (struct Strtab *st, size_t *size)
310 {
311 size_t copylen;
312 char *endp;
313 char *retval;
314
315 /* Fill in the information. */
316 endp = retval = (char *) xmalloc (st->total + 1);
317
318 /* Always put an empty string at the beginning so that a zero offset
319 can mean error. */
320 *endp++ = '\0';
321
322 /* Now run through the tree and add all the string while also updating
323 the offset members of the elfstrent records. */
324 copylen = 1;
325 copystrings (st->root, &endp, ©len);
326 assert (copylen == st->total + 1);
327 assert (endp == retval + st->total + 1);
328 *size = copylen;
329
330 return retval;
331 }
332
333
334 size_t
335 strtaboffset (struct Strent *se)
336 {
337 return se->offset;
338 }