Remove sun compat bits
[kopensolaris-gnu/glibc.git] / string / strcoll_l.c
1 /* Copyright (C) 1995,96,97,2002, 2004, 2007 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Written by Ulrich Drepper <drepper@gnu.org>, 1995.
4
5    The GNU C Library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public
7    License as published by the Free Software Foundation; either
8    version 2.1 of the License, or (at your option) any later version.
9
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    Lesser General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with the GNU C Library; if not, write to the Free
17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
18    02111-1307 USA.  */
19
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
29 #ifndef STRING_TYPE
30 # define STRING_TYPE char
31 # define USTRING_TYPE unsigned char
32 # define STRCOLL __strcoll_l
33 # define STRCMP strcmp
34 # define STRLEN strlen
35 # define WEIGHT_H "../locale/weight.h"
36 # define SUFFIX MB
37 # define L(arg) arg
38 #endif
39
40 #define CONCAT(a,b) CONCAT1(a,b)
41 #define CONCAT1(a,b) a##b
42
43 #include "../locale/localeinfo.h"
44
45 int
46 STRCOLL (s1, s2, l)
47      const STRING_TYPE *s1;
48      const STRING_TYPE *s2;
49      __locale_t l;
50 {
51   struct locale_data *current = l->__locales[LC_COLLATE];
52   uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
53   /* We don't assign the following values right away since it might be
54      unnecessary in case there are no rules.  */
55   const unsigned char *rulesets;
56   const int32_t *table;
57   const USTRING_TYPE *weights;
58   const USTRING_TYPE *extra;
59   const int32_t *indirect;
60   uint_fast32_t pass;
61   int result = 0;
62   const USTRING_TYPE *us1;
63   const USTRING_TYPE *us2;
64   size_t s1len;
65   size_t s2len;
66   int32_t *idx1arr;
67   int32_t *idx2arr;
68   unsigned char *rule1arr;
69   unsigned char *rule2arr;
70   size_t idx1max;
71   size_t idx2max;
72   size_t idx1cnt;
73   size_t idx2cnt;
74   size_t idx1now;
75   size_t idx2now;
76   size_t backw1_stop;
77   size_t backw2_stop;
78   size_t backw1;
79   size_t backw2;
80   int val1;
81   int val2;
82   int position;
83   int seq1len;
84   int seq2len;
85   int use_malloc;
86
87 #include WEIGHT_H
88
89   if (nrules == 0)
90     return STRCMP (s1, s2);
91
92   rulesets = (const unsigned char *)
93     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
94   table = (const int32_t *)
95     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
96   weights = (const USTRING_TYPE *)
97     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
98   extra = (const USTRING_TYPE *)
99     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
100   indirect = (const int32_t *)
101     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
102   use_malloc = 0;
103
104   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
105   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
106   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
107   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
108
109   /* We need this a few times.  */
110   s1len = STRLEN (s1);
111   s2len = STRLEN (s2);
112
113   /* Catch empty strings.  */
114   if (__builtin_expect (s1len == 0, 0) || __builtin_expect (s2len == 0, 0))
115     return (s1len != 0) - (s2len != 0);
116
117   /* We need the elements of the strings as unsigned values since they
118      are used as indeces.  */
119   us1 = (const USTRING_TYPE *) s1;
120   us2 = (const USTRING_TYPE *) s2;
121
122   /* Perform the first pass over the string and while doing this find
123      and store the weights for each character.  Since we want this to
124      be as fast as possible we are using `alloca' to store the temporary
125      values.  But since there is no limit on the length of the string
126      we have to use `malloc' if the string is too long.  We should be
127      very conservative here.
128
129      Please note that the localedef programs makes sure that `position'
130      is not used at the first level.  */
131   if (! __libc_use_alloca ((s1len + s2len) * (sizeof (int32_t) + 1)))
132     {
133       idx1arr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
134       idx2arr = &idx1arr[s1len];
135       rule1arr = (unsigned char *) &idx2arr[s2len];
136       rule2arr = &rule1arr[s1len];
137
138       if (idx1arr == NULL)
139         /* No memory.  Well, go with the stack then.
140
141            XXX Once this implementation is stable we will handle this
142            differently.  Instead of precomputing the indeces we will
143            do this in time.  This means, though, that this happens for
144            every pass again.  */
145         goto try_stack;
146       use_malloc = 1;
147     }
148   else
149     {
150     try_stack:
151       idx1arr = (int32_t *) alloca (s1len * sizeof (int32_t));
152       idx2arr = (int32_t *) alloca (s2len * sizeof (int32_t));
153       rule1arr = (unsigned char *) alloca (s1len);
154       rule2arr = (unsigned char *) alloca (s2len);
155     }
156
157   idx1cnt = 0;
158   idx2cnt = 0;
159   idx1max = 0;
160   idx2max = 0;
161   idx1now = 0;
162   idx2now = 0;
163   backw1_stop = ~0ul;
164   backw2_stop = ~0ul;
165   backw1 = ~0ul;
166   backw2 = ~0ul;
167   seq1len = 0;
168   seq2len = 0;
169   position = rulesets[0] & sort_position;
170   while (1)
171     {
172       val1 = 0;
173       val2 = 0;
174
175       /* Get the next non-IGNOREd element for string `s1'.  */
176       if (seq1len == 0)
177         do
178           {
179             ++val1;
180
181             if (backw1_stop != ~0ul)
182               {
183                 /* The is something pushed.  */
184                 if (backw1 == backw1_stop)
185                   {
186                     /* The last pushed character was handled.  Continue
187                        with forward characters.  */
188                     if (idx1cnt < idx1max)
189                       {
190                         idx1now = idx1cnt;
191                         backw1_stop = ~0ul;
192                       }
193                     else
194                       /* Nothing anymore.  The backward sequence ended with
195                          the last sequence in the string.  Note that seq1len
196                          is still zero.  */
197                       break;
198                   }
199                 else
200                   idx1now = --backw1;
201               }
202             else
203               {
204                 backw1_stop = idx1max;
205
206                 while (*us1 != L('\0'))
207                   {
208                     int32_t tmp = findidx (&us1);
209                     rule1arr[idx1max] = tmp >> 24;
210                     idx1arr[idx1max] = tmp & 0xffffff;
211                     idx1cnt = idx1max++;
212
213                     if ((rulesets[rule1arr[idx1cnt] * nrules]
214                          & sort_backward) == 0)
215                       /* No more backward characters to push.  */
216                       break;
217                     ++idx1cnt;
218                   }
219
220                 if (backw1_stop >= idx1cnt)
221                   {
222                     /* No sequence at all or just one.  */
223                     if (idx1cnt == idx1max || backw1_stop > idx1cnt)
224                       /* Note that seq1len is still zero.  */
225                       break;
226
227                     backw1_stop = ~0ul;
228                     idx1now = idx1cnt;
229                   }
230                 else
231                   /* We pushed backward sequences.  */
232                   idx1now = backw1 = idx1cnt - 1;
233               }
234           }
235         while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
236
237       /* And the same for string `s2'.  */
238       if (seq2len == 0)
239         do
240           {
241             ++val2;
242
243             if (backw2_stop != ~0ul)
244               {
245                 /* The is something pushed.  */
246                 if (backw2 == backw2_stop)
247                   {
248                     /* The last pushed character was handled.  Continue
249                        with forward characters.  */
250                     if (idx2cnt < idx2max)
251                       {
252                         idx2now = idx2cnt;
253                         backw2_stop = ~0ul;
254                       }
255                     else
256                       /* Nothing anymore.  The backward sequence ended with
257                          the last sequence in the string.  Note that seq2len
258                          is still zero.  */
259                       break;
260                   }
261                 else
262                   idx2now = --backw2;
263               }
264             else
265               {
266                 backw2_stop = idx2max;
267
268                 while (*us2 != L('\0'))
269                   {
270                     int32_t tmp = findidx (&us2);
271                     rule2arr[idx2max] = tmp >> 24;
272                     idx2arr[idx2max] = tmp & 0xffffff;
273                     idx2cnt = idx2max++;
274
275                     if ((rulesets[rule2arr[idx2cnt] * nrules]
276                          & sort_backward) == 0)
277                       /* No more backward characters to push.  */
278                       break;
279                     ++idx2cnt;
280                   }
281
282                 if (backw2_stop >= idx2cnt)
283                   {
284                     /* No sequence at all or just one.  */
285                     if (idx2cnt == idx2max || backw2_stop > idx2cnt)
286                       /* Note that seq1len is still zero.  */
287                       break;
288
289                     backw2_stop = ~0ul;
290                     idx2now = idx2cnt;
291                   }
292                 else
293                   /* We pushed backward sequences.  */
294                   idx2now = backw2 = idx2cnt - 1;
295               }
296           }
297         while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
298
299       /* See whether any or both strings are empty.  */
300       if (seq1len == 0 || seq2len == 0)
301         {
302           if (seq1len == seq2len)
303             /* Both ended.  So far so good, both strings are equal at the
304                first level.  */
305             break;
306
307           /* This means one string is shorter than the other.  Find out
308              which one and return an appropriate value.  */
309           result = seq1len == 0 ? -1 : 1;
310           goto free_and_return;
311         }
312
313       /* Test for position if necessary.  */
314       if (position && val1 != val2)
315         {
316           result = val1 - val2;
317           goto free_and_return;
318         }
319
320       /* Compare the two sequences.  */
321       do
322         {
323           if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
324             {
325               /* The sequences differ.  */
326               result = weights[idx1arr[idx1now]] - weights[idx2arr[idx2now]];
327               goto free_and_return;
328             }
329
330           /* Increment the offsets.  */
331           ++idx1arr[idx1now];
332           ++idx2arr[idx2now];
333
334           --seq1len;
335           --seq2len;
336         }
337       while (seq1len > 0 && seq2len > 0);
338
339       if (position && seq1len != seq2len)
340         {
341           result = seq1len - seq2len;
342           goto free_and_return;
343         }
344     }
345
346   /* Now the remaining passes over the weights.  We now use the
347      indeces we found before.  */
348   for (pass = 1; pass < nrules; ++pass)
349     {
350       /* We assume that if a rule has defined `position' in one section
351          this is true for all of them.  */
352       idx1cnt = 0;
353       idx2cnt = 0;
354       backw1_stop = ~0ul;
355       backw2_stop = ~0ul;
356       backw1 = ~0ul;
357       backw2 = ~0ul;
358       position = rulesets[rule1arr[0] * nrules + pass] & sort_position;
359
360       while (1)
361         {
362           val1 = 0;
363           val2 = 0;
364
365           /* Get the next non-IGNOREd element for string `s1'.  */
366           if (seq1len == 0)
367             do
368               {
369                 ++val1;
370
371                 if (backw1_stop != ~0ul)
372                   {
373                     /* The is something pushed.  */
374                     if (backw1 == backw1_stop)
375                       {
376                         /* The last pushed character was handled.  Continue
377                            with forward characters.  */
378                         if (idx1cnt < idx1max)
379                           {
380                             idx1now = idx1cnt;
381                             backw1_stop = ~0ul;
382                           }
383                         else
384                           {
385                             /* Nothing anymore.  The backward sequence
386                                ended with the last sequence in the string.  */
387                             idx1now = ~0ul;
388                             break;
389                           }
390                       }
391                     else
392                       idx1now = --backw1;
393                   }
394                 else
395                   {
396                     backw1_stop = idx1cnt;
397
398                     while (idx1cnt < idx1max)
399                       {
400                         if ((rulesets[rule1arr[idx1cnt] * nrules + pass]
401                              & sort_backward) == 0)
402                           /* No more backward characters to push.  */
403                           break;
404                         ++idx1cnt;
405                       }
406
407                     if (backw1_stop == idx1cnt)
408                       {
409                         /* No sequence at all or just one.  */
410                         if (idx1cnt == idx1max)
411                           /* Note that seq1len is still zero.  */
412                           break;
413
414                         backw1_stop = ~0ul;
415                         idx1now = idx1cnt++;
416                       }
417                     else
418                       /* We pushed backward sequences.  */
419                       idx1now = backw1 = idx1cnt - 1;
420                   }
421               }
422             while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
423
424           /* And the same for string `s2'.  */
425           if (seq2len == 0)
426             do
427               {
428                 ++val2;
429
430                 if (backw2_stop != ~0ul)
431                   {
432                     /* The is something pushed.  */
433                     if (backw2 == backw2_stop)
434                       {
435                         /* The last pushed character was handled.  Continue
436                            with forward characters.  */
437                         if (idx2cnt < idx2max)
438                           {
439                             idx2now = idx2cnt;
440                             backw2_stop = ~0ul;
441                           }
442                         else
443                           {
444                             /* Nothing anymore.  The backward sequence
445                                ended with the last sequence in the string.  */
446                             idx2now = ~0ul;
447                             break;
448                           }
449                       }
450                     else
451                       idx2now = --backw2;
452                   }
453                 else
454                   {
455                     backw2_stop = idx2cnt;
456
457                     while (idx2cnt < idx2max)
458                       {
459                         if ((rulesets[rule2arr[idx2cnt] * nrules + pass]
460                              & sort_backward) == 0)
461                           /* No more backward characters to push.  */
462                           break;
463                         ++idx2cnt;
464                       }
465
466                     if (backw2_stop == idx2cnt)
467                       {
468                         /* No sequence at all or just one.  */
469                         if (idx2cnt == idx2max)
470                           /* Note that seq2len is still zero.  */
471                           break;
472
473                         backw2_stop = ~0ul;
474                         idx2now = idx2cnt++;
475                       }
476                     else
477                       /* We pushed backward sequences.  */
478                       idx2now = backw2 = idx2cnt - 1;
479                   }
480               }
481             while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
482
483           /* See whether any or both strings are empty.  */
484           if (seq1len == 0 || seq2len == 0)
485             {
486               if (seq1len == seq2len)
487                 /* Both ended.  So far so good, both strings are equal
488                    at this level.  */
489                 break;
490
491               /* This means one string is shorter than the other.  Find out
492                  which one and return an appropriate value.  */
493               result = seq1len == 0 ? -1 : 1;
494               goto free_and_return;
495             }
496
497           /* Test for position if necessary.  */
498           if (position && val1 != val2)
499             {
500               result = val1 - val2;
501               goto free_and_return;
502             }
503
504           /* Compare the two sequences.  */
505           do
506             {
507               if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
508                 {
509                   /* The sequences differ.  */
510                   result = (weights[idx1arr[idx1now]]
511                             - weights[idx2arr[idx2now]]);
512                   goto free_and_return;
513                 }
514
515               /* Increment the offsets.  */
516               ++idx1arr[idx1now];
517               ++idx2arr[idx2now];
518
519               --seq1len;
520               --seq2len;
521             }
522           while (seq1len > 0 && seq2len > 0);
523
524           if (position && seq1len != seq2len)
525             {
526               result = seq1len - seq2len;
527               goto free_and_return;
528             }
529         }
530     }
531
532   /* Free the memory if needed.  */
533  free_and_return:
534   if (use_malloc)
535     free (idx1arr);
536
537   return result;
538 }
539 libc_hidden_def (STRCOLL)
540
541 #ifndef WIDE_CHAR_VERSION
542 weak_alias (__strcoll_l, strcoll_l)
543 #endif