icuSources/i18n/ucoleitr.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 ******************************************************************************
   5 *   Copyright (C) 2001-2016, International Business Machines
   6 *   Corporation and others.  All Rights Reserved.
   7 ******************************************************************************
   8 *
   9 * File ucoleitr.cpp
  10 *
  11 * Modification History:
  12 *
  13 * Date        Name        Description
  14 * 02/15/2001  synwee      Modified all methods to process its own function
  15 *                         instead of calling the equivalent c++ api (coleitr.h)
  16 * 2012-2014   markus      Rewritten in C++ again.
  17 ******************************************************************************/
  18
  19 #include "unicode/utypes.h"
  20
  21 #if !UCONFIG_NO_COLLATION
  22
  23 #include "unicode/coleitr.h"
  24 #include "unicode/tblcoll.h"
  25 #include "unicode/ucoleitr.h"
  26 #include "unicode/ustring.h"
  27 #include "unicode/sortkey.h"
  28 #include "unicode/uobject.h"
  29 #include "cmemory.h"
  30 #include "usrchimp.h"
  31
  32 U_NAMESPACE_USE
  33
  34 #define BUFFER_LENGTH             100
  35
  36 #define DEFAULT_BUFFER_SIZE 16
  37 #define BUFFER_GROW 8
  38
  39 #define ARRAY_COPY(dst, src, count) uprv_memcpy((void *) (dst), (void *) (src), (size_t)(count) * sizeof (src)[0])
  40
  41 #define NEW_ARRAY(type, count) (type *) uprv_malloc((size_t)(count) * sizeof(type))
  42
  43 #define DELETE_ARRAY(array) uprv_free((void *) (array))
  44
  45 struct RCEI
  46 {
  47     uint32_t ce;
  48     int32_t  low;
  49     int32_t  high;
  50 };
  51
  52 U_NAMESPACE_BEGIN
  53
  54 struct RCEBuffer
  55 {
  56     RCEI    defaultBuffer[DEFAULT_BUFFER_SIZE];
  57     RCEI   *buffer;
  58     int32_t bufferIndex;
  59     int32_t bufferSize;
  60
  61     RCEBuffer();
  62     ~RCEBuffer();
  63
  64     UBool isEmpty() const;
  65     void  put(uint32_t ce, int32_t ixLow, int32_t ixHigh, UErrorCode &errorCode);
  66     const RCEI *get();
  67 };
  68
  69 RCEBuffer::RCEBuffer()
  70 {
  71     buffer = defaultBuffer;
  72     bufferIndex = 0;
  73     bufferSize = UPRV_LENGTHOF(defaultBuffer);
  74 }
  75
  76 RCEBuffer::~RCEBuffer()
  77 {
  78     if (buffer != defaultBuffer) {
  79         DELETE_ARRAY(buffer);
  80     }
  81 }
  82
  83 UBool RCEBuffer::isEmpty() const
  84 {
  85     return bufferIndex <= 0;
  86 }
  87
  88 void RCEBuffer::put(uint32_t ce, int32_t ixLow, int32_t ixHigh, UErrorCode &errorCode)
  89 {
  90     if (U_FAILURE(errorCode)) {
  91         return;
  92     }
  93     if (bufferIndex >= bufferSize) {
  94         RCEI *newBuffer = NEW_ARRAY(RCEI, bufferSize + BUFFER_GROW);
  95         if (newBuffer == NULL) {
  96             errorCode = U_MEMORY_ALLOCATION_ERROR;
  97             return;
  98         }
  99
 100         ARRAY_COPY(newBuffer, buffer, bufferSize);
 101
 102         if (buffer != defaultBuffer) {
 103             DELETE_ARRAY(buffer);
 104         }
 105
 106         buffer = newBuffer;
 107         bufferSize += BUFFER_GROW;
 108     }
 109
 110     buffer[bufferIndex].ce   = ce;
 111     buffer[bufferIndex].low  = ixLow;
 112     buffer[bufferIndex].high = ixHigh;
 113
 114     bufferIndex += 1;
 115 }
 116
 117 const RCEI *RCEBuffer::get()
 118 {
 119     if (bufferIndex > 0) {
 120      return &buffer[--bufferIndex];
 121     }
 122
 123     return NULL;
 124 }
 125
 126 PCEBuffer::PCEBuffer()
 127 {
 128     buffer = defaultBuffer;
 129     bufferIndex = 0;
 130     bufferSize = UPRV_LENGTHOF(defaultBuffer);
 131 }
 132
 133 PCEBuffer::~PCEBuffer()
 134 {
 135     if (buffer != defaultBuffer) {
 136         DELETE_ARRAY(buffer);
 137     }
 138 }
 139
 140 void PCEBuffer::reset()
 141 {
 142     bufferIndex = 0;
 143 }
 144
 145 UBool PCEBuffer::isEmpty() const
 146 {
 147     return bufferIndex <= 0;
 148 }
 149
 150 void PCEBuffer::put(uint64_t ce, int32_t ixLow, int32_t ixHigh, UErrorCode &errorCode)
 151 {
 152     if (U_FAILURE(errorCode)) {
 153         return;
 154     }
 155     if (bufferIndex >= bufferSize) {
 156         PCEI *newBuffer = NEW_ARRAY(PCEI, bufferSize + BUFFER_GROW);
 157         if (newBuffer == NULL) {
 158             errorCode = U_MEMORY_ALLOCATION_ERROR;
 159             return;
 160         }
 161
 162         ARRAY_COPY(newBuffer, buffer, bufferSize);
 163
 164         if (buffer != defaultBuffer) {
 165             DELETE_ARRAY(buffer);
 166         }
 167
 168         buffer = newBuffer;
 169         bufferSize += BUFFER_GROW;
 170     }
 171
 172     buffer[bufferIndex].ce   = ce;
 173     buffer[bufferIndex].low  = ixLow;
 174     buffer[bufferIndex].high = ixHigh;
 175
 176     bufferIndex += 1;
 177 }
 178
 179 const PCEI *PCEBuffer::get()
 180 {
 181     if (bufferIndex > 0) {
 182      return &buffer[--bufferIndex];
 183     }
 184
 185     return NULL;
 186 }
 187
 188 UCollationPCE::UCollationPCE(UCollationElements *elems) { init(elems); }
 189
 190 UCollationPCE::UCollationPCE(CollationElementIterator *iter) { init(iter); }
 191
 192 void UCollationPCE::init(UCollationElements *elems) {
 193     init(CollationElementIterator::fromUCollationElements(elems));
 194 }
 195
 196 void UCollationPCE::init(CollationElementIterator *iter)
 197 {
 198     cei = iter;
 199     init(*iter->rbc_);
 200 }
 201
 202 void UCollationPCE::init(const Collator &coll)
 203 {
 204     UErrorCode status = U_ZERO_ERROR;
 205
 206     strength    = coll.getAttribute(UCOL_STRENGTH, status);
 207     toShift     = coll.getAttribute(UCOL_ALTERNATE_HANDLING, status) == UCOL_SHIFTED;
 208     isShifted   = FALSE;
 209     variableTop = coll.getVariableTop(status);
 210 }
 211
 212 UCollationPCE::~UCollationPCE()
 213 {
 214     // nothing to do
 215 }
 216
 217 uint64_t UCollationPCE::processCE(uint32_t ce)
 218 {
 219     uint64_t primary = 0, secondary = 0, tertiary = 0, quaternary = 0;
 220
 221     // This is clean, but somewhat slow...
 222     // We could apply the mask to ce and then
 223     // just get all three orders...
 224     switch(strength) {
 225     default:
 226         tertiary = ucol_tertiaryOrder(ce);
 227         U_FALLTHROUGH;
 228
 229     case UCOL_SECONDARY:
 230         secondary = ucol_secondaryOrder(ce);
 231         U_FALLTHROUGH;
 232
 233     case UCOL_PRIMARY:
 234         primary = ucol_primaryOrder(ce);
 235     }
 236
 237     // **** This should probably handle continuations too.  ****
 238     // **** That means that we need 24 bits for the primary ****
 239     // **** instead of the 16 that we're currently using.   ****
 240     // **** So we can lay out the 64 bits as: 24.12.12.16.  ****
 241     // **** Another complication with continuations is that ****
 242     // **** the *second* CE is marked as a continuation, so ****
 243     // **** we always have to peek ahead to know how long   ****
 244     // **** the primary is...                               ****
 245     if ((toShift && variableTop > ce && primary != 0)
 246                 || (isShifted && primary == 0)) {
 247
 248         if (primary == 0) {
 249             return UCOL_IGNORABLE;
 250         }
 251
 252         if (strength >= UCOL_QUATERNARY) {
 253             quaternary = primary;
 254         }
 255
 256         primary = secondary = tertiary = 0;
 257         isShifted = TRUE;
 258     } else {
 259         if (strength >= UCOL_QUATERNARY) {
 260             quaternary = 0xFFFF;
 261         }
 262
 263         isShifted = FALSE;
 264     }
 265
 266     return primary << 48 | secondary << 32 | tertiary << 16 | quaternary;
 267 }
 268
 269 U_NAMESPACE_END
 270
 271 /* public methods ---------------------------------------------------- */
 272
 273 U_CAPI UCollationElements* U_EXPORT2
 274 ucol_openElements(const UCollator  *coll,
 275                   const UChar      *text,
 276                         int32_t    textLength,
 277                         UErrorCode *status)
 278 {
 279     if (U_FAILURE(*status)) {
 280         return NULL;
 281     }
 282     if (coll == NULL || (text == NULL && textLength != 0)) {
 283         *status = U_ILLEGAL_ARGUMENT_ERROR;
 284         return NULL;
 285     }
 286     const RuleBasedCollator *rbc = RuleBasedCollator::rbcFromUCollator(coll);
 287     if (rbc == NULL) {
 288         *status = U_UNSUPPORTED_ERROR;  // coll is a Collator but not a RuleBasedCollator
 289         return NULL;
 290     }
 291
 292     UnicodeString s((UBool)(textLength < 0), text, textLength);
 293     CollationElementIterator *cei = rbc->createCollationElementIterator(s);
 294     if (cei == NULL) {
 295         *status = U_MEMORY_ALLOCATION_ERROR;
 296         return NULL;
 297     }
 298
 299     return cei->toUCollationElements();
 300 }
 301
 302
 303 U_CAPI void U_EXPORT2
 304 ucol_closeElements(UCollationElements *elems)
 305 {
 306     delete CollationElementIterator::fromUCollationElements(elems);
 307 }
 308
 309 U_CAPI void U_EXPORT2
 310 ucol_reset(UCollationElements *elems)
 311 {
 312     CollationElementIterator::fromUCollationElements(elems)->reset();
 313 }
 314
 315 U_CAPI int32_t U_EXPORT2
 316 ucol_next(UCollationElements *elems,
 317           UErrorCode         *status)
 318 {
 319     if (U_FAILURE(*status)) {
 320         return UCOL_NULLORDER;
 321     }
 322
 323     return CollationElementIterator::fromUCollationElements(elems)->next(*status);
 324 }
 325
 326 // temporarily restore the following removed internal function which is used by Spotlight
 327 U_CAPI int64_t U_EXPORT2
 328 ucol_nextProcessed(UCollationElements *elems,
 329                    int32_t            *ixLow,
 330                    int32_t            *ixHigh,
 331                    UErrorCode         *status)
 332 {
 333     return (UCollationPCE(elems)).nextProcessed(ixLow, ixHigh, status);
 334 }
 335
 336
 337 U_NAMESPACE_BEGIN
 338
 339 int64_t
 340 UCollationPCE::nextProcessed(
 341                    int32_t            *ixLow,
 342                    int32_t            *ixHigh,
 343                    UErrorCode         *status)
 344 {
 345     int64_t result = UCOL_IGNORABLE;
 346     uint32_t low = 0, high = 0;
 347
 348     if (U_FAILURE(*status)) {
 349         return UCOL_PROCESSED_NULLORDER;
 350     }
 351
 352     pceBuffer.reset();
 353
 354     do {
 355         low = cei->getOffset();
 356         int32_t ce = cei->next(*status);
 357         high = cei->getOffset();
 358
 359         if (ce == UCOL_NULLORDER) {
 360              result = UCOL_PROCESSED_NULLORDER;
 361              break;
 362         }
 363
 364         result = processCE((uint32_t)ce);
 365     } while (result == UCOL_IGNORABLE);
 366
 367     if (ixLow != NULL) {
 368         *ixLow = low;
 369     }
 370
 371     if (ixHigh != NULL) {
 372         *ixHigh = high;
 373     }
 374
 375     return result;
 376 }
 377
 378 U_NAMESPACE_END
 379
 380 U_CAPI int32_t U_EXPORT2
 381 ucol_previous(UCollationElements *elems,
 382               UErrorCode         *status)
 383 {
 384     if(U_FAILURE(*status)) {
 385         return UCOL_NULLORDER;
 386     }
 387     return CollationElementIterator::fromUCollationElements(elems)->previous(*status);
 388 }
 389
 390 // temporarily restore the following removed internal function which is used by Spotlight
 391 U_CAPI int64_t U_EXPORT2
 392 ucol_previousProcessed(UCollationElements *elems,
 393                    int32_t            *ixLow,
 394                    int32_t            *ixHigh,
 395                    UErrorCode         *status)
 396 {
 397     return (UCollationPCE(elems)).previousProcessed(ixLow, ixHigh, status);
 398 }
 399
 400 U_NAMESPACE_BEGIN
 401
 402 int64_t
 403 UCollationPCE::previousProcessed(
 404                    int32_t            *ixLow,
 405                    int32_t            *ixHigh,
 406                    UErrorCode         *status)
 407 {
 408     int64_t result = UCOL_IGNORABLE;
 409     int32_t  low = 0, high = 0;
 410
 411     if (U_FAILURE(*status)) {
 412         return UCOL_PROCESSED_NULLORDER;
 413     }
 414
 415     // pceBuffer.reset();
 416
 417     while (pceBuffer.isEmpty()) {
 418         // buffer raw CEs up to non-ignorable primary
 419         RCEBuffer rceb;
 420         int32_t ce;
 421
 422         // **** do we need to reset rceb, or will it always be empty at this point ****
 423         do {
 424             high = cei->getOffset();
 425             ce   = cei->previous(*status);
 426             low  = cei->getOffset();
 427
 428             if (ce == UCOL_NULLORDER) {
 429                 if (!rceb.isEmpty()) {
 430                     break;
 431                 }
 432
 433                 goto finish;
 434             }
 435
 436             rceb.put((uint32_t)ce, low, high, *status);
 437         } while (U_SUCCESS(*status) && ((ce & UCOL_PRIMARYORDERMASK) == 0 || isContinuation(ce)));
 438
 439         // process the raw CEs
 440         while (U_SUCCESS(*status) && !rceb.isEmpty()) {
 441             const RCEI *rcei = rceb.get();
 442
 443             result = processCE(rcei->ce);
 444
 445             if (result != UCOL_IGNORABLE) {
 446                 pceBuffer.put(result, rcei->low, rcei->high, *status);
 447             }
 448         }
 449         if (U_FAILURE(*status)) {
 450             return UCOL_PROCESSED_NULLORDER;
 451         }
 452     }
 453
 454 finish:
 455     if (pceBuffer.isEmpty()) {
 456         // **** Is -1 the right value for ixLow, ixHigh? ****
 457         if (ixLow != NULL) {
 458                 *ixLow = -1;
 459         }
 460
 461         if (ixHigh != NULL) {
 462                 *ixHigh = -1
 463                 ;
 464         }
 465         return UCOL_PROCESSED_NULLORDER;
 466     }
 467
 468     const PCEI *pcei = pceBuffer.get();
 469
 470     if (ixLow != NULL) {
 471         *ixLow = pcei->low;
 472     }
 473
 474     if (ixHigh != NULL) {
 475         *ixHigh = pcei->high;
 476     }
 477
 478     return pcei->ce;
 479 }
 480
 481 U_NAMESPACE_END
 482
 483 U_CAPI int32_t U_EXPORT2
 484 ucol_getMaxExpansion(const UCollationElements *elems,
 485                            int32_t            order)
 486 {
 487     return CollationElementIterator::fromUCollationElements(elems)->getMaxExpansion(order);
 488
 489     // TODO: The old code masked the order according to strength and then did a binary search.
 490     // However this was probably at least partially broken because of the following comment.
 491     // Still, it might have found a match when this version may not.
 492
 493     // FIXME: with a masked search, there might be more than one hit,
 494     // so we need to look forward and backward from the match to find all
 495     // of the hits...
 496 }
 497
 498 U_CAPI void U_EXPORT2
 499 ucol_setText(      UCollationElements *elems,
 500              const UChar              *text,
 501                    int32_t            textLength,
 502                    UErrorCode         *status)
 503 {
 504     if (U_FAILURE(*status)) {
 505         return;
 506     }
 507
 508     if ((text == NULL && textLength != 0)) {
 509         *status = U_ILLEGAL_ARGUMENT_ERROR;
 510         return;
 511     }
 512     UnicodeString s((UBool)(textLength < 0), text, textLength);
 513     return CollationElementIterator::fromUCollationElements(elems)->setText(s, *status);
 514 }
 515
 516 U_CAPI int32_t U_EXPORT2
 517 ucol_getOffset(const UCollationElements *elems)
 518 {
 519     return CollationElementIterator::fromUCollationElements(elems)->getOffset();
 520 }
 521
 522 U_CAPI void U_EXPORT2
 523 ucol_setOffset(UCollationElements    *elems,
 524                int32_t           offset,
 525                UErrorCode            *status)
 526 {
 527     if (U_FAILURE(*status)) {
 528         return;
 529     }
 530
 531     CollationElementIterator::fromUCollationElements(elems)->setOffset(offset, *status);
 532 }
 533
 534 U_CAPI int32_t U_EXPORT2
 535 ucol_primaryOrder (int32_t order)
 536 {
 537     return (order >> 16) & 0xffff;
 538 }
 539
 540 U_CAPI int32_t U_EXPORT2
 541 ucol_secondaryOrder (int32_t order)
 542 {
 543     return (order >> 8) & 0xff;
 544 }
 545
 546 U_CAPI int32_t U_EXPORT2
 547 ucol_tertiaryOrder (int32_t order)
 548 {
 549     return order & 0xff;
 550 }
 551
 552 #endif /* #if !UCONFIG_NO_COLLATION */