(tst-strxfrm2-ENV): Define.
[kopensolaris-gnu/glibc.git] / string / strxfrm_l.c
1 /* Copyright (C) 1995, 1996, 1997, 2002, 2004, 2005, 2006
2    Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Written by Ulrich Drepper <drepper@gnu.org>, 1995.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the 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    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 #include <assert.h>
22 #include <langinfo.h>
23 #include <locale.h>
24 #include <stddef.h>
25 #include <stdint.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <sys/param.h>
29
30 #ifndef STRING_TYPE
31 # define STRING_TYPE char
32 # define USTRING_TYPE unsigned char
33 # define STRXFRM __strxfrm_l
34 # define STRCMP strcmp
35 # define STRLEN strlen
36 # define STPNCPY __stpncpy
37 # define WEIGHT_H "../locale/weight.h"
38 # define SUFFIX MB
39 # define L(arg) arg
40 #endif
41
42 #define CONCAT(a,b) CONCAT1(a,b)
43 #define CONCAT1(a,b) a##b
44
45 #include "../locale/localeinfo.h"
46
47
48 #ifndef WIDE_CHAR_VERSION
49
50 /* We need UTF-8 encoding of numbers.  */
51 static int
52 utf8_encode (char *buf, int val)
53 {
54   int retval;
55
56   if (val < 0x80)
57     {
58       *buf++ = (char) val;
59       retval = 1;
60     }
61   else
62     {
63       int step;
64
65       for (step = 2; step < 6; ++step)
66         if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
67           break;
68       retval = step;
69
70       *buf = (unsigned char) (~0xff >> step);
71       --step;
72       do
73         {
74           buf[step] = 0x80 | (val & 0x3f);
75           val >>= 6;
76         }
77       while (--step > 0);
78       *buf |= val;
79     }
80
81   return retval;
82 }
83 #endif
84
85
86 size_t
87 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, __locale_t l)
88 {
89   struct locale_data *current = l->__locales[LC_COLLATE];
90   uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
91   /* We don't assign the following values right away since it might be
92      unnecessary in case there are no rules.  */
93   const unsigned char *rulesets;
94   const int32_t *table;
95   const USTRING_TYPE *weights;
96   const USTRING_TYPE *extra;
97   const int32_t *indirect;
98   uint_fast32_t pass;
99   size_t needed;
100   size_t last_needed;
101   const USTRING_TYPE *usrc;
102   size_t srclen = STRLEN (src);
103   int32_t *idxarr;
104   unsigned char *rulearr;
105   size_t idxmax;
106   size_t idxcnt;
107   int use_malloc;
108
109 #include WEIGHT_H
110
111   if (nrules == 0)
112     {
113       if (n != 0)
114         STPNCPY (dest, src, MIN (srclen + 1, n));
115
116       return srclen;
117     }
118
119   rulesets = (const unsigned char *)
120     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
121   table = (const int32_t *)
122     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
123   weights = (const USTRING_TYPE *)
124     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
125   extra = (const USTRING_TYPE *)
126     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
127   indirect = (const int32_t *)
128     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
129   use_malloc = 0;
130
131   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
132   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
133   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
134   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
135
136   /* Handle an empty string as a special case.  */
137   if (srclen == 0)
138     {
139       if (n != 0)
140         *dest = L('\0');
141       return 0;
142     }
143
144   /* We need the elements of the string as unsigned values since they
145      are used as indeces.  */
146   usrc = (const USTRING_TYPE *) src;
147
148   /* Perform the first pass over the string and while doing this find
149      and store the weights for each character.  Since we want this to
150      be as fast as possible we are using `alloca' to store the temporary
151      values.  But since there is no limit on the length of the string
152      we have to use `malloc' if the string is too long.  We should be
153      very conservative here.  */
154   if (! __libc_use_alloca (srclen))
155     {
156       idxarr = (int32_t *) malloc ((srclen + 1) * (sizeof (int32_t) + 1));
157       rulearr = (unsigned char *) &idxarr[srclen];
158
159       if (idxarr == NULL)
160         /* No memory.  Well, go with the stack then.
161
162            XXX Once this implementation is stable we will handle this
163            differently.  Instead of precomputing the indeces we will
164            do this in time.  This means, though, that this happens for
165            every pass again.  */
166         goto try_stack;
167       use_malloc = 1;
168     }
169   else
170     {
171     try_stack:
172       idxarr = (int32_t *) alloca (srclen * sizeof (int32_t));
173       rulearr = (unsigned char *) alloca (srclen + 1);
174     }
175
176   idxmax = 0;
177   do
178     {
179       int32_t tmp = findidx (&usrc);
180       rulearr[idxmax] = tmp >> 24;
181       idxarr[idxmax] = tmp & 0xffffff;
182
183       ++idxmax;
184     }
185   while (*usrc != L('\0'));
186
187   /* This element is only read, the value never used but to determine
188      another value which then is ignored.  */
189   rulearr[idxmax] = '\0';
190
191   /* Now the passes over the weights.  We now use the indeces we found
192      before.  */
193   needed = 0;
194   for (pass = 0; pass < nrules; ++pass)
195     {
196       size_t backw_stop = ~0ul;
197       int rule = rulesets[rulearr[0] * nrules + pass];
198       /* We assume that if a rule has defined `position' in one section
199          this is true for all of them.  */
200       int position = rule & sort_position;
201
202       last_needed = needed;
203       if (position == 0)
204         {
205           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
206             {
207               if ((rule & sort_forward) != 0)
208                 {
209                   size_t len;
210
211                   if (backw_stop != ~0ul)
212                     {
213                       /* Handle the pushed elements now.  */
214                       size_t backw;
215
216                       for (backw = idxcnt; backw > backw_stop; )
217                         {
218                           --backw;
219                           len = weights[idxarr[backw]++];
220
221                           if (needed + len < n)
222                             while (len-- > 0)
223                               dest[needed++] = weights[idxarr[backw]++];
224                           else
225                             {
226                                 /* No more characters fit into the buffer.  */
227                               needed += len;
228                               idxarr[backw] += len;
229                             }
230                         }
231
232                       backw_stop = ~0ul;
233                     }
234
235                   /* Now handle the forward element.  */
236                   len = weights[idxarr[idxcnt]++];
237                   if (needed + len < n)
238                     while (len-- > 0)
239                       dest[needed++] = weights[idxarr[idxcnt]++];
240                   else
241                     {
242                       /* No more characters fit into the buffer.  */
243                       needed += len;
244                       idxarr[idxcnt] += len;
245                     }
246                 }
247               else
248                 {
249                   /* Remember where the backwards series started.  */
250                   if (backw_stop == ~0ul)
251                     backw_stop = idxcnt;
252                 }
253
254               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
255             }
256
257
258           if (backw_stop != ~0ul)
259             {
260               /* Handle the pushed elements now.  */
261               size_t backw;
262
263               backw = idxcnt;
264               while (backw > backw_stop)
265                 {
266                   size_t len = weights[idxarr[--backw]++];
267
268                   if (needed + len < n)
269                     while (len-- > 0)
270                       dest[needed++] = weights[idxarr[backw]++];
271                   else
272                     {
273                       /* No more characters fit into the buffer.  */
274                       needed += len;
275                       idxarr[backw] += len;
276                     }
277                 }
278             }
279         }
280       else
281         {
282           int val = 1;
283 #ifndef WIDE_CHAR_VERSION
284           char buf[7];
285           size_t buflen;
286 #endif
287           size_t i;
288
289           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
290             {
291               if ((rule & sort_forward) != 0)
292                 {
293                   size_t len;
294
295                   if (backw_stop != ~0ul)
296                     {
297                      /* Handle the pushed elements now.  */
298                       size_t backw;
299
300                       for (backw = idxcnt; backw > backw_stop; )
301                         {
302                           --backw;
303                           len = weights[idxarr[backw]++];
304                           if (len != 0)
305                             {
306 #ifdef WIDE_CHAR_VERSION
307                               if (needed + 1 + len < n)
308                                 {
309                                   dest[needed] = val;
310                                   for (i = 0; i < len; ++i)
311                                     dest[needed + 1 + i] =
312                                       weights[idxarr[backw] + i];
313                                 }
314                               needed += 1 + len;
315 #else
316                               buflen = utf8_encode (buf, val);
317                               if (needed + buflen + len < n)
318                                 {
319                                   for (i = 0; i < buflen; ++i)
320                                     dest[needed + i] = buf[i];
321                                   for (i = 0; i < len; ++i)
322                                     dest[needed + buflen + i] =
323                                       weights[idxarr[backw] + i];
324                                 }
325                               needed += buflen + len;
326 #endif
327                               idxarr[backw] += len;
328                               val = 1;
329                             }
330                           else
331                             ++val;
332                         }
333
334                       backw_stop = ~0ul;
335                     }
336
337                   /* Now handle the forward element.  */
338                   len = weights[idxarr[idxcnt]++];
339                   if (len != 0)
340                     {
341 #ifdef WIDE_CHAR_VERSION
342                       if (needed + 1+ len < n)
343                         {
344                           dest[needed] = val;
345                           for (i = 0; i < len; ++i)
346                             dest[needed + 1 + i] =
347                               weights[idxarr[idxcnt] + i];
348                         }
349                       needed += 1 + len;
350 #else
351                       buflen = utf8_encode (buf, val);
352                       if (needed + buflen + len < n)
353                         {
354                           for (i = 0; i < buflen; ++i)
355                             dest[needed + i] = buf[i];
356                           for (i = 0; i < len; ++i)
357                             dest[needed + buflen + i] =
358                               weights[idxarr[idxcnt] + i];
359                         }
360                       needed += buflen + len;
361 #endif
362                       idxarr[idxcnt] += len;
363                       val = 1;
364                     }
365                   else
366                     /* Note that we don't have to increment `idxarr[idxcnt]'
367                        since the length is zero.  */
368                     ++val;
369                 }
370               else
371                 {
372                   /* Remember where the backwards series started.  */
373                   if (backw_stop == ~0ul)
374                     backw_stop = idxcnt;
375                 }
376
377               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
378             }
379
380           if (backw_stop != ~0ul)
381             {
382               /* Handle the pushed elements now.  */
383               size_t backw;
384
385               backw = idxmax - 1;
386               while (backw > backw_stop)
387                 {
388                   size_t len = weights[idxarr[--backw]++];
389                   if (len != 0)
390                     {
391 #ifdef WIDE_CHAR_VERSION
392                       if (needed + 1 + len < n)
393                         {
394                           dest[needed] = val;
395                           for (i = 0; i < len; ++i)
396                             dest[needed + 1 + i] =
397                               weights[idxarr[backw] + i];
398                         }
399                       needed += 1 + len;
400 #else
401                       buflen = utf8_encode (buf, val);
402                       if (needed + buflen + len < n)
403                         {
404                           for (i = 0; i < buflen; ++i)
405                             dest[needed + i] = buf[i];
406                           for (i = 0; i < len; ++i)
407                             dest[needed + buflen + i] =
408                               weights[idxarr[backw] + i];
409                         }
410                       needed += buflen + len;
411 #endif
412                       idxarr[backw] += len;
413                       val = 1;
414                     }
415                   else
416                     ++val;
417                 }
418             }
419         }
420
421       /* Finally store the byte to separate the passes or terminate
422          the string.  */
423       if (needed < n)
424         dest[needed] = pass + 1 < nrules ? L('\1') : L('\0');
425       ++needed;
426     }
427
428   /* This is a little optimization: many collation specifications have
429      a `position' rule at the end and if no non-ignored character
430      is found the last \1 byte is immediately followed by a \0 byte
431      signalling this.  We can avoid the \1 byte(s).  */
432   if (needed > 2 && needed == last_needed + 1)
433     {
434       /* Remove the \1 byte.  */
435       if (--needed <= n)
436         dest[needed - 1] = L('\0');
437     }
438
439   /* Free the memory if needed.  */
440   if (use_malloc)
441     free (idxarr);
442
443   /* Return the number of bytes/words we need, but don't count the NUL
444      byte/word at the end.  */
445   return needed - 1;
446 }
447 libc_hidden_def (STRXFRM)
448
449 #ifndef WIDE_CHAR_VERSION
450 weak_alias (__strxfrm_l, strxfrm_l)
451 #endif