+
+/* This is a collation key that is very very likely to sort before any
+ * collation key that libc strxfrm generates. We use this before any
+ * special case (dot or number) to make sure that its sorted before
+ * anything else.
+ */
+#define COLLATION_SENTINEL "\1\1\1"
+
+/**
+ * g_utf8_collate_key_for_filename:
+ * @str: a UTF-8 encoded string.
+ * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
+ *
+ * Converts a string into a collation key that can be compared
+ * with other collation keys produced by the same function using strcmp().
+ *
+ * In order to sort filenames correctly, this function treats the dot '.'
+ * as a special case. Most dictionary orderings seem to consider it
+ * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
+ * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
+ * would like to treat numbers intelligently so that "file1" "file10" "file5"
+ * is sorted as "file1" "file5" "file10".
+ *
+ * Note that this function depends on the [current locale][setlocale].
+ *
+ * Returns: a newly allocated string. This string should
+ * be freed with g_free() when you are done with it.
+ *
+ * Since: 2.8
+ */
+gchar *
+g_utf8_collate_key_for_filename (const gchar *str,
+ gssize len)
+{
+#ifndef HAVE_CARBON
+ GString *result;
+ GString *append;
+ const gchar *p;
+ const gchar *prev;
+ const gchar *end;
+ gchar *collate_key;
+ gint digits;
+ gint leading_zeros;
+
+ /*
+ * How it works:
+ *
+ * Split the filename into collatable substrings which do
+ * not contain [.0-9] and special-cased substrings. The collatable
+ * substrings are run through the normal g_utf8_collate_key() and the
+ * resulting keys are concatenated with keys generated from the
+ * special-cased substrings.
+ *
+ * Special cases: Dots are handled by replacing them with '\1' which
+ * implies that short dot-delimited substrings are before long ones,
+ * e.g.
+ *
+ * a\1a (a.a)
+ * a-\1a (a-.a)
+ * aa\1a (aa.a)
+ *
+ * Numbers are handled by prepending to each number d-1 superdigits
+ * where d = number of digits in the number and SUPERDIGIT is a
+ * character with an integer value higher than any digit (for instance
+ * ':'). This ensures that single-digit numbers are sorted before
+ * double-digit numbers which in turn are sorted separately from
+ * triple-digit numbers, etc. To avoid strange side-effects when
+ * sorting strings that already contain SUPERDIGITs, a '\2'
+ * is also prepended, like this
+ *
+ * file\21 (file1)
+ * file\25 (file5)
+ * file\2:10 (file10)
+ * file\2:26 (file26)
+ * file\2::100 (file100)
+ * file:foo (file:foo)
+ *
+ * This has the side-effect of sorting numbers before everything else (except
+ * dots), but this is probably OK.
+ *
+ * Leading digits are ignored when doing the above. To discriminate
+ * numbers which differ only in the number of leading digits, we append
+ * the number of leading digits as a byte at the very end of the collation
+ * key.
+ *
+ * To try avoid conflict with any collation key sequence generated by libc we
+ * start each switch to a special cased part with a sentinel that hopefully
+ * will sort before anything libc will generate.
+ */
+
+ if (len < 0)
+ len = strlen (str);
+
+ result = g_string_sized_new (len * 2);
+ append = g_string_sized_new (0);
+
+ end = str + len;
+
+ /* No need to use utf8 functions, since we're only looking for ascii chars */
+ for (prev = p = str; p < end; p++)
+ {
+ switch (*p)
+ {
+ case '.':
+ if (prev != p)
+ {
+ collate_key = g_utf8_collate_key (prev, p - prev);
+ g_string_append (result, collate_key);
+ g_free (collate_key);
+ }
+
+ g_string_append (result, COLLATION_SENTINEL "\1");
+
+ /* skip the dot */
+ prev = p + 1;
+ break;
+
+ case '0':
+ case '1':
+ case '2':
+ case '3':
+ case '4':
+ case '5':
+ case '6':
+ case '7':
+ case '8':
+ case '9':
+ if (prev != p)
+ {
+ collate_key = g_utf8_collate_key (prev, p - prev);
+ g_string_append (result, collate_key);
+ g_free (collate_key);
+ }
+
+ g_string_append (result, COLLATION_SENTINEL "\2");
+
+ prev = p;
+
+ /* write d-1 colons */
+ if (*p == '0')
+ {
+ leading_zeros = 1;
+ digits = 0;
+ }
+ else
+ {
+ leading_zeros = 0;
+ digits = 1;
+ }
+
+ while (++p < end)
+ {
+ if (*p == '0' && !digits)
+ ++leading_zeros;
+ else if (g_ascii_isdigit(*p))
+ ++digits;
+ else
+ {
+ /* count an all-zero sequence as
+ * one digit plus leading zeros
+ */
+ if (!digits)
+ {
+ ++digits;
+ --leading_zeros;
+ }
+ break;
+ }
+ }
+
+ while (digits > 1)
+ {
+ g_string_append_c (result, ':');
+ --digits;
+ }
+
+ if (leading_zeros > 0)
+ {
+ g_string_append_c (append, (char)leading_zeros);
+ prev += leading_zeros;
+ }
+
+ /* write the number itself */
+ g_string_append_len (result, prev, p - prev);
+
+ prev = p;
+ --p; /* go one step back to avoid disturbing outer loop */
+ break;
+
+ default:
+ /* other characters just accumulate */
+ break;
+ }
+ }
+
+ if (prev != p)
+ {
+ collate_key = g_utf8_collate_key (prev, p - prev);
+ g_string_append (result, collate_key);
+ g_free (collate_key);
+ }
+
+ g_string_append (result, append->str);
+ g_string_free (append, TRUE);
+
+ return g_string_free (result, FALSE);
+#else /* HAVE_CARBON */
+ return carbon_collate_key_for_filename (str, len);
+#endif
+}