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