1 /* Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Library General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Library General Public License for more details.
15 You should have received a copy of the GNU Library General Public
16 License along with the GNU C Library; see the file COPYING.LIB. If not,
17 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA. */
27 #include <sys/param.h>
30 # define STRING_TYPE char
31 # define USTRING_TYPE unsigned char
32 # ifdef USE_IN_EXTENDED_LOCALE_MODEL
33 # define STRXFRM __strxfrm_l
35 # define STRXFRM strxfrm
37 # define STRCMP strcmp
38 # define STRLEN strlen
39 # define STPNCPY __stpncpy
40 # define WEIGHT_H "../locale/weight.h"
45 #define CONCAT(a,b) CONCAT1(a,b)
46 #define CONCAT1(a,b) a##b
48 #include "../locale/localeinfo.h"
51 #ifndef WIDE_CHAR_VERSION
53 /* We need UTF-8 encoding of numbers. */
55 utf8_encode (char *buf
, int val
)
68 for (step
= 2; step
< 6; ++step
)
69 if ((val
& (~(uint32_t)0 << (5 * step
+ 1))) == 0)
73 *buf
= (unsigned char) (~0xff >> step
);
77 buf
[step
] = 0x80 | (val
& 0x3f);
89 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
91 STRXFRM (STRING_TYPE
*dest
, const STRING_TYPE
*src
, size_t n
)
94 STRXFRM (STRING_TYPE
*dest
, const STRING_TYPE
*src
, size_t n
, __locale_t l
)
97 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
98 struct locale_data
*current
= l
->__locales
[LC_COLLATE
];
99 uint_fast32_t nrules
= *((const uint32_t *) current
->values
[_NL_ITEM_INDEX (_NL_COLLATE_NRULES
)].string
);
101 uint32_t nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
103 /* We don't assign the following values right away since it might be
104 unnecessary in case there are no rules. */
105 const unsigned char *rulesets
;
106 const int32_t *table
;
107 const USTRING_TYPE
*weights
;
108 const USTRING_TYPE
*extra
;
109 const int32_t *indirect
;
112 const USTRING_TYPE
*usrc
;
113 size_t srclen
= STRLEN (src
);
115 unsigned char *rulearr
;
125 STPNCPY (dest
, src
, MIN (srclen
+ 1, n
));
130 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
131 rulesets
= (const unsigned char *)
132 current
->values
[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS
)].string
;
133 table
= (const int32_t *)
134 current
->values
[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE
,SUFFIX
))].string
;
135 weights
= (const USTRING_TYPE
*)
136 current
->values
[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT
,SUFFIX
))].string
;
137 extra
= (const USTRING_TYPE
*)
138 current
->values
[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA
,SUFFIX
))].string
;
139 indirect
= (const int32_t *)
140 current
->values
[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT
,SUFFIX
))].string
;
142 rulesets
= (const unsigned char *)
143 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_RULESETS
);
144 table
= (const int32_t *)
145 _NL_CURRENT (LC_COLLATE
, CONCAT(_NL_COLLATE_TABLE
,SUFFIX
));
146 weights
= (const USTRING_TYPE
*)
147 _NL_CURRENT (LC_COLLATE
, CONCAT(_NL_COLLATE_WEIGHT
,SUFFIX
));
148 extra
= (const USTRING_TYPE
*)
149 _NL_CURRENT (LC_COLLATE
, CONCAT(_NL_COLLATE_EXTRA
,SUFFIX
));
150 indirect
= (const int32_t *)
151 _NL_CURRENT (LC_COLLATE
, CONCAT(_NL_COLLATE_INDIRECT
,SUFFIX
));
155 assert (((uintptr_t) table
) % __alignof__ (table
[0]) == 0);
156 assert (((uintptr_t) weights
) % __alignof__ (weights
[0]) == 0);
157 assert (((uintptr_t) extra
) % __alignof__ (extra
[0]) == 0);
158 assert (((uintptr_t) indirect
) % __alignof__ (indirect
[0]) == 0);
160 /* Handle an empty string as a special case. */
168 /* We need the elements of the string as unsigned values since they
169 are used as indeces. */
170 usrc
= (const USTRING_TYPE
*) src
;
172 /* Perform the first pass over the string and while doing this find
173 and store the weights for each character. Since we want this to
174 be as fast as possible we are using `alloca' to store the temporary
175 values. But since there is no limit on the length of the string
176 we have to use `malloc' if the string is too long. We should be
177 very conservative here. */
180 idxarr
= (int32_t *) malloc (srclen
* (sizeof (int32_t) + 1));
181 rulearr
= (unsigned char *) &idxarr
[srclen
];
184 /* No memory. Well, go with the stack then.
186 XXX Once this implementation is stable we will handle this
187 differently. Instead of precomputing the indeces we will
188 do this in time. This means, though, that this happens for
196 idxarr
= (int32_t *) alloca (srclen
* sizeof (int32_t));
197 rulearr
= (unsigned char *) alloca (srclen
);
203 int32_t tmp
= findidx (&usrc
);
204 rulearr
[idxmax
] = tmp
>> 24;
205 idxarr
[idxmax
] = tmp
& 0xffffff;
209 while (*usrc
!= L('\0'));
211 /* Now the passes over the weights. We now use the indeces we found
214 for (pass
= 0; pass
< nrules
; ++pass
)
216 size_t backw_stop
= ~0ul;
217 int rule
= rulesets
[rulearr
[0] * nrules
+ pass
];
218 /* We assume that if a rule has defined `position' in one section
219 this is true for all of them. */
220 int position
= rule
& sort_position
;
224 for (idxcnt
= 0; idxcnt
< idxmax
; ++idxcnt
)
226 if ((rule
& sort_forward
) != 0)
230 if (backw_stop
!= ~0ul)
232 /* Handle the pushed elements now. */
235 for (backw
= idxcnt
- 1; backw
>= backw_stop
; --backw
)
237 len
= weights
[idxarr
[backw
]++];
239 if (needed
+ len
< n
)
241 dest
[needed
++] = weights
[idxarr
[backw
]++];
244 /* No more characters fit into the buffer. */
246 idxarr
[backw
] += len
;
253 /* Now handle the forward element. */
254 len
= weights
[idxarr
[idxcnt
]++];
255 if (needed
+ len
< n
)
257 dest
[needed
++] = weights
[idxarr
[idxcnt
]++];
260 /* No more characters fit into the buffer. */
262 idxarr
[idxcnt
] += len
;
267 /* Remember where the backwards series started. */
268 if (backw_stop
== ~0ul)
272 rule
= rulesets
[rulearr
[idxcnt
+ 1] * nrules
+ pass
];
276 if (backw_stop
!= ~0ul)
278 /* Handle the pushed elements now. */
282 while (backw
> backw_stop
)
284 size_t len
= weights
[idxarr
[--backw
]++];
286 if (needed
+ len
< n
)
288 dest
[needed
++] = weights
[idxarr
[backw
]++];
291 /* No more characters fit into the buffer. */
293 idxarr
[backw
] += len
;
301 #ifndef WIDE_CHAR_VERSION
307 for (idxcnt
= 0; idxcnt
< idxmax
; ++idxcnt
)
309 if ((rule
& sort_forward
) != 0)
313 if (backw_stop
!= ~0ul)
315 /* Handle the pushed elements now. */
318 for (backw
= idxcnt
- 1; backw
>= backw_stop
; --backw
)
320 len
= weights
[idxarr
[backw
]++];
323 #ifdef WIDE_CHAR_VERSION
324 if (needed
+ 1 + len
< n
)
327 for (i
= 0; i
< len
; ++i
)
328 dest
[needed
+ 1 + i
] =
329 weights
[idxarr
[backw
] + i
];
333 buflen
= utf8_encode (buf
, val
);
334 if (needed
+ buflen
+ len
< n
)
336 for (i
= 0; i
< buflen
; ++i
)
337 dest
[needed
+ i
] = buf
[i
];
338 for (i
= 0; i
< len
; ++i
)
339 dest
[needed
+ buflen
+ i
] =
340 weights
[idxarr
[backw
] + i
];
342 needed
+= buflen
+ len
;
344 idxarr
[backw
] += len
;
354 /* Now handle the forward element. */
355 len
= weights
[idxarr
[idxcnt
]++];
358 #ifdef WIDE_CHAR_VERSION
359 if (needed
+ 1+ len
< n
)
362 for (i
= 0; i
< len
; ++i
)
363 dest
[needed
+ 1 + i
] =
364 weights
[idxarr
[idxcnt
] + i
];
368 buflen
= utf8_encode (buf
, val
);
369 if (needed
+ buflen
+ len
< n
)
371 for (i
= 0; i
< buflen
; ++i
)
372 dest
[needed
+ i
] = buf
[i
];
373 for (i
= 0; i
< len
; ++i
)
374 dest
[needed
+ buflen
+ i
] =
375 weights
[idxarr
[idxcnt
] + i
];
377 needed
+= buflen
+ len
;
379 idxarr
[idxcnt
] += len
;
383 /* Note that we don't have to increment `idxarr[idxcnt]'
384 since the length is zero. */
389 /* Remember where the backwards series started. */
390 if (backw_stop
== ~0ul)
394 rule
= rulesets
[rulearr
[idxcnt
+ 1] * nrules
+ pass
];
397 if (backw_stop
!= ~0ul)
399 /* Handle the pushed elements now. */
403 while (backw
> backw_stop
)
405 size_t len
= weights
[idxarr
[--backw
]++];
408 #ifdef WIDE_CHAR_VERSION
409 if (needed
+ 1 + len
< n
)
412 for (i
= 0; i
< len
; ++i
)
413 dest
[needed
+ 1 + i
] =
414 weights
[idxarr
[backw
] + i
];
418 buflen
= utf8_encode (buf
, val
);
419 if (needed
+ buflen
+ len
< n
)
421 for (i
= 0; i
< buflen
; ++i
)
422 dest
[needed
+ i
] = buf
[i
];
423 for (i
= 0; i
< len
; ++i
)
424 dest
[needed
+ buflen
+ i
] =
425 weights
[idxarr
[backw
] + i
];
427 needed
+= buflen
+ len
;
429 idxarr
[backw
] += len
;
438 /* Finally store the byte to separate the passes or terminate
441 dest
[needed
] = pass
+ 1 < nrules
? L('\1') : L('\0');
445 /* This is a little optimization: many collation specifications have
446 a `position' rule at the end and if no non-ignored character
447 is found the last \1 byte is immediately followed by a \0 byte
448 signalling this. We can avoid the \1 byte(s). */
449 if (needed
<= n
&& needed
> 2 && dest
[needed
- 2] == L('\1'))
451 /* Remove the \1 byte. */
453 dest
[needed
- 1] = L('\0');
456 /* Free the memory if needed. */
460 /* Return the number of bytes/words we need, but don't count the NUL
461 byte/word at the end. */