src/third_party/icu/source/i18n/ucol_res.cpp

   1 /*
   2 *******************************************************************************
   3 *   Copyright (C) 1996-2013, International Business Machines
   4 *   Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 *   file name:  ucol_res.cpp
   7 *   encoding:   US-ASCII
   8 *   tab size:   8 (not used)
   9 *   indentation:4
  10 *
  11 * Description:
  12 * This file contains dependencies that the collation run-time doesn't normally
  13 * need. This mainly contains resource bundle usage and collation meta information
  14 *
  15 * Modification history
  16 * Date        Name      Comments
  17 * 1996-1999   various members of ICU team maintained C API for collation framework
  18 * 02/16/2001  synwee    Added internal method getPrevSpecialCE
  19 * 03/01/2001  synwee    Added maxexpansion functionality.
  20 * 03/16/2001  weiv      Collation framework is rewritten in C and made UCA compliant
  21 * 12/08/2004  grhoten   Split part of ucol.cpp into ucol_res.cpp
  22 */
  23
  24 #include "unicode/utypes.h"
  25
  26 #if !UCONFIG_NO_COLLATION
  27 #include "unicode/uloc.h"
  28 #include "unicode/coll.h"
  29 #include "unicode/tblcoll.h"
  30 #include "unicode/caniter.h"
  31 #include "unicode/uscript.h"
  32 #include "unicode/ustring.h"
  33
  34 #include "ucol_bld.h"
  35 #include "ucol_imp.h"
  36 #include "ucol_tok.h"
  37 #include "ucol_elm.h"
  38 #include "uresimp.h"
  39 #include "ustr_imp.h"
  40 #include "cstring.h"
  41 #include "umutex.h"
  42 #include "ucln_in.h"
  43 #include "ustrenum.h"
  44 #include "putilimp.h"
  45 #include "utracimp.h"
  46 #include "cmemory.h"
  47 #include "uassert.h"
  48 #include "uenumimp.h"
  49 #include "ulist.h"
  50
  51 U_NAMESPACE_USE
  52
  53 static void ucol_setReorderCodesFromParser(UCollator *coll, UColTokenParser *parser, UErrorCode *status);
  54
  55 // static UCA. There is only one. Collators don't use it.
  56 // It is referenced only in ucol_initUCA and ucol_cleanup
  57 static UCollator* _staticUCA = NULL;
  58 static icu::UInitOnce gStaticUCAInitOnce = U_INITONCE_INITIALIZER;
  59 // static pointer to udata memory. Inited in ucol_initUCA
  60 // used for cleanup in ucol_cleanup
  61 static UDataMemory* UCA_DATA_MEM = NULL;
  62
  63 U_CDECL_BEGIN
  64 static UBool U_CALLCONV
  65 ucol_res_cleanup(void)
  66 {
  67     if (UCA_DATA_MEM) {
  68         udata_close(UCA_DATA_MEM);
  69         UCA_DATA_MEM = NULL;
  70     }
  71     if (_staticUCA) {
  72         ucol_close(_staticUCA);
  73         _staticUCA = NULL;
  74     }
  75     gStaticUCAInitOnce.reset();
  76     return TRUE;
  77 }
  78
  79 static UBool U_CALLCONV
  80 isAcceptableUCA(void * /*context*/,
  81              const char * /*type*/, const char * /*name*/,
  82              const UDataInfo *pInfo){
  83   /* context, type & name are intentionally not used */
  84     if( pInfo->size>=20 &&
  85         pInfo->isBigEndian==U_IS_BIG_ENDIAN &&
  86         pInfo->charsetFamily==U_CHARSET_FAMILY &&
  87         pInfo->dataFormat[0]==UCA_DATA_FORMAT_0 &&   /* dataFormat="UCol" */
  88         pInfo->dataFormat[1]==UCA_DATA_FORMAT_1 &&
  89         pInfo->dataFormat[2]==UCA_DATA_FORMAT_2 &&
  90         pInfo->dataFormat[3]==UCA_DATA_FORMAT_3 &&
  91         pInfo->formatVersion[0]==UCA_FORMAT_VERSION_0
  92 #if UCA_FORMAT_VERSION_1!=0
  93         && pInfo->formatVersion[1]>=UCA_FORMAT_VERSION_1
  94 #endif
  95         //pInfo->formatVersion[1]==UCA_FORMAT_VERSION_1 &&
  96         //pInfo->formatVersion[2]==UCA_FORMAT_VERSION_2 && // Too harsh
  97         //pInfo->formatVersion[3]==UCA_FORMAT_VERSION_3 && // Too harsh
  98         ) {
  99         return TRUE;
 100         // Note: In ICU 51 and earlier,
 101         // we used to check that the UCA data version (pInfo->dataVersion)
 102         // matches the UCD version (u_getUnicodeVersion())
 103         // but that complicated version updates, and
 104         // a mismatch is "only" a problem for handling canonical equivalence.
 105         // It need not be a fatal error.
 106     } else {
 107         return FALSE;
 108     }
 109 }
 110 U_CDECL_END
 111
 112 static void U_CALLCONV ucol_initStaticUCA(UErrorCode &status) {
 113     U_ASSERT(_staticUCA == NULL);
 114     U_ASSERT(UCA_DATA_MEM == NULL);
 115     ucln_i18n_registerCleanup(UCLN_I18N_UCOL_RES, ucol_res_cleanup);
 116
 117     UDataMemory *result = udata_openChoice(U_ICUDATA_COLL, UCA_DATA_TYPE, UCA_DATA_NAME, isAcceptableUCA, NULL, &status);
 118     if(U_FAILURE(status)){
 119         udata_close(result);
 120         return;
 121     }
 122
 123     _staticUCA = ucol_initCollator((const UCATableHeader *)udata_getMemory(result), NULL, NULL, &status);
 124     if(U_SUCCESS(status)){
 125         // Initalize variables for implicit generation
 126         uprv_uca_initImplicitConstants(&status);
 127         UCA_DATA_MEM = result;
 128
 129     }else{
 130         ucol_close(_staticUCA);
 131         _staticUCA = NULL;
 132         udata_close(result);
 133     }
 134 }
 135
 136
 137 /* do not close UCA returned by ucol_initUCA! */
 138 UCollator *
 139 ucol_initUCA(UErrorCode *status) {
 140     umtx_initOnce(gStaticUCAInitOnce, &ucol_initStaticUCA, *status);
 141     return _staticUCA;
 142 }
 143
 144 U_CAPI void U_EXPORT2
 145 ucol_forgetUCA(void)
 146 {
 147     _staticUCA = NULL;
 148     UCA_DATA_MEM = NULL;
 149     gStaticUCAInitOnce.reset();
 150 }
 151
 152 /****************************************************************************/
 153 /* Following are the open/close functions                                   */
 154 /*                                                                          */
 155 /****************************************************************************/
 156 static UCollator*
 157 tryOpeningFromRules(UResourceBundle *collElem, UErrorCode *status) {
 158     int32_t rulesLen = 0;
 159     const UChar *rules = ures_getStringByKey(collElem, "Sequence", &rulesLen, status);
 160     return ucol_openRules(rules, rulesLen, UCOL_DEFAULT, UCOL_DEFAULT, NULL, status);
 161 }
 162
 163
 164 // API in ucol_imp.h
 165
 166 U_CFUNC UCollator*
 167 ucol_open_internal(const char *loc,
 168                    UErrorCode *status)
 169 {
 170     UErrorCode intStatus = U_ZERO_ERROR;
 171     const UCollator* UCA = ucol_initUCA(status);
 172
 173     /* New version */
 174     if(U_FAILURE(*status)) return 0;
 175
 176
 177
 178     UCollator *result = NULL;
 179     UResourceBundle *b = ures_open(U_ICUDATA_COLL, loc, status);
 180
 181     /* we try to find stuff from keyword */
 182     UResourceBundle *collations = ures_getByKey(b, "collations", NULL, status);
 183     UResourceBundle *collElem = NULL;
 184     char keyBuffer[256];
 185     // if there is a keyword, we pick it up and try to get elements
 186     if(!uloc_getKeywordValue(loc, "collation", keyBuffer, 256, status) ||
 187         !uprv_strcmp(keyBuffer,"default")) { /* Treat 'zz@collation=default' as 'zz'. */
 188         // no keyword. we try to find the default setting, which will give us the keyword value
 189         intStatus = U_ZERO_ERROR;
 190         // finding default value does not affect collation fallback status
 191         UResourceBundle *defaultColl = ures_getByKeyWithFallback(collations, "default", NULL, &intStatus);
 192         if(U_SUCCESS(intStatus)) {
 193             int32_t defaultKeyLen = 0;
 194             const UChar *defaultKey = ures_getString(defaultColl, &defaultKeyLen, &intStatus);
 195             u_UCharsToChars(defaultKey, keyBuffer, defaultKeyLen);
 196             keyBuffer[defaultKeyLen] = 0;
 197         } else {
 198             *status = U_INTERNAL_PROGRAM_ERROR;
 199             return NULL;
 200         }
 201         ures_close(defaultColl);
 202     }
 203     collElem = ures_getByKeyWithFallback(collations, keyBuffer, collations, status);
 204     collations = NULL; // We just reused the collations object as collElem.
 205
 206     UResourceBundle *binary = NULL;
 207     UResourceBundle *reorderRes = NULL;
 208
 209     if(*status == U_MISSING_RESOURCE_ERROR) { /* We didn't find the tailoring data, we fallback to the UCA */
 210         *status = U_USING_DEFAULT_WARNING;
 211         result = ucol_initCollator(UCA->image, result, UCA, status);
 212         if (U_FAILURE(*status)) {
 213             goto clean;
 214         }
 215         // if we use UCA, real locale is root
 216         ures_close(b);
 217         b = ures_open(U_ICUDATA_COLL, "", status);
 218         ures_close(collElem);
 219         collElem = ures_open(U_ICUDATA_COLL, "", status);
 220         if(U_FAILURE(*status)) {
 221             goto clean;
 222         }
 223         result->hasRealData = FALSE;
 224     } else if(U_SUCCESS(*status)) {
 225         intStatus = U_ZERO_ERROR;
 226
 227         binary = ures_getByKey(collElem, "%%CollationBin", NULL, &intStatus);
 228
 229         if(intStatus == U_MISSING_RESOURCE_ERROR) { /* we didn't find the binary image, we should use the rules */
 230             binary = NULL;
 231             result = tryOpeningFromRules(collElem, status);
 232             if(U_FAILURE(*status)) {
 233                 goto clean;
 234             }
 235         } else if(U_SUCCESS(intStatus)) { /* otherwise, we'll pick a collation data that exists */
 236             int32_t len = 0;
 237             const uint8_t *inData = ures_getBinary(binary, &len, status);
 238             if(U_FAILURE(*status)) {
 239                 goto clean;
 240             }
 241             UCATableHeader *colData = (UCATableHeader *)inData;
 242             if(uprv_memcmp(colData->UCAVersion, UCA->image->UCAVersion, sizeof(UVersionInfo)) != 0 ||
 243                 uprv_memcmp(colData->UCDVersion, UCA->image->UCDVersion, sizeof(UVersionInfo)) != 0 ||
 244                 colData->version[0] != UCOL_BUILDER_VERSION)
 245             {
 246                 *status = U_DIFFERENT_UCA_VERSION;
 247                 result = tryOpeningFromRules(collElem, status);
 248             } else {
 249                 if(U_FAILURE(*status)){
 250                     goto clean;
 251                 }
 252                 if((uint32_t)len > (paddedsize(sizeof(UCATableHeader)) + paddedsize(sizeof(UColOptionSet)))) {
 253                     result = ucol_initCollator((const UCATableHeader *)inData, result, UCA, status);
 254                     if(U_FAILURE(*status)){
 255                         goto clean;
 256                     }
 257                     result->hasRealData = TRUE;
 258                 } else {
 259                     result = ucol_initCollator(UCA->image, result, UCA, status);
 260                     ucol_setOptionsFromHeader(result, (UColOptionSet *)(inData+((const UCATableHeader *)inData)->options), status);
 261                     if(U_FAILURE(*status)){
 262                         goto clean;
 263                     }
 264                     result->hasRealData = FALSE;
 265                 }
 266                 result->freeImageOnClose = FALSE;
 267
 268                 reorderRes = ures_getByKey(collElem, "%%ReorderCodes", NULL, &intStatus);
 269                 if (U_SUCCESS(intStatus)) {
 270                     int32_t reorderCodesLen = 0;
 271                     const int32_t* reorderCodes = ures_getIntVector(reorderRes, &reorderCodesLen, status);
 272                     if (reorderCodesLen > 0) {
 273                         ucol_setReorderCodes(result, reorderCodes, reorderCodesLen, status);
 274                         // copy the reorder codes into the default reorder codes
 275                         result->defaultReorderCodesLength = result->reorderCodesLength;
 276                         result->defaultReorderCodes =  (int32_t*) uprv_malloc(result->defaultReorderCodesLength * sizeof(int32_t));
 277                         uprv_memcpy(result->defaultReorderCodes, result->reorderCodes, result->defaultReorderCodesLength * sizeof(int32_t));
 278                         result->freeDefaultReorderCodesOnClose = TRUE;
 279                     }
 280                     if (U_FAILURE(*status)) {
 281                         goto clean;
 282                     }
 283                 }
 284             }
 285
 286         } else { // !U_SUCCESS(binaryStatus)
 287             if(U_SUCCESS(*status)) {
 288                 *status = intStatus; // propagate underlying error
 289             }
 290             goto clean;
 291         }
 292         intStatus = U_ZERO_ERROR;
 293         result->rules = ures_getStringByKey(collElem, "Sequence", &result->rulesLength, &intStatus);
 294         result->freeRulesOnClose = FALSE;
 295     } else { /* There is another error, and we're just gonna clean up */
 296         goto clean;
 297     }
 298
 299     intStatus = U_ZERO_ERROR;
 300     result->ucaRules = ures_getStringByKey(b,"UCARules",NULL,&intStatus);
 301
 302     if(loc == NULL) {
 303         loc = ures_getLocaleByType(b, ULOC_ACTUAL_LOCALE, status);
 304     }
 305     result->requestedLocale = uprv_strdup(loc);
 306     /* test for NULL */
 307     if (result->requestedLocale == NULL) {
 308         *status = U_MEMORY_ALLOCATION_ERROR;
 309         goto clean;
 310     }
 311     loc = ures_getLocaleByType(collElem, ULOC_ACTUAL_LOCALE, status);
 312     result->actualLocale = uprv_strdup(loc);
 313     /* test for NULL */
 314     if (result->actualLocale == NULL) {
 315         *status = U_MEMORY_ALLOCATION_ERROR;
 316         goto clean;
 317     }
 318     loc = ures_getLocaleByType(b, ULOC_ACTUAL_LOCALE, status);
 319     result->validLocale = uprv_strdup(loc);
 320     /* test for NULL */
 321     if (result->validLocale == NULL) {
 322         *status = U_MEMORY_ALLOCATION_ERROR;
 323         goto clean;
 324     }
 325
 326     ures_close(b);
 327     ures_close(collElem);
 328     ures_close(binary);
 329     ures_close(reorderRes);
 330     return result;
 331
 332 clean:
 333     ures_close(b);
 334     ures_close(collElem);
 335     ures_close(binary);
 336     ures_close(reorderRes);
 337     ucol_close(result);
 338     return NULL;
 339 }
 340
 341 U_CAPI UCollator*
 342 ucol_open(const char *loc,
 343           UErrorCode *status)
 344 {
 345     U_NAMESPACE_USE
 346
 347     UTRACE_ENTRY_OC(UTRACE_UCOL_OPEN);
 348     UTRACE_DATA1(UTRACE_INFO, "locale = \"%s\"", loc);
 349     UCollator *result = NULL;
 350
 351 #if !UCONFIG_NO_SERVICE
 352     result = Collator::createUCollator(loc, status);
 353     if (result == NULL)
 354 #endif
 355     {
 356         result = ucol_open_internal(loc, status);
 357     }
 358     UTRACE_EXIT_PTR_STATUS(result, *status);
 359     return result;
 360 }
 361
 362
 363 UCollator*
 364 ucol_openRulesForImport( const UChar        *rules,
 365                          int32_t            rulesLength,
 366                          UColAttributeValue normalizationMode,
 367                          UCollationStrength strength,
 368                          UParseError        *parseError,
 369                          GetCollationRulesFunction  importFunc,
 370                          void* context,
 371                          UErrorCode         *status)
 372 {
 373     UColTokenParser src;
 374     UColAttributeValue norm;
 375     UParseError tErr;
 376
 377     if(status == NULL || U_FAILURE(*status)){
 378         return 0;
 379     }
 380
 381     if(rules == NULL || rulesLength < -1) {
 382         *status = U_ILLEGAL_ARGUMENT_ERROR;
 383         return 0;
 384     }
 385
 386     if(rulesLength == -1) {
 387         rulesLength = u_strlen(rules);
 388     }
 389
 390     if(parseError == NULL){
 391         parseError = &tErr;
 392     }
 393
 394     switch(normalizationMode) {
 395     case UCOL_OFF:
 396     case UCOL_ON:
 397     case UCOL_DEFAULT:
 398         norm = normalizationMode;
 399         break;
 400     default:
 401         *status = U_ILLEGAL_ARGUMENT_ERROR;
 402         return 0;
 403     }
 404
 405     UCollator *result = NULL;
 406     UCATableHeader *table = NULL;
 407     UCollator *UCA = ucol_initUCA(status);
 408
 409     if(U_FAILURE(*status)){
 410         return NULL;
 411     }
 412
 413     ucol_tok_initTokenList(&src, rules, rulesLength, UCA, importFunc, context, status);
 414     ucol_tok_assembleTokenList(&src,parseError, status);
 415
 416     if(U_FAILURE(*status)) {
 417         /* if status is U_ILLEGAL_ARGUMENT_ERROR, src->current points at the offending option */
 418         /* if status is U_INVALID_FORMAT_ERROR, src->current points after the problematic part of the rules */
 419         /* so something might be done here... or on lower level */
 420 #ifdef UCOL_DEBUG
 421         if(*status == U_ILLEGAL_ARGUMENT_ERROR) {
 422             fprintf(stderr, "bad option starting at offset %i\n", (int)(src.current-src.source));
 423         } else {
 424             fprintf(stderr, "invalid rule just before offset %i\n", (int)(src.current-src.source));
 425         }
 426 #endif
 427         goto cleanup;
 428     }
 429
 430      /* if we have a set of rules, let's make something of it */
 431     if(src.resultLen > 0 || src.removeSet != NULL) {
 432         /* also, if we wanted to remove some contractions, we should make a tailoring */
 433         table = ucol_assembleTailoringTable(&src, status);
 434         if(U_SUCCESS(*status)) {
 435             // builder version
 436             table->version[0] = UCOL_BUILDER_VERSION;
 437             // no tailoring information on this level
 438             table->version[1] = table->version[2] = table->version[3] = 0;
 439             // set UCD version
 440             u_getUnicodeVersion(table->UCDVersion);
 441             // set UCA version
 442             uprv_memcpy(table->UCAVersion, UCA->image->UCAVersion, sizeof(UVersionInfo));
 443             result = ucol_initCollator(table, 0, UCA, status);
 444             if (U_FAILURE(*status)) {
 445                 goto cleanup;
 446             }
 447             result->hasRealData = TRUE;
 448             result->freeImageOnClose = TRUE;
 449         } else {
 450             goto cleanup;
 451         }
 452     } else { /* no rules, but no error either */
 453         // must be only options
 454         // We will init the collator from UCA
 455         result = ucol_initCollator(UCA->image, 0, UCA, status);
 456         // Check for null result
 457         if (U_FAILURE(*status)) {
 458             goto cleanup;
 459         }
 460         // And set only the options
 461         UColOptionSet *opts = (UColOptionSet *)uprv_malloc(sizeof(UColOptionSet));
 462         /* test for NULL */
 463         if (opts == NULL) {
 464             *status = U_MEMORY_ALLOCATION_ERROR;
 465             goto cleanup;
 466         }
 467         uprv_memcpy(opts, src.opts, sizeof(UColOptionSet));
 468         ucol_setOptionsFromHeader(result, opts, status);
 469         result->freeOptionsOnClose = TRUE;
 470         result->hasRealData = FALSE;
 471         result->freeImageOnClose = FALSE;
 472     }
 473
 474     ucol_setReorderCodesFromParser(result, &src, status);
 475
 476     if(U_SUCCESS(*status)) {
 477         UChar *newRules;
 478         result->dataVersion[0] = UCOL_BUILDER_VERSION;
 479         if(rulesLength > 0) {
 480             newRules = (UChar *)uprv_malloc((rulesLength+1)*U_SIZEOF_UCHAR);
 481             /* test for NULL */
 482             if (newRules == NULL) {
 483                 *status = U_MEMORY_ALLOCATION_ERROR;
 484                 goto cleanup;
 485             }
 486             uprv_memcpy(newRules, rules, rulesLength*U_SIZEOF_UCHAR);
 487             newRules[rulesLength]=0;
 488             result->rules = newRules;
 489             result->rulesLength = rulesLength;
 490             result->freeRulesOnClose = TRUE;
 491         }
 492         result->ucaRules = NULL;
 493         result->actualLocale = NULL;
 494         result->validLocale = NULL;
 495         result->requestedLocale = NULL;
 496         ucol_buildPermutationTable(result, status);
 497         ucol_setAttribute(result, UCOL_STRENGTH, strength, status);
 498         ucol_setAttribute(result, UCOL_NORMALIZATION_MODE, norm, status);
 499     } else {
 500 cleanup:
 501         if(result != NULL) {
 502             ucol_close(result);
 503         } else {
 504             if(table != NULL) {
 505                 uprv_free(table);
 506             }
 507         }
 508         result = NULL;
 509     }
 510
 511     ucol_tok_closeTokenList(&src);
 512
 513     return result;
 514 }
 515
 516 U_CAPI UCollator* U_EXPORT2
 517 ucol_openRules( const UChar        *rules,
 518                int32_t            rulesLength,
 519                UColAttributeValue normalizationMode,
 520                UCollationStrength strength,
 521                UParseError        *parseError,
 522                UErrorCode         *status)
 523 {
 524     return ucol_openRulesForImport(rules,
 525                                    rulesLength,
 526                                    normalizationMode,
 527                                    strength,
 528                                    parseError,
 529                                    ucol_tok_getRulesFromBundle,
 530                                    NULL,
 531                                    status);
 532 }
 533
 534 U_CAPI int32_t U_EXPORT2
 535 ucol_getRulesEx(const UCollator *coll, UColRuleOption delta, UChar *buffer, int32_t bufferLen) {
 536     UErrorCode status = U_ZERO_ERROR;
 537     int32_t len = 0;
 538     int32_t UCAlen = 0;
 539     const UChar* ucaRules = 0;
 540     const UChar *rules = ucol_getRules(coll, &len);
 541     if(delta == UCOL_FULL_RULES) {
 542         /* take the UCA rules and append real rules at the end */
 543         /* UCA rules will be probably coming from the root RB */
 544         ucaRules = coll->ucaRules;
 545         if (ucaRules) {
 546             UCAlen = u_strlen(ucaRules);
 547         }
 548         /*
 549         ucaRules = ures_getStringByKey(coll->rb,"UCARules",&UCAlen,&status);
 550         UResourceBundle* cresb = ures_getByKeyWithFallback(coll->rb, "collations", NULL, &status);
 551         UResourceBundle*  uca = ures_getByKeyWithFallback(cresb, "UCA", NULL, &status);
 552         ucaRules = ures_getStringByKey(uca,"Sequence",&UCAlen,&status);
 553         ures_close(uca);
 554         ures_close(cresb);
 555         */
 556     }
 557     if(U_FAILURE(status)) {
 558         return 0;
 559     }
 560     if(buffer!=0 && bufferLen>0){
 561         *buffer=0;
 562         if(UCAlen > 0) {
 563             u_memcpy(buffer, ucaRules, uprv_min(UCAlen, bufferLen));
 564         }
 565         if(len > 0 && bufferLen > UCAlen) {
 566             u_memcpy(buffer+UCAlen, rules, uprv_min(len, bufferLen-UCAlen));
 567         }
 568     }
 569     return u_terminateUChars(buffer, bufferLen, len+UCAlen, &status);
 570 }
 571
 572 static const UChar _NUL = 0;
 573
 574 U_CAPI const UChar* U_EXPORT2
 575 ucol_getRules(    const    UCollator       *coll,
 576               int32_t            *length)
 577 {
 578     if(coll->rules != NULL) {
 579         *length = coll->rulesLength;
 580         return coll->rules;
 581     }
 582     else {
 583         *length = 0;
 584         return &_NUL;
 585     }
 586 }
 587
 588 U_CAPI UBool U_EXPORT2
 589 ucol_equals(const UCollator *source, const UCollator *target) {
 590     UErrorCode status = U_ZERO_ERROR;
 591     // if pointers are equal, collators are equal
 592     if(source == target) {
 593         return TRUE;
 594     }
 595     int32_t i = 0, j = 0;
 596     // if any of attributes are different, collators are not equal
 597     for(i = 0; i < UCOL_ATTRIBUTE_COUNT; i++) {
 598         if(ucol_getAttribute(source, (UColAttribute)i, &status) != ucol_getAttribute(target, (UColAttribute)i, &status) || U_FAILURE(status)) {
 599             return FALSE;
 600         }
 601     }
 602     if (source->reorderCodesLength != target->reorderCodesLength){
 603         return FALSE;
 604     }
 605     for (i = 0; i < source->reorderCodesLength; i++) {
 606         if(source->reorderCodes[i] != target->reorderCodes[i]) {
 607             return FALSE;
 608         }
 609     }
 610
 611     int32_t sourceRulesLen = 0, targetRulesLen = 0;
 612     const UChar *sourceRules = ucol_getRules(source, &sourceRulesLen);
 613     const UChar *targetRules = ucol_getRules(target, &targetRulesLen);
 614
 615     if(sourceRulesLen == targetRulesLen && u_strncmp(sourceRules, targetRules, sourceRulesLen) == 0) {
 616         // all the attributes are equal and the rules are equal - collators are equal
 617         return(TRUE);
 618     }
 619     // hard part, need to construct tree from rules and see if they yield the same tailoring
 620     UBool result = TRUE;
 621     UParseError parseError;
 622     UColTokenParser sourceParser, targetParser;
 623     int32_t sourceListLen = 0, targetListLen = 0;
 624     ucol_tok_initTokenList(&sourceParser, sourceRules, sourceRulesLen, source->UCA, ucol_tok_getRulesFromBundle, NULL, &status);
 625     ucol_tok_initTokenList(&targetParser, targetRules, targetRulesLen, target->UCA, ucol_tok_getRulesFromBundle, NULL, &status);
 626     sourceListLen = ucol_tok_assembleTokenList(&sourceParser, &parseError, &status);
 627     targetListLen = ucol_tok_assembleTokenList(&targetParser, &parseError, &status);
 628
 629     if(sourceListLen != targetListLen) {
 630         // different number of resets
 631         result = FALSE;
 632     } else {
 633         UColToken *sourceReset = NULL, *targetReset = NULL;
 634         UChar *sourceResetString = NULL, *targetResetString = NULL;
 635         int32_t sourceStringLen = 0, targetStringLen = 0;
 636         for(i = 0; i < sourceListLen; i++) {
 637             sourceReset = sourceParser.lh[i].reset;
 638             sourceResetString = sourceParser.source+(sourceReset->source & 0xFFFFFF);
 639             sourceStringLen = sourceReset->source >> 24;
 640             for(j = 0; j < sourceListLen; j++) {
 641                 targetReset = targetParser.lh[j].reset;
 642                 targetResetString = targetParser.source+(targetReset->source & 0xFFFFFF);
 643                 targetStringLen = targetReset->source >> 24;
 644                 if(sourceStringLen == targetStringLen && (u_strncmp(sourceResetString, targetResetString, sourceStringLen) == 0)) {
 645                     sourceReset = sourceParser.lh[i].first;
 646                     targetReset = targetParser.lh[j].first;
 647                     while(sourceReset != NULL && targetReset != NULL) {
 648                         sourceResetString = sourceParser.source+(sourceReset->source & 0xFFFFFF);
 649                         sourceStringLen = sourceReset->source >> 24;
 650                         targetResetString = targetParser.source+(targetReset->source & 0xFFFFFF);
 651                         targetStringLen = targetReset->source >> 24;
 652                         if(sourceStringLen != targetStringLen || (u_strncmp(sourceResetString, targetResetString, sourceStringLen) != 0)) {
 653                             result = FALSE;
 654                             goto returnResult;
 655                         }
 656                         // probably also need to check the expansions
 657                         if(sourceReset->expansion) {
 658                             if(!targetReset->expansion) {
 659                                 result = FALSE;
 660                                 goto returnResult;
 661                             } else {
 662                                 // compare expansions
 663                                 sourceResetString = sourceParser.source+(sourceReset->expansion& 0xFFFFFF);
 664                                 sourceStringLen = sourceReset->expansion >> 24;
 665                                 targetResetString = targetParser.source+(targetReset->expansion & 0xFFFFFF);
 666                                 targetStringLen = targetReset->expansion >> 24;
 667                                 if(sourceStringLen != targetStringLen || (u_strncmp(sourceResetString, targetResetString, sourceStringLen) != 0)) {
 668                                     result = FALSE;
 669                                     goto returnResult;
 670                                 }
 671                             }
 672                         } else {
 673                             if(targetReset->expansion) {
 674                                 result = FALSE;
 675                                 goto returnResult;
 676                             }
 677                         }
 678                         sourceReset = sourceReset->next;
 679                         targetReset = targetReset->next;
 680                     }
 681                     if(sourceReset != targetReset) { // at least one is not NULL
 682                         // there are more tailored elements in one list
 683                         result = FALSE;
 684                         goto returnResult;
 685                     }
 686
 687
 688                     break;
 689                 }
 690             }
 691             // couldn't find the reset anchor, so the collators are not equal
 692             if(j == sourceListLen) {
 693                 result = FALSE;
 694                 goto returnResult;
 695             }
 696         }
 697     }
 698
 699 returnResult:
 700     ucol_tok_closeTokenList(&sourceParser);
 701     ucol_tok_closeTokenList(&targetParser);
 702     return result;
 703
 704 }
 705
 706 U_CAPI int32_t U_EXPORT2
 707 ucol_getDisplayName(    const    char        *objLoc,
 708                     const    char        *dispLoc,
 709                     UChar             *result,
 710                     int32_t         resultLength,
 711                     UErrorCode        *status)
 712 {
 713     U_NAMESPACE_USE
 714
 715     if(U_FAILURE(*status)) return -1;
 716     UnicodeString dst;
 717     if(!(result==NULL && resultLength==0)) {
 718         // NULL destination for pure preflighting: empty dummy string
 719         // otherwise, alias the destination buffer
 720         dst.setTo(result, 0, resultLength);
 721     }
 722     Collator::getDisplayName(Locale(objLoc), Locale(dispLoc), dst);
 723     return dst.extract(result, resultLength, *status);
 724 }
 725
 726 U_CAPI const char* U_EXPORT2
 727 ucol_getAvailable(int32_t index)
 728 {
 729     int32_t count = 0;
 730     const Locale *loc = Collator::getAvailableLocales(count);
 731     if (loc != NULL && index < count) {
 732         return loc[index].getName();
 733     }
 734     return NULL;
 735 }
 736
 737 U_CAPI int32_t U_EXPORT2
 738 ucol_countAvailable()
 739 {
 740     int32_t count = 0;
 741     Collator::getAvailableLocales(count);
 742     return count;
 743 }
 744
 745 #if !UCONFIG_NO_SERVICE
 746 U_CAPI UEnumeration* U_EXPORT2
 747 ucol_openAvailableLocales(UErrorCode *status) {
 748     U_NAMESPACE_USE
 749
 750     // This is a wrapper over Collator::getAvailableLocales()
 751     if (U_FAILURE(*status)) {
 752         return NULL;
 753     }
 754     StringEnumeration *s = icu::Collator::getAvailableLocales();
 755     if (s == NULL) {
 756         *status = U_MEMORY_ALLOCATION_ERROR;
 757         return NULL;
 758     }
 759     return uenum_openFromStringEnumeration(s, status);
 760 }
 761 #endif
 762
 763 // Note: KEYWORDS[0] != RESOURCE_NAME - alan
 764
 765 static const char RESOURCE_NAME[] = "collations";
 766
 767 static const char* const KEYWORDS[] = { "collation" };
 768
 769 #define KEYWORD_COUNT (sizeof(KEYWORDS)/sizeof(KEYWORDS[0]))
 770
 771 U_CAPI UEnumeration* U_EXPORT2
 772 ucol_getKeywords(UErrorCode *status) {
 773     UEnumeration *result = NULL;
 774     if (U_SUCCESS(*status)) {
 775         return uenum_openCharStringsEnumeration(KEYWORDS, KEYWORD_COUNT, status);
 776     }
 777     return result;
 778 }
 779
 780 U_CAPI UEnumeration* U_EXPORT2
 781 ucol_getKeywordValues(const char *keyword, UErrorCode *status) {
 782     if (U_FAILURE(*status)) {
 783         return NULL;
 784     }
 785     // hard-coded to accept exactly one collation keyword
 786     // modify if additional collation keyword is added later
 787     if (keyword==NULL || uprv_strcmp(keyword, KEYWORDS[0])!=0)
 788     {
 789         *status = U_ILLEGAL_ARGUMENT_ERROR;
 790         return NULL;
 791     }
 792     return ures_getKeywordValues(U_ICUDATA_COLL, RESOURCE_NAME, status);
 793 }
 794
 795 static const UEnumeration defaultKeywordValues = {
 796     NULL,
 797     NULL,
 798     ulist_close_keyword_values_iterator,
 799     ulist_count_keyword_values,
 800     uenum_unextDefault,
 801     ulist_next_keyword_value,
 802     ulist_reset_keyword_values_iterator
 803 };
 804
 805 #include <stdio.h>
 806
 807 U_CAPI UEnumeration* U_EXPORT2
 808 ucol_getKeywordValuesForLocale(const char* /*key*/, const char* locale,
 809                                UBool /*commonlyUsed*/, UErrorCode* status) {
 810     /* Get the locale base name. */
 811     char localeBuffer[ULOC_FULLNAME_CAPACITY] = "";
 812     uloc_getBaseName(locale, localeBuffer, sizeof(localeBuffer), status);
 813
 814     /* Create the 2 lists
 815      * -values is the temp location for the keyword values
 816      * -results hold the actual list used by the UEnumeration object
 817      */
 818     UList *values = ulist_createEmptyList(status);
 819     UList *results = ulist_createEmptyList(status);
 820     UEnumeration *en = (UEnumeration *)uprv_malloc(sizeof(UEnumeration));
 821     if (U_FAILURE(*status) || en == NULL) {
 822         if (en == NULL) {
 823             *status = U_MEMORY_ALLOCATION_ERROR;
 824         } else {
 825             uprv_free(en);
 826         }
 827         ulist_deleteList(values);
 828         ulist_deleteList(results);
 829         return NULL;
 830     }
 831
 832     memcpy(en, &defaultKeywordValues, sizeof(UEnumeration));
 833     en->context = results;
 834
 835     /* Open the resource bundle for collation with the given locale. */
 836     UResourceBundle bundle, collations, collres, defres;
 837     ures_initStackObject(&bundle);
 838     ures_initStackObject(&collations);
 839     ures_initStackObject(&collres);
 840     ures_initStackObject(&defres);
 841
 842     ures_openFillIn(&bundle, U_ICUDATA_COLL, localeBuffer, status);
 843
 844     while (U_SUCCESS(*status)) {
 845         ures_getByKey(&bundle, RESOURCE_NAME, &collations, status);
 846         ures_resetIterator(&collations);
 847         while (U_SUCCESS(*status) && ures_hasNext(&collations)) {
 848             ures_getNextResource(&collations, &collres, status);
 849             const char *key = ures_getKey(&collres);
 850             /* If the key is default, get the string and store it in results list only
 851              * if results list is empty.
 852              */
 853             if (uprv_strcmp(key, "default") == 0) {
 854                 if (ulist_getListSize(results) == 0) {
 855                     char *defcoll = (char *)uprv_malloc(sizeof(char) * ULOC_KEYWORDS_CAPACITY);
 856                     int32_t defcollLength = ULOC_KEYWORDS_CAPACITY;
 857
 858                     ures_getNextResource(&collres, &defres, status);
 859 #if U_CHARSET_FAMILY==U_ASCII_FAMILY
 860                         /* optimize - use the utf-8 string */
 861                     ures_getUTF8String(&defres, defcoll, &defcollLength, TRUE, status);
 862 #else
 863                     {
 864                        const UChar* defString = ures_getString(&defres, &defcollLength, status);
 865                        if(U_SUCCESS(*status)) {
 866                            if(defcollLength+1 > ULOC_KEYWORDS_CAPACITY) {
 867                                 *status = U_BUFFER_OVERFLOW_ERROR;
 868                            } else {
 869                                 u_UCharsToChars(defString, defcoll, defcollLength+1);
 870                            }
 871                        }
 872                     }
 873 #endif
 874
 875                     ulist_addItemBeginList(results, defcoll, TRUE, status);
 876                 }
 877             } else {
 878                 ulist_addItemEndList(values, key, FALSE, status);
 879             }
 880         }
 881
 882         /* If the locale is "" this is root so exit. */
 883         if (uprv_strlen(localeBuffer) == 0) {
 884             break;
 885         }
 886         /* Get the parent locale and open a new resource bundle. */
 887         uloc_getParent(localeBuffer, localeBuffer, sizeof(localeBuffer), status);
 888         ures_openFillIn(&bundle, U_ICUDATA_COLL, localeBuffer, status);
 889     }
 890
 891     ures_close(&defres);
 892     ures_close(&collres);
 893     ures_close(&collations);
 894     ures_close(&bundle);
 895
 896     if (U_SUCCESS(*status)) {
 897         char *value = NULL;
 898         ulist_resetList(values);
 899         while ((value = (char *)ulist_getNext(values)) != NULL) {
 900             if (!ulist_containsString(results, value, (int32_t)uprv_strlen(value))) {
 901                 ulist_addItemEndList(results, value, FALSE, status);
 902                 if (U_FAILURE(*status)) {
 903                     break;
 904                 }
 905             }
 906         }
 907     }
 908
 909     ulist_deleteList(values);
 910
 911     if (U_FAILURE(*status)){
 912         uenum_close(en);
 913         en = NULL;
 914     } else {
 915         ulist_resetList(results);
 916     }
 917
 918     return en;
 919 }
 920
 921 U_CAPI int32_t U_EXPORT2
 922 ucol_getFunctionalEquivalent(char* result, int32_t resultCapacity,
 923                              const char* keyword, const char* locale,
 924                              UBool* isAvailable, UErrorCode* status)
 925 {
 926     // N.B.: Resource name is "collations" but keyword is "collation"
 927     return ures_getFunctionalEquivalent(result, resultCapacity, U_ICUDATA_COLL,
 928         "collations", keyword, locale,
 929         isAvailable, TRUE, status);
 930 }
 931
 932 /* returns the locale name the collation data comes from */
 933 U_CAPI const char * U_EXPORT2
 934 ucol_getLocale(const UCollator *coll, ULocDataLocaleType type, UErrorCode *status) {
 935     return ucol_getLocaleByType(coll, type, status);
 936 }
 937
 938 U_CAPI const char * U_EXPORT2
 939 ucol_getLocaleByType(const UCollator *coll, ULocDataLocaleType type, UErrorCode *status) {
 940     const char *result = NULL;
 941     if(status == NULL || U_FAILURE(*status)) {
 942         return NULL;
 943     }
 944     UTRACE_ENTRY(UTRACE_UCOL_GETLOCALE);
 945     UTRACE_DATA1(UTRACE_INFO, "coll=%p", coll);
 946
 947     if(coll->delegate!=NULL) {
 948       return ((const Collator*)coll->delegate)->getLocale(type, *status).getName();
 949     }
 950     switch(type) {
 951     case ULOC_ACTUAL_LOCALE:
 952         result = coll->actualLocale;
 953         break;
 954     case ULOC_VALID_LOCALE:
 955         result = coll->validLocale;
 956         break;
 957     case ULOC_REQUESTED_LOCALE:
 958         result = coll->requestedLocale;
 959         break;
 960     default:
 961         *status = U_ILLEGAL_ARGUMENT_ERROR;
 962     }
 963     UTRACE_DATA1(UTRACE_INFO, "result = %s", result);
 964     UTRACE_EXIT_STATUS(*status);
 965     return result;
 966 }
 967
 968 U_CFUNC void U_EXPORT2
 969 ucol_setReqValidLocales(UCollator *coll, char *requestedLocaleToAdopt, char *validLocaleToAdopt, char *actualLocaleToAdopt)
 970 {
 971     if (coll) {
 972         if (coll->validLocale) {
 973             uprv_free(coll->validLocale);
 974         }
 975         coll->validLocale = validLocaleToAdopt;
 976         if (coll->requestedLocale) { // should always have
 977             uprv_free(coll->requestedLocale);
 978         }
 979         coll->requestedLocale = requestedLocaleToAdopt;
 980         if (coll->actualLocale) {
 981             uprv_free(coll->actualLocale);
 982         }
 983         coll->actualLocale = actualLocaleToAdopt;
 984     }
 985 }
 986
 987 U_CAPI USet * U_EXPORT2
 988 ucol_getTailoredSet(const UCollator *coll, UErrorCode *status)
 989 {
 990     U_NAMESPACE_USE
 991
 992     if(status == NULL || U_FAILURE(*status)) {
 993         return NULL;
 994     }
 995     if(coll == NULL || coll->UCA == NULL) {
 996         *status = U_ILLEGAL_ARGUMENT_ERROR;
 997         return NULL;
 998     }
 999     UParseError parseError;
1000     UColTokenParser src;
1001     int32_t rulesLen = 0;
1002     const UChar *rules = ucol_getRules(coll, &rulesLen);
1003     UBool startOfRules = TRUE;
1004     // we internally use the C++ class, for the following reasons:
1005     // 1. we need to utilize canonical iterator, which is a C++ only class
1006     // 2. canonical iterator returns UnicodeStrings - USet cannot take them
1007     // 3. USet is internally really UnicodeSet, C is just a wrapper
1008     UnicodeSet *tailored = new UnicodeSet();
1009     UnicodeString pattern;
1010     UnicodeString empty;
1011     CanonicalIterator it(empty, *status);
1012
1013
1014     // The idea is to tokenize the rule set. For each non-reset token,
1015     // we add all the canonicaly equivalent FCD sequences
1016     ucol_tok_initTokenList(&src, rules, rulesLen, coll->UCA, ucol_tok_getRulesFromBundle, NULL, status);
1017     while (ucol_tok_parseNextToken(&src, startOfRules, &parseError, status) != NULL) {
1018         startOfRules = FALSE;
1019         if(src.parsedToken.strength != UCOL_TOK_RESET) {
1020             const UChar *stuff = src.source+(src.parsedToken.charsOffset);
1021             it.setSource(UnicodeString(stuff, src.parsedToken.charsLen), *status);
1022             pattern = it.next();
1023             while(!pattern.isBogus()) {
1024                 if(Normalizer::quickCheck(pattern, UNORM_FCD, *status) != UNORM_NO) {
1025                     tailored->add(pattern);
1026                 }
1027                 pattern = it.next();
1028             }
1029         }
1030     }
1031     ucol_tok_closeTokenList(&src);
1032     return (USet *)tailored;
1033 }
1034
1035 /*
1036  * Collation Reordering
1037  */
1038
1039 void ucol_setReorderCodesFromParser(UCollator *coll, UColTokenParser *parser, UErrorCode *status) {
1040     if (U_FAILURE(*status)) {
1041         return;
1042     }
1043
1044     if (parser->reorderCodesLength == 0 || parser->reorderCodes == NULL) {
1045         return;
1046     }
1047
1048     coll->reorderCodesLength = 0;
1049     if (coll->reorderCodes != NULL && coll->freeReorderCodesOnClose == TRUE) {
1050         uprv_free(coll->reorderCodes);
1051     }
1052     coll->reorderCodes = NULL;
1053     coll->freeReorderCodesOnClose = FALSE;
1054
1055     if (coll->defaultReorderCodes != NULL && coll->freeDefaultReorderCodesOnClose == TRUE) {
1056         uprv_free(coll->defaultReorderCodes);
1057     }
1058     coll->freeDefaultReorderCodesOnClose = FALSE;
1059     coll->defaultReorderCodesLength = parser->reorderCodesLength;
1060     coll->defaultReorderCodes =  (int32_t*) uprv_malloc(coll->defaultReorderCodesLength * sizeof(int32_t));
1061     if (coll->defaultReorderCodes == NULL) {
1062         *status = U_MEMORY_ALLOCATION_ERROR;
1063         return;
1064     }
1065     uprv_memcpy(coll->defaultReorderCodes, parser->reorderCodes, coll->defaultReorderCodesLength * sizeof(int32_t));
1066     coll->freeDefaultReorderCodesOnClose = TRUE;
1067
1068     coll->reorderCodesLength = parser->reorderCodesLength;
1069     coll->reorderCodes = (int32_t*) uprv_malloc(coll->reorderCodesLength * sizeof(int32_t));
1070     if (coll->reorderCodes == NULL) {
1071         *status = U_MEMORY_ALLOCATION_ERROR;
1072         return;
1073     }
1074     uprv_memcpy(coll->reorderCodes, parser->reorderCodes, coll->reorderCodesLength * sizeof(int32_t));
1075     coll->freeReorderCodesOnClose = TRUE;
1076 }
1077
1078 /*
1079  * Data is stored in the reorder code to lead byte table as:
1080  *  index count - unsigned short (2 bytes) - number of index entries
1081  *  data size - unsigned short (2 bytes) - number of unsigned short data elements
1082  *  index[index count] - array of 2 unsigned shorts (4 bytes each entry)
1083  *      - reorder code, offset
1084  *      - index is sorted by reorder code
1085  *      - if an offset has the high bit set then it is not an offset but a single data entry
1086  *        once the high bit is stripped off
1087  *  data[data size] - array of unsigned short (2 bytes each entry)
1088  *      - the data is an usigned short count followed by count number
1089  *        of lead bytes stored in an unsigned short
1090  */
1091 U_CFUNC int U_EXPORT2
1092 ucol_getLeadBytesForReorderCode(const UCollator *uca, int reorderCode, uint16_t* returnLeadBytes, int returnCapacity) {
1093     uint16_t reorderCodeIndexLength = *((uint16_t*) ((uint8_t *)uca->image + uca->image->scriptToLeadByte));
1094     uint16_t* reorderCodeIndex = (uint16_t*) ((uint8_t *)uca->image + uca->image->scriptToLeadByte + 2 *sizeof(uint16_t));
1095
1096     // reorder code index is 2 uint16_t's - reorder code + offset
1097     for (int i = 0; i < reorderCodeIndexLength; i++) {
1098         if (reorderCode == reorderCodeIndex[i*2]) {
1099             uint16_t dataOffset = reorderCodeIndex[(i*2) + 1];
1100             if ((dataOffset & 0x8000) == 0x8000) {
1101                 // offset isn't offset but instead is a single data element
1102                 if (returnCapacity >= 1) {
1103                     returnLeadBytes[0] = dataOffset & ~0x8000;
1104                     return 1;
1105                 }
1106                 return 0;
1107             }
1108             uint16_t* dataOffsetBase = (uint16_t*) ((uint8_t *)reorderCodeIndex + reorderCodeIndexLength * (2 * sizeof(uint16_t)));
1109             uint16_t leadByteCount = *(dataOffsetBase + dataOffset);
1110             leadByteCount = leadByteCount > returnCapacity ? returnCapacity : leadByteCount;
1111             uprv_memcpy(returnLeadBytes, dataOffsetBase + dataOffset + 1, leadByteCount * sizeof(uint16_t));
1112             return leadByteCount;
1113         }
1114     }
1115     return 0;
1116 }
1117
1118 /*
1119  * Data is stored in the lead byte to reorder code table as:
1120  *  index count - unsigned short (2 bytes) - number of index entries
1121  *  data size - unsigned short (2 bytes) - number of unsigned short data elements
1122  *  index[index count] - array of unsigned short (2 bytes each entry)
1123  *      - index is sorted by lead byte
1124  *      - if an index has the high bit set then it is not an index but a single data entry
1125  *        once the high bit is stripped off
1126  *  data[data size] - array of unsigned short (2 bytes each entry)
1127  *      - the data is an usigned short count followed by count number of reorder codes
1128  */
1129 U_CFUNC int U_EXPORT2
1130 ucol_getReorderCodesForLeadByte(const UCollator *uca, int leadByte, int16_t* returnReorderCodes, int returnCapacity) {
1131     uint16_t* leadByteTable = ((uint16_t*) ((uint8_t *)uca->image + uca->image->leadByteToScript));
1132     uint16_t leadByteIndexLength = *leadByteTable;
1133     if (leadByte >= leadByteIndexLength) {
1134         return 0;
1135     }
1136     uint16_t leadByteIndex = *(leadByteTable + (2 + leadByte));
1137
1138     if ((leadByteIndex & 0x8000) == 0x8000) {
1139         // offset isn't offset but instead is a single data element
1140         if (returnCapacity >= 1) {
1141             returnReorderCodes[0] = leadByteIndex & ~0x8000;
1142             return 1;
1143         }
1144         return 0;
1145     }
1146     //uint16_t* dataOffsetBase = leadByteTable + (2 + leadByteIndexLength);
1147     uint16_t* reorderCodeData = leadByteTable + (2 + leadByteIndexLength) + leadByteIndex;
1148     uint16_t reorderCodeCount = *reorderCodeData > returnCapacity ? returnCapacity : *reorderCodeData;
1149     uprv_memcpy(returnReorderCodes, reorderCodeData + 1, reorderCodeCount * sizeof(uint16_t));
1150     return reorderCodeCount;
1151 }
1152
1153 // used to mark ignorable reorder code slots
1154 static const int32_t UCOL_REORDER_CODE_IGNORE = UCOL_REORDER_CODE_LIMIT + 1;
1155
1156 U_CFUNC void U_EXPORT2
1157 ucol_buildPermutationTable(UCollator *coll, UErrorCode *status) {
1158     uint16_t leadBytesSize = 256;
1159     uint16_t leadBytes[256];
1160
1161     // The lowest byte that hasn't been assigned a mapping
1162     int toBottom = 0x03;
1163     // The highest byte that hasn't been assigned a mapping - don't include the special or trailing
1164     int toTop = 0xe4;
1165
1166     // are we filling from the bottom?
1167     bool fromTheBottom = true;
1168     int32_t reorderCodesIndex = -1;
1169
1170     // lead bytes that have alread been assigned to the permutation table
1171     bool newLeadByteUsed[256];
1172     // permutation table slots that have already been filled
1173     bool permutationSlotFilled[256];
1174
1175     // nothing to do
1176     if(U_FAILURE(*status) || coll == NULL) {
1177         return;
1178     }
1179
1180     // clear the reordering
1181     if (coll->reorderCodes == NULL || coll->reorderCodesLength == 0
1182             || (coll->reorderCodesLength == 1 && coll->reorderCodes[0] == UCOL_REORDER_CODE_NONE)) {
1183         if (coll->leadBytePermutationTable != NULL) {
1184             if (coll->freeLeadBytePermutationTableOnClose) {
1185                 uprv_free(coll->leadBytePermutationTable);
1186             }
1187             coll->leadBytePermutationTable = NULL;
1188             coll->freeLeadBytePermutationTableOnClose = FALSE;
1189             coll->reorderCodesLength = 0;
1190         }
1191         return;
1192     }
1193
1194     // set reordering to the default reordering
1195     if (coll->reorderCodes[0] == UCOL_REORDER_CODE_DEFAULT) {
1196         if (coll->reorderCodesLength != 1) {
1197             *status = U_ILLEGAL_ARGUMENT_ERROR;
1198             return;
1199         }
1200         if (coll->freeReorderCodesOnClose == TRUE) {
1201             uprv_free(coll->reorderCodes);
1202         }
1203         coll->reorderCodes = NULL;
1204         coll->freeReorderCodesOnClose = FALSE;
1205
1206         if (coll->leadBytePermutationTable != NULL && coll->freeLeadBytePermutationTableOnClose == TRUE) {
1207             uprv_free(coll->leadBytePermutationTable);
1208         }
1209         coll->leadBytePermutationTable = NULL;
1210         coll->freeLeadBytePermutationTableOnClose = FALSE;
1211
1212         if (coll->defaultReorderCodesLength == 0) {
1213             return;
1214         }
1215
1216         coll->reorderCodes = (int32_t*)uprv_malloc(coll->defaultReorderCodesLength * sizeof(int32_t));
1217         if (coll->reorderCodes == NULL) {
1218             *status = U_MEMORY_ALLOCATION_ERROR;
1219             return;
1220         }
1221         coll->freeReorderCodesOnClose = TRUE;
1222         coll->reorderCodesLength = coll->defaultReorderCodesLength;
1223         uprv_memcpy(coll->reorderCodes, coll->defaultReorderCodes, coll->reorderCodesLength * sizeof(int32_t));
1224     }
1225
1226     if (coll->leadBytePermutationTable == NULL) {
1227         coll->leadBytePermutationTable = (uint8_t*)uprv_malloc(256*sizeof(uint8_t));
1228         if (coll->leadBytePermutationTable == NULL) {
1229             *status = U_MEMORY_ALLOCATION_ERROR;
1230             return;
1231         }
1232         coll->freeLeadBytePermutationTableOnClose = TRUE;
1233     }
1234
1235     int32_t internalReorderCodesLength = coll->reorderCodesLength + (UCOL_REORDER_CODE_LIMIT - UCOL_REORDER_CODE_FIRST);
1236     LocalMemory<int32_t> internalReorderCodes((int32_t*)uprv_malloc(internalReorderCodesLength * sizeof(int32_t)));
1237     if (internalReorderCodes.isNull()) {
1238         *status = U_MEMORY_ALLOCATION_ERROR;
1239         if (coll->leadBytePermutationTable != NULL && coll->freeLeadBytePermutationTableOnClose == TRUE) {
1240             uprv_free(coll->leadBytePermutationTable);
1241         }
1242         coll->leadBytePermutationTable = NULL;
1243         coll->freeLeadBytePermutationTableOnClose = FALSE;
1244         return;
1245     }
1246
1247     // prefill the reordering codes with the leading entries
1248     for (uint32_t codeIndex = 0; codeIndex < (UCOL_REORDER_CODE_LIMIT - UCOL_REORDER_CODE_FIRST); codeIndex++) {
1249         internalReorderCodes[codeIndex] = UCOL_REORDER_CODE_FIRST + codeIndex;
1250     }
1251     for (int32_t codeIndex = 0; codeIndex < coll->reorderCodesLength; codeIndex++) {
1252         uint32_t reorderCodesCode = coll->reorderCodes[codeIndex];
1253         internalReorderCodes[codeIndex + (UCOL_REORDER_CODE_LIMIT - UCOL_REORDER_CODE_FIRST)] = reorderCodesCode;
1254         if (reorderCodesCode >= UCOL_REORDER_CODE_FIRST && reorderCodesCode < UCOL_REORDER_CODE_LIMIT) {
1255             internalReorderCodes[reorderCodesCode - UCOL_REORDER_CODE_FIRST] = UCOL_REORDER_CODE_IGNORE;
1256         }
1257     }
1258
1259     for (int i = 0; i < 256; i++) {
1260         if (i < toBottom || i > toTop) {
1261             permutationSlotFilled[i] = true;
1262             newLeadByteUsed[i] = true;
1263             coll->leadBytePermutationTable[i] = i;
1264         } else {
1265             permutationSlotFilled[i] = false;
1266             newLeadByteUsed[i] = false;
1267             coll->leadBytePermutationTable[i] = 0;
1268         }
1269     }
1270
1271     /* Start from the front of the list and place each script we encounter at the
1272      * earliest possible locatation in the permutation table. If we encounter
1273      * UNKNOWN, start processing from the back, and place each script in the last
1274      * possible location. At each step, we also need to make sure that any scripts
1275      * that need to not be moved are copied to their same location in the final table.
1276      */
1277     for (int reorderCodesCount = 0; reorderCodesCount < internalReorderCodesLength; reorderCodesCount++) {
1278         reorderCodesIndex += fromTheBottom ? 1 : -1;
1279         int32_t next = internalReorderCodes[reorderCodesIndex];
1280         if (next == UCOL_REORDER_CODE_IGNORE) {
1281             continue;
1282         }
1283         if (next == USCRIPT_UNKNOWN) {
1284             if (fromTheBottom == false) {
1285                 // double turnaround
1286                 *status = U_ILLEGAL_ARGUMENT_ERROR;
1287                 if (coll->leadBytePermutationTable != NULL && coll->freeLeadBytePermutationTableOnClose == TRUE) {
1288                     uprv_free(coll->leadBytePermutationTable);
1289                 }
1290                 coll->leadBytePermutationTable = NULL;
1291                 coll->freeLeadBytePermutationTableOnClose = FALSE;
1292                 coll->reorderCodesLength = 0;
1293                 return;
1294             }
1295             fromTheBottom = false;
1296             reorderCodesIndex = internalReorderCodesLength;
1297             continue;
1298         }
1299
1300         uint16_t leadByteCount = ucol_getLeadBytesForReorderCode(coll->UCA, next, leadBytes, leadBytesSize);
1301         if (fromTheBottom) {
1302             for (int leadByteIndex = 0; leadByteIndex < leadByteCount; leadByteIndex++) {
1303                 // don't place a lead byte twice in the permutation table
1304                 if (permutationSlotFilled[leadBytes[leadByteIndex]]) {
1305                     // lead byte already used
1306                     *status = U_ILLEGAL_ARGUMENT_ERROR;
1307                     if (coll->leadBytePermutationTable != NULL && coll->freeLeadBytePermutationTableOnClose == TRUE) {
1308                         uprv_free(coll->leadBytePermutationTable);
1309                     }
1310                     coll->leadBytePermutationTable = NULL;
1311                     coll->freeLeadBytePermutationTableOnClose = FALSE;
1312                     coll->reorderCodesLength = 0;
1313                     return;
1314                 }
1315
1316                 coll->leadBytePermutationTable[leadBytes[leadByteIndex]] = toBottom;
1317                 newLeadByteUsed[toBottom] = true;
1318                 permutationSlotFilled[leadBytes[leadByteIndex]] = true;
1319                 toBottom++;
1320             }
1321         } else {
1322             for (int leadByteIndex = leadByteCount - 1; leadByteIndex >= 0; leadByteIndex--) {
1323                 // don't place a lead byte twice in the permutation table
1324                 if (permutationSlotFilled[leadBytes[leadByteIndex]]) {
1325                     // lead byte already used
1326                     *status = U_ILLEGAL_ARGUMENT_ERROR;
1327                     if (coll->leadBytePermutationTable != NULL && coll->freeLeadBytePermutationTableOnClose == TRUE) {
1328                         uprv_free(coll->leadBytePermutationTable);
1329                     }
1330                     coll->leadBytePermutationTable = NULL;
1331                     coll->freeLeadBytePermutationTableOnClose = FALSE;
1332                     coll->reorderCodesLength = 0;
1333                     return;
1334                 }
1335
1336                 coll->leadBytePermutationTable[leadBytes[leadByteIndex]] = toTop;
1337                 newLeadByteUsed[toTop] = true;
1338                 permutationSlotFilled[leadBytes[leadByteIndex]] = true;
1339                 toTop--;
1340             }
1341         }
1342     }
1343
1344 #ifdef REORDER_DEBUG
1345     fprintf(stdout, "\n@@@@ Partial Script Reordering Table\n");
1346     for (int i = 0; i < 256; i++) {
1347         fprintf(stdout, "\t%02x = %02x\n", i, coll->leadBytePermutationTable[i]);
1348     }
1349     fprintf(stdout, "\n@@@@ Lead Byte Used Table\n");
1350     for (int i = 0; i < 256; i++) {
1351         fprintf(stdout, "\t%02x = %02x\n", i, newLeadByteUsed[i]);
1352     }
1353     fprintf(stdout, "\n@@@@ Permutation Slot Filled Table\n");
1354     for (int i = 0; i < 256; i++) {
1355         fprintf(stdout, "\t%02x = %02x\n", i, permutationSlotFilled[i]);
1356     }
1357 #endif
1358
1359     /* Copy everything that's left over */
1360     int reorderCode = 0;
1361     for (int i = 0; i < 256; i++) {
1362         if (!permutationSlotFilled[i]) {
1363             while (reorderCode < 256 && newLeadByteUsed[reorderCode]) {
1364                 reorderCode++;
1365             }
1366             coll->leadBytePermutationTable[i] = reorderCode;
1367             permutationSlotFilled[i] = true;
1368             newLeadByteUsed[reorderCode] = true;
1369         }
1370     }
1371
1372 #ifdef REORDER_DEBUG
1373     fprintf(stdout, "\n@@@@ Script Reordering Table\n");
1374     for (int i = 0; i < 256; i++) {
1375         fprintf(stdout, "\t%02x = %02x\n", i, coll->leadBytePermutationTable[i]);
1376     }
1377 #endif
1378
1379     // force a regen of the latin one table since it is affected by the script reordering
1380     coll->latinOneRegenTable = TRUE;
1381     ucol_updateInternalState(coll, status);
1382 }
1383
1384 #endif /* #if !UCONFIG_NO_COLLATION */