nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /* gunicollate.c - Collation
2 *
3 * Copyright 2001,2005 Red Hat, Inc.
4 *
5 * The Gnome Library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser 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.
9 *
10 * The Gnome 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 Gnome Library; see the file COPYING.LIB. If not,
17 * see <http://www.gnu.org/licenses/>.
18 */
19  
20 #include "config.h"
21  
22 #include <locale.h>
23 #include <string.h>
24 #ifdef __STDC_ISO_10646__
25 #include <wchar.h>
26 #endif
27  
28 #ifdef HAVE_CARBON
29 #include <CoreServices/CoreServices.h>
30 #endif
31  
32 #include "gmem.h"
33 #include "gunicode.h"
34 #include "gunicodeprivate.h"
35 #include "gstring.h"
36 #include "gstrfuncs.h"
37 #include "gtestutils.h"
38 #include "gcharset.h"
39 #ifndef __STDC_ISO_10646__
40 #include "gconvert.h"
41 #endif
42  
43  
44 #ifdef _MSC_VER
45 /* Workaround for bug in MSVCR80.DLL */
46 static gsize
47 msc_strxfrm_wrapper (char *string1,
48 const char *string2,
49 gsize count)
50 {
51 if (!string1 || count <= 0)
52 {
53 char tmp;
54  
55 return strxfrm (&tmp, string2, 1);
56 }
57 return strxfrm (string1, string2, count);
58 }
59 #define strxfrm msc_strxfrm_wrapper
60 #endif
61  
62 /**
63 * g_utf8_collate:
64 * @str1: a UTF-8 encoded string
65 * @str2: a UTF-8 encoded string
66 *
67 * Compares two strings for ordering using the linguistically
68 * correct rules for the [current locale][setlocale].
69 * When sorting a large number of strings, it will be significantly
70 * faster to obtain collation keys with g_utf8_collate_key() and
71 * compare the keys with strcmp() when sorting instead of sorting
72 * the original strings.
73 *
74 * Returns: < 0 if @str1 compares before @str2,
75 * 0 if they compare equal, > 0 if @str1 compares after @str2.
76 **/
77 gint
78 g_utf8_collate (const gchar *str1,
79 const gchar *str2)
80 {
81 gint result;
82  
83 #ifdef HAVE_CARBON
84  
85 UniChar *str1_utf16;
86 UniChar *str2_utf16;
87 glong len1;
88 glong len2;
89 SInt32 retval = 0;
90  
91 g_return_val_if_fail (str1 != NULL, 0);
92 g_return_val_if_fail (str2 != NULL, 0);
93  
94 str1_utf16 = g_utf8_to_utf16 (str1, -1, NULL, &len1, NULL);
95 str2_utf16 = g_utf8_to_utf16 (str2, -1, NULL, &len2, NULL);
96  
97 UCCompareTextDefault (kUCCollateStandardOptions,
98 str1_utf16, len1, str2_utf16, len2,
99 NULL, &retval);
100 result = retval;
101  
102 g_free (str2_utf16);
103 g_free (str1_utf16);
104  
105 #elif defined(__STDC_ISO_10646__)
106  
107 gunichar *str1_norm;
108 gunichar *str2_norm;
109  
110 g_return_val_if_fail (str1 != NULL, 0);
111 g_return_val_if_fail (str2 != NULL, 0);
112  
113 str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);
114 str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);
115  
116 result = wcscoll ((wchar_t *)str1_norm, (wchar_t *)str2_norm);
117  
118 g_free (str1_norm);
119 g_free (str2_norm);
120  
121 #else /* !__STDC_ISO_10646__ */
122  
123 const gchar *charset;
124 gchar *str1_norm;
125 gchar *str2_norm;
126  
127 g_return_val_if_fail (str1 != NULL, 0);
128 g_return_val_if_fail (str2 != NULL, 0);
129  
130 str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);
131 str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);
132  
133 if (g_get_charset (&charset))
134 {
135 result = strcoll (str1_norm, str2_norm);
136 }
137 else
138 {
139 gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
140 gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
141  
142 if (str1_locale && str2_locale)
143 result = strcoll (str1_locale, str2_locale);
144 else if (str1_locale)
145 result = -1;
146 else if (str2_locale)
147 result = 1;
148 else
149 result = strcmp (str1_norm, str2_norm);
150  
151 g_free (str1_locale);
152 g_free (str2_locale);
153 }
154  
155 g_free (str1_norm);
156 g_free (str2_norm);
157  
158 #endif /* __STDC_ISO_10646__ */
159  
160 return result;
161 }
162  
163 #if defined(__STDC_ISO_10646__) || defined(HAVE_CARBON)
164 /* We need UTF-8 encoding of numbers to encode the weights if
165 * we are using wcsxfrm. However, we aren't encoding Unicode
166 * characters, so we can't simply use g_unichar_to_utf8.
167 *
168 * The following routine is taken (with modification) from GNU
169 * libc's strxfrm routine:
170 *
171 * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
172 * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
173 */
174 static inline int
175 utf8_encode (char *buf, wchar_t val)
176 {
177 int retval;
178  
179 if (val < 0x80)
180 {
181 if (buf)
182 *buf++ = (char) val;
183 retval = 1;
184 }
185 else
186 {
187 int step;
188  
189 for (step = 2; step < 6; ++step)
190 if ((val & (~(guint32)0 << (5 * step + 1))) == 0)
191 break;
192 retval = step;
193  
194 if (buf)
195 {
196 *buf = (unsigned char) (~0xff >> step);
197 --step;
198 do
199 {
200 buf[step] = 0x80 | (val & 0x3f);
201 val >>= 6;
202 }
203 while (--step > 0);
204 *buf |= val;
205 }
206 }
207  
208 return retval;
209 }
210 #endif /* __STDC_ISO_10646__ || HAVE_CARBON */
211  
212 #ifdef HAVE_CARBON
213  
214 static gchar *
215 collate_key_to_string (UCCollationValue *key,
216 gsize key_len)
217 {
218 gchar *result;
219 gsize result_len = 0;
220 const gsize start = 2 * sizeof (void *) / sizeof (UCCollationValue);
221 gsize i;
222  
223 /* The first codes should be skipped: the same string on the same
224 * system can get different values at runtime in those positions,
225 * and they do not sort correctly. The exact size of the prefix
226 * depends on whether we are building 64 or 32 bit.
227 */
228 if (key_len <= start)
229 return g_strdup ("");
230  
231 for (i = start; i < key_len; i++)
232 result_len += utf8_encode (NULL, g_htonl (key[i] + 1));
233  
234 result = g_malloc (result_len + 1);
235 result_len = 0;
236 for (i = start; i < key_len; i++)
237 result_len += utf8_encode (result + result_len, g_htonl (key[i] + 1));
238  
239 result[result_len] = '\0';
240  
241 return result;
242 }
243  
244 static gchar *
245 carbon_collate_key_with_collator (const gchar *str,
246 gssize len,
247 CollatorRef collator)
248 {
249 UniChar *str_utf16 = NULL;
250 glong len_utf16;
251 OSStatus ret;
252 UCCollationValue staticbuf[512];
253 UCCollationValue *freeme = NULL;
254 UCCollationValue *buf;
255 ItemCount buf_len;
256 ItemCount key_len;
257 ItemCount try_len;
258 gchar *result = NULL;
259  
260 str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);
261 try_len = len_utf16 * 5 + 2;
262  
263 if (try_len <= sizeof staticbuf)
264 {
265 buf = staticbuf;
266 buf_len = sizeof staticbuf;
267 }
268 else
269 {
270 freeme = g_new (UCCollationValue, try_len);
271 buf = freeme;
272 buf_len = try_len;
273 }
274  
275 ret = UCGetCollationKey (collator, str_utf16, len_utf16,
276 buf_len, &key_len, buf);
277  
278 if (ret == kCollateBufferTooSmall)
279 {
280 freeme = g_renew (UCCollationValue, freeme, try_len * 2);
281 buf = freeme;
282 buf_len = try_len * 2;
283 ret = UCGetCollationKey (collator, str_utf16, len_utf16,
284 buf_len, &key_len, buf);
285 }
286  
287 if (ret == 0)
288 result = collate_key_to_string (buf, key_len);
289 else
290 result = g_strdup ("");
291  
292 g_free (freeme);
293 g_free (str_utf16);
294 return result;
295 }
296  
297 static gchar *
298 carbon_collate_key (const gchar *str,
299 gssize len)
300 {
301 static CollatorRef collator;
302  
303 if (G_UNLIKELY (!collator))
304 {
305 UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);
306  
307 if (!collator)
308 {
309 static gboolean been_here;
310 if (!been_here)
311 g_warning ("%s: UCCreateCollator failed", G_STRLOC);
312 been_here = TRUE;
313 return g_strdup ("");
314 }
315 }
316  
317 return carbon_collate_key_with_collator (str, len, collator);
318 }
319  
320 static gchar *
321 carbon_collate_key_for_filename (const gchar *str,
322 gssize len)
323 {
324 static CollatorRef collator;
325  
326 if (G_UNLIKELY (!collator))
327 {
328 /* http://developer.apple.com/qa/qa2004/qa1159.html */
329 UCCreateCollator (NULL, 0,
330 kUCCollateComposeInsensitiveMask
331 | kUCCollateWidthInsensitiveMask
332 | kUCCollateCaseInsensitiveMask
333 | kUCCollateDigitsOverrideMask
334 | kUCCollateDigitsAsNumberMask
335 | kUCCollatePunctuationSignificantMask,
336 &collator);
337  
338 if (!collator)
339 {
340 static gboolean been_here;
341 if (!been_here)
342 g_warning ("%s: UCCreateCollator failed", G_STRLOC);
343 been_here = TRUE;
344 return g_strdup ("");
345 }
346 }
347  
348 return carbon_collate_key_with_collator (str, len, collator);
349 }
350  
351 #endif /* HAVE_CARBON */
352  
353 /**
354 * g_utf8_collate_key:
355 * @str: a UTF-8 encoded string.
356 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
357 *
358 * Converts a string into a collation key that can be compared
359 * with other collation keys produced by the same function using
360 * strcmp().
361 *
362 * The results of comparing the collation keys of two strings
363 * with strcmp() will always be the same as comparing the two
364 * original keys with g_utf8_collate().
365 *
366 * Note that this function depends on the [current locale][setlocale].
367 *
368 * Returns: a newly allocated string. This string should
369 * be freed with g_free() when you are done with it.
370 **/
371 gchar *
372 g_utf8_collate_key (const gchar *str,
373 gssize len)
374 {
375 gchar *result;
376  
377 #ifdef HAVE_CARBON
378  
379 g_return_val_if_fail (str != NULL, NULL);
380 result = carbon_collate_key (str, len);
381  
382 #elif defined(__STDC_ISO_10646__)
383  
384 gsize xfrm_len;
385 gunichar *str_norm;
386 wchar_t *result_wc;
387 gsize i;
388 gsize result_len = 0;
389  
390 g_return_val_if_fail (str != NULL, NULL);
391  
392 str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);
393  
394 xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
395 result_wc = g_new (wchar_t, xfrm_len + 1);
396 wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);
397  
398 for (i = 0; i < xfrm_len; i++)
399 result_len += utf8_encode (NULL, result_wc[i]);
400  
401 result = g_malloc (result_len + 1);
402 result_len = 0;
403 for (i = 0; i < xfrm_len; i++)
404 result_len += utf8_encode (result + result_len, result_wc[i]);
405  
406 result[result_len] = '\0';
407  
408 g_free (result_wc);
409 g_free (str_norm);
410  
411 return result;
412 #else /* !__STDC_ISO_10646__ */
413  
414 gsize xfrm_len;
415 const gchar *charset;
416 gchar *str_norm;
417  
418 g_return_val_if_fail (str != NULL, NULL);
419  
420 str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);
421  
422 result = NULL;
423  
424 if (g_get_charset (&charset))
425 {
426 xfrm_len = strxfrm (NULL, str_norm, 0);
427 if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
428 {
429 result = g_malloc (xfrm_len + 1);
430 strxfrm (result, str_norm, xfrm_len + 1);
431 }
432 }
433 else
434 {
435 gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
436  
437 if (str_locale)
438 {
439 xfrm_len = strxfrm (NULL, str_locale, 0);
440 if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
441 {
442 g_free (str_locale);
443 str_locale = NULL;
444 }
445 }
446 if (str_locale)
447 {
448 result = g_malloc (xfrm_len + 2);
449 result[0] = 'A';
450 strxfrm (result + 1, str_locale, xfrm_len + 1);
451  
452 g_free (str_locale);
453 }
454 }
455  
456 if (!result)
457 {
458 xfrm_len = strlen (str_norm);
459 result = g_malloc (xfrm_len + 2);
460 result[0] = 'B';
461 memcpy (result + 1, str_norm, xfrm_len);
462 result[xfrm_len+1] = '\0';
463 }
464  
465 g_free (str_norm);
466 #endif /* __STDC_ISO_10646__ */
467  
468 return result;
469 }
470  
471 /* This is a collation key that is very very likely to sort before any
472 * collation key that libc strxfrm generates. We use this before any
473 * special case (dot or number) to make sure that its sorted before
474 * anything else.
475 */
476 #define COLLATION_SENTINEL "\1\1\1"
477  
478 /**
479 * g_utf8_collate_key_for_filename:
480 * @str: a UTF-8 encoded string.
481 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
482 *
483 * Converts a string into a collation key that can be compared
484 * with other collation keys produced by the same function using strcmp().
485 *
486 * In order to sort filenames correctly, this function treats the dot '.'
487 * as a special case. Most dictionary orderings seem to consider it
488 * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
489 * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
490 * would like to treat numbers intelligently so that "file1" "file10" "file5"
491 * is sorted as "file1" "file5" "file10".
492 *
493 * Note that this function depends on the [current locale][setlocale].
494 *
495 * Returns: a newly allocated string. This string should
496 * be freed with g_free() when you are done with it.
497 *
498 * Since: 2.8
499 */
500 gchar *
501 g_utf8_collate_key_for_filename (const gchar *str,
502 gssize len)
503 {
504 #ifndef HAVE_CARBON
505 GString *result;
506 GString *append;
507 const gchar *p;
508 const gchar *prev;
509 const gchar *end;
510 gchar *collate_key;
511 gint digits;
512 gint leading_zeros;
513  
514 /*
515 * How it works:
516 *
517 * Split the filename into collatable substrings which do
518 * not contain [.0-9] and special-cased substrings. The collatable
519 * substrings are run through the normal g_utf8_collate_key() and the
520 * resulting keys are concatenated with keys generated from the
521 * special-cased substrings.
522 *
523 * Special cases: Dots are handled by replacing them with '\1' which
524 * implies that short dot-delimited substrings are before long ones,
525 * e.g.
526 *
527 * a\1a (a.a)
528 * a-\1a (a-.a)
529 * aa\1a (aa.a)
530 *
531 * Numbers are handled by prepending to each number d-1 superdigits
532 * where d = number of digits in the number and SUPERDIGIT is a
533 * character with an integer value higher than any digit (for instance
534 * ':'). This ensures that single-digit numbers are sorted before
535 * double-digit numbers which in turn are sorted separately from
536 * triple-digit numbers, etc. To avoid strange side-effects when
537 * sorting strings that already contain SUPERDIGITs, a '\2'
538 * is also prepended, like this
539 *
540 * file\21 (file1)
541 * file\25 (file5)
542 * file\2:10 (file10)
543 * file\2:26 (file26)
544 * file\2::100 (file100)
545 * file:foo (file:foo)
546 *
547 * This has the side-effect of sorting numbers before everything else (except
548 * dots), but this is probably OK.
549 *
550 * Leading digits are ignored when doing the above. To discriminate
551 * numbers which differ only in the number of leading digits, we append
552 * the number of leading digits as a byte at the very end of the collation
553 * key.
554 *
555 * To try avoid conflict with any collation key sequence generated by libc we
556 * start each switch to a special cased part with a sentinel that hopefully
557 * will sort before anything libc will generate.
558 */
559  
560 if (len < 0)
561 len = strlen (str);
562  
563 result = g_string_sized_new (len * 2);
564 append = g_string_sized_new (0);
565  
566 end = str + len;
567  
568 /* No need to use utf8 functions, since we're only looking for ascii chars */
569 for (prev = p = str; p < end; p++)
570 {
571 switch (*p)
572 {
573 case '.':
574 if (prev != p)
575 {
576 collate_key = g_utf8_collate_key (prev, p - prev);
577 g_string_append (result, collate_key);
578 g_free (collate_key);
579 }
580  
581 g_string_append (result, COLLATION_SENTINEL "\1");
582  
583 /* skip the dot */
584 prev = p + 1;
585 break;
586  
587 case '0':
588 case '1':
589 case '2':
590 case '3':
591 case '4':
592 case '5':
593 case '6':
594 case '7':
595 case '8':
596 case '9':
597 if (prev != p)
598 {
599 collate_key = g_utf8_collate_key (prev, p - prev);
600 g_string_append (result, collate_key);
601 g_free (collate_key);
602 }
603  
604 g_string_append (result, COLLATION_SENTINEL "\2");
605  
606 prev = p;
607  
608 /* write d-1 colons */
609 if (*p == '0')
610 {
611 leading_zeros = 1;
612 digits = 0;
613 }
614 else
615 {
616 leading_zeros = 0;
617 digits = 1;
618 }
619  
620 while (++p < end)
621 {
622 if (*p == '0' && !digits)
623 ++leading_zeros;
624 else if (g_ascii_isdigit(*p))
625 ++digits;
626 else
627 {
628 /* count an all-zero sequence as
629 * one digit plus leading zeros
630 */
631 if (!digits)
632 {
633 ++digits;
634 --leading_zeros;
635 }
636 break;
637 }
638 }
639  
640 while (digits > 1)
641 {
642 g_string_append_c (result, ':');
643 --digits;
644 }
645  
646 if (leading_zeros > 0)
647 {
648 g_string_append_c (append, (char)leading_zeros);
649 prev += leading_zeros;
650 }
651  
652 /* write the number itself */
653 g_string_append_len (result, prev, p - prev);
654  
655 prev = p;
656 --p; /* go one step back to avoid disturbing outer loop */
657 break;
658  
659 default:
660 /* other characters just accumulate */
661 break;
662 }
663 }
664  
665 if (prev != p)
666 {
667 collate_key = g_utf8_collate_key (prev, p - prev);
668 g_string_append (result, collate_key);
669 g_free (collate_key);
670 }
671  
672 g_string_append (result, append->str);
673 g_string_free (append, TRUE);
674  
675 return g_string_free (result, FALSE);
676 #else /* HAVE_CARBON */
677 return carbon_collate_key_for_filename (str, len);
678 #endif
679 }