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