iconv/iconvconfig.c

   1 /* Generate fastloading iconv module configuration files.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004 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    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library 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 GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #include <argp.h>
  22 #include <assert.h>
  23 #include <error.h>
  24 #include <errno.h>
  25 #include <fcntl.h>
  26 #include <libintl.h>
  27 #include <locale.h>
  28 #include <mcheck.h>
  29 #include <search.h>
  30 #include <stdint.h>
  31 #include <stdbool.h>
  32 #include <stdio.h>
  33 #include <stdio_ext.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include <unistd.h>
  37 #include <sys/cdefs.h>
  38 #include <sys/uio.h>
  39
  40 #include "iconvconfig.h"
  41
  42 /* Get libc version number.  */
  43 #include "../version.h"
  44
  45 #define PACKAGE _libc_intl_domainname
  46
  47
  48 /* The hashing function we use.  */
  49 #include "../intl/hash-string.h"
  50
  51
  52 /* Types used.  */
  53 struct module
  54 {
  55   char *fromname;
  56   struct Strent *fromname_strent;
  57   char *filename;
  58   struct Strent *filename_strent;
  59   const char *directory;
  60   struct Strent *directory_strent;
  61   struct module *next;
  62   int cost;
  63   struct Strent *toname_strent;
  64   char toname[0];
  65 };
  66
  67 struct alias
  68 {
  69   char *fromname;
  70   struct Strent *froment;
  71   struct module *module;
  72   struct Strent *toent;
  73   char toname[0];
  74 };
  75
  76 struct name
  77 {
  78   const char *name;
  79   struct Strent *strent;
  80   int module_idx;
  81   uint32_t hashval;
  82 };
  83
  84 struct name_info
  85 {
  86   const char *canonical_name;
  87   struct Strent *canonical_strent;
  88
  89   struct module *from_internal;
  90   struct module *to_internal;
  91
  92   struct other_conv_list
  93   {
  94     int dest_idx;
  95     struct other_conv
  96     {
  97       gidx_t module_idx;
  98       struct module *module;
  99       struct other_conv *next;
 100     } other_conv;
 101     struct other_conv_list *next;
 102   } *other_conv_list;
 103 };
 104
 105
 106 /* Name and version of program.  */
 107 static void print_version (FILE *stream, struct argp_state *state);
 108 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
 109
 110 /* Short description of program.  */
 111 static const char doc[] = N_("\
 112 Create fastloading iconv module configuration file.");
 113
 114 /* Strings for arguments in help texts.  */
 115 static const char args_doc[] = N_("[DIR...]");
 116
 117 /* Prototype for option handler.  */
 118 static error_t parse_opt (int key, char *arg, struct argp_state *state);
 119
 120 /* Function to print some extra text in the help message.  */
 121 static char *more_help (int key, const char *text, void *input);
 122
 123 /* Definitions of arguments for argp functions.  */
 124 #define OPT_PREFIX 300
 125 #define OPT_NOSTDLIB 301
 126 static const struct argp_option options[] =
 127 {
 128   { "prefix", OPT_PREFIX, "PATH", 0, N_("Prefix used for all file accesses") },
 129   { "output", 'o', "FILE", 0, N_("\
 130 Put output in FILE instead of installed location\
 131  (--prefix does not apply to FILE)") },
 132   { "nostdlib", OPT_NOSTDLIB, NULL, 0,
 133     N_("Do not search standard directories, only those on the command line") },
 134   { NULL, 0, NULL, 0, NULL }
 135 };
 136
 137 /* Data structure to communicate with argp functions.  */
 138 static struct argp argp =
 139 {
 140   options, parse_opt, args_doc, doc, NULL, more_help
 141 };
 142
 143
 144 /* The function doing the actual work.  */
 145 static int handle_dir (const char *dir);
 146
 147 /* Add all known builtin conversions and aliases.  */
 148 static void add_builtins (void);
 149
 150 /* Create list of all aliases without circular aliases.  */
 151 static void get_aliases (void);
 152
 153 /* Create list of all modules.  */
 154 static void get_modules (void);
 155
 156 /* Get list of all the names and thereby indexing them.  */
 157 static void generate_name_list (void);
 158
 159 /* Collect information about all the names.  */
 160 static void generate_name_info (void);
 161
 162 /* Write the output file.  */
 163 static int write_output (void);
 164
 165
 166 /* Prefix to be used for all file accesses.  */
 167 static const char *prefix = "";
 168 /* Its length.  */
 169 static size_t prefix_len;
 170
 171 /* Directory to place output file in.  */
 172 static const char *output_file;
 173 /* Its length.  */
 174 static size_t output_file_len;
 175
 176 /* If true, omit the GCONV_PATH directories and require some arguments.  */
 177 static bool nostdlib;
 178
 179 /* Search tree of the modules we know.  */
 180 static void *modules;
 181
 182 /* Search tree of the aliases we know.  */
 183 static void *aliases;
 184
 185 /* Search tree for name to index mapping.  */
 186 static void *names;
 187
 188 /* Number of names we know about.  */
 189 static int nnames;
 190
 191 /* List of all aliases.  */
 192 static struct alias **alias_list;
 193 static size_t nalias_list;
 194 static size_t nalias_list_max;
 195
 196 /* List of all modules.  */
 197 static struct module **module_list;
 198 static size_t nmodule_list;
 199 static size_t nmodule_list_max;
 200
 201 /* Names and information about them.  */
 202 static struct name_info *name_info;
 203 static size_t nname_info;
 204
 205 /* Number of translations not from or to INTERNAL.  */
 206 static size_t nextra_modules;
 207
 208
 209 /* Names and aliases for the builtin transformations.  */
 210 static struct
 211 {
 212   const char *from;
 213   const char *to;
 214 } builtin_alias[] =
 215   {
 216 #define BUILTIN_ALIAS(alias, real) \
 217     { .from = alias, .to = real },
 218 #define BUILTIN_TRANSFORMATION(From, To, Cost, Name, Fct, BtowcFct, \
 219                                MinF, MaxF, MinT, MaxT)
 220 #include <gconv_builtin.h>
 221   };
 222 #undef BUILTIN_ALIAS
 223 #undef BUILTIN_TRANSFORMATION
 224 #define nbuiltin_alias (sizeof (builtin_alias) / sizeof (builtin_alias[0]))
 225
 226 static struct
 227 {
 228   const char *from;
 229   const char *to;
 230   const char *module;
 231   int cost;
 232 } builtin_trans[] =
 233   {
 234 #define BUILTIN_ALIAS(alias, real)
 235 #define BUILTIN_TRANSFORMATION(From, To, Cost, Name, Fct, BtowcFct, \
 236                                MinF, MaxF, MinT, MaxT) \
 237     { .from = From, .to = To, .module = Name, .cost = Cost },
 238 #include <gconv_builtin.h>
 239   };
 240 #undef BUILTIN_ALIAS
 241 #undef BUILTIN_TRANSFORMATION
 242 #define nbuiltin_trans (sizeof (builtin_trans) / sizeof (builtin_trans[0]))
 243
 244
 245 /* Filename extension for the modules.  */
 246 #ifndef MODULE_EXT
 247 # define MODULE_EXT ".so"
 248 #endif
 249 static const char gconv_module_ext[] = MODULE_EXT;
 250
 251
 252 extern void *xmalloc (size_t n) __attribute_malloc__;
 253 extern void *xcalloc (size_t n, size_t m) __attribute_malloc__;
 254 extern void *xrealloc (void *p, size_t n);
 255
 256
 257 /* C string table handling.  */
 258 struct Strtab;
 259 struct Strent;
 260
 261 /* Create new C string table object in memory.  */
 262 extern struct Strtab *strtabinit (void);
 263
 264 /* Free resources allocated for C string table ST.  */
 265 extern void strtabfree (struct Strtab *st);
 266
 267 /* Add string STR (length LEN is != 0) to C string table ST.  */
 268 extern struct Strent *strtabadd (struct Strtab *st, const char *str,
 269                                  size_t len);
 270
 271 /* Finalize string table ST and store size in *SIZE and return a pointer.  */
 272 extern void *strtabfinalize (struct Strtab *st, size_t *size);
 273
 274 /* Get offset in string table for string associated with SE.  */
 275 extern size_t strtaboffset (struct Strent *se);
 276
 277 /* String table we construct.  */
 278 static struct Strtab *strtab;
 279
 280
 281
 282 int
 283 main (int argc, char *argv[])
 284 {
 285   int remaining;
 286   int status = 0;
 287
 288   /* Enable memory use testing.  */
 289   /* mcheck_pedantic (NULL); */
 290   mtrace ();
 291
 292   /* Set locale via LC_ALL.  */
 293   setlocale (LC_ALL, "");
 294
 295   /* Set the text message domain.  */
 296   textdomain (_libc_intl_domainname);
 297
 298   /* Parse and process arguments.  */
 299   argp_parse (&argp, argc, argv, 0, &remaining, NULL);
 300
 301   if (nostdlib && remaining == argc)
 302     error (2, 0, _("Directory arguments required when using --nostdlib"));
 303
 304   /* Initialize the string table.  */
 305   strtab = strtabinit ();
 306
 307   /* Handle all directories mentioned.  */
 308   while (remaining < argc)
 309     status |= handle_dir (argv[remaining++]);
 310
 311   if (! nostdlib)
 312     {
 313       /* In any case also handle the standard directory.  */
 314       char *path = strdupa (GCONV_PATH), *tp = strsep (&path, ":");
 315       while (tp != NULL)
 316         {
 317           status |= handle_dir (tp);
 318
 319           tp = strsep (&path, ":");
 320         }
 321     }
 322
 323   /* Add the builtin transformations and aliases without overwriting
 324      anything.  */
 325   add_builtins ();
 326
 327   /* Store aliases in an array.  */
 328   get_aliases ();
 329
 330   /* Get list of all modules.  */
 331   get_modules ();
 332
 333   /* Generate list of all the names we know to handle in some way.  */
 334   generate_name_list ();
 335
 336   /* Now we know all the names we will handle, collect information
 337      about them.  */
 338   generate_name_info ();
 339
 340   /* Write the output file, but only if we haven't seen any error.  */
 341   if (status == 0)
 342     status = write_output ();
 343   else
 344     error (1, 0, _("no output file produced because warning were issued"));
 345
 346   return status;
 347 }
 348
 349
 350 /* Handle program arguments.  */
 351 static error_t
 352 parse_opt (int key, char *arg, struct argp_state *state)
 353 {
 354   switch (key)
 355     {
 356     case OPT_PREFIX:
 357       prefix = arg;
 358       prefix_len = strlen (prefix);
 359       break;
 360     case 'o':
 361       output_file = arg;
 362       output_file_len = strlen (output_file);
 363       break;
 364     case OPT_NOSTDLIB:
 365       nostdlib = true;
 366       break;
 367     default:
 368       return ARGP_ERR_UNKNOWN;
 369     }
 370   return 0;
 371 }
 372
 373
 374 static char *
 375 more_help (int key, const char *text, void *input)
 376 {
 377   switch (key)
 378     {
 379     case ARGP_KEY_HELP_EXTRA:
 380       /* We print some extra information.  */
 381       return strdup (gettext ("\
 382 For bug reporting instructions, please see:\n\
 383 <http://www.gnu.org/software/libc/bugs.html>.\n"));
 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 (GNU %s) %s\n", PACKAGE, 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 "), "2004");
 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     4            Offset of string table (stoff)
 989    0008     4            Offset of name hashing table (hoff)
 990    000C     4            Hashing table size (hsize)
 991    0010     4            Offset of module table (moff)
 992    0014     4            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   header.magic = GCONVCACHE_MAGIC;
