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 current locale. When sorting a large
58 * number of strings, it will be significantly faster to
59 * obtain collation keys with g_utf8_collate_key() and
60 * compare the keys with strcmp() when
61 * sorting instead of sorting 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
187 * The results of comparing the collation keys of two strings
188 * with strcmp() will always be the same as
189 * comparing the two original keys with g_utf8_collate().
191 * Return value: a newly allocated string. This string should
192 * be freed with g_free() when you are done with it.
195 g_utf8_collate_key (const gchar
*str
,
201 #ifdef __STDC_ISO_10646__
206 size_t result_len
= 0;
208 g_return_val_if_fail (str
!= NULL
, NULL
);
210 str_norm
= _g_utf8_normalize_wc (str
, len
, G_NORMALIZE_ALL_COMPOSE
);
212 setlocale (LC_COLLATE
, "");
214 xfrm_len
= wcsxfrm (NULL
, (wchar_t *)str_norm
, 0);
215 result_wc
= g_new (wchar_t, xfrm_len
+ 1);
216 wcsxfrm (result_wc
, (wchar_t *)str_norm
, xfrm_len
+ 1);
218 for (i
=0; i
< xfrm_len
; i
++)
219 result_len
+= utf8_encode (NULL
, result_wc
[i
]);
221 result
= g_malloc (result_len
+ 1);
223 for (i
=0; i
< xfrm_len
; i
++)
224 result_len
+= utf8_encode (result
+ result_len
, result_wc
[i
]);
226 result
[result_len
] = '\0';
232 #else /* !__STDC_ISO_10646__ */
234 const gchar
*charset
;
237 g_return_val_if_fail (str
!= NULL
, NULL
);
239 str_norm
= g_utf8_normalize (str
, len
, G_NORMALIZE_ALL_COMPOSE
);
241 if (g_get_charset (&charset
))
243 xfrm_len
= strxfrm (NULL
, str_norm
, 0);
244 result
= g_malloc (xfrm_len
+ 1);
245 strxfrm (result
, str_norm
, xfrm_len
+ 1);
249 gchar
*str_locale
= g_convert (str_norm
, -1, charset
, "UTF-8", NULL
, NULL
, NULL
);
253 xfrm_len
= strxfrm (NULL
, str_locale
, 0);
254 if (xfrm_len
< 0 || xfrm_len
>= G_MAXINT
- 2)
262 result
= g_malloc (xfrm_len
+ 2);
264 strxfrm (result
+ 1, str_locale
, xfrm_len
+ 1);
270 xfrm_len
= strlen (str_norm
);
271 result
= g_malloc (xfrm_len
+ 2);
273 memcpy (result
+ 1, str_norm
, xfrm_len
);
274 result
[xfrm_len
+1] = '\0';
279 #endif /* __STDC_ISO_10646__ */
284 /* This is a collation key that is very very likely to sort before any
285 collation key that libc strxfrm generates. We use this before any
286 special case (dot or number) to make sure that its sorted before
289 #define COLLATION_SENTINEL "\1\1\1"
292 * g_utf8_collate_key_for_filename:
293 * @str: a UTF-8 encoded string.
294 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
296 * Converts a string into a collation key that can be compared
297 * with other collation keys produced by the same function using strcmp().
299 * In order to sort filenames correctly, this function treats the dot '.'
300 * as a special case. Most dictionary orderings seem to consider it
301 * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
302 * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
303 * would like to treat numbers intelligently so that "file1" "file10" "file5"
304 * is sorted as "file1" "file5" "file10".
306 * Return value: a newly allocated string. This string should
307 * be freed with g_free() when you are done with it.
312 g_utf8_collate_key_for_filename (const gchar
*str
,
327 * Split the filename into collatable substrings which do
328 * not contain [.0-9] and special-cased substrings. The collatable
329 * substrings are run through the normal g_utf8_collate_key() and the
330 * resulting keys are concatenated with keys generated from the
331 * special-cased substrings.
333 * Special cases: Dots are handled by replacing them with '\1' which
334 * implies that short dot-delimited substrings are before long ones,
341 * Numbers are handled by prepending to each number d-1 superdigits
342 * where d = number of digits in the number and SUPERDIGIT is a
343 * character with an integer value higher than any digit (for instance
344 * ':'). This ensures that single-digit numbers are sorted before
345 * double-digit numbers which in turn are sorted separately from
346 * triple-digit numbers, etc. To avoid strange side-effects when
347 * sorting strings that already contain SUPERDIGITs, a '\2'
348 * is also prepended, like this
354 * file\2::100 (file100)
355 * file:foo (file:foo)
357 * This has the side-effect of sorting numbers before everything else (except
358 * dots), but this is probably OK.
360 * Leading digits are ignored when doing the above. To discriminate
361 * numbers which differ only in the number of leading digits, we append
362 * the number of leading digits as a byte at the very end of the collation
365 * To try avoid conflict with any collation key sequence generated by libc we
366 * start each switch to a special cased part with a sentinel that hopefully
367 * will sort before anything libc will generate.
373 result
= g_string_sized_new (len
* 2);
374 append
= g_string_sized_new (0);
378 /* No need to use utf8 functions, since we're only looking for ascii chars */
379 for (prev
= p
= str
; p
< end
; p
++)
386 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
387 g_string_append (result
, collate_key
);
388 g_free (collate_key
);
391 g_string_append (result
, COLLATION_SENTINEL
"\1");
409 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
410 g_string_append (result
, collate_key
);
411 g_free (collate_key
);
414 g_string_append (result
, COLLATION_SENTINEL
"\2");
418 /* write d-1 colons */
432 if (*p
== '0' && !digits
)
434 else if (g_ascii_isdigit(*p
))
438 /* count an all-zero sequence as
439 * one digit plus leading zeros
452 g_string_append_c (result
, ':');
456 if (leading_zeros
> 0)
458 g_string_append_c (append
, (char)leading_zeros
);
459 prev
+= leading_zeros
;
462 /* write the number itself */
463 g_string_append_len (result
, prev
, p
- prev
);
466 --p
; /* go one step back to avoid disturbing outer loop */
470 /* other characters just accumulate */
477 collate_key
= g_utf8_collate_key (prev
, p
- prev
);
478 g_string_append (result
, collate_key
);
479 g_free (collate_key
);
482 g_string_append (result
, append
->str
);
483 g_string_free (append
, TRUE
);
485 return g_string_free (result
, FALSE
);
489 #define __G_UNICOLLATE_C__
490 #include "galiasdef.c"