(free_derivation): Don't call a step's destructor if the reference is zero.
[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].__counter > 0
167         && deriv->steps[cnt].__end_fct != NULL)
168       DL_CALL_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 /* Decrement the reference count for a single step in a steps array.  */
180 static inline void
181 release_step (struct __gconv_step *step)
182 {
183   if (--step->__counter == 0)
184     {
185       /* Call the destructor.  */
186       if (step->__end_fct != NULL)
187         DL_CALL_FCT (step->__end_fct, (step));
188
189 #ifndef STATIC_GCONV
190       /* Skip builtin modules; they are not reference counted.  */
191       if (step->__shlib_handle != NULL)
192         {
193           /* Release the loaded module.  */
194           __gconv_release_shlib (step->__shlib_handle);
195           step->__shlib_handle = NULL;
196         }
197 #endif
198     }
199 }
200
201 static int
202 internal_function
203 gen_steps (struct derivation_step *best, const char *toset,
204            const char *fromset, struct __gconv_step **handle, size_t *nsteps)
205 {
206   size_t step_cnt = 0;
207   struct __gconv_step *result;
208   struct derivation_step *current;
209   int status = __GCONV_NOMEM;
210
211   /* First determine number of steps.  */
212   for (current = best; current->last != NULL; current = current->last)
213     ++step_cnt;
214
215   result = (struct __gconv_step *) malloc (sizeof (struct __gconv_step)
216                                            * step_cnt);
217   if (result != NULL)
218     {
219       int failed = 0;
220
221       status = __GCONV_OK;
222       *nsteps = step_cnt;
223       current = best;
224       while (step_cnt-- > 0)
225         {
226           result[step_cnt].__from_name = (step_cnt == 0
227                                           ? __strdup (fromset)
228                                           : current->last->result_set);
229           result[step_cnt].__to_name = (step_cnt + 1 == *nsteps
230                                         ? __strdup (current->result_set)
231                                         : result[step_cnt + 1].__from_name);
232
233 #ifndef STATIC_GCONV
234           if (current->code->module_name[0] == '/')
235             {
236               /* Load the module, return handle for it.  */
237               struct __gconv_loaded_object *shlib_handle =
238                 __gconv_find_shlib (current->code->module_name);
239
240               if (shlib_handle == NULL)
241                 {
242                   failed = 1;
243                   break;
244                 }
245
246               result[step_cnt].__shlib_handle = shlib_handle;
247               result[step_cnt].__modname = shlib_handle->name;
248               result[step_cnt].__fct = shlib_handle->fct;
249               result[step_cnt].__init_fct = shlib_handle->init_fct;
250               result[step_cnt].__end_fct = shlib_handle->end_fct;
251             }
252           else
253 #endif
254             /* It's a builtin transformation.  */
255             __gconv_get_builtin_trans (current->code->module_name,
256                                        &result[step_cnt]);
257
258           result[step_cnt].__counter = 1;
259
260           /* Call the init function.  */
261           result[step_cnt].__data = NULL;
262           if (result[step_cnt].__init_fct != NULL)
263              {
264                status = DL_CALL_FCT (result[step_cnt].__init_fct,
265                                       (&result[step_cnt]));
266
267                if (__builtin_expect (status, __GCONV_OK) != __GCONV_OK)
268                  {
269                    failed = 1;
270                    /* Make sure we unload this modules.  */
271                    --step_cnt;
272                    result[step_cnt].__end_fct = NULL;
273                    break;
274                  }
275              }
276
277           current = current->last;
278         }
279
280       if (__builtin_expect (failed, 0) != 0)
281         {
282           /* Something went wrong while initializing the modules.  */
283           while (++step_cnt < *nsteps)
284             release_step (&result[step_cnt]);
285           free (result);
286           *nsteps = 0;
287           *handle = NULL;
288           if (status == __GCONV_OK)
289             status = __GCONV_NOCONV;
290         }
291       else
292         *handle = result;
293     }
294   else
295     {
296       *nsteps = 0;
297       *handle = NULL;
298     }
299
300   return status;
301 }
302
303
304 #ifndef STATIC_GCONV
305 static int
306 internal_function
307 increment_counter (struct __gconv_step *steps, size_t nsteps)
308 {
309   /* Increment the user counter.  */
310   size_t cnt = nsteps;
311   int result = __GCONV_OK;
312
313   while (cnt-- > 0)
314     {
315       struct __gconv_step *step = &steps[cnt];
316
317       if (step->__counter++ == 0)
318         {
319           /* Skip builtin modules.  */
320           if (step->__modname != NULL)
321             {
322               /* Reopen a previously used module.  */
323               step->__shlib_handle = __gconv_find_shlib (step->__modname);
324               if (step->__shlib_handle == NULL)
325                 {
326                   /* Oops, this is the second time we use this module
327                      (after unloading) and this time loading failed!?  */
328                   --step->__counter;
329                   while (++cnt < nsteps)
330                     release_step (&steps[cnt]);
331                   result = __GCONV_NOCONV;
332                   break;
333                 }
334
335               /* The function addresses defined by the module may
336                  have changed.  */
337               step->__fct = step->__shlib_handle->fct;
338               step->__init_fct = step->__shlib_handle->init_fct;
339               step->__end_fct = step->__shlib_handle->end_fct;
340             }
341
342           if (step->__init_fct != NULL)
343             DL_CALL_FCT (step->__init_fct, (step));
344         }
345     }
346   return result;
347 }
348 #endif
349
350
351 /* The main function: find a possible derivation from the `fromset' (either
352    the given name or the alias) to the `toset' (again with alias).  */
353 static int
354 internal_function
355 find_derivation (const char *toset, const char *toset_expand,
356                  const char *fromset, const char *fromset_expand,
357                  struct __gconv_step **handle, size_t *nsteps)
358 {
359   struct derivation_step *first, *current, **lastp, *solution = NULL;
360   int best_cost_hi = INT_MAX;
361   int best_cost_lo = INT_MAX;
362   int result;
363
364   /* Look whether an earlier call to `find_derivation' has already
365      computed a possible derivation.  If so, return it immediately.  */
366   result = derivation_lookup (fromset_expand ?: fromset, toset_expand ?: toset,
367                               handle, nsteps);
368   if (result == __GCONV_OK)
369     {
370 #ifndef STATIC_GCONV
371       result = increment_counter (*handle, *nsteps);
372 #endif
373       return result;
374     }
375
376   /* The task is to find a sequence of transformations, backed by the
377      existing modules - whether builtin or dynamically loadable -,
378      starting at `fromset' (or `fromset_expand') and ending at `toset'
379      (or `toset_expand'), and with minimal cost.
380
381      For computer scientists, this is a shortest path search in the
382      graph where the nodes are all possible charsets and the edges are
383      the transformations listed in __gconv_modules_db.
384
385      For now we use a simple algorithm with quadratic runtime behaviour.
386      A breadth-first search, starting at `fromset' and `fromset_expand'.
387      The list starting at `first' contains all nodes that have been
388      visited up to now, in the order in which they have been visited --
389      excluding the goal nodes `toset' and `toset_expand' which get
390      managed in the list starting at `solution'.
391      `current' walks through the list starting at `first' and looks
392      which nodes are reachable from the current node, adding them to
393      the end of the list [`first' or `solution' respectively] (if
394      they are visited the first time) or updating them in place (if
395      they have have already been visited).
396      In each node of either list, cost_lo and cost_hi contain the
397      minimum cost over any paths found up to now, starting at `fromset'
398      or `fromset_expand', ending at that node.  best_cost_lo and
399      best_cost_hi represent the minimum over the elements of the
400      `solution' list.  */
401
402   if (fromset_expand != NULL)
403     {
404       first = NEW_STEP (fromset_expand, 0, 0, NULL, NULL);
405       first->next = NEW_STEP (fromset, 0, 0, NULL, NULL);
406       lastp = &first->next->next;
407     }
408   else
409     {
410       first = NEW_STEP (fromset, 0, 0, NULL, NULL);
411       lastp = &first->next;
412     }
413
414   for (current = first; current != NULL; current = current->next)
415     {
416       /* Now match all the available module specifications against the
417          current charset name.  If any of them matches check whether
418          we already have a derivation for this charset.  If yes, use the
419          one with the lower costs.  Otherwise add the new charset at the
420          end.
421
422          The module database is organized in a tree form which allows
423          searching for prefixes.  So we search for the first entry with a
424          matching prefix and any other matching entry can be found from
425          this place.  */
426       struct gconv_module *node;
427
428       /* Maybe it is not necessary anymore to look for a solution for
429          this entry since the cost is already as high (or higher) as
430          the cost for the best solution so far.  */
431       if (current->cost_hi > best_cost_hi
432           || (current->cost_hi == best_cost_hi
433               && current->cost_lo >= best_cost_lo))
434         continue;
435
436       node = __gconv_modules_db;
437       while (node != NULL)
438         {
439           int cmpres = strcmp (current->result_set, node->from_string);
440           if (cmpres == 0)
441             {
442               /* Walk through the list of modules with this prefix and
443                  try to match the name.  */
444               struct gconv_module *runp;
445
446               /* Check all the modules with this prefix.  */
447               runp = node;
448               do
449                 {
450                   const char *result_set = (strcmp (runp->to_string, "-") == 0
451                                             ? (toset_expand ?: toset)
452                                             : runp->to_string);
453                   int cost_hi = runp->cost_hi + current->cost_hi;
454                   int cost_lo = runp->cost_lo + current->cost_lo;
455                   struct derivation_step *step;
456
457                   /* We managed to find a derivation.  First see whether
458                      we have reached one of the goal nodes.  */
459                   if (strcmp (result_set, toset) == 0
460                       || (toset_expand != NULL
461                           && strcmp (result_set, toset_expand) == 0))
462                     {
463                       /* Append to the `solution' list if there
464                          is no entry with this name.  */
465                       for (step = solution; step != NULL; step = step->next)
466                         if (strcmp (result_set, step->result_set) == 0)
467                           break;
468
469                       if (step == NULL)
470                         {
471                           step = NEW_STEP (result_set,
472                                            cost_hi, cost_lo,
473                                            runp, current);
474                           step->next = solution;
475                           solution = step;
476                         }
477                       else if (step->cost_hi > cost_hi
478                                || (step->cost_hi == cost_hi
479                                    && step->cost_lo > cost_lo))
480                         {
481                           /* A better path was found for the node,
482                              on the `solution' list.  */
483                           step->code = runp;
484                           step->last = current;
485                           step->cost_hi = cost_hi;
486                           step->cost_lo = cost_lo;
487                         }
488
489                       /* Update best_cost accordingly.  */
490                       if (cost_hi < best_cost_hi
491                           || (cost_hi == best_cost_hi
492                               && cost_lo < best_cost_lo))
493                         {
494                           best_cost_hi = cost_hi;
495                           best_cost_lo = cost_lo;
496                         }
497                     }
498                   else if (cost_hi < best_cost_hi
499                            || (cost_hi == best_cost_hi
500                                && cost_lo < best_cost_lo))
501                     {
502                       /* Append at the end of the `first' list if there
503                          is no entry with this name.  */
504                       for (step = first; step != NULL; step = step->next)
505                         if (strcmp (result_set, step->result_set) == 0)
506                           break;
507
508                       if (step == NULL)
509                         {
510                           *lastp = NEW_STEP (result_set,
511                                              cost_hi, cost_lo,
512                                              runp, current);
513                           lastp = &(*lastp)->next;
514                         }
515                       else if (step->cost_hi > cost_hi
516                                || (step->cost_hi == cost_hi
517                                    && step->cost_lo > cost_lo))
518                         {
519                           /* A better path was found for the node,
520                              on the `first' list.  */
521                           step->code = runp;
522                           step->last = current;
523
524                           /* Update the cost for all steps.  */
525                           for (step = first; step != NULL;
526                                step = step->next)
527                             /* But don't update the start nodes.  */
528                             if (step->code != NULL)
529                               {
530                                 struct derivation_step *back;
531                                 int hi, lo;
532
533                                 hi = step->code->cost_hi;
534                                 lo = step->code->cost_lo;
535
536                                 for (back = step->last; back->code != NULL;
537                                      back = back->last)
538                                   {
539                                     hi += back->code->cost_hi;
540                                     lo += back->code->cost_lo;
541                                   }
542
543                                 step->cost_hi = hi;
544                                 step->cost_lo = lo;
545                               }
546
547                           /* Likewise for the nodes on the solution list.
548                              Also update best_cost accordingly.  */
549                           for (step = solution; step != NULL;
550                                step = step->next)
551                             {
552                               step->cost_hi = (step->code->cost_hi
553                                                + step->last->cost_hi);
554                               step->cost_lo = (step->code->cost_lo
555                                                + step->last->cost_lo);
556
557                               if (step->cost_hi < best_cost_hi
558                                   || (step->cost_hi == best_cost_hi
559                                       && step->cost_lo < best_cost_lo))
560                                 {
561                                   best_cost_hi = step->cost_hi;
562                                   best_cost_lo = step->cost_lo;
563                                 }
564                             }
565                         }
566                     }
567
568                   runp = runp->same;
569                 }
570               while (runp != NULL);
571
572               break;
573             }
574           else if (cmpres < 0)
575             node = node->left;
576           else
577             node = node->right;
578         }
579     }
580
581   if (solution != NULL)
582     {
583       /* We really found a way to do the transformation.  */
584
585       /* Choose the best solution.  This is easy because we know that
586          the solution list has at most length 2 (one for every possible
587          goal node).  */
588       if (solution->next != NULL)
589         {
590           struct derivation_step *solution2 = solution->next;
591
592           if (solution2->cost_hi < solution->cost_hi
593               || (solution2->cost_hi == solution->cost_hi
594                   && solution2->cost_lo < solution->cost_lo))
595             solution = solution2;
596         }
597
598       /* Now build a data structure describing the transformation steps.  */
599       result = gen_steps (solution, toset_expand ?: toset,
600                           fromset_expand ?: fromset, handle, nsteps);
601     }
602   else
603     {
604       /* We haven't found a transformation.  Clear the result values.  */
605       *handle = NULL;
606       *nsteps = 0;
607     }
608
609   /* Add result in any case to list of known derivations.  */
610   add_derivation (fromset_expand ?: fromset, toset_expand ?: toset,
611                   *handle, *nsteps);
612
613   return result;
614 }
615
616
617 int
618 internal_function
619 __gconv_find_transform (const char *toset, const char *fromset,
620                         struct __gconv_step **handle, size_t *nsteps,
621                         int flags)
622 {
623   __libc_once_define (static, once);
624   const char *fromset_expand = NULL;
625   const char *toset_expand = NULL;
626   int result;
627
628   /* Ensure that the configuration data is read.  */
629   __libc_once (once, __gconv_read_conf);
630
631   /* Acquire the lock.  */
632   __libc_lock_lock (lock);
633
634   /* If we don't have a module database return with an error.  */
635   if (__gconv_modules_db == NULL)
636     {
637       __libc_lock_unlock (lock);
638       return __GCONV_NOCONV;
639     }
640
641   /* See whether the names are aliases.  */
642   if (__gconv_alias_db != NULL)
643     {
644       struct gconv_alias key;
645       struct gconv_alias **found;
646
647       key.fromname = fromset;
648       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
649       fromset_expand = found != NULL ? (*found)->toname : NULL;
650
651       key.fromname = toset;
652       found = __tfind (&key, &__gconv_alias_db, __gconv_alias_compare);
653       toset_expand = found != NULL ? (*found)->toname : NULL;
654     }
655
656   if (__builtin_expect (flags & GCONV_AVOID_NOCONV, 0)
657       /* We are not supposed to create a pseudo transformation (means
658          copying) when the input and output character set are the same.  */
659       && (strcmp (toset, fromset) == 0
660           || (toset_expand != NULL && strcmp (toset_expand, fromset) == 0)
661           || (fromset_expand != NULL
662               && (strcmp (toset, fromset_expand) == 0
663                   || (toset_expand != NULL
664                       && strcmp (toset_expand, fromset_expand) == 0)))))
665     {
666       /* Both character sets are the same.  */
667       __libc_lock_unlock (lock);
668       return __GCONV_NOCONV;
669     }
670
671   result = find_derivation (toset, toset_expand, fromset, fromset_expand,
672                             handle, nsteps);
673
674   /* Release the lock.  */
675   __libc_lock_unlock (lock);
676
677   /* The following code is necessary since `find_derivation' will return
678      GCONV_OK even when no derivation was found but the same request
679      was processed before.  I.e., negative results will also be cached.  */
680   return (result == __GCONV_OK
681           ? (*handle == NULL ? __GCONV_NOCONV : __GCONV_OK)
682           : result);
683 }
684
685
686 /* Release the entries of the modules list.  */
687 int
688 internal_function
689 __gconv_close_transform (struct __gconv_step *steps, size_t nsteps)
690 {
691   int result = __GCONV_OK;
692
693 #ifndef STATIC_GCONV
694   /* Acquire the lock.  */
695   __libc_lock_lock (lock);
696
697   while (nsteps-- > 0)
698     release_step (&steps[nsteps]);
699
700   /* Release the lock.  */
701   __libc_lock_unlock (lock);
702 #endif
703
704   return result;
705 }
706
707
708 /* Free the modules mentioned.  */
709 static void
710 internal_function
711 free_modules_db (struct gconv_module *node)
712 {
713   if (node->left != NULL)
714     free_modules_db (node->left);
715   if (node->right != NULL)
716     free_modules_db (node->right);
717   do
718     {
719       struct gconv_module *act = node;
720       node = node->same;
721       if (act->module_name[0] == '/')
722         free (act);
723     }
724   while (node != NULL);
725 }
726
727
728 /* Free all resources if necessary.  */
729 static void __attribute__ ((unused))
730 free_mem (void)
731 {
732   if (__gconv_alias_db != NULL)
733     __tdestroy (__gconv_alias_db, free);
734
735   if (__gconv_modules_db != NULL)
736     free_modules_db (__gconv_modules_db);
737
738   if (known_derivations != NULL)
739     __tdestroy (known_derivations, free_derivation);
740 }
741
742 text_set_element (__libc_subfreeres, free_mem);