(gen_steps): Always initialize __data field of step.
[kopensolaris-gnu/glibc.git] / 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           result[step_cnt].__data = NULL;
238           if (result[step_cnt].__init_fct != NULL)
239              {
240                status = DL_CALL_FCT (result[step_cnt].__init_fct,
241                                       (&result[step_cnt]));
242
243                if (__builtin_expect (status, __GCONV_OK) != __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 (__builtin_expect (failed, 0) != 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                 DL_CALL_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 #ifndef STATIC_GCONV
286 static int
287 internal_function
288 increment_counter (struct __gconv_step *steps, size_t nsteps)
289 {
290   /* Increment the user counter.  */
291   size_t cnt = nsteps;
292   int result = __GCONV_OK;
293
294   while (cnt-- > 0)
295     if (steps[cnt].__counter++ == 0)
296       {
297         steps[cnt].__shlib_handle =
298           __gconv_find_shlib (steps[cnt].__modname);
299         if (steps[cnt].__shlib_handle == NULL)
300           {
301             /* Oops, this is the second time we use this module (after
302                unloading) and this time loading failed!?  */
303             while (++cnt < nsteps)
304               __gconv_release_shlib (steps[cnt].__shlib_handle);
305             result = __GCONV_NOCONV;
306             break;
307           }
308       }
309   return result;
310 }
311 #endif
312
313
314 /* The main function: find a possible derivation from the `fromset' (either
315    the given name or the alias) to the `toset' (again with alias).  */
316 static int
317 internal_function
318 find_derivation (const char *toset, const char *toset_expand,
319                  const char *fromset, const char *fromset_expand,
320                  struct __gconv_step **handle, size_t *nsteps)
321 {
322   struct derivation_step *first, *current, **lastp, *solution = NULL;
323   int best_cost_hi = INT_MAX;
324   int best_cost_lo = INT_MAX;
325   int result;
326
327   /* There is a small chance that this derivation is meanwhile found.  This
328      can happen if in `find_derivation' we look for this derivation, didn't
329      find it but at the same time another thread looked for this derivation. */
330   result = derivation_lookup (fromset_expand ?: fromset, toset_expand ?: toset,
331                               handle, nsteps);
332   if (result == __GCONV_OK)
333     {
334 #ifndef STATIC_GCONV
335       result = increment_counter (*handle, *nsteps);
336 #endif
337       return result;
338     }
339
340   /* For now we use a simple algorithm with quadratic runtime behaviour.
341      The task is to match the `toset' with any of the available rules,
342      starting from FROMSET.  */
343   if (fromset_expand != NULL)
344     {
345       first = NEW_STEP (fromset_expand, 0, 0, NULL, NULL);
346       first->next = NEW_STEP (fromset, 0, 0, NULL, NULL);
347       lastp = &first->next->next;
348     }
349   else
350     {
351       first = NEW_STEP (fromset, 0, 0, NULL, NULL);
352       lastp = &first->next;
353     }
354
355   for (current = first; current != NULL; current = current->next)
356     {
357       /* Now match all the available module specifications against the
358          current charset name.  If any of them matches check whether
359          we already have a derivation for this charset.  If yes, use the
360          one with the lower costs.  Otherwise add the new charset at the
361          end.
362
363          The module database is organized in a tree form which allows
364          searching for prefixes.  So we search for the first entry with a
365          matching prefix and any other matching entry can be found from
366          this place.  */
367       struct gconv_module *node = __gconv_modules_db;
368
369       /* Maybe it is not necessary anymore to look for a solution for
370          this entry since the cost is already as high (or heigher) as
371          the cost for the best solution so far.  */
372       if (current->cost_hi > best_cost_hi
373           || (current->cost_hi == best_cost_hi
374               && current->cost_lo >= best_cost_lo))
375         continue;
376
377       while (node != NULL)
378         {
379           int cmpres = strcmp (current->result_set, node->from_string);
380           if (cmpres == 0)
381             {
382               /* Walk through the list of modules with this prefix and
383                  try to match the name.  */
384               struct gconv_module *runp;
385
386               /* Check all the modules with this prefix.  */
387               runp = node;
388               do
389                 {
390                   const char *result_set = (strcmp (runp->to_string, "-") == 0
391                                             ? (toset_expand ?: toset)
392                                             : runp->to_string);
393                   int cost_hi = runp->cost_hi + current->cost_hi;
394                   int cost_lo = runp->cost_lo + current->cost_lo;
395                   struct derivation_step *step;
396
397                   /* We managed to find a derivation.  First see whether
398                      this is what we are looking for.  */
399                   if (strcmp (result_set, toset) == 0
400                       || (toset_expand != NULL
401                           && strcmp (result_set, toset_expand) == 0))
402                     {
403                       if (solution == NULL || cost_hi < best_cost_hi
404                           || (cost_hi == best_cost_hi
405                               && cost_lo < best_cost_lo))
406                         {
407                           best_cost_hi = cost_hi;
408                           best_cost_lo = cost_lo;
409                         }
410
411                       /* Append this solution to list.  */
412                       if (solution == NULL)
413                         solution = NEW_STEP (result_set, 0, 0, runp, current);
414                       else
415                         {
416                           while (solution->next != NULL)
417                             solution = solution->next;
418
419                           solution->next = NEW_STEP (result_set, 0, 0,
420                                                      runp, current);
421                         }
422                     }
423                   else if (cost_hi < best_cost_hi
424                            || (cost_hi == best_cost_hi
425                                && cost_lo < best_cost_lo))
426                     {
427                       /* Append at the end if there is no entry with
428                          this name.  */
429                       for (step = first; step != NULL; step = step->next)
430                         if (strcmp (result_set, step->result_set) == 0)
431                           break;
432
433                       if (step == NULL)
434                         {
435                           *lastp = NEW_STEP (result_set,
436                                              cost_hi, cost_lo,
437                                              runp, current);
438                           lastp = &(*lastp)->next;
439                         }
440                       else if (step->cost_hi > cost_hi
441                                || (step->cost_hi == cost_hi
442                                    && step->cost_lo > cost_lo))
443                         {
444                           step->code = runp;
445                           step->last = current;
446
447                           /* Update the cost for all steps.  */
448                           for (step = first; step != NULL;
449                                step = step->next)
450                             {
451                               struct derivation_step *back;
452
453                               if (step->code == NULL)
454                                 /* This is one of the entries we started
455                                    from.  */
456                                 continue;
457
458                               step->cost_hi = step->code->cost_hi;
459                               step->cost_lo = step->code->cost_lo;
460
461                               for (back = step->last; back->code != NULL;
462                                    back = back->last)
463                                 {
464                                   step->cost_hi += back->code->cost_hi;
465                                   step->cost_lo += back->code->cost_lo;
466                                 }
467                             }
468
469                           for (step = solution; step != NULL;
470                                step = step->next)
471                             {
472                               step->cost_hi = (step->code->cost_hi
473                                                + step->last->cost_hi);
474                               step->cost_lo = (step->code->cost_lo
475                                                + step->last->cost_lo);
476
477                               if (step->cost_hi < best_cost_hi
478                                   || (step->cost_hi == best_cost_hi
479                                       && step->cost_lo < best_cost_lo))
480                                 {
481                                   solution = step;
482                                   best_cost_hi = step->cost_hi;
483                                   best_cost_lo = step->cost_lo;
484                                 }
485                             }
486                         }
487                     }
488
489                   runp = runp->same;
490                 }
491               while (runp != NULL);
492
493               break;
494             }
495           else if (cmpres < 0)
496             node = node->left;
497           else
498             node = node->right;
499         }
500     }
501
502   if (solution != NULL)
503     /* We really found a way to do the transformation.  Now build a data
504        structure describing the transformation steps.*/
505     result = gen_steps (solution, toset_expand ?: toset,
506                         fromset_expand ?: fromset, handle, nsteps);
507   else
508     {
509       /* We haven't found a transformation.  Clear the result values.  */
510       *handle = NULL;
511       *nsteps = 0;
512     }
513
514   /* Add result in any case to list of known derivations.  */
515   add_derivation (fromset_expand ?: fromset, toset_expand ?: toset,
516                   *handle, *nsteps);
517
518   return result;
519 }
520
521
522 int
523 internal_function
524 __gconv_find_transform (const char *toset, const char *fromset,
525                         struct __gconv_step **handle, size_t *nsteps,
526                         int flags)
527 {
528   __libc_once_define (static, once);
529   const char *fromset_expand = NULL;
530   const char *toset_expand = NULL;
531   int result;
532
533   /* Ensure that the configuration data is read.  */
534   __libc_once (once, __gconv_read_conf);
535
536   /* Acquire the lock.  */
537   __libc_lock_lock (lock);
538
539   /* If we don't have a module database return with an error.  */
540   if (__gconv_modules_db == NULL)
541     {
542       __libc_lock_unlock (lock);
543       return __GCONV_NOCONV;
544     }
545
546   /* See whether the names are aliases.  */
547   if (__gconv_alias_db != NULL)
548     {
549       struct gconv_alias key;
550       struct gconv_alias **found;
551
552       key.fromname = fromset;
553       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
554       fromset_expand = found != NULL ? (*found)->toname : NULL;
555
556       key.fromname = toset;
557       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
558       toset_expand = found != NULL ? (*found)->toname : NULL;
559     }
560
561   if (__builtin_expect (flags & GCONV_AVOID_NOCONV, 0)
562       /* We are not supposed to create a pseudo transformation (means
563          copying) when the input and output character set are the same.  */
564       && (strcmp (toset, fromset) == 0
565           || (toset_expand != NULL && strcmp (toset_expand, fromset) == 0)
566           || (fromset_expand != NULL
567               && (strcmp (toset, fromset_expand) == 0
568                   || (toset_expand != NULL
569                       && strcmp (toset_expand, fromset_expand) == 0)))))
570     {
571       /* Both character sets are the same.  */
572       __libc_lock_unlock (lock);
573       return __GCONV_NOCONV;
574     }
575
576   result = find_derivation (toset, toset_expand, fromset, fromset_expand,
577                             handle, nsteps);
578
579   /* Release the lock.  */
580   __libc_lock_unlock (lock);
581
582   /* The following code is necessary since `find_derivation' will return
583      GCONV_OK even when no derivation was found but the same request
584      was processed before.  I.e., negative results will also be cached.  */
585   return (result == __GCONV_OK
586           ? (*handle == NULL ? __GCONV_NOCONV : __GCONV_OK)
587           : result);
588 }
589
590
591 /* Release the entries of the modules list.  */
592 int
593 internal_function
594 __gconv_close_transform (struct __gconv_step *steps, size_t nsteps)
595 {
596   int result = __GCONV_OK;
597
598 #ifndef STATIC_GCONV
599   /* Acquire the lock.  */
600   __libc_lock_lock (lock);
601
602   while (nsteps-- > 0)
603     if (steps[nsteps].__shlib_handle != NULL
604         && --steps[nsteps].__counter == 0)
605       {
606         result = __gconv_release_shlib (steps[nsteps].__shlib_handle);
607         if (result != __GCONV_OK)
608           break;
609         steps[nsteps].__shlib_handle = NULL;
610       }
611
612   /* Release the lock.  */
613   __libc_lock_unlock (lock);
614 #endif
615
616   return result;
617 }
618
619
620 /* Free the modules mentioned.  */
621 static void
622 internal_function
623 free_modules_db (struct gconv_module *node)
624 {
625   if (node->left != NULL)
626     free_modules_db (node->left);
627   if (node->right != NULL)
628     free_modules_db (node->right);
629   do
630     {
631       struct gconv_module *act = node;
632       node = node->same;
633       if (act->module_name[0] == '/')
634         free (act);
635     }
636   while (node != NULL);
637 }
638
639
640 /* Free all resources if necessary.  */
641 static void __attribute__ ((unused))
642 free_mem (void)
643 {
644   if (__gconv_alias_db != NULL)
645     __tdestroy (__gconv_alias_db, free);
646
647   if (__gconv_modules_db != NULL)
648     free_modules_db (__gconv_modules_db);
649
650   if (known_derivations != NULL)
651     __tdestroy (known_derivations, free_derivation);
652 }
653
654 text_set_element (__libc_subfreeres, free_mem);