2007-07-24 Roland McGrath <roland@redhat.com>
[kopensolaris-gnu/glibc.git] / iconv / strtab.c
1 /* C string table handling.
2    Copyright (C) 2000, 2001, 2005 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 *
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
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
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 *
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 **
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 *
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
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 *) mempcpy (*freep, nodep->string, nodep->len);
297   *offsetp += nodep->len;
298
299   for (subs = nodep->next; subs != NULL; subs = subs->next)
300     {
301       assert (subs->len < nodep->len);
302       subs->offset = nodep->offset + nodep->len - subs->len;
303     }
304
305   if (nodep->right != NULL)
306     copystrings (nodep->right, freep, offsetp);
307 }
308
309
310 void *
311 strtabfinalize (struct Strtab *st, size_t *size)
312 {
313   size_t copylen;
314   char *endp;
315   char *retval;
316
317   /* Fill in the information.  */
318   endp = retval = (char *) xmalloc (st->total + 1);
319
320   /* Always put an empty string at the beginning so that a zero offset
321      can mean error.  */
322   *endp++ = '\0';
323
324   /* Now run through the tree and add all the string while also updating
325      the offset members of the elfstrent records.  */
326   copylen = 1;
327   copystrings (st->root, &endp, &copylen);
328   assert (copylen == st->total + 1);
329   assert (endp == retval + st->total + 1);
330   *size = copylen;
331
332   return retval;
333 }
334
335
336 size_t
337 strtaboffset (struct Strent *se)
338 {
339   return se->offset;
340 }