iconv/iconvconfig.c

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