glib/gunicollate.c - third_party/glib - Git at Google

 /* gunicollate.c - Collation
  *
  *  Copyright 2001,2005 Red Hat, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public License
  * along with this library; if not, see <http://www.gnu.org/licenses/>.
  */

 #include "config.h"

 #include <locale.h>
 #include <string.h>
 #ifdef __STDC_ISO_10646__
 #include <wchar.h>
 #endif

 #ifdef HAVE_CARBON
 #include <CoreServices/CoreServices.h>
 #endif

 #include "gmem.h"
 #include "gunicode.h"
 #include "gunicodeprivate.h"
 #include "gstring.h"
 #include "gstrfuncs.h"
 #include "gtestutils.h"
 #include "gcharset.h"
 #ifndef __STDC_ISO_10646__
 #include "gconvert.h"
 #endif


 #ifdef _MSC_VER
 /* Workaround for bug in MSVCR80.DLL */
 static gsize
 msc_strxfrm_wrapper (char       *string1,
 		     const char *string2,
 		     gsize       count)
 {
   if (!string1 || count <= 0)
     {
       char tmp;

       return strxfrm (&tmp, string2, 1);
     }
   return strxfrm (string1, string2, count);
 }
 #define strxfrm msc_strxfrm_wrapper
 #endif

 /**
  * g_utf8_collate:
  * @str1: a UTF-8 encoded string
  * @str2: a UTF-8 encoded string
  *
  * Compares two strings for ordering using the linguistically
  * correct rules for the [current locale][setlocale].
  * When sorting a large number of strings, it will be significantly
  * faster to obtain collation keys with g_utf8_collate_key() and
  * compare the keys with strcmp() when sorting instead of sorting
  * the original strings.
  *
  * Returns: < 0 if @str1 compares before @str2,
  *   0 if they compare equal, > 0 if @str1 compares after @str2.
  **/
 gint
 g_utf8_collate (const gchar *str1,
 		const gchar *str2)
 {
   gint result;

 #ifdef HAVE_CARBON

   UniChar *str1_utf16;
   UniChar *str2_utf16;
   glong len1;
   glong len2;
   SInt32 retval = 0;

   g_return_val_if_fail (str1 != NULL, 0);
   g_return_val_if_fail (str2 != NULL, 0);

   str1_utf16 = g_utf8_to_utf16 (str1, -1, NULL, &len1, NULL);
   str2_utf16 = g_utf8_to_utf16 (str2, -1, NULL, &len2, NULL);

   UCCompareTextDefault (kUCCollateStandardOptions,
                         str1_utf16, len1, str2_utf16, len2,
                         NULL, &retval);
   result = retval;

   g_free (str2_utf16);
   g_free (str1_utf16);

 #elif defined(__STDC_ISO_10646__)

   gunichar *str1_norm;
   gunichar *str2_norm;

   g_return_val_if_fail (str1 != NULL, 0);
   g_return_val_if_fail (str2 != NULL, 0);

   str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);
   str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);

   result = wcscoll ((wchar_t *)str1_norm, (wchar_t *)str2_norm);

   g_free (str1_norm);
   g_free (str2_norm);

 #else /* !__STDC_ISO_10646__ */

   const gchar *charset;
   gchar *str1_norm;
   gchar *str2_norm;

   g_return_val_if_fail (str1 != NULL, 0);
   g_return_val_if_fail (str2 != NULL, 0);

   str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);
   str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);

   if (g_get_charset (&charset))
     {
       result = strcoll (str1_norm, str2_norm);
     }
   else
     {
       gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
       gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

       if (str1_locale && str2_locale)
 	result =  strcoll (str1_locale, str2_locale);
       else if (str1_locale)
 	result = -1;
       else if (str2_locale)
 	result = 1;
       else
 	result = strcmp (str1_norm, str2_norm);

       g_free (str1_locale);
       g_free (str2_locale);
     }

   g_free (str1_norm);
   g_free (str2_norm);

 #endif /* __STDC_ISO_10646__ */

   return result;
 }

 #if defined(__STDC_ISO_10646__)
 /* We need UTF-8 encoding of numbers to encode the weights if
  * we are using wcsxfrm. However, we aren't encoding Unicode
  * characters, so we can't simply use g_unichar_to_utf8.
  *
  * The following routine is taken (with modification) from GNU
  * libc's strxfrm routine:
  *
  * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
  * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
  */
 static inline int
 utf8_encode (char *buf, wchar_t val)
 {
   int retval;

   if (val < 0x80)
     {
       if (buf)
 	*buf++ = (char) val;
       retval = 1;
     }
   else
     {
       int step;

       for (step = 2; step < 6; ++step)
         if ((val & (~(guint32)0 << (5 * step + 1))) == 0)
           break;
       retval = step;

       if (buf)
 	{
 	  *buf = (unsigned char) (~0xff >> step);
 	  --step;
 	  do
 	    {
 	      buf[step] = 0x80 | (val & 0x3f);
 	      val >>= 6;
 	    }
 	  while (--step > 0);
 	  *buf |= val;
 	}
     }

   return retval;
 }
 #endif /* __STDC_ISO_10646__ */

 #ifdef HAVE_CARBON

 static gchar *
 collate_key_to_string (UCCollationValue *key,
                        gsize             key_len)
 {
   gchar *result;
   gsize result_len;
   long *lkey = (long *) key;

   /* UCCollationValue format:
    *
    * UCCollateOptions (32/64 bits)
    * SizeInBytes      (32/64 bits)
    * Value            (8 bits arrey)
    *
    * UCCollateOptions: ordering option mask of the collator
    * used to create the key. Size changes on 32-bit / 64-bit
    * hosts. On 64-bits also the extra half-word seems to have
    * some extra (unknown) meaning.
    * SizeInBytes: size of the whole structure, in bytes
    * (including UCCollateOptions and SizeInBytes fields). Size
    * changes on 32-bit & 64-bit hosts.
    * Value: array of bytes containing the comparison weights.
    * Seems to have several sub-strings separated by \001 and \002
    * chars. Also, experience shows this is directly strcmp-able.
    */

   result_len = lkey[1];
   result = g_malloc (result_len + 1);
   memcpy (result, &lkey[2], result_len);
   result[result_len] = '\0';

   return result;
 }

 static gchar *
 carbon_collate_key_with_collator (const gchar *str,
                                   gssize       len,
                                   CollatorRef  collator)
 {
   UniChar *str_utf16 = NULL;
   glong len_utf16;
   OSStatus ret;
   UCCollationValue staticbuf[512];
   UCCollationValue *freeme = NULL;
   UCCollationValue *buf;
   ItemCount buf_len;
   ItemCount key_len;
   ItemCount try_len;
   gchar *result = NULL;

   str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);
   try_len = len_utf16 * 5 + 2;

   if (try_len <= sizeof staticbuf)
     {
       buf = staticbuf;
       buf_len = sizeof staticbuf;
     }
   else
     {
       freeme = g_new (UCCollationValue, try_len);
       buf = freeme;
       buf_len = try_len;
     }

   ret = UCGetCollationKey (collator, str_utf16, len_utf16,
                            buf_len, &key_len, buf);

   if (ret == kCollateBufferTooSmall)
     {
       freeme = g_renew (UCCollationValue, freeme, try_len * 2);
       buf = freeme;
       buf_len = try_len * 2;
       ret = UCGetCollationKey (collator, str_utf16, len_utf16,
                                buf_len, &key_len, buf);
     }

   if (ret == 0)
     result = collate_key_to_string (buf, key_len);
   else
     result = g_strdup ("");

   g_free (freeme);
   g_free (str_utf16);
   return result;
 }

 static gchar *
 carbon_collate_key (const gchar *str,
                     gssize       len)
 {
   static CollatorRef collator;

   if (G_UNLIKELY (!collator))
     {
       UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);

       if (!collator)
         {
           static gboolean been_here;
           if (!been_here)
             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
           been_here = TRUE;
           return g_strdup ("");
         }
     }

   return carbon_collate_key_with_collator (str, len, collator);
 }

 static gchar *
 carbon_collate_key_for_filename (const gchar *str,
                                  gssize       len)
 {
   static CollatorRef collator;

   if (G_UNLIKELY (!collator))
     {
       /* http://developer.apple.com/qa/qa2004/qa1159.html */
       UCCreateCollator (NULL, 0,
                         kUCCollateComposeInsensitiveMask
                          | kUCCollateWidthInsensitiveMask
                          | kUCCollateCaseInsensitiveMask
                          | kUCCollateDigitsOverrideMask
                          | kUCCollateDigitsAsNumberMask
                          | kUCCollatePunctuationSignificantMask,
                         &collator);

       if (!collator)
         {
           static gboolean been_here;
           if (!been_here)
             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
           been_here = TRUE;
           return g_strdup ("");
         }
     }

   return carbon_collate_key_with_collator (str, len, collator);
 }

 #endif /* HAVE_CARBON */

 /**
  * g_utf8_collate_key:
  * @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().
  *
  * The results of comparing the collation keys of two strings
  * with strcmp() will always be the same as comparing the two
  * original keys with g_utf8_collate().
  *
  * 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.
  **/
 gchar *
 g_utf8_collate_key (const gchar *str,
 		    gssize       len)
 {
   gchar *result;

 #ifdef HAVE_CARBON

   g_return_val_if_fail (str != NULL, NULL);
   result = carbon_collate_key (str, len);

 #elif defined(__STDC_ISO_10646__)

   gsize xfrm_len;
   gunichar *str_norm;
   wchar_t *result_wc;
   gsize i;
   gsize result_len = 0;

   g_return_val_if_fail (str != NULL, NULL);

   str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);

   xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
   result_wc = g_new (wchar_t, xfrm_len + 1);
   wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);

   for (i = 0; i < xfrm_len; i++)
     result_len += utf8_encode (NULL, result_wc[i]);

   result = g_malloc (result_len + 1);
   result_len = 0;
   for (i = 0; i < xfrm_len; i++)
     result_len += utf8_encode (result + result_len, result_wc[i]);

   result[result_len] = '\0';

   g_free (result_wc);
   g_free (str_norm);

   return result;
 #else /* !__STDC_ISO_10646__ */

   gsize xfrm_len;
   const gchar *charset;
   gchar *str_norm;

   g_return_val_if_fail (str != NULL, NULL);

   str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);

   result = NULL;

   if (g_get_charset (&charset))
     {
       xfrm_len = strxfrm (NULL, str_norm, 0);
       if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
         {
           result = g_malloc (xfrm_len + 1);
           strxfrm (result, str_norm, xfrm_len + 1);
         }
     }
   else
     {
       gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

       if (str_locale)
 	{
 	  xfrm_len = strxfrm (NULL, str_locale, 0);
 	  if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
 	    {
 	      g_free (str_locale);
 	      str_locale = NULL;
 	    }
 	}
       if (str_locale)
 	{
 	  result = g_malloc (xfrm_len + 2);
 	  result[0] = 'A';
 	  strxfrm (result + 1, str_locale, xfrm_len + 1);

 	  g_free (str_locale);
 	}
     }

   if (!result)
     {
       xfrm_len = strlen (str_norm);
       result = g_malloc (xfrm_len + 2);
       result[0] = 'B';
       memcpy (result + 1, str_norm, xfrm_len);
       result[xfrm_len+1] = '\0';
     }

   g_free (str_norm);
 #endif /* __STDC_ISO_10646__ */

   return result;
 }

 /* 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
 }
	/* gunicollate.c - Collation
	*
	* Copyright 2001,2005 Red Hat, Inc.
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Lesser General Public
	* License as published by the Free Software Foundation; either
	* version 2.1 of the License, or (at your option) any later version.
	*
	* This library is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	* Lesser General Public License for more details.
	*
	* You should have received a copy of the GNU Lesser General Public License
	* along with this library; if not, see <http://www.gnu.org/licenses/>.
	*/

	#include "config.h"

	#include <locale.h>
	#include <string.h>
	#ifdef __STDC_ISO_10646__
	#include <wchar.h>
	#endif

	#ifdef HAVE_CARBON
	#include <CoreServices/CoreServices.h>
	#endif

	#include "gmem.h"
	#include "gunicode.h"
	#include "gunicodeprivate.h"
	#include "gstring.h"
	#include "gstrfuncs.h"
	#include "gtestutils.h"
	#include "gcharset.h"
	#ifndef __STDC_ISO_10646__
	#include "gconvert.h"
	#endif


	#ifdef _MSC_VER
	/* Workaround for bug in MSVCR80.DLL */
	static gsize
	msc_strxfrm_wrapper (char *string1,
	const char *string2,
	gsize count)
	{
	if (!string1 \|\| count <= 0)
	{
	char tmp;

	return strxfrm (&tmp, string2, 1);
	}
	return strxfrm (string1, string2, count);
	}
	#define strxfrm msc_strxfrm_wrapper
	#endif

	/**
	* g_utf8_collate:
	* @str1: a UTF-8 encoded string
	* @str2: a UTF-8 encoded string
	*
	* Compares two strings for ordering using the linguistically
	* correct rules for the [current locale][setlocale].
	* When sorting a large number of strings, it will be significantly
	* faster to obtain collation keys with g_utf8_collate_key() and
	* compare the keys with strcmp() when sorting instead of sorting
	* the original strings.
	*
	* Returns: < 0 if @str1 compares before @str2,
	* 0 if they compare equal, > 0 if @str1 compares after @str2.
	**/
	gint
	g_utf8_collate (const gchar *str1,
	const gchar *str2)
	{
	gint result;

	#ifdef HAVE_CARBON

	UniChar *str1_utf16;
	UniChar *str2_utf16;
	glong len1;
	glong len2;
	SInt32 retval = 0;

	g_return_val_if_fail (str1 != NULL, 0);
	g_return_val_if_fail (str2 != NULL, 0);

	str1_utf16 = g_utf8_to_utf16 (str1, -1, NULL, &len1, NULL);
	str2_utf16 = g_utf8_to_utf16 (str2, -1, NULL, &len2, NULL);

	UCCompareTextDefault (kUCCollateStandardOptions,
	str1_utf16, len1, str2_utf16, len2,
	NULL, &retval);
	result = retval;

	g_free (str2_utf16);
	g_free (str1_utf16);

	#elif defined(__STDC_ISO_10646__)

	gunichar *str1_norm;
	gunichar *str2_norm;

	g_return_val_if_fail (str1 != NULL, 0);
	g_return_val_if_fail (str2 != NULL, 0);

	str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);
	str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);

	result = wcscoll ((wchar_t )str1_norm, (wchar_t )str2_norm);

	g_free (str1_norm);
	g_free (str2_norm);

	#else /* !__STDC_ISO_10646__ */

	const gchar *charset;
	gchar *str1_norm;
	gchar *str2_norm;

	g_return_val_if_fail (str1 != NULL, 0);
	g_return_val_if_fail (str2 != NULL, 0);

	str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);
	str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);

	if (g_get_charset (&charset))
	{
	result = strcoll (str1_norm, str2_norm);
	}
	else
	{
	gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
	gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

	if (str1_locale && str2_locale)
	result = strcoll (str1_locale, str2_locale);
	else if (str1_locale)
	result = -1;
	else if (str2_locale)
	result = 1;
	else
	result = strcmp (str1_norm, str2_norm);

	g_free (str1_locale);
	g_free (str2_locale);
	}

	g_free (str1_norm);
	g_free (str2_norm);

	#endif /* __STDC_ISO_10646__ */

	return result;
	}

	#if defined(__STDC_ISO_10646__)
	/* We need UTF-8 encoding of numbers to encode the weights if
	* we are using wcsxfrm. However, we aren't encoding Unicode
	* characters, so we can't simply use g_unichar_to_utf8.
	*
	* The following routine is taken (with modification) from GNU
	* libc's strxfrm routine:
	*
	* Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
	* Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
	*/
	static inline int
	utf8_encode (char *buf, wchar_t val)
	{
	int retval;

	if (val < 0x80)
	{
	if (buf)
	*buf++ = (char) val;
	retval = 1;
	}
	else
	{
	int step;

	for (step = 2; step < 6; ++step)
	if ((val & (~(guint32)0 << (5 * step + 1))) == 0)
	break;
	retval = step;

	if (buf)
	{
	*buf = (unsigned char) (~0xff >> step);
	--step;
	do
	{
	buf[step] = 0x80 \| (val & 0x3f);
	val >>= 6;
	}
	while (--step > 0);
	*buf \|= val;
	}
	}

	return retval;
	}
	#endif /* __STDC_ISO_10646__ */

	#ifdef HAVE_CARBON

	static gchar *
	collate_key_to_string (UCCollationValue *key,
	gsize key_len)
	{
	gchar *result;
	gsize result_len;
	long lkey = (long ) key;

	/* UCCollationValue format:
	*
	* UCCollateOptions (32/64 bits)
	* SizeInBytes (32/64 bits)
	* Value (8 bits arrey)
	*
	* UCCollateOptions: ordering option mask of the collator
	* used to create the key. Size changes on 32-bit / 64-bit
	* hosts. On 64-bits also the extra half-word seems to have
	* some extra (unknown) meaning.
	* SizeInBytes: size of the whole structure, in bytes
	* (including UCCollateOptions and SizeInBytes fields). Size
	* changes on 32-bit & 64-bit hosts.
	* Value: array of bytes containing the comparison weights.
	* Seems to have several sub-strings separated by \001 and \002
	* chars. Also, experience shows this is directly strcmp-able.
	*/

	result_len = lkey[1];
	result = g_malloc (result_len + 1);
	memcpy (result, &lkey[2], result_len);
	result[result_len] = '\0';

	return result;
	}

	static gchar *
	carbon_collate_key_with_collator (const gchar *str,
	gssize len,
	CollatorRef collator)
	{
	UniChar *str_utf16 = NULL;
	glong len_utf16;
	OSStatus ret;
	UCCollationValue staticbuf[512];
	UCCollationValue *freeme = NULL;
	UCCollationValue *buf;
	ItemCount buf_len;
	ItemCount key_len;
	ItemCount try_len;
	gchar *result = NULL;

	str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);
	try_len = len_utf16 * 5 + 2;

	if (try_len <= sizeof staticbuf)
	{
	buf = staticbuf;
	buf_len = sizeof staticbuf;
	}
	else
	{
	freeme = g_new (UCCollationValue, try_len);
	buf = freeme;
	buf_len = try_len;
	}

	ret = UCGetCollationKey (collator, str_utf16, len_utf16,
	buf_len, &key_len, buf);

	if (ret == kCollateBufferTooSmall)
	{
	freeme = g_renew (UCCollationValue, freeme, try_len * 2);
	buf = freeme;
	buf_len = try_len * 2;
	ret = UCGetCollationKey (collator, str_utf16, len_utf16,
	buf_len, &key_len, buf);
	}

	if (ret == 0)
	result = collate_key_to_string (buf, key_len);
	else
	result = g_strdup ("");

	g_free (freeme);
	g_free (str_utf16);
	return result;
	}

	static gchar *
	carbon_collate_key (const gchar *str,
	gssize len)
	{
	static CollatorRef collator;

	if (G_UNLIKELY (!collator))
	{
	UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);

	if (!collator)
	{
	static gboolean been_here;
	if (!been_here)
	g_warning ("%s: UCCreateCollator failed", G_STRLOC);
	been_here = TRUE;
	return g_strdup ("");
	}
	}

	return carbon_collate_key_with_collator (str, len, collator);
	}

	static gchar *
	carbon_collate_key_for_filename (const gchar *str,
	gssize len)
	{
	static CollatorRef collator;

	if (G_UNLIKELY (!collator))
	{
	/* http://developer.apple.com/qa/qa2004/qa1159.html */
	UCCreateCollator (NULL, 0,
	kUCCollateComposeInsensitiveMask
	\| kUCCollateWidthInsensitiveMask
	\| kUCCollateCaseInsensitiveMask
	\| kUCCollateDigitsOverrideMask
	\| kUCCollateDigitsAsNumberMask
	\| kUCCollatePunctuationSignificantMask,
	&collator);

	if (!collator)
	{
	static gboolean been_here;
	if (!been_here)
	g_warning ("%s: UCCreateCollator failed", G_STRLOC);
	been_here = TRUE;
	return g_strdup ("");
	}
	}

	return carbon_collate_key_with_collator (str, len, collator);
	}

	#endif /* HAVE_CARBON */

	/**
	* g_utf8_collate_key:
	* @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().
	*
	* The results of comparing the collation keys of two strings
	* with strcmp() will always be the same as comparing the two
	* original keys with g_utf8_collate().
	*
	* 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.
	**/
	gchar *
	g_utf8_collate_key (const gchar *str,
	gssize len)
	{
	gchar *result;

	#ifdef HAVE_CARBON

	g_return_val_if_fail (str != NULL, NULL);
	result = carbon_collate_key (str, len);

	#elif defined(__STDC_ISO_10646__)

	gsize xfrm_len;
	gunichar *str_norm;
	wchar_t *result_wc;
	gsize i;
	gsize result_len = 0;

	g_return_val_if_fail (str != NULL, NULL);

	str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);

	xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
	result_wc = g_new (wchar_t, xfrm_len + 1);
	wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);

	for (i = 0; i < xfrm_len; i++)
	result_len += utf8_encode (NULL, result_wc[i]);

	result = g_malloc (result_len + 1);
	result_len = 0;
	for (i = 0; i < xfrm_len; i++)
	result_len += utf8_encode (result + result_len, result_wc[i]);

	result[result_len] = '\0';

	g_free (result_wc);
	g_free (str_norm);

	return result;
	#else /* !__STDC_ISO_10646__ */

	gsize xfrm_len;
	const gchar *charset;
	gchar *str_norm;

	g_return_val_if_fail (str != NULL, NULL);

	str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);

	result = NULL;

	if (g_get_charset (&charset))
	{
	xfrm_len = strxfrm (NULL, str_norm, 0);
	if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
	{
	result = g_malloc (xfrm_len + 1);
	strxfrm (result, str_norm, xfrm_len + 1);
	}
	}
	else
	{
	gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

	if (str_locale)
	{
	xfrm_len = strxfrm (NULL, str_locale, 0);
	if (xfrm_len < 0 \|\| xfrm_len >= G_MAXINT - 2)
	{
	g_free (str_locale);
	str_locale = NULL;
	}
	}
	if (str_locale)
	{
	result = g_malloc (xfrm_len + 2);
	result[0] = 'A';
	strxfrm (result + 1, str_locale, xfrm_len + 1);

	g_free (str_locale);
	}
	}

	if (!result)
	{
	xfrm_len = strlen (str_norm);
	result = g_malloc (xfrm_len + 2);
	result[0] = 'B';
	memcpy (result + 1, str_norm, xfrm_len);
	result[xfrm_len+1] = '\0';
	}

	g_free (str_norm);
	#endif /* __STDC_ISO_10646__ */

	return result;
	}

	/* 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
	}