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