1 /* gunicollate.c - Collation
3 * Copyright 2001,2005 Red Hat, Inc.
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.
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.
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/>.
24 #ifdef __STDC_ISO_10646__
29 #include <CoreServices/CoreServices.h>
34 #include "gunicodeprivate.h"
36 #include "gstrfuncs.h"
37 #include "gtestutils.h"
39 #ifndef __STDC_ISO_10646__
45 /* Workaround for bug in MSVCR80.DLL */
47 msc_strxfrm_wrapper (char *string1
,
51 if (!string1
|| count
<= 0)
55 return strxfrm (&tmp
, string2
, 1);
57 return strxfrm (string1
, string2
, count
);
59 #define strxfrm msc_strxfrm_wrapper
64 * @str1: a UTF-8 encoded string
65 * @str2: a UTF-8 encoded string
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.
74 * Returns: < 0 if @str1 compares before @str2,
75 * 0 if they compare equal, > 0 if @str1 compares after @str2.
78 g_utf8_collate (const gchar
*str1
,
91 g_return_val_if_fail (str1
!= NULL
, 0);
92 g_return_val_if_fail (str2
!= NULL
, 0);
94 str1_utf16
= g_utf8_to_utf16 (str1
, -1, NULL
, &len1
, NULL
);
95 str2_utf16
= g_utf8_to_utf16 (str2
, -1, NULL
, &len2
, NULL
);
97 UCCompareTextDefault (kUCCollateStandardOptions
,
98 str1_utf16
, len1
, str2_utf16
, len2
,
105 #elif defined(__STDC_ISO_10646__)
110 g_return_val_if_fail (str1
!= NULL
, 0);
111 g_return_val_if_fail (str2
!= NULL
, 0);
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
);
116 result
= wcscoll ((wchar_t *)str1_norm
, (wchar_t *)str2_norm
);
121 #else /* !__STDC_ISO_10646__ */
123 const gchar
*charset
;
127 g_return_val_if_fail (str1
!= NULL
, 0);
128 g_return_val_if_fail (str2
!= NULL
, 0);
130 str1_norm
= g_utf8_normalize (str1
, -1, G_NORMALIZE_ALL_COMPOSE
);
131 str2_norm
= g_utf8_normalize (str2
, -1, G_NORMALIZE_ALL_COMPOSE
);
133 if (g_get_charset (&charset
))
135 result
= strcoll (str1_norm
, str2_norm
);
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
);
142 if (str1_locale
&& str2_locale
)
143 result
= strcoll (str1_locale
, str2_locale
);
144 else if (str1_locale
)
146 else if (str2_locale
)
149 result
= strcmp (str1_norm
, str2_norm
);
151 g_free (str1_locale
);
152 g_free (str2_locale
);
158 #endif /* __STDC_ISO_10646__ */
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.
168 * The following routine is taken (with modification) from GNU
169 * libc's strxfrm routine:
171 * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
172 * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
175 utf8_encode (char *buf
, wchar_t val
)
189 for (step
= 2; step
< 6; ++step
)
190 if ((val
& (~(guint32
)0 << (5 * step
+ 1))) == 0)
196 *buf
= (unsigned char) (~0xff >> step
);
200 buf
[step
] = 0x80 | (val
& 0x3f);
210 #endif /* __STDC_ISO_10646__ || HAVE_CARBON */
215 collate_key_to_string (UCCollationValue
*key
,
219 gsize result_len
= 0;
220 const gsize start
= 2 * sizeof (void *) / sizeof (UCCollationValue
);
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.
228 if (key_len
<= start
)
229 return g_strdup ("");
231 for (i
= start
; i
< key_len
; i
++)
232 result_len
+= utf8_encode (NULL
, g_htonl (key
[i
] + 1));
234 result
= g_malloc (result_len
+ 1);
236 for (i
= start
; i
< key_len
; i
++)
237 result_len
+= utf8_encode (result
+ result_len
, g_htonl (key
[i
] + 1));
239 result
[result_len
] = '\0';
245 carbon_collate_key_with_collator (const gchar
*str
,
247 CollatorRef collator
)
249 UniChar
*str_utf16
= NULL
;
252 UCCollationValue staticbuf
[512];
253 UCCollationValue
*freeme
= NULL
;
254 UCCollationValue
*buf
;
258 gchar
*result
= NULL
;
260 str_utf16
= g_utf8_to_utf16 (str
, len
, NULL
, &len_utf16
, NULL
);
261 try_len
= len_utf16
* 5 + 2;
263 if (try_len
<= sizeof staticbuf
)
266 buf_len
= sizeof staticbuf
;
270 freeme
= g_new (UCCollationValue
, try_len
);
275 ret
= UCGetCollationKey (collator
, str_utf16
, len_utf16
,
276 buf_len
, &key_len
, buf
);
278 if (ret
== kCollateBufferTooSmall
)
280 freeme
= g_renew (UCCollationValue
, freeme
, try_len
* 2);
282 buf_len
= try_len
* 2;
283 ret
= UCGetCollationKey (collator
, str_utf16
, len_utf16
,
284 buf_len
, &key_len
, buf
);
288 result
= collate_key_to_string (buf
, key_len
);
290 result
= g_strdup ("");
298 carbon_collate_key (const gchar
*str
,
301 static CollatorRef collator
;
303 if (G_UNLIKELY (!collator
))
305 UCCreateCollator (NULL
, 0, kUCCollateStandardOptions
, &collator
);
309 static gboolean been_here
;
311 g_warning ("%s: UCCreateCollator failed", G_STRLOC
);
313 return g_strdup ("");
317 return carbon_collate_key_with_collator (str
, len
, collator
);
321 carbon_collate_key_for_filename (const gchar
*str
,
324 static CollatorRef collator
;
326 if (G_UNLIKELY (!collator
))
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
,
340 static gboolean been_here
;
342 g_warning ("%s: UCCreateCollator failed", G_STRLOC
);
344 return g_strdup ("");
348 return carbon_collate_key_with_collator (str
, len
, collator
);
351 #endif /* HAVE_CARBON */
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.
358 * Converts a string into a collation key that can be compared
359 * with other collation keys produced by the same function using
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().
366 * Note that this function depends on the [current locale][setlocale].
368 * Returns: a newly allocated string. This string should
369 * be freed with g_free() when you are done with it.
372 g_utf8_collate_key (const gchar
*str
,
379 g_return_val_if_fail (str
!= NULL
, NULL
);
380 result
= carbon_collate_key (str
, len
);
382 #elif defined(__STDC_ISO_10646__)
388 gsize result_len
= 0;
390 g_return_val_if_fail (str
!= NULL
, NULL
);
392 str_norm
= _g_utf8_normalize_wc (str
, len
, G_NORMALIZE_ALL_COMPOSE
);
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);
398 for (i
= 0; i
< xfrm_len
; i
++)
399 result_len
+= utf8_encode (NULL
, result_wc
[i
]);
401 result
= g_malloc (result_len
+ 1);
403 for (i
= 0; i
< xfrm_len
; i
++)
404 result_len
+= utf8_encode (result
+ result_len
, result_wc
[i
]);
406 result
[result_len
] = '\0';
412 #else /* !__STDC_ISO_10646__ */
415 const gchar
*charset
;
418 g_return_val_if_fail (str
!= NULL
, NULL
);
420 str_norm
= g_utf8_normalize (str
, len
, G_NORMALIZE_ALL_COMPOSE
);
424 if (g_get_charset (&charset
))
426 xfrm_len
= strxfrm (NULL
, str_norm
, 0);
427 if (xfrm_len
>= 0 && xfrm_len
< G_MAXINT
- 2)
429 result
= g_malloc (xfrm_len
+ 1);
430 strxfrm (result
, str_norm
, xfrm_len
+ 1);
435 gchar
*str_locale
= g_convert (str_norm
, -1, charset
, "UTF-8", NULL
, NULL
, NULL
);
439 xfrm_len
= strxfrm (NULL
, str_locale
, 0);
440 if (xfrm_len
< 0 || xfrm_len
>= G_MAXINT
- 2)
448 result
= g_malloc (xfrm_len
+ 2);
450 strxfrm (result
+ 1, str_locale
, xfrm_len
+ 1);
458 xfrm_len
= strlen (str_norm
);
459 result
= g_malloc (xfrm_len
+ 2);
461 memcpy (result
+ 1, str_norm
, xfrm_len
);
462 result
[xfrm_len
+1] = '\0';
466 #endif /* __STDC_ISO_10646__ */
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
476 #define COLLATION_SENTINEL "\1\1\1"
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.
483 * Converts a string into a collation key that can be compared
484 * with other collation keys produced by the same function using strcmp().
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".
493 * Note that this function depends on the [current locale][setlocale].
495 * Returns: a newly allocated string. This string should
496 * be freed with g_free() when you are done with it.
501 g_utf8_collate_key_for_filename (const gchar
*str
,
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.
523 * Special cases: Dots are handled by replacing them with '\1' which
524 * implies that short dot-delimited substrings are before long ones,
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
544 * file\2::100 (file100)
545 * file:foo (file:foo)
547 * This has the side-effect of sorting numbers before everything else (except
548 * dots), but this is probably OK.
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
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.
563 result
= g_string_sized_new (len
* 2);
564 append
= g_string_sized_new (0);
568 /* No need to use utf8 functions, since we're only looking for ascii chars */
569 for (prev
= p
= str
; p
< end
; p
++)
576 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
577 g_string_append (result
, collate_key
);
578 g_free (collate_key
);
581 g_string_append (result
, COLLATION_SENTINEL
"\1");
599 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
600 g_string_append (result
, collate_key
);
601 g_free (collate_key
);
604 g_string_append (result
, COLLATION_SENTINEL
"\2");
608 /* write d-1 colons */
622 if (*p
== '0' && !digits
)
624 else if (g_ascii_isdigit(*p
))
628 /* count an all-zero sequence as
629 * one digit plus leading zeros
642 g_string_append_c (result
, ':');
646 if (leading_zeros
> 0)
648 g_string_append_c (append
, (char)leading_zeros
);
649 prev
+= leading_zeros
;
652 /* write the number itself */
653 g_string_append_len (result
, prev
, p
- prev
);
656 --p
; /* go one step back to avoid disturbing outer loop */
660 /* other characters just accumulate */
667 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
668 g_string_append (result
, collate_key
);
669 g_free (collate_key
);
672 g_string_append (result
, append
->str
);
673 g_string_free (append
, TRUE
);
675 return g_string_free (result
, FALSE
);
676 #else /* HAVE_CARBON */
677 return carbon_collate_key_for_filename (str
, len
);