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 * write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
25 #ifdef __STDC_ISO_10646__
30 #include "gunicodeprivate.h"
34 /* Workaround for bug in MSVCR80.DLL */
36 msc_strxfrm_wrapper (char *string1,
40 if (!string1 || count <= 0)
44 return strxfrm (&tmp, string2, 1);
46 return strxfrm (string1, string2, count);
48 #define strxfrm msc_strxfrm_wrapper
53 * @str1: a UTF-8 encoded string
54 * @str2: a UTF-8 encoded string
56 * Compares two strings for ordering using the linguistically
57 * correct rules for the <link linkend="setlocale">current locale</link>.
58 * When sorting a large number of strings, it will be significantly
59 * faster to obtain collation keys with g_utf8_collate_key() and
60 * compare the keys with strcmp() when sorting instead of sorting
61 * the original strings.
63 * Return value: < 0 if @str1 compares before @str2,
64 * 0 if they compare equal, > 0 if @str1 compares after @str2.
67 g_utf8_collate (const gchar *str1,
72 #ifdef __STDC_ISO_10646__
77 g_return_val_if_fail (str1 != NULL, 0);
78 g_return_val_if_fail (str2 != NULL, 0);
80 str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);
81 str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);
83 result = wcscoll ((wchar_t *)str1_norm, (wchar_t *)str2_norm);
88 #else /* !__STDC_ISO_10646__ */
94 g_return_val_if_fail (str1 != NULL, 0);
95 g_return_val_if_fail (str2 != NULL, 0);
97 str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);
98 str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);
100 if (g_get_charset (&charset))
102 result = strcoll (str1_norm, str2_norm);
106 gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
107 gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
109 if (str1_locale && str2_locale)
110 result = strcoll (str1_locale, str2_locale);
111 else if (str1_locale)
113 else if (str2_locale)
116 result = strcmp (str1_norm, str2_norm);
118 g_free (str1_locale);
119 g_free (str2_locale);
125 #endif /* __STDC_ISO_10646__ */
130 #ifdef __STDC_ISO_10646__
131 /* We need UTF-8 encoding of numbers to encode the weights if
132 * we are using wcsxfrm. However, we aren't encoding Unicode
133 * characters, so we can't simply use g_unichar_to_utf8.
135 * The following routine is taken (with modification) from GNU
136 * libc's strxfrm routine:
138 * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
139 * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
142 utf8_encode (char *buf, wchar_t val)
156 for (step = 2; step < 6; ++step)
157 if ((val & (~(guint32)0 << (5 * step + 1))) == 0)
163 *buf = (unsigned char) (~0xff >> step);
167 buf[step] = 0x80 | (val & 0x3f);
177 #endif /* __STDC_ISO_10646__ */
180 * g_utf8_collate_key:
181 * @str: a UTF-8 encoded string.
182 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
184 * Converts a string into a collation key that can be compared
185 * with other collation keys produced by the same function using
188 * The results of comparing the collation keys of two strings
189 * with strcmp() will always be the same as comparing the two
190 * original keys with g_utf8_collate().
192 * Note that this function depends on the
193 * <link linkend="setlocale">current locale</link>.
195 * Return value: a newly allocated string. This string should
196 * be freed with g_free() when you are done with it.
199 g_utf8_collate_key (const gchar *str,
205 #ifdef __STDC_ISO_10646__
210 gsize result_len = 0;
212 g_return_val_if_fail (str != NULL, NULL);
214 str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);
216 xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
217 result_wc = g_new (wchar_t, xfrm_len + 1);
218 wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);
220 for (i=0; i < xfrm_len; i++)
221 result_len += utf8_encode (NULL, result_wc[i]);
223 result = g_malloc (result_len + 1);
225 for (i=0; i < xfrm_len; i++)
226 result_len += utf8_encode (result + result_len, result_wc[i]);
228 result[result_len] = '\0';
234 #else /* !__STDC_ISO_10646__ */
236 const gchar *charset;
239 g_return_val_if_fail (str != NULL, NULL);
241 str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);
243 if (g_get_charset (&charset))
245 xfrm_len = strxfrm (NULL, str_norm, 0);
246 result = g_malloc (xfrm_len + 1);
247 strxfrm (result, str_norm, xfrm_len + 1);
251 gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
255 xfrm_len = strxfrm (NULL, str_locale, 0);
256 if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
264 result = g_malloc (xfrm_len + 2);
266 strxfrm (result + 1, str_locale, xfrm_len + 1);
272 xfrm_len = strlen (str_norm);
273 result = g_malloc (xfrm_len + 2);
275 memcpy (result + 1, str_norm, xfrm_len);
276 result[xfrm_len+1] = '\0';
281 #endif /* __STDC_ISO_10646__ */
286 /* This is a collation key that is very very likely to sort before any
287 collation key that libc strxfrm generates. We use this before any
288 special case (dot or number) to make sure that its sorted before
291 #define COLLATION_SENTINEL "\1\1\1"
294 * g_utf8_collate_key_for_filename:
295 * @str: a UTF-8 encoded string.
296 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
298 * Converts a string into a collation key that can be compared
299 * with other collation keys produced by the same function using strcmp().
301 * In order to sort filenames correctly, this function treats the dot '.'
302 * as a special case. Most dictionary orderings seem to consider it
303 * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
304 * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
305 * would like to treat numbers intelligently so that "file1" "file10" "file5"
306 * is sorted as "file1" "file5" "file10".
308 * Note that this function depends on the
309 * <link linkend="setlocale">current locale</link>.
311 * Return value: a newly allocated string. This string should
312 * be freed with g_free() when you are done with it.
317 g_utf8_collate_key_for_filename (const gchar *str,
332 * Split the filename into collatable substrings which do
333 * not contain [.0-9] and special-cased substrings. The collatable
334 * substrings are run through the normal g_utf8_collate_key() and the
335 * resulting keys are concatenated with keys generated from the
336 * special-cased substrings.
338 * Special cases: Dots are handled by replacing them with '\1' which
339 * implies that short dot-delimited substrings are before long ones,
346 * Numbers are handled by prepending to each number d-1 superdigits
347 * where d = number of digits in the number and SUPERDIGIT is a
348 * character with an integer value higher than any digit (for instance
349 * ':'). This ensures that single-digit numbers are sorted before
350 * double-digit numbers which in turn are sorted separately from
351 * triple-digit numbers, etc. To avoid strange side-effects when
352 * sorting strings that already contain SUPERDIGITs, a '\2'
353 * is also prepended, like this
359 * file\2::100 (file100)
360 * file:foo (file:foo)
362 * This has the side-effect of sorting numbers before everything else (except
363 * dots), but this is probably OK.
365 * Leading digits are ignored when doing the above. To discriminate
366 * numbers which differ only in the number of leading digits, we append
367 * the number of leading digits as a byte at the very end of the collation
370 * To try avoid conflict with any collation key sequence generated by libc we
371 * start each switch to a special cased part with a sentinel that hopefully
372 * will sort before anything libc will generate.
378 result = g_string_sized_new (len * 2);
379 append = g_string_sized_new (0);
383 /* No need to use utf8 functions, since we're only looking for ascii chars */
384 for (prev = p = str; p < end; p++)
391 collate_key = g_utf8_collate_key (prev, p - prev);
392 g_string_append (result, collate_key);
393 g_free (collate_key);
396 g_string_append (result, COLLATION_SENTINEL "\1");
414 collate_key = g_utf8_collate_key (prev, p - prev);
415 g_string_append (result, collate_key);
416 g_free (collate_key);
419 g_string_append (result, COLLATION_SENTINEL "\2");
423 /* write d-1 colons */
437 if (*p == '0' && !digits)
439 else if (g_ascii_isdigit(*p))
443 /* count an all-zero sequence as
444 * one digit plus leading zeros
457 g_string_append_c (result, ':');
461 if (leading_zeros > 0)
463 g_string_append_c (append, (char)leading_zeros);
464 prev += leading_zeros;
467 /* write the number itself */
468 g_string_append_len (result, prev, p - prev);
471 --p; /* go one step back to avoid disturbing outer loop */
475 /* other characters just accumulate */
482 collate_key = g_utf8_collate_key (prev, p - prev);
483 g_string_append (result, collate_key);
484 g_free (collate_key);
487 g_string_append (result, append->str);
488 g_string_free (append, TRUE);
490 return g_string_free (result, FALSE);
494 #define __G_UNICOLLATE_C__
495 #include "galiasdef.c"