1 /* C string table handling.
2 Copyright (C) 2000-2019 Free Software Foundation, Inc.
3 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
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)
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 <https://www.gnu.org/licenses/>. */
28 #include <sys/cdefs.h>
29 #include <sys/param.h>
46 struct memoryblock
*next
;
54 struct memoryblock
*memory
;
63 /* Cache for the pagesize. We correct this value a bit so that `malloc'
64 is not allocating more than a page. */
68 #include <programs/xmalloc.h>
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. */
73 extern struct Strtab
*strtabinit (void);
75 /* Free resources allocated for C string table ST. */
76 extern void strtabfree (struct Strtab
*st
);
78 /* Add string STR (length LEN is != 0) to C string table ST. */
79 extern struct Strent
*strtabadd (struct Strtab
*st
, const char *str
,
82 /* Finalize string table ST and store size in *SIZE and return a pointer. */
83 extern void *strtabfinalize (struct Strtab
*st
, size_t *size
);
85 /* Get offset in string table for string associated with SE. */
86 extern size_t strtaboffset (struct Strent
*se
);
96 ps
= sysconf (_SC_PAGESIZE
) - 2 * sizeof (void *);
97 assert (sizeof (struct memoryblock
) < ps
);
100 ret
= (struct Strtab
*) calloc (1, sizeof (struct Strtab
));
104 ret
->null
.string
= "";
111 morememory (struct Strtab
*st
, size_t len
)
113 struct memoryblock
*newmem
;
117 newmem
= (struct memoryblock
*) malloc (len
);
121 newmem
->next
= st
->memory
;
123 st
->backp
= newmem
->memory
;
124 st
->left
= len
- offsetof (struct memoryblock
, memory
);
129 strtabfree (struct Strtab
*st
)
131 struct memoryblock
*mb
= st
->memory
;
144 static struct Strent
*
145 newstring (struct Strtab
*st
, const char *str
, size_t len
)
147 struct Strent
*newstr
;
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));
157 /* Make sure there is enough room in the memory block. */
158 if (st
->left
< align
+ sizeof (struct Strent
) + len
)
160 morememory (st
, sizeof (struct Strent
) + len
);
164 /* Create the reserved string. */
165 newstr
= (struct Strent
*) (st
->backp
+ align
);
166 newstr
->string
= str
;
170 newstr
->right
= NULL
;
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
;
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. */
185 static struct Strent
**
186 searchstring (struct Strent
**sep
, struct Strent
*newstr
)
197 /* Compare the strings. */
198 cmpres
= memcmp ((*sep
)->reverse
, newstr
->reverse
,
199 MIN ((*sep
)->len
, newstr
->len
) - 1);
201 /* We found a matching string. */
204 return searchstring (&(*sep
)->left
, newstr
);
206 return searchstring (&(*sep
)->right
, newstr
);
210 /* Add new string. The actual string is assumed to be permanent. */
212 strtabadd (struct Strtab
*st
, const char *str
, size_t len
)
214 struct Strent
*newstr
;
217 /* Compute the string length if the caller doesn't know it. */
219 len
= strlen (str
) + 1;
221 /* Make sure all "" strings get offset 0. */
225 /* Allocate memory for the new string and its associated information. */
226 newstr
= newstring (st
, str
, len
);
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
);
234 /* This is not the same entry. This means we have a prefix match. */
235 if ((*sep
)->len
> newstr
->len
)
239 for (subs
= (*sep
)->next
; subs
; subs
= subs
->next
)
240 if (subs
->len
== newstr
->len
)
242 /* We have an exact match with a substring. Free the memory
244 st
->left
+= st
->backp
- (char *) newstr
;
245 st
->backp
= (char *) newstr
;
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
;
255 newstr
->next
= (*sep
)->next
;
256 (*sep
)->next
= newstr
;
258 else if ((*sep
)->len
!= newstr
->len
)
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
;
265 newstr
->left
= (*sep
)->left
;
266 newstr
->right
= (*sep
)->right
;
271 /* We have an exact match. Free the memory we allocated. */
272 st
->left
+= st
->backp
- (char *) newstr
;
273 st
->backp
= (char *) newstr
;
279 st
->total
+= newstr
->len
;
286 copystrings (struct Strent
*nodep
, char **freep
, size_t *offsetp
)
290 if (nodep
->left
!= NULL
)
291 copystrings (nodep
->left
, freep
, offsetp
);
293 /* Process the current node. */
294 nodep
->offset
= *offsetp
;
295 *freep
= (char *) mempcpy (*freep
, nodep
->string
, nodep
->len
);
296 *offsetp
+= nodep
->len
;
298 for (subs
= nodep
->next
; subs
!= NULL
; subs
= subs
->next
)
300 assert (subs
->len
< nodep
->len
);
301 subs
->offset
= nodep
->offset
+ nodep
->len
- subs
->len
;
304 if (nodep
->right
!= NULL
)
305 copystrings (nodep
->right
, freep
, offsetp
);
310 strtabfinalize (struct Strtab
*st
, size_t *size
)
316 /* Fill in the information. */
317 endp
= retval
= (char *) xmalloc (st
->total
+ 1);
319 /* Always put an empty string at the beginning so that a zero offset
323 /* Now run through the tree and add all the string while also updating
324 the offset members of the elfstrent records. */
326 copystrings (st
->root
, &endp
, ©len
);
327 assert (copylen
== st
->total
+ 1);
328 assert (endp
== retval
+ st
->total
+ 1);
336 strtaboffset (struct Strent
*se
)