]>
git.ipfire.org Git - thirdparty/glibc.git/blob - iconv/gconv_db.c
1 /* Provide access to the collection of available transformation modules.
2 Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Ulrich Drepper <drepper@cygnus.com>, 1997.
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
);
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
= memcpy (new_deriv
+ 1, fromset
, fromset_len
);
143 new_deriv
->to
= memcpy ((char *) new_deriv
->from
+ fromset_len
,
146 new_deriv
->steps
= handle
;
147 new_deriv
->nsteps
= nsteps
;
149 __tsearch (new_deriv
, &known_derivations
, derivation_compare
);
151 /* Please note that we don't complain if the allocation failed. This
152 is not tragically but in case we use the memory debugging facilities
153 not all memory will be freed. */
157 free_derivation (void *p
)
159 struct known_derivation
*deriv
= (struct known_derivation
*) p
;
162 for (cnt
= 0; cnt
< deriv
->nsteps
; ++cnt
)
163 if (deriv
->steps
[cnt
].end_fct
)
164 _CALL_DL_FCT (deriv
->steps
[cnt
].end_fct
, (&deriv
->steps
[cnt
]));
166 /* Free the name strings. */
167 free ((char *) deriv
->steps
[0].from_name
);
168 free ((char *) deriv
->steps
[deriv
->nsteps
- 1].to_name
);
170 free ((struct gconv_step
*) deriv
->steps
);
177 gen_steps (struct derivation_step
*best
, const char *toset
,
178 const char *fromset
, struct gconv_step
**handle
, size_t *nsteps
)
181 struct gconv_step
*result
;
182 struct derivation_step
*current
;
183 int status
= GCONV_NOMEM
;
185 /* First determine number of steps. */
186 for (current
= best
; current
->last
!= NULL
; current
= current
->last
)
189 result
= (struct gconv_step
*) malloc (sizeof (struct gconv_step
)
198 while (step_cnt
-- > 0)
200 result
[step_cnt
].from_name
= (step_cnt
== 0
202 : current
->last
->result_set
);
203 result
[step_cnt
].to_name
= (step_cnt
+ 1 == *nsteps
204 ? __strdup (current
->result_set
)
205 : result
[step_cnt
+ 1].from_name
);
208 if (current
->code
->module_name
[0] == '/')
210 /* Load the module, return handle for it. */
211 struct gconv_loaded_object
*shlib_handle
=
212 __gconv_find_shlib (current
->code
->module_name
);
214 if (shlib_handle
== NULL
)
220 result
[step_cnt
].shlib_handle
= shlib_handle
;
221 result
[step_cnt
].modname
= shlib_handle
->name
;
222 result
[step_cnt
].counter
= 0;
223 result
[step_cnt
].fct
= shlib_handle
->fct
;
224 result
[step_cnt
].init_fct
= shlib_handle
->init_fct
;
225 result
[step_cnt
].end_fct
= shlib_handle
->end_fct
;
229 /* It's a builtin transformation. */
230 __gconv_get_builtin_trans (current
->code
->module_name
,
233 /* Call the init function. */
234 if (result
[step_cnt
].init_fct
!= NULL
)
236 status
= _CALL_DL_FCT (result
[step_cnt
].init_fct
,
237 (&result
[step_cnt
]));
239 if (status
!= GCONV_OK
)
242 /* Make sure we unload this modules. */
248 current
= current
->last
;
253 /* Something went wrong while initializing the modules. */
254 while (++step_cnt
< *nsteps
)
256 if (result
[step_cnt
].end_fct
!= NULL
)
257 _CALL_DL_FCT (result
[step_cnt
].end_fct
, (&result
[step_cnt
]));
259 __gconv_release_shlib (result
[step_cnt
].shlib_handle
);
265 if (status
== GCONV_OK
)
266 status
= GCONV_NOCONV
;
281 /* The main function: find a possible derivation from the `fromset' (either
282 the given name or the alias) to the `toset' (again with alias). */
285 find_derivation (const char *toset
, const char *toset_expand
,
286 const char *fromset
, const char *fromset_expand
,
287 struct gconv_step
**handle
, size_t *nsteps
)
289 __libc_lock_define_initialized (static, lock
)
290 struct derivation_step
*first
, *current
, **lastp
, *solution
= NULL
;
291 int best_cost_hi
= INT_MAX
;
292 int best_cost_lo
= INT_MAX
;
295 result
= derivation_lookup (fromset_expand
?: fromset
, toset_expand
?: toset
,
297 if (result
== GCONV_OK
)
300 __libc_lock_lock (lock
);
302 /* There is a small chance that this derivation is meanwhile found. This
303 can happen if in `find_derivation' we look for this derivation, didn't
304 find it but at the same time another thread looked for this derivation. */
305 result
= derivation_lookup (fromset_expand
?: fromset
, toset_expand
?: toset
,
307 if (result
== GCONV_OK
)
309 __libc_lock_unlock (lock
);
313 /* For now we use a simple algorithm with quadratic runtime behaviour.
314 The task is to match the `toset' with any of the available rules,
315 starting from FROMSET. */
316 if (fromset_expand
!= NULL
)
318 first
= NEW_STEP (fromset_expand
, 0, 0, NULL
, NULL
);
319 first
->next
= NEW_STEP (fromset
, 0, 0, NULL
, NULL
);
320 lastp
= &first
->next
->next
;
324 first
= NEW_STEP (fromset
, 0, 0, NULL
, NULL
);
325 lastp
= &first
->next
;
328 for (current
= first
; current
!= NULL
; current
= current
->next
)
330 /* Now match all the available module specifications against the
331 current charset name. If any of them matches check whether
332 we already have a derivation for this charset. If yes, use the
333 one with the lower costs. Otherwise add the new charset at the
336 The module database is organized in a tree form which allows to
337 search for prefixes. So we search for the first entry with a
338 matching prefix and any other matching entry can be found from
340 struct gconv_module
*node
= __gconv_modules_db
;
342 /* Maybe it is not necessary anymore to look for a solution for
343 this entry since the cost is already as high (or heigher) as
344 the cost for the best solution so far. */
345 if (current
->cost_hi
> best_cost_hi
346 || (current
->cost_hi
== best_cost_hi
347 && current
->cost_lo
>= best_cost_lo
))
352 int cmpres
= strncmp (current
->result_set
, node
->from_constpfx
,
353 MIN (current
->result_set_len
,
354 node
->from_constpfx_len
));
358 /* Walk through the list of modules with this prefix and
359 try to match the name. */
360 struct gconv_module
*runp
;
362 if (current
->result_set_len
< node
->from_constpfx_len
)
363 /* Cannot possibly match. */
366 /* Check all the modules with this prefix. */
370 const char *result_set
= NULL
;
372 if (runp
->from_pattern
== NULL
)
374 /* This is a simple entry and therefore we have a
375 found an matching entry if the strings are really
377 if (current
->result_set_len
== runp
->from_constpfx_len
)
379 if (strcmp (runp
->to_string
, "-") == 0)
380 result_set
= toset_expand
?: toset
;
382 result_set
= runp
->to_string
;
387 /* Compile the regular expression if necessary. */
388 if (runp
->from_regex
== NULL
)
390 if (__regcomp (&runp
->from_regex_mem
,
392 REG_EXTENDED
| REG_ICASE
) != 0)
393 /* Something is wrong. Remember this. */
394 runp
->from_regex
= (regex_t
*) -1L;
396 runp
->from_regex
= &runp
->from_regex_mem
;
399 if (runp
->from_regex
!= (regex_t
*) -1L)
403 /* Try to match the regular expression. */
404 if (__regexec (runp
->from_regex
, current
->result_set
,
406 && match
[0].rm_so
== 0
407 && current
->result_set
[match
[0].rm_eo
] == '\0')
409 /* At least the whole <from> string is matched.
410 We must now match sed-like possible
411 subexpressions from the match to the
413 #define ENSURE_LEN(LEN) \
414 if (wp + (LEN) >= constr + len - 1) \
416 char *newp = alloca (len += 128); \
417 wp = __mempcpy (newp, constr, wp - constr); \
421 char *constr
= alloca (len
);
423 const char *cp
= runp
->to_string
;
432 else if (cp
[1] == '\0')
433 /* Backslash at end of string. */
443 else if (*cp
< '1' || *cp
> '3')
448 if (match
[idx
].rm_so
== -1)
452 ENSURE_LEN (match
[idx
].rm_eo
455 ¤t
->result_set
[match
[idx
].rm_so
],
462 if (*cp
== '\0' && wp
!= constr
)
464 /* Terminate the constructed string. */
472 if (result_set
!= NULL
)
474 int cost_hi
= runp
->cost_hi
+ current
->cost_hi
;
475 int cost_lo
= runp
->cost_lo
+ current
->cost_lo
;
476 struct derivation_step
*step
;
478 /* We managed to find a derivation. First see whether
479 this is what we are looking for. */
480 if (strcmp (result_set
, toset
) == 0
481 || (toset_expand
!= NULL
482 && strcmp (result_set
, toset_expand
) == 0))
484 if (solution
== NULL
|| cost_hi
< best_cost_hi
485 || (cost_hi
== best_cost_hi
486 && cost_lo
< best_cost_lo
))
488 best_cost_hi
= cost_hi
;
489 best_cost_lo
= cost_lo
;
492 /* Append this solution to list. */
493 if (solution
== NULL
)
494 solution
= NEW_STEP (result_set
, 0, 0, runp
,
498 while (solution
->next
!= NULL
)
499 solution
= solution
->next
;
501 solution
->next
= NEW_STEP (result_set
, 0, 0,
505 else if (cost_hi
< best_cost_hi
506 || (cost_hi
== best_cost_hi
507 && cost_lo
< best_cost_lo
))
509 /* Append at the end if there is no entry with
511 for (step
= first
; step
!= NULL
; step
= step
->next
)
512 if (strcmp (result_set
, step
->result_set
) == 0)
517 *lastp
= NEW_STEP (result_set
,
520 lastp
= &(*lastp
)->next
;
522 else if (step
->cost_hi
> cost_hi
523 || (step
->cost_hi
== cost_hi
524 && step
->cost_lo
> cost_lo
))
527 step
->last
= current
;
529 /* Update the cost for all steps. */
530 for (step
= first
; step
!= NULL
;
533 struct derivation_step
*back
;
535 if (step
->code
== NULL
)
536 /* This is one of the entries we started
540 step
->cost_hi
= step
->code
->cost_hi
;
541 step
->cost_lo
= step
->code
->cost_lo
;
543 for (back
= step
->last
; back
->code
!= NULL
;
546 step
->cost_hi
+= back
->code
->cost_hi
;
547 step
->cost_lo
+= back
->code
->cost_lo
;
551 for (step
= solution
; step
!= NULL
;
554 step
->cost_hi
= (step
->code
->cost_hi
555 + step
->last
->cost_hi
);
556 step
->cost_lo
= (step
->code
->cost_lo
557 + step
->last
->cost_lo
);
559 if (step
->cost_hi
< best_cost_hi
560 || (step
->cost_hi
== best_cost_hi
561 && step
->cost_lo
< best_cost_lo
))
564 best_cost_hi
= step
->cost_hi
;
565 best_cost_lo
= step
->cost_lo
;
574 while (runp
!= NULL
);
576 if (current
->result_set_len
== node
->from_constpfx_len
)
579 node
= node
->matching
;
588 if (solution
!= NULL
)
589 /* We really found a way to do the transformation. Now build a data
590 structure describing the transformation steps.*/
591 result
= gen_steps (solution
, toset_expand
?: toset
,
592 fromset_expand
?: fromset
, handle
, nsteps
);
595 /* We haven't found a transformation. Clear the result values. */
600 /* Add result in any case to list of known derivations. */
601 add_derivation (fromset_expand
?: fromset
, toset_expand
?: toset
,
604 __libc_lock_unlock (lock
);
612 __gconv_find_transform (const char *toset
, const char *fromset
,
613 struct gconv_step
**handle
, size_t *nsteps
)
615 __libc_once_define (static, once
);
616 const char *fromset_expand
= NULL
;
617 const char *toset_expand
= NULL
;
620 /* Ensure that the configuration data is read. */
621 __libc_once (once
, __gconv_read_conf
);
623 /* Acquire the lock. */
624 __libc_lock_lock (lock
);
626 /* If we don't have a module database return with an error. */
627 if (__gconv_modules_db
== NULL
)
629 __libc_lock_unlock (lock
);
633 /* See whether the names are aliases. */
634 if (__gconv_alias_db
!= NULL
)
636 struct gconv_alias key
;
637 struct gconv_alias
**found
;
639 key
.fromname
= fromset
;
640 found
= __tfind (&key
, &__gconv_alias_db
, __gconv_alias_compare
);
641 fromset_expand
= found
!= NULL
? (*found
)->toname
: NULL
;
643 key
.fromname
= toset
;
644 found
= __tfind (&key
, &__gconv_alias_db
, __gconv_alias_compare
);
645 toset_expand
= found
!= NULL
? (*found
)->toname
: NULL
;
648 result
= find_derivation (toset
, toset_expand
, fromset
, fromset_expand
,
652 /* Increment the user counter. */
653 if (result
== GCONV_OK
)
655 size_t cnt
= *nsteps
;
656 struct gconv_step
*steps
= *handle
;
659 if (steps
[--cnt
].counter
++ == 0)
661 steps
[cnt
].shlib_handle
=
662 __gconv_find_shlib (steps
[cnt
].modname
);
663 if (steps
[cnt
].shlib_handle
== NULL
)
665 /* Oops, this is the second time we use this module (after
666 unloading) and this time loading failed!? */
667 while (++cnt
< *nsteps
)
668 __gconv_release_shlib (steps
[cnt
].shlib_handle
);
669 result
= GCONV_NOCONV
;
676 /* Release the lock. */
677 __libc_lock_unlock (lock
);
679 /* The following code is necessary since `find_derivation' will return
680 GCONV_OK even when no derivation was found but the same request
681 was processed before. I.e., negative results will also be cached. */
682 return (result
== GCONV_OK
683 ? (*handle
== NULL
? GCONV_NOCONV
: GCONV_OK
)
688 /* Release the entries of the modules list. */
691 __gconv_close_transform (struct gconv_step
*steps
, size_t nsteps
)
693 int result
= GCONV_OK
;
696 /* Acquire the lock. */
697 __libc_lock_lock (lock
);
700 if (steps
[nsteps
].shlib_handle
!= NULL
701 && --steps
[nsteps
].counter
== 0)
703 result
= __gconv_release_shlib (steps
[nsteps
].shlib_handle
);
704 if (result
!= GCONV_OK
)
706 steps
[nsteps
].shlib_handle
= NULL
;
709 /* Release the lock. */
710 __libc_lock_unlock (lock
);
717 /* Free the modules mentioned. */
720 free_modules_db (struct gconv_module
*node
)
722 if (node
->left
!= NULL
)
723 free_modules_db (node
->left
);
724 if (node
->right
!= NULL
)
725 free_modules_db (node
->right
);
726 if (node
->same
!= NULL
)
727 free_modules_db (node
->same
);
730 struct gconv_module
*act
= node
;
731 node
= node
->matching
;
732 if (act
->module_name
[0] == '/')
735 while (node
!= NULL
);
739 /* Free all resources if necessary. */
740 static void __attribute__ ((unused
))
743 if (__gconv_alias_db
!= NULL
)
744 __tdestroy (__gconv_alias_db
, free
);
746 if (__gconv_modules_db
!= NULL
)
747 free_modules_db (__gconv_modules_db
);
749 if (known_derivations
!= NULL
)
750 __tdestroy (known_derivations
, free_derivation
);
753 text_set_element (__libc_subfreeres
, free_mem
);