iconv/iconvconfig.c

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