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