1183
1184   iov[0].iov_base = &header;
1185   iov[0].iov_len = sizeof (struct gconvcache_header);
1186   total = iov[0].iov_len;
1187
1188   header.string_offset = total;
1189   iov[1].iov_base = string_table;
1190   iov[1].iov_len = string_table_size;
1191   total += iov[1].iov_len;
1192
1193   idx = 2;
1194   if ((string_table_size & (sizeof (gidx_t) - 1)) != 0)
1195     {
1196       iov[2].iov_base = (void *) &null_word;
1197       iov[2].iov_len = (sizeof (gidx_t)
1198                         - (string_table_size & (sizeof (gidx_t) - 1)));
1199       total += iov[2].iov_len;
1200       ++idx;
1201     }
1202
1203   header.hash_offset = total;
1204   header.hash_size = hash_size;
1205   iov[idx].iov_base = hash_table;
1206   iov[idx].iov_len = hash_size * sizeof (struct hash_entry);
1207   total += iov[idx].iov_len;
1208   ++idx;
1209
1210   header.module_offset = total;
1211   iov[idx].iov_base = module_table;
1212   iov[idx].iov_len = nname_info * sizeof (struct module_entry);
1213   total += iov[idx].iov_len;
1214   ++idx;
1215
1216   assert ((size_t) (cur_extra_table - extra_table)
1217           <= ((sizeof (struct extra_entry) + sizeof (gidx_t)
1218                + sizeof (struct extra_entry_module))
1219               * nextra_modules));
1220   header.otherconv_offset = total;
1221   iov[idx].iov_base = extra_table;
1222   iov[idx].iov_len = cur_extra_table - extra_table;
1223   total += iov[idx].iov_len;
1224   ++idx;
1225
1226   if ((size_t) TEMP_FAILURE_RETRY (writev (fd, iov, idx)) != total
1227       /* The file was created with mode 0600.  Make it world-readable.  */
1228       || fchmod (fd, 0644) != 0
1229       /* Rename the file, possibly replacing an old one.  */
1230       || rename (tmpfname, output_file ?: finalname) != 0)
1231     {
1232       int save_errno = errno;
1233       close (fd);
1234       unlink (tmpfname);
1235       error (EXIT_FAILURE, save_errno,
1236              gettext ("cannot generate output file"));
1237     }
1238
1239   close (fd);
1240
1241   return 0;
1242 }