iconv/gconv_db.c

   1 /* Provide access to the collection of available transformation modules.
   2    Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1997.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Library General Public License as
   8    published by the Free Software Foundation; either version 2 of the
   9    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    Library General Public License for more details.
  15
  16    You should have received a copy of the GNU Library General Public
  17    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  18    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 #include <limits.h>
  22 #include <search.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <sys/param.h>
  26 #include <bits/libc-lock.h>
  27
  28 #include <dlfcn.h>
  29 #include <gconv_int.h>
  30
  31
  32 /* Simple data structure for alias mapping.  We have two names, `from'
  33    and `to'.  */
  34 void *__gconv_alias_db;
  35
  36 /* Array with available modules.  */
  37 struct gconv_module *__gconv_modules_db;
  38
  39 /* We modify global data.   */
  40 __libc_lock_define_initialized (static, lock)
  41
  42
  43 /* Function for searching alias.  */
  44 int
  45 __gconv_alias_compare (const void *p1, const void *p2)
  46 {
  47   struct gconv_alias *s1 = (struct gconv_alias *) p1;
  48   struct gconv_alias *s2 = (struct gconv_alias *) p2;
  49   return strcmp (s1->fromname, s2->fromname);
  50 }
  51
  52
  53 /* To search for a derivation we create a list of intermediate steps.
  54    Each element contains a pointer to the element which precedes it
  55    in the derivation order.  */
  56 struct derivation_step
  57 {
  58   const char *result_set;
  59   size_t result_set_len;
  60   int cost_lo;
  61   int cost_hi;
  62   struct gconv_module *code;
  63   struct derivation_step *last;
  64   struct derivation_step *next;
  65 };
  66
  67 #define NEW_STEP(result, hi, lo, module, last_mod) \
  68   ({ struct derivation_step *newp = alloca (sizeof (struct derivation_step)); \
  69      newp->result_set = result;                                               \
  70      newp->result_set_len = strlen (result);                                  \
  71      newp->cost_hi = hi;                                                      \
  72      newp->cost_lo = lo;                                                      \
  73      newp->code = module;                                                     \
  74      newp->last = last_mod;                                                   \
  75      newp->next = NULL;                                                       \
  76      newp; })
  77
  78
  79 /* If a specific transformation is used more than once we should not need
  80    to start looking for it again.  Instead cache each successful result.  */
  81 struct known_derivation
  82 {
  83   const char *from;
  84   const char *to;
  85   struct __gconv_step *steps;
  86   size_t nsteps;
  87 };
  88
  89 /* Compare function for database of found derivations.  */
  90 static int
  91 derivation_compare (const void *p1, const void *p2)
  92 {
  93   struct known_derivation *s1 = (struct known_derivation *) p1;
  94   struct known_derivation *s2 = (struct known_derivation *) p2;
  95   int result;
  96
  97   result = strcmp (s1->from, s2->from);
  98   if (result == 0)
  99     result = strcmp (s1->to, s2->to);
 100   return result;
 101 }
 102
 103 /* The search tree for known derivations.  */
 104 static void *known_derivations;
 105
 106 /* Look up whether given transformation was already requested before.  */
 107 static int
 108 internal_function
 109 derivation_lookup (const char *fromset, const char *toset,
 110                    struct __gconv_step **handle, size_t *nsteps)
 111 {
 112   struct known_derivation key = { fromset, toset, NULL, 0 };
 113   struct known_derivation **result;
 114
 115   result = __tfind (&key, &known_derivations, derivation_compare);
 116
 117   if (result == NULL)
 118     return __GCONV_NOCONV;
 119
 120   *handle = (*result)->steps;
 121   *nsteps = (*result)->nsteps;
 122
 123   /* Please note that we return GCONV_OK even if the last search for
 124      this transformation was unsuccessful.  */
 125   return __GCONV_OK;
 126 }
 127
 128 /* Add new derivation to list of known ones.  */
 129 static void
 130 internal_function
 131 add_derivation (const char *fromset, const char *toset,
 132                 struct __gconv_step *handle, size_t nsteps)
 133 {
 134   struct known_derivation *new_deriv;
 135   size_t fromset_len = strlen (fromset) + 1;
 136   size_t toset_len = strlen (toset) + 1;
 137
 138   new_deriv = (struct known_derivation *)
 139     malloc (sizeof (struct known_derivation) + fromset_len + toset_len);
 140   if (new_deriv != NULL)
 141     {
 142       new_deriv->from = (char *) (new_deriv + 1);
 143       new_deriv->to = memcpy (__mempcpy (new_deriv + 1, fromset, fromset_len),
 144                               toset, toset_len);
 145
 146       new_deriv->steps = handle;
 147       new_deriv->nsteps = nsteps;
 148
 149       if (__tsearch (new_deriv, &known_derivations, derivation_compare)
 150           == NULL)
 151         /* There is some kind of memory allocation problem.  */
 152         free (new_deriv);
 153     }
 154   /* Please note that we don't complain if the allocation failed.  This
 155      is not tragically but in case we use the memory debugging facilities
 156      not all memory will be freed.  */
 157 }
 158
 159 static void
 160 free_derivation (void *p)
 161 {
 162   struct known_derivation *deriv = (struct known_derivation *) p;
 163   size_t cnt;
 164
 165   for (cnt = 0; cnt < deriv->nsteps; ++cnt)
 166     if (deriv->steps[cnt].__end_fct)
 167       DL_CALL_FCT (deriv->steps[cnt].__end_fct, (&deriv->steps[cnt]));
 168
 169   /* Free the name strings.  */
 170   free ((char *) deriv->steps[0].__from_name);
 171   free ((char *) deriv->steps[deriv->nsteps - 1].__to_name);
 172
 173   free ((struct __gconv_step *) deriv->steps);
 174   free (deriv);
 175 }
 176
 177
 178 static int
 179 internal_function
 180 gen_steps (struct derivation_step *best, const char *toset,
 181            const char *fromset, struct __gconv_step **handle, size_t *nsteps)
 182 {
 183   size_t step_cnt = 0;
 184   struct __gconv_step *result;
 185   struct derivation_step *current;
 186   int status = __GCONV_NOMEM;
 187
 188   /* First determine number of steps.  */
 189   for (current = best; current->last != NULL; current = current->last)
 190     ++step_cnt;
 191
 192   result = (struct __gconv_step *) malloc (sizeof (struct __gconv_step)
 193                                            * step_cnt);
 194   if (result != NULL)
 195     {
 196       int failed = 0;
 197
 198       status = __GCONV_OK;
 199       *nsteps = step_cnt;
 200       current = best;
 201       while (step_cnt-- > 0)
 202         {
 203           result[step_cnt].__from_name = (step_cnt == 0
 204                                           ? __strdup (fromset)
 205                                           : current->last->result_set);
 206           result[step_cnt].__to_name = (step_cnt + 1 == *nsteps
 207                                         ? __strdup (current->result_set)
 208                                         : result[step_cnt + 1].__from_name);
 209
 210 #ifndef STATIC_GCONV
 211           if (current->code->module_name[0] == '/')
 212             {
 213               /* Load the module, return handle for it.  */
 214               struct __gconv_loaded_object *shlib_handle =
 215                 __gconv_find_shlib (current->code->module_name);
 216
 217               if (shlib_handle == NULL)
 218                 {
 219                   failed = 1;
 220                   break;
 221                 }
 222
 223               result[step_cnt].__shlib_handle = shlib_handle;
 224               result[step_cnt].__modname = shlib_handle->name;
 225               result[step_cnt].__counter = 1;
 226               result[step_cnt].__fct = shlib_handle->fct;
 227               result[step_cnt].__init_fct = shlib_handle->init_fct;
 228               result[step_cnt].__end_fct = shlib_handle->end_fct;
 229             }
 230           else
 231 #endif
 232             /* It's a builtin transformation.  */
 233             __gconv_get_builtin_trans (current->code->module_name,
 234                                        &result[step_cnt]);
 235
 236           /* Call the init function.  */
 237           if (result[step_cnt].__init_fct != NULL)
 238              {
 239                status = DL_CALL_FCT (result[step_cnt].__init_fct,
 240                                       (&result[step_cnt]));
 241
 242                if (__builtin_expect (status, __GCONV_OK) != __GCONV_OK)
 243                  {
 244                    failed = 1;
 245                    /* Make sure we unload this modules.  */
 246                    --step_cnt;
 247                    break;
 248                  }
 249              }
 250
 251           current = current->last;
 252         }
 253
 254       if (__builtin_expect (failed, 0) != 0)
 255         {
 256           /* Something went wrong while initializing the modules.  */
 257           while (++step_cnt < *nsteps)
 258             {
 259               if (result[step_cnt].__end_fct != NULL)
 260                 DL_CALL_FCT (result[step_cnt].__end_fct, (&result[step_cnt]));
 261 #ifndef STATIC_GCONV
 262               __gconv_release_shlib (result[step_cnt].__shlib_handle);
 263 #endif
 264             }
 265           free (result);
 266           *nsteps = 0;
 267           *handle = NULL;
 268           if (status == __GCONV_OK)
 269             status = __GCONV_NOCONV;
 270         }
 271       else
 272         *handle = result;
 273     }
 274   else
 275     {
 276       *nsteps = 0;
 277       *handle = NULL;
 278     }
 279
 280   return status;
 281 }
 282
 283
 284 #ifndef STATIC_GCONV
 285 static int
 286 internal_function
 287 increment_counter (struct __gconv_step *steps, size_t nsteps)
 288 {
 289   /* Increment the user counter.  */
 290   size_t cnt = nsteps;
 291   int result = __GCONV_OK;
 292
 293   while (cnt-- > 0)
 294     if (steps[cnt].__counter++ == 0)
 295       {
 296         steps[cnt].__shlib_handle =
 297           __gconv_find_shlib (steps[cnt].__modname);
 298         if (steps[cnt].__shlib_handle == NULL)
 299           {
 300             /* Oops, this is the second time we use this module (after
 301                unloading) and this time loading failed!?  */
 302             while (++cnt < nsteps)
 303               __gconv_release_shlib (steps[cnt].__shlib_handle);
 304             result = __GCONV_NOCONV;
 305             break;
 306           }
 307       }
 308   return result;
 309 }
 310 #endif
 311
 312
 313 /* The main function: find a possible derivation from the `fromset' (either
 314    the given name or the alias) to the `toset' (again with alias).  */
 315 static int
 316 internal_function
 317 find_derivation (const char *toset, const char *toset_expand,
 318                  const char *fromset, const char *fromset_expand,
 319                  struct __gconv_step **handle, size_t *nsteps)
 320 {
 321   struct derivation_step *first, *current, **lastp, *solution = NULL;
 322   int best_cost_hi = INT_MAX;
 323   int best_cost_lo = INT_MAX;
 324   int result;
 325
 326   /* There is a small chance that this derivation is meanwhile found.  This
 327      can happen if in `find_derivation' we look for this derivation, didn't
 328      find it but at the same time another thread looked for this derivation. */
 329   result = derivation_lookup (fromset_expand ?: fromset, toset_expand ?: toset,
 330                               handle, nsteps);
 331   if (result == __GCONV_OK)
 332     {
 333 #ifndef STATIC_GCONV
 334       result = increment_counter (*handle, *nsteps);
 335 #endif
 336       return result;
 337     }
 338
 339   /* For now we use a simple algorithm with quadratic runtime behaviour.
 340      The task is to match the `toset' with any of the available rules,
 341      starting from FROMSET.  */
 342   if (fromset_expand != NULL)
 343     {
 344       first = NEW_STEP (fromset_expand, 0, 0, NULL, NULL);
 345       first->next = NEW_STEP (fromset, 0, 0, NULL, NULL);
 346       lastp = &first->next->next;
 347     }
 348   else
 349     {
 350       first = NEW_STEP (fromset, 0, 0, NULL, NULL);
 351       lastp = &first->next;
 352     }
 353
 354   for (current = first; current != NULL; current = current->next)
 355     {
 356       /* Now match all the available module specifications against the
 357          current charset name.  If any of them matches check whether
 358          we already have a derivation for this charset.  If yes, use the
 359          one with the lower costs.  Otherwise add the new charset at the
 360          end.
 361
 362          The module database is organized in a tree form which allows
 363          searching for prefixes.  So we search for the first entry with a
 364          matching prefix and any other matching entry can be found from
 365          this place.  */
 366       struct gconv_module *node = __gconv_modules_db;
 367
 368       /* Maybe it is not necessary anymore to look for a solution for
 369          this entry since the cost is already as high (or heigher) as
 370          the cost for the best solution so far.  */
 371       if (current->cost_hi > best_cost_hi
 372           || (current->cost_hi == best_cost_hi
 373               && current->cost_lo >= best_cost_lo))
 374         continue;
 375
 376       while (node != NULL)
 377         {
 378           int cmpres = strcmp (current->result_set, node->from_string);
 379           if (cmpres == 0)
 380             {
 381               /* Walk through the list of modules with this prefix and
 382                  try to match the name.  */
 383               struct gconv_module *runp;
 384
 385               /* Check all the modules with this prefix.  */
 386               runp = node;
 387               do
 388                 {
 389                   const char *result_set = (strcmp (runp->to_string, "-") == 0
 390                                             ? (toset_expand ?: toset)
 391                                             : runp->to_string);
 392                   int cost_hi = runp->cost_hi + current->cost_hi;
 393                   int cost_lo = runp->cost_lo + current->cost_lo;
 394                   struct derivation_step *step;
 395
 396                   /* We managed to find a derivation.  First see whether
 397                      this is what we are looking for.  */
 398                   if (strcmp (result_set, toset) == 0
 399                       || (toset_expand != NULL
 400                           && strcmp (result_set, toset_expand) == 0))
 401                     {
 402                       if (solution == NULL || cost_hi < best_cost_hi
 403                           || (cost_hi == best_cost_hi
 404                               && cost_lo < best_cost_lo))
 405                         {
 406                           best_cost_hi = cost_hi;
 407                           best_cost_lo = cost_lo;
 408                         }
 409
 410                       /* Append this solution to list.  */
 411                       if (solution == NULL)
 412                         solution = NEW_STEP (result_set, 0, 0, runp, current);
 413                       else
 414                         {
 415                           while (solution->next != NULL)
 416                             solution = solution->next;
 417
 418                           solution->next = NEW_STEP (result_set, 0, 0,
 419                                                      runp, current);
 420                         }
 421                     }
 422                   else if (cost_hi < best_cost_hi
 423                            || (cost_hi == best_cost_hi
 424                                && cost_lo < best_cost_lo))
 425                     {
 426                       /* Append at the end if there is no entry with
 427                          this name.  */
 428                       for (step = first; step != NULL; step = step->next)
 429                         if (strcmp (result_set, step->result_set) == 0)
 430                           break;
 431
 432                       if (step == NULL)
 433                         {
 434                           *lastp = NEW_STEP (result_set,
 435                                              cost_hi, cost_lo,
 436                                              runp, current);
 437                           lastp = &(*lastp)->next;
 438                         }
 439                       else if (step->cost_hi > cost_hi
 440                                || (step->cost_hi == cost_hi
 441                                    && step->cost_lo > cost_lo))
 442                         {
 443                           step->code = runp;
 444                           step->last = current;
 445
 446                           /* Update the cost for all steps.  */
 447                           for (step = first; step != NULL;
 448                                step = step->next)
 449                             {
 450                               struct derivation_step *back;
 451
 452                               if (step->code == NULL)
 453                                 /* This is one of the entries we started
 454                                    from.  */
 455                                 continue;
 456
 457                               step->cost_hi = step->code->cost_hi;
 458                               step->cost_lo = step->code->cost_lo;
 459
 460                               for (back = step->last; back->code != NULL;
 461                                    back = back->last)
 462                                 {
 463                                   step->cost_hi += back->code->cost_hi;
 464                                   step->cost_lo += back->code->cost_lo;
 465                                 }
 466                             }
 467
 468                           for (step = solution; step != NULL;
 469                                step = step->next)
 470                             {
 471                               step->cost_hi = (step->code->cost_hi
 472                                                + step->last->cost_hi);
 473                               step->cost_lo = (step->code->cost_lo
 474                                                + step->last->cost_lo);
 475
 476                               if (step->cost_hi < best_cost_hi
 477                                   || (step->cost_hi == best_cost_hi
 478                                       && step->cost_lo < best_cost_lo))
 479                                 {
 480                                   solution = step;
 481                                   best_cost_hi = step->cost_hi;
 482                                   best_cost_lo = step->cost_lo;
 483                                 }
 484                             }
 485                         }
 486                     }
 487
 488                   runp = runp->same;
 489                 }
 490               while (runp != NULL);
 491
 492               break;
 493             }
 494           else if (cmpres < 0)
 495             node = node->left;
 496           else
 497             node = node->right;
 498         }
 499     }
 500
 501   if (solution != NULL)
 502     /* We really found a way to do the transformation.  Now build a data
 503        structure describing the transformation steps.*/
 504     result = gen_steps (solution, toset_expand ?: toset,
 505                         fromset_expand ?: fromset, handle, nsteps);
 506   else
 507     {
 508       /* We haven't found a transformation.  Clear the result values.  */
 509       *handle = NULL;
 510       *nsteps = 0;
 511     }
 512
 513   /* Add result in any case to list of known derivations.  */
 514   add_derivation (fromset_expand ?: fromset, toset_expand ?: toset,
 515                   *handle, *nsteps);
 516
 517   return result;
 518 }
 519
 520
 521 int
 522 internal_function
 523 __gconv_find_transform (const char *toset, const char *fromset,
 524                         struct __gconv_step **handle, size_t *nsteps,
 525                         int flags)
 526 {
 527   __libc_once_define (static, once);
 528   const char *fromset_expand = NULL;
 529   const char *toset_expand = NULL;
 530   int result;
 531
 532   /* Ensure that the configuration data is read.  */
 533   __libc_once (once, __gconv_read_conf);
 534
 535   /* Acquire the lock.  */
 536   __libc_lock_lock (lock);
 537
 538   /* If we don't have a module database return with an error.  */
 539   if (__gconv_modules_db == NULL)
 540     {
 541       __libc_lock_unlock (lock);
 542       return __GCONV_NOCONV;
 543     }
 544
 545   /* See whether the names are aliases.  */
 546   if (__gconv_alias_db != NULL)
 547     {
 548       struct gconv_alias key;
 549       struct gconv_alias **found;
 550
 551       key.fromname = fromset;
 552       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
 553       fromset_expand = found != NULL ? (*found)->toname : NULL;
 554
 555       key.fromname = toset;
 556       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
 557       toset_expand = found != NULL ? (*found)->toname : NULL;
 558     }
 559
 560   if (__builtin_expect (flags & GCONV_AVOID_NOCONV, 0)
 561       /* We are not supposed to create a pseudo transformation (means
 562          copying) when the input and output character set are the same.  */
 563       && (strcmp (toset, fromset) == 0
 564           || (toset_expand != NULL && strcmp (toset_expand, fromset) == 0)
 565           || (fromset_expand != NULL
 566               && (strcmp (toset, fromset_expand) == 0
 567                   || (toset_expand != NULL
 568                       && strcmp (toset_expand, fromset_expand) == 0)))))
 569     {
 570       /* Both character sets are the same.  */
 571       __libc_lock_unlock (lock);
 572       return __GCONV_NOCONV;
 573     }
 574
 575   result = find_derivation (toset, toset_expand, fromset, fromset_expand,
 576                             handle, nsteps);
 577
 578   /* Release the lock.  */
 579   __libc_lock_unlock (lock);
 580
 581   /* The following code is necessary since `find_derivation' will return
 582      GCONV_OK even when no derivation was found but the same request
 583      was processed before.  I.e., negative results will also be cached.  */
 584   return (result == __GCONV_OK
 585           ? (*handle == NULL ? __GCONV_NOCONV : __GCONV_OK)
 586           : result);
 587 }
 588
 589
 590 /* Release the entries of the modules list.  */
 591 int
 592 internal_function
 593 __gconv_close_transform (struct __gconv_step *steps, size_t nsteps)
 594 {
 595   int result = __GCONV_OK;
 596
 597 #ifndef STATIC_GCONV
 598   /* Acquire the lock.  */
 599   __libc_lock_lock (lock);
 600
 601   while (nsteps-- > 0)
 602     if (steps[nsteps].__shlib_handle != NULL
 603         && --steps[nsteps].__counter == 0)
 604       {
 605         result = __gconv_release_shlib (steps[nsteps].__shlib_handle);
 606         if (result != __GCONV_OK)
 607           break;
 608         steps[nsteps].__shlib_handle = NULL;
 609       }
 610
 611   /* Release the lock.  */
 612   __libc_lock_unlock (lock);
 613 #endif
 614
 615   return result;
 616 }
 617
 618
 619 /* Free the modules mentioned.  */
 620 static void
 621 internal_function
 622 free_modules_db (struct gconv_module *node)
 623 {
 624   if (node->left != NULL)
 625     free_modules_db (node->left);
 626   if (node->right != NULL)
 627     free_modules_db (node->right);
 628   do
 629     {
 630       struct gconv_module *act = node;
 631       node = node->same;
 632       if (act->module_name[0] == '/')
 633         free (act);
 634     }
 635   while (node != NULL);
 636 }
 637
 638
 639 /* Free all resources if necessary.  */
 640 static void __attribute__ ((unused))
 641 free_mem (void)
 642 {
 643   if (__gconv_alias_db != NULL)
 644     __tdestroy (__gconv_alias_db, free);
 645
 646   if (__gconv_modules_db != NULL)
 647     free_modules_db (__gconv_modules_db);
 648
 649   if (known_derivations != NULL)
 650     __tdestroy (known_derivations, free_derivation);
 651 }
 652
 653 text_set_element (__libc_subfreeres, free_mem);