Undo last two changes.
[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           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);