text: /*
     +----------------------------------------------------------------------+
     | This source file is subject to version 3.01 of the PHP license,      |
     | that is bundled with this package in the file LICENSE, and is        |
     | available through the world-wide-web at the following url:           |
     | http://www.php.net/license/3_01.txt                                  |
     | If you did not receive a copy of the PHP license and are unable to   |
     | obtain it through the world-wide-web, please send a note to          |
     | license@php.net so we can mail you a copy immediately.               |
     +----------------------------------------------------------------------+
     | Authors: Vadim Savchuk <vsavchuk@productengine.com>                  |
     |          Dmitry Lakhtyuk <dlakhtyuk@productengine.com>               |
     +----------------------------------------------------------------------+
   */
  
  #ifdef HAVE_CONFIG_H
  #include "config.h"
  #endif
  
  #include "php_intl.h"
  #include "collator.h"
  #include "collator_class.h"
  #include "collator_sort.h"
  #include "collator_convert.h"
  #include "intl_convert.h"
  
  #if !defined(HAVE_PTRDIFF_T) && !defined(_PTRDIFF_T_DEFINED)
  typedef zend_long ptrdiff_t;
  #endif
  
  /**
   * Declare 'index' which will point to sort key in sort key
   * buffer.
   */
  typedef struct _collator_sort_key_index {
  	char* key;       /* pointer to sort key */
  	zval* zstr;     /* pointer to original string(hash-item) */
  } collator_sort_key_index_t;
  
  ZEND_EXTERN_MODULE_GLOBALS( intl )
  
  static const size_t DEF_SORT_KEYS_BUF_SIZE = 1048576;
  static const size_t DEF_SORT_KEYS_BUF_INCREMENT = 1048576;
  
  static const size_t DEF_SORT_KEYS_INDX_BUF_SIZE = 1048576;
  static const size_t DEF_SORT_KEYS_INDX_BUF_INCREMENT = 1048576;
  
  static const size_t DEF_UTF16_BUF_SIZE = 1024;
  
  /* {{{ collator_regular_compare_function */
  static int collator_regular_compare_function(zval *result, zval *op1, zval *op2)
  {
  	Collator_object* co = NULL;
  	int rc = SUCCESS;
  	zval str1, str2;
  	zval num1, num2;
  	zval norm1, norm2;
  	zval *num1_p = NULL, *num2_p = NULL;
  	zval *norm1_p = NULL, *norm2_p = NULL;
  	zval *str1_p, *str2_p;
  
  	ZVAL_NULL(&str1);
  	str1_p  = collator_convert_object_to_string( op1, &str1 );
  	ZVAL_NULL(&str2);
  	str2_p  = collator_convert_object_to_string( op2, &str2 );
  
  	/* If both args are strings AND either of args is not numeric string
  	 * then use ICU-compare. Otherwise PHP-compare. */
  	if( Z_TYPE_P(str1_p) == IS_STRING && Z_TYPE_P(str2_p) == IS_STRING &&
  		( str1_p == ( num1_p = collator_convert_string_to_number_if_possible( str1_p, &num1 ) ) ||
  		  str2_p == ( num2_p = collator_convert_string_to_number_if_possible( str2_p, &num2 ) ) ) )
  	{
  		/* Fetch collator object. */
  		co = Z_INTL_COLLATOR_P(&INTL_G(current_collator));
  
  		if (!co || !co->ucoll) {
  			intl_error_set_code( NULL, COLLATOR_ERROR_CODE( co ) );
  			intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ),
  				"Object not initialized", 0 );
  			zend_throw_error(NULL, "Object not initialized");
  			rc = FAILURE;
  			goto cleanup;
  		}
  
  		/* Compare the strings using ICU. */
  		ZVAL_LONG(result, ucol_strcoll(
  					co->ucoll,
  					INTL_Z_STRVAL_P(str1_p), INTL_Z_STRLEN_P(str1_p),
  					INTL_Z_STRVAL_P(str2_p), INTL_Z_STRLEN_P(str2_p) ));
  	}
  	else
  	{
  		/* num1 is set if str1 and str2 are strings. */
  		if( num1_p )
  		{
  			if( num1_p == str1_p )
  			{
  				/* str1 is string but not numeric string
  				 * just convert it to utf8.
  				 */
  				norm1_p = collator_convert_zstr_utf16_to_utf8( str1_p, &norm1 );
  
  				/* num2 is not set but str2 is string => do normalization. */
  				norm2_p = collator_normalize_sort_argument( str2_p, &norm2 );
  			}
  			else
  			{
  				/* str1 is numeric strings => passthru to PHP-compare. */
  				Z_TRY_ADDREF_P(num1_p);
  				norm1_p = num1_p;
  
  				/* str2 is numeric strings => passthru to PHP-compare. */
  				Z_TRY_ADDREF_P(num2_p);
  				norm2_p = num2_p;
  			}
  		}
  		else
  		{
  			/* num1 is not set if str1 or str2 is not a string => do normalization. */
  			norm1_p = collator_normalize_sort_argument( str1_p, &norm1 );
  
  			/* if num1 is not set then num2 is not set as well => do normalization. */
  			norm2_p = collator_normalize_sort_argument( str2_p, &norm2 );
  		}
  
  		rc = compare_function( result, norm1_p, norm2_p );
  
  		zval_ptr_dtor( norm1_p );
  		zval_ptr_dtor( norm2_p );
  	}
  
  cleanup:
  	if( num1_p )
  		zval_ptr_dtor( num1_p );
  
  	if( num2_p )
  		zval_ptr_dtor( num2_p );
  
  	zval_ptr_dtor( str1_p );
  	zval_ptr_dtor( str2_p );
  
  	return rc;
  }
  /* }}} */
  
  /* {{{ collator_numeric_compare_function
   * Convert input args to double and compare it.
   */
  static int collator_numeric_compare_function(zval *result, zval *op1, zval *op2)
  {
  	zval num1, num2;
  	zval *num1_p = NULL;
  	zval *num2_p = NULL;
  
  	if( Z_TYPE_P(op1) == IS_STRING )
  	{
  		num1_p = collator_convert_string_to_double( op1, &num1 );
  		op1 = num1_p;
  	}
  
  	if( Z_TYPE_P(op2) == IS_STRING )
  	{
  		num2_p = collator_convert_string_to_double( op2, &num2 );
  		op2 = num2_p;
  	}
  
  	ZVAL_LONG(result, numeric_compare_function(op1, op2));
  
  	if( num1_p )
  		zval_ptr_dtor( num1_p );
  	if( num2_p )
  		zval_ptr_dtor( num2_p );
  
  	return SUCCESS;
  }
  /* }}} */
  
  /* {{{ collator_icu_compare_function
   * Direct use of ucol_strcoll.
  */
  static int collator_icu_compare_function(zval *result, zval *op1, zval *op2)
  {
  	zval str1, str2;
  	int rc              = SUCCESS;
  	Collator_object* co = NULL;
  	zval *str1_p        = NULL;
  	zval *str2_p        = NULL;
  
  	str1_p = collator_make_printable_zval( op1, &str1);
  	str2_p = collator_make_printable_zval( op2, &str2 );
  
  	/* Fetch collator object. */
  	co = Z_INTL_COLLATOR_P(&INTL_G(current_collator));
  
  	/* Compare the strings using ICU. */
  	ZVAL_LONG(result, ucol_strcoll(
  				co->ucoll,
  				INTL_Z_STRVAL_P(str1_p), INTL_Z_STRLEN_P(str1_p),
  				INTL_Z_STRVAL_P(str2_p), INTL_Z_STRLEN_P(str2_p) ));
  
  	zval_ptr_dtor( str1_p );
  	zval_ptr_dtor( str2_p );
  
  	return rc;
  }
  /* }}} */
  
  /* {{{ collator_compare_func
   * Taken from PHP7 source (array_data_compare).
   */
  static int collator_compare_func( const void* a, const void* b )
  {
  	Bucket *f;
  	Bucket *s;
  	zval result;
  	zval *first;
  	zval *second;
  
  	f = (Bucket *) a;
  	s = (Bucket *) b;
  
  	first = &f->val;
  	second = &s->val;
  
  	if( INTL_G(compare_func)( &result, first, second) == FAILURE )
  		return 0;
  
  	if( Z_TYPE(result) == IS_DOUBLE )
  	{
  		if( Z_DVAL(result) < 0 )
  			return -1;
  		else if( Z_DVAL(result) > 0 )
  			return 1;
  		else
  			return 0;
  	}
  
  	convert_to_long(&result);
  
  	if( Z_LVAL(result) < 0 )
  		return -1;
  	else if( Z_LVAL(result) > 0 )
  		return 1;
  
  	return 0;
  }
  /* }}} */
  
  /* {{{ collator_cmp_sort_keys
   * Compare sort keys
   */
  static int collator_cmp_sort_keys( const void *p1, const void *p2 )
  {
  	char* key1 = ((collator_sort_key_index_t*)p1)->key;
  	char* key2 = ((collator_sort_key_index_t*)p2)->key;
  
  	return strcmp( key1, key2 );
  }
  /* }}} */
  
  /* {{{ collator_get_compare_function
   * Choose compare function according to sort flags.
   */
  static collator_compare_func_t collator_get_compare_function( const zend_long sort_flags )
  {
  	collator_compare_func_t func;
  
  	switch( sort_flags )
  	{
  		case COLLATOR_SORT_NUMERIC:
  			func = collator_numeric_compare_function;
  			break;
  
  		case COLLATOR_SORT_STRING:
  			func = collator_icu_compare_function;
  			break;
  
  		case COLLATOR_SORT_REGULAR:
  		default:
  			func = collator_regular_compare_function;
  			break;
  	}
  
  	return func;
  }
  /* }}} */
  
  /* {{{ collator_sort_internal
   * Common code shared by collator_sort() and collator_asort() API functions.
   */
  static void collator_sort_internal( int renumber, INTERNAL_FUNCTION_PARAMETERS )
  {
  	zval           saved_collator;
  	zval*          array            = NULL;
  	HashTable*     hash             = NULL;
  	zend_long           sort_flags       = COLLATOR_SORT_REGULAR;
  
  	COLLATOR_METHOD_INIT_VARS
  
  	/* Parse parameters. */
  	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Oa/|l",
  		&object, Collator_ce_ptr, &array, &sort_flags ) == FAILURE )
  	{
  		RETURN_FALSE;
  	}
  
  	/* Fetch the object. */
  	COLLATOR_METHOD_FETCH_OBJECT;
  
  	/* Set 'compare function' according to sort flags. */
  	INTL_G(compare_func) = collator_get_compare_function( sort_flags );
  
  	hash = Z_ARRVAL_P( array );
  
  	/* Convert strings in the specified array from UTF-8 to UTF-16. */
  	collator_convert_hash_from_utf8_to_utf16( hash, COLLATOR_ERROR_CODE_P( co ) );
  	COLLATOR_CHECK_STATUS( co, "Error converting hash from UTF-8 to UTF-16" );
  
  	/* Save specified collator in the request-global (?) variable. */
  	ZVAL_COPY_VALUE(&saved_collator, &INTL_G( current_collator ));
  	ZVAL_OBJ(&INTL_G( current_collator ), Z_OBJ_P(object));
  
  	/* Sort specified array. */
  	zend_hash_sort(hash, collator_compare_func, renumber);
  
  	/* Restore saved collator. */
  	ZVAL_COPY_VALUE(&INTL_G( current_collator ), &saved_collator);
  
  	/* Convert strings in the specified array back to UTF-8. */
  	collator_convert_hash_from_utf16_to_utf8( hash, COLLATOR_ERROR_CODE_P( co ) );
  	COLLATOR_CHECK_STATUS( co, "Error converting hash from UTF-16 to UTF-8" );
  
  	RETURN_TRUE;
  }
  /* }}} */
  
  /* {{{ proto bool Collator::sort( Collator $coll, array(string) $arr [, int $sort_flags] )
   * Sort array using specified collator. }}} */
  /* {{{ proto bool collator_sort(  Collator $coll, array(string) $arr [, int $sort_flags] )
   * Sort array using specified collator.
   */
  PHP_FUNCTION( collator_sort )
  {
  	collator_sort_internal( TRUE, INTERNAL_FUNCTION_PARAM_PASSTHRU );
  }
  /* }}} */
  
  static void collator_sortkey_swap(collator_sort_key_index_t *p, collator_sort_key_index_t *q) /* {{{ */
  {
  	collator_sort_key_index_t t;
  	t = *p;
  	*p = *q;
  	*q = t;
  }
  /* }}} */
  
  /* {{{ proto bool Collator::sortWithSortKeys( Collator $coll, array(string) $arr )
   * Equivalent to standard PHP sort using Collator.
   * Uses ICU ucol_getSortKey for performance. }}} */
  /* {{{ proto bool collator_sort_with_sort_keys( Collator $coll, array(string) $arr )
   * Equivalent to standard PHP sort using Collator.
   * Uses ICU ucol_getSortKey for performance.
   */
  PHP_FUNCTION( collator_sort_with_sort_keys )
  {
  	zval*       array                = NULL;
  	zval        garbage;
  	HashTable*  hash                 = NULL;
  	zval*       hashData             = NULL;                     /* currently processed item of input hash */
  
  	char*       sortKeyBuf           = NULL;                     /* buffer to store sort keys */
  	uint32_t    sortKeyBufSize       = DEF_SORT_KEYS_BUF_SIZE;   /* buffer size */
  	ptrdiff_t   sortKeyBufOffset     = 0;                        /* pos in buffer to store sort key */
  	uint32_t    sortKeyLen           = 0;                        /* the length of currently processing key */
  	uint32_t    bufLeft              = 0;
  	uint32_t    bufIncrement         = 0;
  
  	collator_sort_key_index_t* sortKeyIndxBuf = NULL;            /* buffer to store 'indexes' which will be passed to 'qsort' */
  	uint32_t    sortKeyIndxBufSize   = DEF_SORT_KEYS_INDX_BUF_SIZE;
  	uint32_t    sortKeyIndxSize      = sizeof( collator_sort_key_index_t );
  
  	uint32_t    sortKeyCount         = 0;
  	uint32_t    j                    = 0;
  
  	UChar*      utf16_buf            = NULL;                     /* tmp buffer to hold current processing string in utf-16 */
  	int         utf16_buf_size       = DEF_UTF16_BUF_SIZE;       /* the length of utf16_buf */
  	int         utf16_len            = 0;                        /* length of converted string */
  
  	COLLATOR_METHOD_INIT_VARS
  
  	/* Parse parameters. */
  	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Oa",
  		&object, Collator_ce_ptr, &array ) == FAILURE )
  	{
  		RETURN_FALSE;
  	}
  
  	/* Fetch the object. */
  	COLLATOR_METHOD_FETCH_OBJECT;
  
  	if (!co || !co->ucoll) {
  		intl_error_set_code( NULL, COLLATOR_ERROR_CODE( co ) );
  		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ),
  			"Object not initialized", 0 );
  		zend_throw_error(NULL, "Object not initialized");
  
  		RETURN_FALSE;
  	}
  
  	/*
  	 * Sort specified array.
  	 */
  	hash = Z_ARRVAL_P( array );
  
  	if( !hash || zend_hash_num_elements( hash ) == 0 )
  		RETURN_TRUE;
  
  	/* Create bufers */
  	sortKeyBuf     = ecalloc( sortKeyBufSize,     sizeof( char    ) );
  	sortKeyIndxBuf = ecalloc( sortKeyIndxBufSize, sizeof( uint8_t ) );
  	utf16_buf      = eumalloc( utf16_buf_size );
  
  	/* Iterate through input hash and create a sort key for each value. */
  	ZEND_HASH_FOREACH_VAL(hash, hashData) {
  		/* Convert current hash item from UTF-8 to UTF-16LE and save the result to utf16_buf. */
  
  		utf16_len = utf16_buf_size;
  
  		/* Process string values only. */
  		if( Z_TYPE_P( hashData ) == IS_STRING )
  		{
  			intl_convert_utf8_to_utf16( &utf16_buf, &utf16_len, Z_STRVAL_P( hashData ), Z_STRLEN_P( hashData ), COLLATOR_ERROR_CODE_P( co ) );
  
  			if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) )
  			{
  				intl_error_set_code( NULL, COLLATOR_ERROR_CODE( co ) );
  				intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ), "Sort with sort keys failed", 0 );
  
  				if( utf16_buf )
  					efree( utf16_buf );
  
  				efree( sortKeyIndxBuf );
  				efree( sortKeyBuf );
  
  				RETURN_FALSE;
  			}
  		}
  		else
  		{
  			/* Set empty string */
  			utf16_len = 0;
  			utf16_buf[utf16_len] = 0;
  		}
  
  		if( (utf16_len + 1) > utf16_buf_size )
  			utf16_buf_size = utf16_len + 1;
  
  		/* Get sort key, reallocating the buffer if needed. */
  		bufLeft = sortKeyBufSize - sortKeyBufOffset;
  
  		sortKeyLen = ucol_getSortKey( co->ucoll,
  									  utf16_buf,
  									  utf16_len,
  									  (uint8_t*)sortKeyBuf + sortKeyBufOffset,
  									  bufLeft );
  
  		/* check for sortKeyBuf overflow, increasing its size of the buffer if needed */
  		if( sortKeyLen > bufLeft )
  		{
  			bufIncrement = ( sortKeyLen > DEF_SORT_KEYS_BUF_INCREMENT ) ? sortKeyLen : DEF_SORT_KEYS_BUF_INCREMENT;
  
  			sortKeyBufSize += bufIncrement;
  			bufLeft += bufIncrement;
  
  			sortKeyBuf = erealloc( sortKeyBuf, sortKeyBufSize );
  
  			sortKeyLen = ucol_getSortKey( co->ucoll, utf16_buf, utf16_len, (uint8_t*)sortKeyBuf + sortKeyBufOffset, bufLeft );
  		}
  
  		/*  check sortKeyIndxBuf overflow, increasing its size of the buffer if needed */
  		if( ( sortKeyCount + 1 ) * sortKeyIndxSize > sortKeyIndxBufSize )
  		{
  			bufIncrement = ( sortKeyIndxSize > DEF_SORT_KEYS_INDX_BUF_INCREMENT ) ? sortKeyIndxSize : DEF_SORT_KEYS_INDX_BUF_INCREMENT;
  
  			sortKeyIndxBufSize += bufIncrement;
  
  			sortKeyIndxBuf = erealloc( sortKeyIndxBuf, sortKeyIndxBufSize );
  		}
  
  		sortKeyIndxBuf[sortKeyCount].key = (char*)sortKeyBufOffset;    /* remember just offset, cause address */
  		                                                               /* of 'sortKeyBuf' may be changed due to realloc. */
  		sortKeyIndxBuf[sortKeyCount].zstr = hashData;
  
  		sortKeyBufOffset += sortKeyLen;
  		++sortKeyCount;
  
  	} ZEND_HASH_FOREACH_END();
  
  	/* update ptrs to point to valid keys. */
  	for( j = 0; j < sortKeyCount; j++ )
  		sortKeyIndxBuf[j].key = sortKeyBuf + (ptrdiff_t)sortKeyIndxBuf[j].key;
  
  	/* sort it */
  	zend_sort( sortKeyIndxBuf, sortKeyCount,
  			sortKeyIndxSize, collator_cmp_sort_keys, (swap_func_t)collator_sortkey_swap);
  
  	ZVAL_COPY_VALUE(&garbage, array);
  	/* for resulting hash we'll assign new hash keys rather then reordering */
  	array_init(array);
  
  	for( j = 0; j < sortKeyCount; j++ )
  	{
  		Z_TRY_ADDREF_P( sortKeyIndxBuf[j].zstr );
  		zend_hash_next_index_insert( Z_ARRVAL_P(array), sortKeyIndxBuf[j].zstr);
  	}
  
  	if( utf16_buf )
  		efree( utf16_buf );
  
  	zval_ptr_dtor(&garbage);
  	efree( sortKeyIndxBuf );
  	efree( sortKeyBuf );
  
  	RETURN_TRUE;
  }
  /* }}} */
  
  /* {{{ proto bool Collator::asort( Collator $coll, array(string) $arr )
   * Sort array using specified collator, maintaining index association. }}} */
  /* {{{ proto bool collator_asort( Collator $coll, array(string) $arr )
   * Sort array using specified collator, maintaining index association.
   */
  PHP_FUNCTION( collator_asort )
  {
  	collator_sort_internal( FALSE, INTERNAL_FUNCTION_PARAM_PASSTHRU );
  }
  /* }}} */
  
  /* {{{ proto bool Collator::getSortKey( Collator $coll, string $str )
   * Get a sort key for a string from a Collator. }}} */
  /* {{{ proto bool collator_get_sort_key( Collator $coll, string $str )
   * Get a sort key for a string from a Collator. */
  PHP_FUNCTION( collator_get_sort_key )
  {
  	char*            str      = NULL;
  	size_t           str_len  = 0;
  	UChar*           ustr     = NULL;
  	int32_t          ustr_len = 0;
  	int              key_len = 0;
  	zend_string*     key_str;
  
  	COLLATOR_METHOD_INIT_VARS
  
  	/* Parse parameters. */
  	if( zend_parse_method_parameters( ZEND_NUM_ARGS(), getThis(), "Os",
  		&object, Collator_ce_ptr, &str, &str_len ) == FAILURE )
  	{
  		RETURN_FALSE;
  	}
  
  	/* Fetch the object. */
  	COLLATOR_METHOD_FETCH_OBJECT;
  
  	if (!co || !co->ucoll) {
  		intl_error_set_code( NULL, COLLATOR_ERROR_CODE( co ) );
  		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ),
  			"Object not initialized", 0 );
  		zend_throw_error(NULL, "Object not initialized");
  
  		RETURN_FALSE;
  	}
  
  	/*
  	 * Compare given strings (converting them to UTF-16 first).
  	 */
  
  	/* First convert the strings to UTF-16. */
  	intl_convert_utf8_to_utf16(
  		&ustr, &ustr_len, str, str_len, COLLATOR_ERROR_CODE_P( co ) );
  	if( U_FAILURE( COLLATOR_ERROR_CODE( co ) ) )
  	{
  		/* Set global error code. */
  		intl_error_set_code( NULL, COLLATOR_ERROR_CODE( co ) );
  
  		/* Set error messages. */
  		intl_errors_set_custom_msg( COLLATOR_ERROR_P( co ),
  			"Error converting first argument to UTF-16", 0 );
  		efree( ustr );
  		RETURN_FALSE;
  	}
  
  	/* ucol_getSortKey is exception in that the key length includes the
  	 * NUL terminator*/
  	key_len = ucol_getSortKey(co->ucoll, ustr, ustr_len, NULL, 0);
  	if(!key_len) {
  		efree( ustr );
  		RETURN_FALSE;
  	}
  	key_str = zend_string_alloc(key_len, 0);
  	key_len = ucol_getSortKey(co->ucoll, ustr, ustr_len, (uint8_t*)ZSTR_VAL(key_str), key_len);
  	efree( ustr );
  	if(!key_len) {
  		RETURN_FALSE;
  	}
  	ZSTR_LEN(key_str) = key_len - 1;
  	RETVAL_NEW_STR(key_str);
  }
  /* }}} */
  