iconv/iconvconfig.c

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