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.
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.
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.
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. */
25 #include <sys/param.h>
26 #include <bits/libc-lock.h>
29 #include <gconv_int.h>
32 /* Simple data structure for alias mapping. We have two names, `from'
34 void *__gconv_alias_db
;
36 /* Array with available modules. */
37 struct gconv_module
*__gconv_modules_db
;
39 /* We modify global data. */
40 __libc_lock_define_initialized (static, lock
)
43 /* Function for searching alias. */
45 __gconv_alias_compare (const void *p1
, const void *p2
)
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
);
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
58 const char *result_set
;
59 size_t result_set_len
;
62 struct gconv_module
*code
;
63 struct derivation_step
*last
;
64 struct derivation_step
*next
;
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); \
73 newp->code = module; \
74 newp->last = last_mod; \
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
85 struct __gconv_step
*steps
;
89 /* Compare function for database of found derivations. */
91 derivation_compare (const void *p1
, const void *p2
)
93 struct known_derivation
*s1
= (struct known_derivation
*) p1
;
94 struct known_derivation
*s2
= (struct known_derivation
*) p2
;
97 result
= strcmp (s1
->from
, s2
->from
);
99 result
= strcmp (s1
->to
, s2
->to
);
103 /* The search tree for known derivations. */
104 static void *known_derivations
;
106 /* Look up whether given transformation was already requested before. */
109 derivation_lookup (const char *fromset
, const char *toset
,
110 struct __gconv_step
**handle
, size_t *nsteps
)
112 struct known_derivation key
= { fromset
, toset
, NULL
, 0 };
113 struct known_derivation
**result
;
115 result
= __tfind (&key
, &known_derivations
, derivation_compare
);
118 return __GCONV_NOCONV
;
120 *handle
= (*result
)->steps
;
121 *nsteps
= (*result
)->nsteps
;
123 /* Please note that we return GCONV_OK even if the last search for
124 this transformation was unsuccessful. */
128 /* Add new derivation to list of known ones. */
131 add_derivation (const char *fromset
, const char *toset
,
132 struct __gconv_step
*handle
, size_t nsteps
)
134 struct known_derivation
*new_deriv
;
135 size_t fromset_len
= strlen (fromset
) + 1;
136 size_t toset_len
= strlen (toset
) + 1;
138 new_deriv
= (struct known_derivation
*)
139 malloc (sizeof (struct known_derivation
) + fromset_len
+ toset_len
);
140 if (new_deriv
!= NULL
)
142 new_deriv
->from
= (char *) (new_deriv
+ 1);
143 new_deriv
->to
= memcpy (__mempcpy (new_deriv
+ 1, fromset
, fromset_len
),
146 new_deriv
->steps
= handle
;
147 new_deriv
->nsteps
= nsteps
;
149 if (__tsearch (new_deriv
, &known_derivations
, derivation_compare
)
151 /* There is some kind of memory allocation problem. */
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. */
160 free_derivation (void *p
)
162 struct known_derivation
*deriv
= (struct known_derivation
*) p
;
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
]));
169 /* Free the name strings. */
170 free ((char *) deriv
->steps
[0].__from_name
);
171 free ((char *) deriv
->steps
[deriv
->nsteps
- 1].__to_name
);
173 free ((struct __gconv_step
*) deriv
->steps
);
180 gen_steps (struct derivation_step
*best
, const char *toset
,
181 const char *fromset
, struct __gconv_step
**handle
, size_t *nsteps
)
184 struct __gconv_step
*result
;
185 struct derivation_step
*current
;
186 int status
= __GCONV_NOMEM
;
188 /* First determine number of steps. */
189 for (current
= best
; current
->last
!= NULL
; current
= current
->last
)
192 result
= (struct __gconv_step
*) malloc (sizeof (struct __gconv_step
)
201 while (step_cnt
-- > 0)
203 result
[step_cnt
].__from_name
= (step_cnt
== 0
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
);
211 if (current
->code
->module_name
[0] == '/')
213 /* Load the module, return handle for it. */
214 struct __gconv_loaded_object
*shlib_handle
=
215 __gconv_find_shlib (current
->code
->module_name
);
217 if (shlib_handle
== NULL
)
223 result
[step_cnt
].__shlib_handle
= shlib_handle
;
224 result
[step_cnt
].__modname
= shlib_handle
->name
;
225 result
[step_cnt
].__counter
= 0;
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
;
232 /* It's a builtin transformation. */
233 __gconv_get_builtin_trans (current
->code
->module_name
,
236 /* Call the init function. */
237 if (result
[step_cnt
].__init_fct
!= NULL
)
239 status
= DL_CALL_FCT (result
[step_cnt
].__init_fct
,
240 (&result
[step_cnt
]));
242 if (status
!= __GCONV_OK
)
245 /* Make sure we unload this modules. */
251 current
= current
->last
;
256 /* Something went wrong while initializing the modules. */
257 while (++step_cnt
< *nsteps
)
259 if (result
[step_cnt
].__end_fct
!= NULL
)
260 DL_CALL_FCT (result
[step_cnt
].__end_fct
, (&result
[step_cnt
]));
262 __gconv_release_shlib (result
[step_cnt
].__shlib_handle
);
268 if (status
== __GCONV_OK
)
269 status
= __GCONV_NOCONV
;
284 /* The main function: find a possible derivation from the `fromset' (either
285 the given name or the alias) to the `toset' (again with alias). */
288 find_derivation (const char *toset
, const char *toset_expand
,
289 const char *fromset
, const char *fromset_expand
,
290 struct __gconv_step
**handle
, size_t *nsteps
)
292 __libc_lock_define_initialized (static, lock
)
293 struct derivation_step
*first
, *current
, **lastp
, *solution
= NULL
;
294 int best_cost_hi
= INT_MAX
;
295 int best_cost_lo
= INT_MAX
;
298 result
= derivation_lookup (fromset_expand
?: fromset
, toset_expand
?: toset
,
300 if (result
== __GCONV_OK
)
303 __libc_lock_lock (lock
);
305 /* There is a small chance that this derivation is meanwhile found. This
306 can happen if in `find_derivation' we look for this derivation, didn't
307 find it but at the same time another thread looked for this derivation. */
308 result
= derivation_lookup (fromset_expand
?: fromset
, toset_expand
?: toset
,
310 if (result
== __GCONV_OK
)
312 __libc_lock_unlock (lock
);
316 /* For now we use a simple algorithm with quadratic runtime behaviour.
317 The task is to match the `toset' with any of the available rules,
318 starting from FROMSET. */
319 if (fromset_expand
!= NULL
)
321 first
= NEW_STEP (fromset_expand
, 0, 0, NULL
, NULL
);
322 first
->next
= NEW_STEP (fromset
, 0, 0, NULL
, NULL
);
323 lastp
= &first
->next
->next
;
327 first
= NEW_STEP (fromset
, 0, 0, NULL
, NULL
);
328 lastp
= &first
->next
;
331 for (current
= first
; current
!= NULL
; current
= current
->next
)
333 /* Now match all the available module specifications against the
334 current charset name. If any of them matches check whether
335 we already have a derivation for this charset. If yes, use the
336 one with the lower costs. Otherwise add the new charset at the
339 The module database is organized in a tree form which allows to
340 search for prefixes. So we search for the first entry with a
341 matching prefix and any other matching entry can be found from
343 struct gconv_module
*node
= __gconv_modules_db
;
345 /* Maybe it is not necessary anymore to look for a solution for
346 this entry since the cost is already as high (or heigher) as
347 the cost for the best solution so far. */
348 if (current
->cost_hi
> best_cost_hi
349 || (current
->cost_hi
== best_cost_hi
350 && current
->cost_lo
>= best_cost_lo
))
355 int cmpres
= strncmp (current
->result_set
, node
->from_constpfx
,
356 MIN (current
->result_set_len
,
357 node
->from_constpfx_len
));
361 /* Walk through the list of modules with this prefix and
362 try to match the name. */
363 struct gconv_module
*runp
;
365 if (current
->result_set_len
< node
->from_constpfx_len
)
366 /* Cannot possibly match. */
369 /* Check all the modules with this prefix. */
373 const char *result_set
= NULL
;
375 if (runp
->from_pattern
== NULL
)
377 /* This is a simple entry and therefore we have a
378 found an matching entry if the strings are really
380 if (current
->result_set_len
== runp
->from_constpfx_len
)
382 if (strcmp (runp
->to_string
, "-") == 0)
383 result_set
= toset_expand
?: toset
;
385 result_set
= runp
->to_string
;
390 /* Compile the regular expression if necessary. */
391 if (runp
->from_regex
== NULL
)
393 if (__regcomp (&runp
->from_regex_mem
,
395 REG_EXTENDED
| REG_ICASE
) != 0)
396 /* Something is wrong. Remember this. */
397 runp
->from_regex
= (regex_t
*) -1L;
399 runp
->from_regex
= &runp
->from_regex_mem
;
402 if (runp
->from_regex
!= (regex_t
*) -1L)
406 /* Try to match the regular expression. */
407 if (__regexec (runp
->from_regex
, current
->result_set
,
409 && match
[0].rm_so
== 0
410 && current
->result_set
[match
[0].rm_eo
] == '\0')
412 /* At least the whole <from> string is matched.
413 We must now match sed-like possible
414 subexpressions from the match to the
416 #define ENSURE_LEN(LEN) \
417 if (wp + (LEN) >= constr + len - 1) \
419 char *newp = alloca (len += 128); \
420 wp = __mempcpy (newp, constr, wp - constr); \
424 char *constr
= alloca (len
);
426 const char *cp
= runp
->to_string
;
435 else if (cp
[1] == '\0')
436 /* Backslash at end of string. */
446 else if (*cp
< '1' || *cp
> '3')
451 if (match
[idx
].rm_so
== -1)
455 ENSURE_LEN (match
[idx
].rm_eo
458 ¤t
->result_set
[match
[idx
].rm_so
],
465 if (*cp
== '\0' && wp
!= constr
)
467 /* Terminate the constructed string. */
475 if (result_set
!= NULL
)
477 int cost_hi
= runp
->cost_hi
+ current
->cost_hi
;
478 int cost_lo
= runp
->cost_lo
+ current
->cost_lo
;
479 struct derivation_step
*step
;
481 /* We managed to find a derivation. First see whether
482 this is what we are looking for. */
483 if (strcmp (result_set
, toset
) == 0
484 || (toset_expand
!= NULL
485 && strcmp (result_set
, toset_expand
) == 0))
487 if (solution
== NULL
|| cost_hi
< best_cost_hi
488 || (cost_hi
== best_cost_hi
489 && cost_lo
< best_cost_lo
))
491 best_cost_hi
= cost_hi
;
492 best_cost_lo
= cost_lo
;
495 /* Append this solution to list. */
496 if (solution
== NULL
)
497 solution
= NEW_STEP (result_set
, 0, 0, runp
,
501 while (solution
->next
!= NULL
)
502 solution
= solution
->next
;
504 solution
->next
= NEW_STEP (result_set
, 0, 0,
508 else if (cost_hi
< best_cost_hi
509 || (cost_hi
== best_cost_hi
510 && cost_lo
< best_cost_lo
))
512 /* Append at the end if there is no entry with
514 for (step
= first
; step
!= NULL
; step
= step
->next
)
515 if (strcmp (result_set
, step
->result_set
) == 0)
520 *lastp
= NEW_STEP (result_set
,
523 lastp
= &(*lastp
)->next
;
525 else if (step
->cost_hi
> cost_hi
526 || (step
->cost_hi
== cost_hi
527 && step
->cost_lo
> cost_lo
))
530 step
->last
= current
;
532 /* Update the cost for all steps. */
533 for (step
= first
; step
!= NULL
;
536 struct derivation_step
*back
;
538 if (step
->code
== NULL
)
539 /* This is one of the entries we started
543 step
->cost_hi
= step
->code
->cost_hi
;
544 step
->cost_lo
= step
->code
->cost_lo
;
546 for (back
= step
->last
; back
->code
!= NULL
;
549 step
->cost_hi
+= back
->code
->cost_hi
;
550 step
->cost_lo
+= back
->code
->cost_lo
;
554 for (step
= solution
; step
!= NULL
;
557 step
->cost_hi
= (step
->code
->cost_hi
558 + step
->last
->cost_hi
);
559 step
->cost_lo
= (step
->code
->cost_lo
560 + step
->last
->cost_lo
);
562 if (step
->cost_hi
< best_cost_hi
563 || (step
->cost_hi
== best_cost_hi
564 && step
->cost_lo
< best_cost_lo
))
567 best_cost_hi
= step
->cost_hi
;
568 best_cost_lo
= step
->cost_lo
;
577 while (runp
!= NULL
);
579 if (current
->result_set_len
== node
->from_constpfx_len
)
582 node
= node
->matching
;
591 if (solution
!= NULL
)
592 /* We really found a way to do the transformation. Now build a data
593 structure describing the transformation steps.*/
594 result
= gen_steps (solution
, toset_expand
?: toset
,
595 fromset_expand
?: fromset
, handle
, nsteps
);
598 /* We haven't found a transformation. Clear the result values. */
603 /* Add result in any case to list of known derivations. */
604 add_derivation (fromset_expand
?: fromset
, toset_expand
?: toset
,
607 __libc_lock_unlock (lock
);
615 __gconv_find_transform (const char *toset
, const char *fromset
,
616 struct __gconv_step
**handle
, size_t *nsteps
,
619 __libc_once_define (static, once
);
620 const char *fromset_expand
= NULL
;
621 const char *toset_expand
= NULL
;
624 /* Ensure that the configuration data is read. */
625 __libc_once (once
, __gconv_read_conf
);
627 /* Acquire the lock. */
628 __libc_lock_lock (lock
);
630 /* If we don't have a module database return with an error. */
631 if (__gconv_modules_db
== NULL
)
633 __libc_lock_unlock (lock
);
634 return __GCONV_NOCONV
;
637 /* See whether the names are aliases. */
638 if (__gconv_alias_db
!= NULL
)
640 struct gconv_alias key
;
641 struct gconv_alias
**found
;
643 key
.fromname
= fromset
;
644 found
= __tfind (&key
, &__gconv_alias_db
, __gconv_alias_compare
);
645 fromset_expand
= found
!= NULL
? (*found
)->toname
: NULL
;
647 key
.fromname
= toset
;
648 found
= __tfind (&key
, &__gconv_alias_db
, __gconv_alias_compare
);
649 toset_expand
= found
!= NULL
? (*found
)->toname
: NULL
;
652 if ((flags
& GCONV_AVOID_NOCONV
)
653 /* We are not supposed to create a pseudo transformation (means
654 copying) when the input and output character set are the same. */
655 && (strcmp (toset
, fromset
) == 0
656 || (toset_expand
!= NULL
&& strcmp (toset_expand
, fromset
) == 0)
657 || (fromset_expand
!= NULL
658 && (strcmp (toset
, fromset_expand
) == 0
659 || (toset_expand
!= NULL
660 && strcmp (toset_expand
, fromset_expand
) == 0)))))
662 /* Both character sets are the same. */
663 __libc_lock_unlock (lock
);
664 return __GCONV_NOCONV
;
667 result
= find_derivation (toset
, toset_expand
, fromset
, fromset_expand
,
671 /* Increment the user counter. */
672 if (result
== __GCONV_OK
)
674 size_t cnt
= *nsteps
;
675 struct __gconv_step
*steps
= *handle
;
678 if (steps
[--cnt
].__counter
++ == 0)
680 steps
[cnt
].__shlib_handle
=
681 __gconv_find_shlib (steps
[cnt
].__modname
);
682 if (steps
[cnt
].__shlib_handle
== NULL
)
684 /* Oops, this is the second time we use this module (after
685 unloading) and this time loading failed!? */
686 while (++cnt
< *nsteps
)
687 __gconv_release_shlib (steps
[cnt
].__shlib_handle
);
688 result
= __GCONV_NOCONV
;
695 /* Release the lock. */
696 __libc_lock_unlock (lock
);
698 /* The following code is necessary since `find_derivation' will return
699 GCONV_OK even when no derivation was found but the same request
700 was processed before. I.e., negative results will also be cached. */
701 return (result
== __GCONV_OK
702 ? (*handle
== NULL
? __GCONV_NOCONV
: __GCONV_OK
)
707 /* Release the entries of the modules list. */
710 __gconv_close_transform (struct __gconv_step
*steps
, size_t nsteps
)
712 int result
= __GCONV_OK
;
715 /* Acquire the lock. */
716 __libc_lock_lock (lock
);
719 if (steps
[nsteps
].__shlib_handle
!= NULL
720 && --steps
[nsteps
].__counter
== 0)
722 result
= __gconv_release_shlib (steps
[nsteps
].__shlib_handle
);
723 if (result
!= __GCONV_OK
)
725 steps
[nsteps
].__shlib_handle
= NULL
;
728 /* Release the lock. */
729 __libc_lock_unlock (lock
);
736 /* Free the modules mentioned. */
739 free_modules_db (struct gconv_module
*node
)
741 if (node
->left
!= NULL
)
742 free_modules_db (node
->left
);
743 if (node
->right
!= NULL
)
744 free_modules_db (node
->right
);
745 if (node
->same
!= NULL
)
746 free_modules_db (node
->same
);
749 struct gconv_module
*act
= node
;
750 node
= node
->matching
;
751 if (act
->module_name
[0] == '/')
754 while (node
!= NULL
);
758 /* Free all resources if necessary. */
759 static void __attribute__ ((unused
))
762 if (__gconv_alias_db
!= NULL
)
763 __tdestroy (__gconv_alias_db
, free
);
765 if (__gconv_modules_db
!= NULL
)
766 free_modules_db (__gconv_modules_db
);
768 if (known_derivations
!= NULL
)
769 __tdestroy (known_derivations
, free_derivation
);
772 text_set_element (__libc_subfreeres
, free_mem
);