Update copyright year.
[kopensolaris-gnu/glibc.git] / iconv / iconvconfig.c
1 /* Generate fastloading iconv module configuration files.
2    Copyright (C) 2000-2007, 2008 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Ulrich Drepper <drepper@redhat.com>, 2000.
5
6    This program is free software; you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published
8    by the Free Software Foundation; version 2 of the License, or
9    (at your option) any later version.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with this program; if not, write to the Free Software Foundation,
18    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
19
20 #include <argp.h>
21 #include <assert.h>
22 #include <error.h>
23 #include <errno.h>
24 #include <fcntl.h>
25 #include <libintl.h>
26 #include <locale.h>
27 #include <mcheck.h>
28 #include <search.h>
29 #include <stdint.h>
30 #include <stdbool.h>
31 #include <stdio.h>
32 #include <stdio_ext.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <unistd.h>
36 #include <sys/cdefs.h>
37 #include <sys/uio.h>
38
39 #include "iconvconfig.h"
40
41 /* Get libc version number.  */
42 #include "../version.h"
43
44 #define PACKAGE _libc_intl_domainname
45
46
47 /* The hashing function we use.  */
48 #include "../intl/hash-string.h"
49
50
51 /* Types used.  */
52 struct module
53 {
54   char *fromname;
55   struct Strent *fromname_strent;
56   char *filename;
57   struct Strent *filename_strent;
58   const char *directory;
59   struct Strent *directory_strent;
60   struct module *next;
61   int cost;
62   struct Strent *toname_strent;
63   char toname[0];
64 };
65
66 struct alias
67 {
68   char *fromname;
69   struct Strent *froment;
70   struct module *module;
71   struct Strent *toent;
72   char toname[0];
73 };
74
75 struct name
76 {
77   const char *name;
78   struct Strent *strent;
79   int module_idx;
80   uint32_t hashval;
81 };
82
83 struct name_info
84 {
85   const char *canonical_name;
86   struct Strent *canonical_strent;
87
88   struct module *from_internal;
89   struct module *to_internal;
90
91   struct other_conv_list
92   {
93     int dest_idx;
94     struct other_conv
95     {
96       gidx_t module_idx;
97       struct module *module;
98       struct other_conv *next;
99     } other_conv;
100     struct other_conv_list *next;
101   } *other_conv_list;
102 };
103
104
105 /* Name and version of program.  */
106 static void print_version (FILE *stream, struct argp_state *state);
107 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
108
109 /* Short description of program.  */
110 static const char doc[] = N_("\
111 Create fastloading iconv module configuration file.");
112
113 /* Strings for arguments in help texts.  */
114 static const char args_doc[] = N_("[DIR...]");
115
116 /* Prototype for option handler.  */
117 static error_t parse_opt (int key, char *arg, struct argp_state *state);
118
119 /* Function to print some extra text in the help message.  */
120 static char *more_help (int key, const char *text, void *input);
121
122 /* Definitions of arguments for argp functions.  */
123 #define OPT_PREFIX 300
124 #define OPT_NOSTDLIB 301
125 static const struct argp_option options[] =
126 {
127   { "prefix", OPT_PREFIX, "PATH", 0, N_("Prefix used for all file accesses") },
128   { "output", 'o', "FILE", 0, N_("\
129 Put output in FILE instead of installed location\
130  (--prefix does not apply to FILE)") },
131   { "nostdlib", OPT_NOSTDLIB, NULL, 0,
132     N_("Do not search standard directories, only those on the command line") },
133   { NULL, 0, NULL, 0, NULL }
134 };
135
136 /* Data structure to communicate with argp functions.  */
137 static struct argp argp =
138 {
139   options, parse_opt, args_doc, doc, NULL, more_help
140 };
141
142
143 /* The function doing the actual work.  */
144 static int handle_dir (const char *dir);
145
146 /* Add all known builtin conversions and aliases.  */
147 static void add_builtins (void);
148
149 /* Create list of all aliases without circular aliases.  */
150 static void get_aliases (void);
151
152 /* Create list of all modules.  */
153 static void get_modules (void);
154
155 /* Get list of all the names and thereby indexing them.  */
156 static void generate_name_list (void);
157
158 /* Collect information about all the names.  */
159 static void generate_name_info (void);
160
161 /* Write the output file.  */
162 static int write_output (void);
163
164
165 /* Prefix to be used for all file accesses.  */
166 static const char *prefix = "";
167 /* Its length.  */
168 static size_t prefix_len;
169
170 /* Directory to place output file in.  */
171 static const char *output_file;
172 /* Its length.  */
173 static size_t output_file_len;
174
175 /* If true, omit the GCONV_PATH directories and require some arguments.  */
176 static bool nostdlib;
177
178 /* Search tree of the modules we know.  */
179 static void *modules;
180
181 /* Search tree of the aliases we know.  */
182 static void *aliases;
183
184 /* Search tree for name to index mapping.  */
185 static void *names;
186
187 /* Number of names we know about.  */
188 static int nnames;
189
190 /* List of all aliases.  */
191 static struct alias **alias_list;
192 static size_t nalias_list;
193 static size_t nalias_list_max;
194
195 /* List of all modules.  */
196 static struct module **module_list;
197 static size_t nmodule_list;
198 static size_t nmodule_list_max;
199
200 /* Names and information about them.  */
201 static struct name_info *name_info;
202 static size_t nname_info;
203
204 /* Number of translations not from or to INTERNAL.  */
205 static size_t nextra_modules;
206
207
208 /* Names and aliases for the builtin transformations.  */
209 static struct
210 {
211   const char *from;
212   const char *to;
213 } builtin_alias[] =
214   {
215 #define BUILTIN_ALIAS(alias, real) \
216     { .from = alias, .to = real },
217 #define BUILTIN_TRANSFORMATION(From, To, Cost, Name, Fct, BtowcFct, \
218                                MinF, MaxF, MinT, MaxT)
219 #include <gconv_builtin.h>
220   };
221 #undef BUILTIN_ALIAS
222 #undef BUILTIN_TRANSFORMATION
223 #define nbuiltin_alias (sizeof (builtin_alias) / sizeof (builtin_alias[0]))
224
225 static struct
226 {
227   const char *from;
228   const char *to;
229   const char *module;
230   int cost;
231 } builtin_trans[] =
232   {
233 #define BUILTIN_ALIAS(alias, real)
234 #define BUILTIN_TRANSFORMATION(From, To, Cost, Name, Fct, BtowcFct, \
235                                MinF, MaxF, MinT, MaxT) \
236     { .from = From, .to = To, .module = Name, .cost = Cost },
237 #include <gconv_builtin.h>
238   };
239 #undef BUILTIN_ALIAS
240 #undef BUILTIN_TRANSFORMATION
241 #define nbuiltin_trans (sizeof (builtin_trans) / sizeof (builtin_trans[0]))
242
243
244 /* Filename extension for the modules.  */
245 #ifndef MODULE_EXT
246 # define MODULE_EXT ".so"
247 #endif
248 static const char gconv_module_ext[] = MODULE_EXT;
249
250
251 extern void *xmalloc (size_t n) __attribute_malloc__;
252 extern void *xcalloc (size_t n, size_t m) __attribute_malloc__;
253 extern void *xrealloc (void *p, size_t n);
254
255
256 /* C string table handling.  */
257 struct Strtab;
258 struct Strent;
259
260 /* Create new C string table object in memory.  */
261 extern struct Strtab *strtabinit (void);
262
263 /* Free resources allocated for C string table ST.  */
264 extern void strtabfree (struct Strtab *st);
265
266 /* Add string STR (length LEN is != 0) to C string table ST.  */
267 extern struct Strent *strtabadd (struct Strtab *st, const char *str,
268                                  size_t len);
269
270 /* Finalize string table ST and store size in *SIZE and return a pointer.  */
271 extern void *strtabfinalize (struct Strtab *st, size_t *size);
272
273 /* Get offset in string table for string associated with SE.  */
274 extern size_t strtaboffset (struct Strent *se);
275
276 /* String table we construct.  */
277 static struct Strtab *strtab;
278
279
280
281 int
282 main (int argc, char *argv[])
283 {
284   int remaining;
285   int status = 0;
286
287   /* Enable memory use testing.  */
288   /* mcheck_pedantic (NULL); */
289   mtrace ();
290
291   /* Set locale via LC_ALL.  */
292   setlocale (LC_ALL, "");
293
294   /* Set the text message domain.  */
295   textdomain (_libc_intl_domainname);
296
297   /* Parse and process arguments.  */
298   argp_parse (&argp, argc, argv, 0, &remaining, NULL);
299
300   if (nostdlib && remaining == argc)
301     error (2, 0, _("Directory arguments required when using --nostdlib"));
302
303   /* Initialize the string table.  */
304   strtab = strtabinit ();
305
306   /* Handle all directories mentioned.  */
307   while (remaining < argc)
308     status |= handle_dir (argv[remaining++]);
309
310   if (! nostdlib)
311     {
312       /* In any case also handle the standard directory.  */
313       char *path = strdupa (GCONV_PATH), *tp = strsep (&path, ":");
314       while (tp != NULL)
315         {
316           status |= handle_dir (tp);
317
318           tp = strsep (&path, ":");
319         }
320     }
321
322   /* Add the builtin transformations and aliases without overwriting
323      anything.  */
324   add_builtins ();
325
326   /* Store aliases in an array.  */
327   get_aliases ();
328
329   /* Get list of all modules.  */
330   get_modules ();
331
332   /* Generate list of all the names we know to handle in some way.  */
333   generate_name_list ();
334
335   /* Now we know all the names we will handle, collect information
336      about them.  */
337   generate_name_info ();
338
339   /* Write the output file, but only if we haven't seen any error.  */
340   if (status == 0)
341     status = write_output ();
342   else
343     error (1, 0, _("no output file produced because warnings were issued"));
344
345   return status;
346 }
347
348
349 /* Handle program arguments.  */
350 static error_t
351 parse_opt (int key, char *arg, struct argp_state *state)
352 {
353   switch (key)
354     {
355     case OPT_PREFIX:
356       prefix = arg;
357       prefix_len = strlen (prefix);
358       break;
359     case 'o':
360       output_file = arg;
361       output_file_len = strlen (output_file);
362       break;
363     case OPT_NOSTDLIB:
364       nostdlib = true;
365       break;
366     default:
367       return ARGP_ERR_UNKNOWN;
368     }
369   return 0;
370 }
371
372
373 static char *
374 more_help (int key, const char *text, void *input)
375 {
376   switch (key)
377     {
378     case ARGP_KEY_HELP_EXTRA:
379       /* We print some extra information.  */
380       return strdup (gettext ("\
381 For bug reporting instructions, please see:\n\
382 <http://www.gnu.org/software/libc/bugs.html>.\n"));
383     default:
384       break;
385     }
386   return (char *) text;
387 }
388
389
390 /* Print the version information.  */
391 static void
392 print_version (FILE *stream, struct argp_state *state)
393 {
394   fprintf (stream, "iconvconfig (GNU %s) %s\n", PACKAGE, VERSION);
395   fprintf (stream, gettext ("\
396 Copyright (C) %s Free Software Foundation, Inc.\n\
397 This is free software; see the source for copying conditions.  There is NO\n\
398 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
399 "), "2008");
400   fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");
401 }
402
403
404 static int
405 alias_compare (const void *p1, const void *p2)
406 {
407   const struct alias *a1 = (const struct alias *) p1;
408   const struct alias *a2 = (const struct alias *) p2;
409
410   return strcmp (a1->fromname, a2->fromname);
411 }
412
413
414 static void
415 new_alias (const char *fromname, size_t fromlen, const char *toname,
416            size_t tolen)
417 {
418   struct alias *newp;
419   void **inserted;
420
421   newp = (struct alias *) xmalloc (sizeof (struct alias) + fromlen + tolen);
422
423   newp->fromname = mempcpy (newp->toname, toname, tolen);
424   memcpy (newp->fromname, fromname, fromlen);
425   newp->module = NULL;
426
427   inserted = (void **) tsearch (newp, &aliases, alias_compare);
428   if (inserted == NULL)
429     error (EXIT_FAILURE, errno, gettext ("while inserting in search tree"));
430   if (*inserted != newp)
431     /* Something went wrong, free this entry.  */
432     free (newp);
433   else
434     {
435       newp->froment = strtabadd (strtab, newp->fromname, fromlen);
436       newp->toent = strtabadd (strtab, newp->toname, tolen);
437     }
438 }
439
440
441 /* Add new alias.  */
442 static void
443 add_alias (char *rp)
444 {
445   /* We now expect two more string.  The strings are normalized
446      (converted to UPPER case) and strored in the alias database.  */
447   char *from;
448   char *to;
449   char *wp;
450
451   while (isspace (*rp))
452     ++rp;
453   from = wp = rp;
454   while (*rp != '\0' && !isspace (*rp))
455     *wp++ = toupper (*rp++);
456   if (*rp == '\0')
457     /* There is no `to' string on the line.  Ignore it.  */
458     return;
459   *wp++ = '\0';
460   to = ++rp;
461   while (isspace (*rp))
462     ++rp;
463   while (*rp != '\0' && !isspace (*rp))
464     *wp++ = toupper (*rp++);
465   if (to == wp)
466     /* No `to' string, ignore the line.  */
467     return;
468   *wp++ = '\0';
469
470   assert (strlen (from) + 1 == (size_t) (to - from));
471   assert (strlen (to) + 1 == (size_t) (wp - to));
472
473   new_alias (from, to - from, to, wp - to);
474 }
475
476
477 static void
478 append_alias (const void *nodep, VISIT value, int level)
479 {
480   if (value != leaf && value != postorder)
481     return;
482
483   if (nalias_list_max == nalias_list)
484     {
485       nalias_list_max += 50;
486       alias_list = (struct alias **) xrealloc (alias_list,
487                                                (nalias_list_max
488                                                 * sizeof (struct alias *)));
489     }
490
491   alias_list[nalias_list++] = *(struct alias **) nodep;
492 }
493
494
495 static void
496 get_aliases (void)
497 {
498   twalk (aliases, append_alias);
499 }
500
501
502 static int
503 module_compare (const void *p1, const void *p2)
504 {
505   const struct module *m1 = (const struct module *) p1;
506   const struct module *m2 = (const struct module *) p2;
507   int result;
508
509   result = strcmp (m1->fromname, m2->fromname);
510   if (result == 0)
511     result = strcmp (m1->toname, m2->toname);
512
513   return result;
514 }
515
516
517 /* Create new module record.  */
518 static void
519 new_module (const char *fromname, size_t fromlen, const char *toname,
520             size_t tolen, const char *directory,
521             const char *filename, size_t filelen, int cost, size_t need_ext)
522 {
523   struct module *new_module;
524   size_t dirlen = strlen (directory) + 1;
525   char *tmp;
526   void **inserted;
527
528   new_module = (struct module *) xmalloc (sizeof (struct module)
529                                           + fromlen + tolen + filelen
530                                           + need_ext);
531
532   new_module->fromname = mempcpy (new_module->toname, toname, tolen);
533
534   new_module->filename = mempcpy (new_module->fromname, fromname, fromlen);
535
536   new_module->cost = cost;
537   new_module->next = NULL;
538
539   tmp = mempcpy (new_module->filename, filename, filelen);
540   if (need_ext)
541     {
542       memcpy (tmp - 1, gconv_module_ext, need_ext + 1);
543       filelen += need_ext;
544     }
545   new_module->directory = directory;
546
547   /* Now insert the new module data structure in our search tree.  */
548   inserted = (void **) tsearch (new_module, &modules, module_compare);
549   if (inserted == NULL)
550     error (EXIT_FAILURE, errno, "while inserting in search tree");
551   if (*inserted != new_module)
552     free (new_module);
553   else
554     {
555       new_module->fromname_strent = strtabadd (strtab, new_module->fromname,
556                                                fromlen);
557       new_module->toname_strent = strtabadd (strtab, new_module->toname,
558                                              tolen);
559       new_module->filename_strent = strtabadd (strtab, new_module->filename,
560                                                filelen);
561       new_module->directory_strent = strtabadd (strtab, directory, dirlen);
562     }
563 }
564
565
566 /* Add new module.  */
567 static void
568 internal_function
569 add_module (char *rp, const char *directory)
570 {
571   /* We expect now
572      1. `from' name
573      2. `to' name
574      3. filename of the module
575      4. an optional cost value
576   */
577   char *from;
578   char *to;
579   char *module;
580   char *wp;
581   int need_ext;
582   int cost;
583
584   while (isspace (*rp))
585     ++rp;
586   from = rp;
587   while (*rp != '\0' && !isspace (*rp))
588     {
589       *rp = toupper (*rp);
590       ++rp;
591     }
592   if (*rp == '\0')
593     return;
594   *rp++ = '\0';
595   to = wp = rp;
596   while (isspace (*rp))
597     ++rp;
598   while (*rp != '\0' && !isspace (*rp))
599     *wp++ = toupper (*rp++);
600   if (*rp == '\0')
601     return;
602   *wp++ = '\0';
603   do
604     ++rp;
605   while (isspace (*rp));
606   module = wp;
607   while (*rp != '\0' && !isspace (*rp))
608     *wp++ = *rp++;
609   if (*rp == '\0')
610     {
611       /* There is no cost, use one by default.  */
612       *wp++ = '\0';
613       cost = 1;
614     }
615   else
616     {
617       /* There might be a cost value.  */
618       char *endp;
619
620       *wp++ = '\0';
621       cost = strtol (rp, &endp, 10);
622       if (rp == endp || cost < 1)
623         /* No useful information.  */
624         cost = 1;
625     }
626
627   if (module[0] == '\0')
628     /* No module name given.  */
629     return;
630
631   /* See whether we must add the ending.  */
632   need_ext = 0;
633   if ((size_t) (wp - module) < sizeof (gconv_module_ext)
634       || memcmp (wp - sizeof (gconv_module_ext), gconv_module_ext,
635                  sizeof (gconv_module_ext)) != 0)
636     /* We must add the module extension.  */
637     need_ext = sizeof (gconv_module_ext) - 1;
638
639   assert (strlen (from) + 1 == (size_t) (to - from));
640   assert (strlen (to) + 1 == (size_t) (module - to));
641   assert (strlen (module) + 1 == (size_t) (wp - module));
642
643   new_module (from, to - from, to, module - to, directory, module, wp - module,
644               cost, need_ext);
645 }
646
647
648 /* Read the config file and add the data for this directory to that.  */
649 static int
650 handle_dir (const char *dir)
651 {
652   char *cp;
653   FILE *fp;
654   char *line = NULL;
655   size_t linelen = 0;
656   size_t dirlen = strlen (dir);
657
658   if (dir[dirlen - 1] != '/')
659     {
660       char *newp = (char *) xmalloc (dirlen + 2);
661       dir = memcpy (newp, dir, dirlen);
662       newp[dirlen++] = '/';
663       newp[dirlen] = '\0';
664     }
665
666   char infile[prefix_len + dirlen + sizeof "gconv-modules"];
667   cp = infile;
668   if (dir[0] == '/')
669     cp = mempcpy (cp, prefix, prefix_len);
670   strcpy (mempcpy (cp, dir, dirlen), "gconv-modules");
671
672   fp = fopen (infile, "r");
673   if (fp == NULL)
674     {
675       error (0, errno, "cannot open `%s'", infile);
676       return 1;
677     }
678
679   /* No threads present.  */
680   __fsetlocking (fp, FSETLOCKING_BYCALLER);
681
682   while (!feof_unlocked (fp))
683     {
684       char *rp, *endp, *word;
685       ssize_t n = __getdelim (&line, &linelen, '\n', fp);
686
687       if (n < 0)
688         /* An error occurred.  */
689         break;
690
691       rp = line;
692       /* Terminate the line (excluding comments or newline) with a NUL
693          byte to simplify the following code.  */
694       endp = strchr (rp, '#');
695       if (endp != NULL)
696         *endp = '\0';
697       else
698         if (rp[n - 1] == '\n')
699           rp[n - 1] = '\0';
700
701       while (isspace (*rp))
702         ++rp;
703
704       /* If this is an empty line go on with the next one.  */
705       if (rp == endp)
706         continue;
707
708       word = rp;
709       while (*rp != '\0' && !isspace (*rp))
710         ++rp;
711
712       if (rp - word == sizeof ("alias") - 1
713           && memcmp (word, "alias", sizeof ("alias") - 1) == 0)
714         add_alias (rp);
715       else if (rp - word == sizeof ("module") - 1
716                && memcmp (word, "module", sizeof ("module") - 1) == 0)
717         add_module (rp, dir);
718       /* else */
719         /* Otherwise ignore the line.  */
720     }
721
722   free (line);
723
724   fclose (fp);
725
726   return 0;
727 }
728
729
730 static void
731 append_module (const void *nodep, VISIT value, int level)
732 {
733   struct module *mo;
734
735   if (value != leaf && value != postorder)
736     return;
737
738   mo = *(struct module **) nodep;
739
740   if (nmodule_list > 0
741       && strcmp (module_list[nmodule_list - 1]->fromname, mo->fromname) == 0)
742     {
743       /* Same name.  */
744       mo->next = module_list[nmodule_list - 1];
745       module_list[nmodule_list - 1] = mo;
746
747       return;
748     }
749
750   if (nmodule_list_max == nmodule_list)
751     {
752       nmodule_list_max += 50;
753       module_list = (struct module **) xrealloc (module_list,
754                                                  (nmodule_list_max
755                                                   * sizeof (struct module *)));
756     }
757
758   module_list[nmodule_list++] = mo;
759 }
760
761
762 static void
763 get_modules (void)
764 {
765   twalk (modules, append_module);
766 }
767
768
769 static void
770 add_builtins (void)
771 {
772   size_t cnt;
773
774   /* Add all aliases.  */
775   for (cnt = 0; cnt < nbuiltin_alias; ++cnt)
776     new_alias (builtin_alias[cnt].from,
777                strlen (builtin_alias[cnt].from) + 1,
778                builtin_alias[cnt].to,
779                strlen (builtin_alias[cnt].to) + 1);
780
781   /* add the builtin transformations.  */
782   for (cnt = 0; cnt < nbuiltin_trans; ++cnt)
783     new_module (builtin_trans[cnt].from,
784                 strlen (builtin_trans[cnt].from) + 1,
785                 builtin_trans[cnt].to,
786                 strlen (builtin_trans[cnt].to) + 1,
787                 "", builtin_trans[cnt].module,
788                 strlen (builtin_trans[cnt].module) + 1,
789                 builtin_trans[cnt].cost, 0);
790 }
791
792
793 static int
794 name_compare (const void *p1, const void *p2)
795 {
796   const struct name *n1 = (const struct name *) p1;
797   const struct name *n2 = (const struct name *) p2;
798
799   return strcmp (n1->name, n2->name);
800 }
801
802
803 static struct name *
804 new_name (const char *str, struct Strent *strent)
805 {
806   struct name *newp = (struct name *) xmalloc (sizeof (struct name));
807
808   newp->name = str;
809   newp->strent = strent;
810   newp->module_idx = -1;
811   newp->hashval = __hash_string (str);
812
813   ++nnames;
814
815   return newp;
816 }
817
818
819 static void
820 generate_name_list (void)
821 {
822   size_t i;
823
824   /* A name we always need.  */
825   tsearch (new_name ("INTERNAL", strtabadd (strtab, "INTERNAL",
826                                             sizeof ("INTERNAL"))),
827            &names, name_compare);
828
829   for (i = 0; i < nmodule_list; ++i)
830     {
831       struct module *runp;
832
833       if (strcmp (module_list[i]->fromname, "INTERNAL") != 0)
834         tsearch (new_name (module_list[i]->fromname,
835                            module_list[i]->fromname_strent),
836                  &names, name_compare);
837
838       for (runp = module_list[i]; runp != NULL; runp = runp->next)
839         if (strcmp (runp->toname, "INTERNAL") != 0)
840           tsearch (new_name (runp->toname, runp->toname_strent),
841                    &names, name_compare);
842     }
843 }
844
845
846 static int
847 name_to_module_idx (const char *name, int add)
848 {
849   struct name **res;
850   struct name fake_name = { .name = name };
851   int idx;
852
853   res = (struct name **) tfind (&fake_name, &names, name_compare);
854   if (res == NULL)
855     abort ();
856
857   idx = (*res)->module_idx;
858   if (idx == -1 && add)
859     /* No module index assigned yet.  */
860     idx = (*res)->module_idx = nname_info++;
861
862   return idx;
863 }
864
865
866 static void
867 generate_name_info (void)
868 {
869   size_t i;
870   int idx;
871
872   name_info = (struct name_info *) xcalloc (nmodule_list + 1,
873                                             sizeof (struct name_info));
874
875   /* First add a special entry for the INTERNAL name.  This must have
876      index zero.  */
877   idx = name_to_module_idx ("INTERNAL", 1);
878   name_info[0].canonical_name = "INTERNAL";
879   name_info[0].canonical_strent = strtabadd (strtab, "INTERNAL",
880                                              sizeof ("INTERNAL"));
881   assert (nname_info == 1);
882
883   for (i = 0; i < nmodule_list; ++i)
884     {
885       struct module *runp;
886
887       for (runp = module_list[i]; runp != NULL; runp = runp->next)
888         if (strcmp (runp->fromname, "INTERNAL") == 0)
889           {
890             idx = name_to_module_idx (runp->toname, 1);
891             name_info[idx].from_internal = runp;
892             assert (name_info[idx].canonical_name == NULL
893                     || strcmp (name_info[idx].canonical_name,
894                                runp->toname) == 0);
895             name_info[idx].canonical_name = runp->toname;
896             name_info[idx].canonical_strent = runp->toname_strent;
897           }
898         else if (strcmp (runp->toname, "INTERNAL") == 0)
899           {
900             idx = name_to_module_idx (runp->fromname, 1);
901             name_info[idx].to_internal = runp;
902             assert (name_info[idx].canonical_name == NULL
903                     || strcmp (name_info[idx].canonical_name,
904                                runp->fromname) == 0);
905             name_info[idx].canonical_name = runp->fromname;
906             name_info[idx].canonical_strent = runp->fromname_strent;
907           }
908         else
909           {
910             /* This is a transformation not to or from the INTERNAL
911                encoding.  */
912             int from_idx = name_to_module_idx (runp->fromname, 1);
913             int to_idx = name_to_module_idx (runp->toname, 1);
914             struct other_conv_list *newp;
915
916             newp = (struct other_conv_list *)
917               xmalloc (sizeof (struct other_conv_list));
918             newp->other_conv.module_idx = to_idx;
919             newp->other_conv.module = runp;
920             newp->other_conv.next = NULL; /* XXX Allow multiple module sequence */
921             newp->dest_idx = to_idx;
922             newp->next = name_info[from_idx].other_conv_list;
923             name_info[from_idx].other_conv_list = newp;
924             assert (name_info[from_idx].canonical_name == NULL
925                     || strcmp (name_info[from_idx].canonical_name,
926                                runp->fromname) == 0);
927             name_info[from_idx].canonical_name = runp->fromname;
928             name_info[from_idx].canonical_strent = runp->fromname_strent;
929
930             ++nextra_modules;
931           }
932     }
933
934   /* Now add the module index information for all the aliases.  */
935   for (i = 0; i < nalias_list; ++i)
936     {
937       struct name fake_name = { .name = alias_list[i]->toname };
938       struct name **tonamep;
939
940       tonamep = (struct name **) tfind (&fake_name, &names, name_compare);
941       if (tonamep != NULL)
942         {
943           struct name *newp = new_name (alias_list[i]->fromname,
944                                         alias_list[i]->froment);
945           newp->module_idx = (*tonamep)->module_idx;
946           tsearch (newp, &names, name_compare);
947         }
948     }
949 }
950
951
952 static int
953 is_prime (unsigned long int candidate)
954 {
955   /* No even number and none less than 10 will be passed here.  */
956   unsigned long int divn = 3;
957   unsigned long int sq = divn * divn;
958
959   while (sq < candidate && candidate % divn != 0)
960     {
961       ++divn;
962       sq += 4 * divn;
963       ++divn;
964     }
965
966   return candidate % divn != 0;
967 }
968
969
970 static uint32_t
971 next_prime (uint32_t seed)
972 {
973   /* Make it definitely odd.  */
974   seed |= 1;
975
976   while (!is_prime (seed))
977     seed += 2;
978
979   return seed;
980 }
981
982
983 /* Format of the output file.
984
985    Offset   Length       Description
986    0000     4            Magic header bytes
987    0004     2            Offset of string table (stoff)
988    0006     2            Offset of name hashing table (hoff)
989    0008     2            Hashing table size (hsize)
990    000A     2            Offset of module table (moff)
991    000C     2            Offset of other conversion module table (ooff)
992
993    stoff    ???          String table
994
995    hoff     8*hsize      Array of tuples
996                             string table offset
997                             module index
998
999    moff     ???          Array of tuples
1000                             canonical name offset
1001                             from-internal module dir name offset
1002                             from-internal module name off
1003                             to-internal module dir name offset
1004                             to-internal module name offset
1005                             offset into other conversion table
1006
1007    ooff     ???          One or more of
1008                             number of steps/modules
1009                             one or more of tuple
1010                               canonical name offset for output
1011                               module dir name offset
1012                               module name offset
1013                          (following last entry with step count 0)
1014 */
1015
1016 static struct hash_entry *hash_table;
1017 static size_t hash_size;
1018
1019 /* Function to insert the names.  */
1020 static void name_insert (const void *nodep, VISIT value, int level)
1021 {
1022   struct name *name;
1023   unsigned int idx;
1024   unsigned int hval2;
1025
1026   if (value != leaf && value != postorder)
1027     return;
1028
1029   name = *(struct name **) nodep;
1030   idx = name->hashval % hash_size;
1031   hval2 = 1 + name->hashval % (hash_size - 2);
1032
1033   while (hash_table[idx].string_offset != 0)
1034     if ((idx += hval2) >= hash_size)
1035       idx -= hash_size;
1036
1037   hash_table[idx].string_offset = strtaboffset (name->strent);
1038
1039   assert (name->module_idx != -1);
1040   hash_table[idx].module_idx = name->module_idx;
1041 }
1042
1043 static int
1044 write_output (void)
1045 {
1046   int fd;
1047   char *string_table;
1048   size_t string_table_size;
1049   struct gconvcache_header header;
1050   struct module_entry *module_table;
1051   char *extra_table;
1052   char *cur_extra_table;
1053   size_t n;
1054   int idx;
1055   struct iovec iov[6];
1056   static const gidx_t null_word;
1057   size_t total;
1058   char finalname[prefix_len + sizeof GCONV_MODULES_CACHE];
1059   char tmpfname[(output_file == NULL ? sizeof finalname : output_file_len + 1)
1060                 + strlen (".XXXXXX")];
1061
1062   /* Open the output file.  */
1063   if (output_file == NULL)
1064     {
1065       assert (GCONV_MODULES_CACHE[0] == '/');
1066       strcpy (stpcpy (mempcpy (tmpfname, prefix, prefix_len),
1067                       GCONV_MODULES_CACHE),
1068               ".XXXXXX");
1069       strcpy (mempcpy (finalname, prefix, prefix_len), GCONV_MODULES_CACHE);
1070     }
1071   else
1072     strcpy (mempcpy (tmpfname, output_file, output_file_len), ".XXXXXX");
1073   fd = mkstemp (tmpfname);
1074   if (fd == -1)
1075     return 1;
1076
1077   /* Create the string table.  */
1078   string_table = strtabfinalize (strtab, &string_table_size);
1079
1080   /* Create the hashing table.  We know how many strings we have.
1081      Creating a perfect hash table is not reasonable here.  Therefore
1082      we use open hashing and a table size which is the next prime 40%
1083      larger than the number of strings.  */
1084   hash_size = next_prime (nnames * 1.4);
1085   hash_table = (struct hash_entry *) xcalloc (hash_size,
1086                                               sizeof (struct hash_entry));
1087   /* Fill the hash table.  */
1088   twalk (names, name_insert);
1089
1090   /* Create the section for the module list.  */
1091   module_table = (struct module_entry *) xcalloc (sizeof (struct module_entry),
1092                                                   nname_info);
1093
1094   /* Allocate memory for the non-INTERNAL conversions.  The allocated
1095      memory can be more than is actually needed.  */
1096   extra_table = (char *) xcalloc (sizeof (struct extra_entry)
1097                                   + sizeof (gidx_t)
1098                                   + sizeof (struct extra_entry_module),
1099                                   nextra_modules);
1100   cur_extra_table = extra_table;
1101
1102   /* Fill in the module information.  */
1103   for (n = 0; n < nname_info; ++n)
1104     {
1105       module_table[n].canonname_offset =
1106         strtaboffset (name_info[n].canonical_strent);
1107
1108       if (name_info[n].from_internal == NULL)
1109         {
1110           module_table[n].fromdir_offset = 0;
1111           module_table[n].fromname_offset = 0;
1112         }
1113       else
1114         {
1115           module_table[n].fromdir_offset =
1116             strtaboffset (name_info[n].from_internal->directory_strent);
1117           module_table[n].fromname_offset =
1118             strtaboffset (name_info[n].from_internal->filename_strent);
1119         }
1120
1121       if (name_info[n].to_internal == NULL)
1122         {
1123           module_table[n].todir_offset = 0;
1124           module_table[n].toname_offset = 0;
1125         }
1126       else
1127         {
1128           module_table[n].todir_offset =
1129             strtaboffset (name_info[n].to_internal->directory_strent);
1130           module_table[n].toname_offset =
1131             strtaboffset (name_info[n].to_internal->filename_strent);
1132         }
1133
1134       if (name_info[n].other_conv_list != NULL)
1135         {
1136           struct other_conv_list *other = name_info[n].other_conv_list;
1137
1138           /* Store the reference.  We add 1 to distinguish the entry
1139              at offset zero from the case where no extra modules are
1140              available.  The file reader has to account for the
1141              offset.  */
1142           module_table[n].extra_offset = 1 + cur_extra_table - extra_table;
1143
1144           do
1145             {
1146               struct other_conv *runp;
1147               struct extra_entry *extra;
1148
1149               /* Allocate new entry.  */
1150               extra = (struct extra_entry *) cur_extra_table;
1151               cur_extra_table += sizeof (struct extra_entry);
1152               extra->module_cnt = 0;
1153
1154               runp = &other->other_conv;
1155               do
1156                 {
1157                   cur_extra_table += sizeof (struct extra_entry_module);
1158                   extra->module[extra->module_cnt].outname_offset =
1159                     runp->next == NULL
1160                     ? other->dest_idx : runp->next->module_idx;
1161                   extra->module[extra->module_cnt].dir_offset =
1162                     strtaboffset (runp->module->directory_strent);
1163                   extra->module[extra->module_cnt].name_offset =
1164                     strtaboffset (runp->module->filename_strent);
1165                   ++extra->module_cnt;
1166
1167                   runp = runp->next;
1168                 }
1169               while (runp != NULL);
1170
1171               other = other->next;
1172             }
1173           while (other != NULL);
1174
1175           /* Final module_cnt is zero.  */
1176           *((gidx_t *) cur_extra_table) = 0;
1177           cur_extra_table += sizeof (gidx_t);
1178         }
1179     }
1180
1181   /* Clear padding.  */
1182   memset (&header, 0, sizeof (struct gconvcache_header));
1183
1184   header.magic = GCONVCACHE_MAGIC;
1185
1186   iov[0].iov_base = &header;
1187   iov[0].iov_len = sizeof (struct gconvcache_header);
1188   total = iov[0].iov_len;
1189
1190   header.string_offset = total;
1191   iov[1].iov_base = string_table;
1192   iov[1].iov_len = string_table_size;
1193   total += iov[1].iov_len;
1194
1195   idx = 2;
1196   if ((string_table_size & (sizeof (gidx_t) - 1)) != 0)
1197     {
1198       iov[2].iov_base = (void *) &null_word;
1199       iov[2].iov_len = (sizeof (gidx_t)
1200                         - (string_table_size & (sizeof (gidx_t) - 1)));
1201       total += iov[2].iov_len;
1202       ++idx;
1203     }
1204
1205   header.hash_offset = total;
1206   header.hash_size = hash_size;
1207   iov[idx].iov_base = hash_table;
1208   iov[idx].iov_len = hash_size * sizeof (struct hash_entry);
1209   total += iov[idx].iov_len;
1210   ++idx;
1211
1212   header.module_offset = total;
1213   iov[idx].iov_base = module_table;
1214   iov[idx].iov_len = nname_info * sizeof (struct module_entry);
1215   total += iov[idx].iov_len;
1216   ++idx;
1217
1218   assert ((size_t) (cur_extra_table - extra_table)
1219           <= ((sizeof (struct extra_entry) + sizeof (gidx_t)
1220                + sizeof (struct extra_entry_module))
1221               * nextra_modules));
1222   header.otherconv_offset = total;
1223   iov[idx].iov_base = extra_table;
1224   iov[idx].iov_len = cur_extra_table - extra_table;
1225   total += iov[idx].iov_len;
1226   ++idx;
1227
1228   if ((size_t) TEMP_FAILURE_RETRY (writev (fd, iov, idx)) != total
1229       /* The file was created with mode 0600.  Make it world-readable.  */
1230       || fchmod (fd, 0644) != 0
1231       /* Rename the file, possibly replacing an old one.  */
1232       || rename (tmpfname, output_file ?: finalname) != 0)
1233     {
1234       int save_errno = errno;
1235       close (fd);
1236       unlink (tmpfname);
1237       error (EXIT_FAILURE, save_errno,
1238              gettext ("cannot generate output file"));
1239     }
1240
1241   close (fd);
1242
1243   return 0;
1244 }