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 <link linkend="setlocale">current locale</link>.
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 * Return value: < 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
367 * <link linkend="setlocale">current locale</link>.
369 * Return value: a newly allocated string. This string should
370 * be freed with g_free() when you are done with it.
373 g_utf8_collate_key (const gchar *str,
380 g_return_val_if_fail (str != NULL, NULL);
381 result = carbon_collate_key (str, len);
383 #elif defined(__STDC_ISO_10646__)
389 gsize result_len = 0;
391 g_return_val_if_fail (str != NULL, NULL);
393 str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);
395 xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
396 result_wc = g_new (wchar_t, xfrm_len + 1);
397 wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);
399 for (i = 0; i < xfrm_len; i++)
400 result_len += utf8_encode (NULL, result_wc[i]);
402 result = g_malloc (result_len + 1);
404 for (i = 0; i < xfrm_len; i++)
405 result_len += utf8_encode (result + result_len, result_wc[i]);
407 result[result_len] = '\0';
413 #else /* !__STDC_ISO_10646__ */
416 const gchar *charset;
419 g_return_val_if_fail (str != NULL, NULL);
421 str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);
425 if (g_get_charset (&charset))
427 xfrm_len = strxfrm (NULL, str_norm, 0);
428 if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
430 result = g_malloc (xfrm_len + 1);
431 strxfrm (result, str_norm, xfrm_len + 1);
436 gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
440 xfrm_len = strxfrm (NULL, str_locale, 0);
441 if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
449 result = g_malloc (xfrm_len + 2);
451 strxfrm (result + 1, str_locale, xfrm_len + 1);
459 xfrm_len = strlen (str_norm);
460 result = g_malloc (xfrm_len + 2);
462 memcpy (result + 1, str_norm, xfrm_len);
463 result[xfrm_len+1] = '\0';
467 #endif /* __STDC_ISO_10646__ */
472 /* This is a collation key that is very very likely to sort before any
473 * collation key that libc strxfrm generates. We use this before any
474 * special case (dot or number) to make sure that its sorted before
477 #define COLLATION_SENTINEL "\1\1\1"
480 * g_utf8_collate_key_for_filename:
481 * @str: a UTF-8 encoded string.
482 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
484 * Converts a string into a collation key that can be compared
485 * with other collation keys produced by the same function using strcmp().
487 * In order to sort filenames correctly, this function treats the dot '.'
488 * as a special case. Most dictionary orderings seem to consider it
489 * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
490 * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
491 * would like to treat numbers intelligently so that "file1" "file10" "file5"
492 * is sorted as "file1" "file5" "file10".
494 * Note that this function depends on the
495 * <link linkend="setlocale">current locale</link>.
497 * Return value: a newly allocated string. This string should
498 * be freed with g_free() when you are done with it.
503 g_utf8_collate_key_for_filename (const gchar *str,
519 * Split the filename into collatable substrings which do
520 * not contain [.0-9] and special-cased substrings. The collatable
521 * substrings are run through the normal g_utf8_collate_key() and the
522 * resulting keys are concatenated with keys generated from the
523 * special-cased substrings.
525 * Special cases: Dots are handled by replacing them with '\1' which
526 * implies that short dot-delimited substrings are before long ones,
533 * Numbers are handled by prepending to each number d-1 superdigits
534 * where d = number of digits in the number and SUPERDIGIT is a
535 * character with an integer value higher than any digit (for instance
536 * ':'). This ensures that single-digit numbers are sorted before
537 * double-digit numbers which in turn are sorted separately from
538 * triple-digit numbers, etc. To avoid strange side-effects when
539 * sorting strings that already contain SUPERDIGITs, a '\2'
540 * is also prepended, like this
546 * file\2::100 (file100)
547 * file:foo (file:foo)
549 * This has the side-effect of sorting numbers before everything else (except
550 * dots), but this is probably OK.
552 * Leading digits are ignored when doing the above. To discriminate
553 * numbers which differ only in the number of leading digits, we append
554 * the number of leading digits as a byte at the very end of the collation
557 * To try avoid conflict with any collation key sequence generated by libc we
558 * start each switch to a special cased part with a sentinel that hopefully
559 * will sort before anything libc will generate.
565 result = g_string_sized_new (len * 2);
566 append = g_string_sized_new (0);
570 /* No need to use utf8 functions, since we're only looking for ascii chars */
571 for (prev = p = str; p < end; p++)
578 collate_key = g_utf8_collate_key (prev, p - prev);
579 g_string_append (result, collate_key);
580 g_free (collate_key);
583 g_string_append (result, COLLATION_SENTINEL "\1");
601 collate_key = g_utf8_collate_key (prev, p - prev);
602 g_string_append (result, collate_key);
603 g_free (collate_key);
606 g_string_append (result, COLLATION_SENTINEL "\2");
610 /* write d-1 colons */
624 if (*p == '0' && !digits)
626 else if (g_ascii_isdigit(*p))
630 /* count an all-zero sequence as
631 * one digit plus leading zeros
644 g_string_append_c (result, ':');
648 if (leading_zeros > 0)
650 g_string_append_c (append, (char)leading_zeros);
651 prev += leading_zeros;
654 /* write the number itself */
655 g_string_append_len (result, prev, p - prev);
658 --p; /* go one step back to avoid disturbing outer loop */
662 /* other characters just accumulate */
669 collate_key = g_utf8_collate_key (prev, p - prev);
670 g_string_append (result, collate_key);
671 g_free (collate_key);
674 g_string_append (result, append->str);
675 g_string_free (append, TRUE);
677 return g_string_free (result, FALSE);
678 #else /* HAVE_CARBON */
679 return carbon_collate_key_for_filename (str, len);