icuSources/i18n/collationcompare.cpp

   1 /*
   2 *******************************************************************************
   3 * Copyright (C) 1996-2015, International Business Machines
   4 * Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 * collationcompare.cpp
   7 *
   8 * created on: 2012feb14 with new and old collation code
   9 * created by: Markus W. Scherer
  10 */
  11
  12 #include "unicode/utypes.h"
  13
  14 #if !UCONFIG_NO_COLLATION
  15
  16 #include "unicode/ucol.h"
  17 #include "cmemory.h"
  18 #include "collation.h"
  19 #include "collationcompare.h"
  20 #include "collationiterator.h"
  21 #include "collationsettings.h"
  22 #include "uassert.h"
  23
  24 U_NAMESPACE_BEGIN
  25
  26 UCollationResult
  27 CollationCompare::compareUpToQuaternary(CollationIterator &left, CollationIterator &right,
  28                                         const CollationSettings &settings,
  29                                         UErrorCode &errorCode) {
  30     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
  31
  32     int32_t options = settings.options;
  33     uint32_t variableTop;
  34     if((options & CollationSettings::ALTERNATE_MASK) == 0) {
  35         variableTop = 0;
  36     } else {
  37         // +1 so that we can use "<" and primary ignorables test out early.
  38         variableTop = settings.variableTop + 1;
  39     }
  40     UBool anyVariable = FALSE;
  41
  42     // Fetch CEs, compare primaries, store secondary & tertiary weights.
  43     for(;;) {
  44         // We fetch CEs until we get a non-ignorable primary or reach the end.
  45         uint32_t leftPrimary;
  46         do {
  47             int64_t ce = left.nextCE(errorCode);
  48             leftPrimary = (uint32_t)(ce >> 32);
  49             if(leftPrimary < variableTop && leftPrimary > Collation::MERGE_SEPARATOR_PRIMARY) {
  50                 // Variable CE, shift it to quaternary level.
  51                 // Ignore all following primary ignorables, and shift further variable CEs.
  52                 anyVariable = TRUE;
  53                 do {
  54                     // Store only the primary of the variable CE.
  55                     left.setCurrentCE(ce & INT64_C(0xffffffff00000000));
  56                     for(;;) {
  57                         ce = left.nextCE(errorCode);
  58                         leftPrimary = (uint32_t)(ce >> 32);
  59                         if(leftPrimary == 0) {
  60                             left.setCurrentCE(0);
  61                         } else {
  62                             break;
  63                         }
  64                     }
  65                 } while(leftPrimary < variableTop &&
  66                         leftPrimary > Collation::MERGE_SEPARATOR_PRIMARY);
  67             }
  68         } while(leftPrimary == 0);
  69
  70         uint32_t rightPrimary;
  71         do {
  72             int64_t ce = right.nextCE(errorCode);
  73             rightPrimary = (uint32_t)(ce >> 32);
  74             if(rightPrimary < variableTop && rightPrimary > Collation::MERGE_SEPARATOR_PRIMARY) {
  75                 // Variable CE, shift it to quaternary level.
  76                 // Ignore all following primary ignorables, and shift further variable CEs.
  77                 anyVariable = TRUE;
  78                 do {
  79                     // Store only the primary of the variable CE.
  80                     right.setCurrentCE(ce & INT64_C(0xffffffff00000000));
  81                     for(;;) {
  82                         ce = right.nextCE(errorCode);
  83                         rightPrimary = (uint32_t)(ce >> 32);
  84                         if(rightPrimary == 0) {
  85                             right.setCurrentCE(0);
  86                         } else {
  87                             break;
  88                         }
  89                     }
  90                 } while(rightPrimary < variableTop &&
  91                         rightPrimary > Collation::MERGE_SEPARATOR_PRIMARY);
  92             }
  93         } while(rightPrimary == 0);
  94
  95         if(leftPrimary != rightPrimary) {
  96             // Return the primary difference, with script reordering.
  97             if(settings.hasReordering()) {
  98                 leftPrimary = settings.reorder(leftPrimary);
  99                 rightPrimary = settings.reorder(rightPrimary);
 100             }
 101             return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER;
 102         }
 103         if(leftPrimary == Collation::NO_CE_PRIMARY) { break; }
 104     }
 105     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
 106
 107     // Compare the buffered secondary & tertiary weights.
 108     // We might skip the secondary level but continue with the case level
 109     // which is turned on separately.
 110     if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) {
 111         if((options & CollationSettings::BACKWARD_SECONDARY) == 0) {
 112             int32_t leftIndex = 0;
 113             int32_t rightIndex = 0;
 114             for(;;) {
 115                 uint32_t leftSecondary;
 116                 do {
 117                     leftSecondary = ((uint32_t)left.getCE(leftIndex++)) >> 16;
 118                 } while(leftSecondary == 0);
 119
 120                 uint32_t rightSecondary;
 121                 do {
 122                     rightSecondary = ((uint32_t)right.getCE(rightIndex++)) >> 16;
 123                 } while(rightSecondary == 0);
 124
 125                 if(leftSecondary != rightSecondary) {
 126                     return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER;
 127                 }
 128                 if(leftSecondary == Collation::NO_CE_WEIGHT16) { break; }
 129             }
 130         } else {
 131             // The backwards secondary level compares secondary weights backwards
 132             // within segments separated by the merge separator (U+FFFE, weight 02).
 133             int32_t leftStart = 0;
 134             int32_t rightStart = 0;
 135             for(;;) {
 136                 // Find the merge separator or the NO_CE terminator.
 137                 uint32_t p;
 138                 int32_t leftLimit = leftStart;
 139                 while((p = (uint32_t)(left.getCE(leftLimit) >> 32)) >
 140                             Collation::MERGE_SEPARATOR_PRIMARY ||
 141                         p == 0) {
 142                     ++leftLimit;
 143                 }
 144                 int32_t rightLimit = rightStart;
 145                 while((p = (uint32_t)(right.getCE(rightLimit) >> 32)) >
 146                             Collation::MERGE_SEPARATOR_PRIMARY ||
 147                         p == 0) {
 148                     ++rightLimit;
 149                 }
 150
 151                 // Compare the segments.
 152                 int32_t leftIndex = leftLimit;
 153                 int32_t rightIndex = rightLimit;
 154                 for(;;) {
 155                     int32_t leftSecondary = 0;
 156                     while(leftSecondary == 0 && leftIndex > leftStart) {
 157                         leftSecondary = ((uint32_t)left.getCE(--leftIndex)) >> 16;
 158                     }
 159
 160                     int32_t rightSecondary = 0;
 161                     while(rightSecondary == 0 && rightIndex > rightStart) {
 162                         rightSecondary = ((uint32_t)right.getCE(--rightIndex)) >> 16;
 163                     }
 164
 165                     if(leftSecondary != rightSecondary) {
 166                         return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER;
 167                     }
 168                     if(leftSecondary == 0) { break; }
 169                 }
 170
 171                 // Did we reach the end of either string?
 172                 // Both strings have the same number of merge separators,
 173                 // or else there would have been a primary-level difference.
 174                 U_ASSERT(left.getCE(leftLimit) == right.getCE(rightLimit));
 175                 if(p == Collation::NO_CE_PRIMARY) { break; }
 176                 // Skip both merge separators and continue.
 177                 leftStart = leftLimit + 1;
 178                 rightStart = rightLimit + 1;
 179             }
 180         }
 181     }
 182
 183     if((options & CollationSettings::CASE_LEVEL) != 0) {
 184         int32_t strength = CollationSettings::getStrength(options);
 185         int32_t leftIndex = 0;
 186         int32_t rightIndex = 0;
 187         for(;;) {
 188             uint32_t leftCase, leftLower32, rightCase;
 189             if(strength == UCOL_PRIMARY) {
 190                 // Primary+caseLevel: Ignore case level weights of primary ignorables.
 191                 // Otherwise we would get a-umlaut > a
 192                 // which is not desirable for accent-insensitive sorting.
 193                 // Check for (lower 32 bits) == 0 as well because variable CEs are stored
 194                 // with only primary weights.
 195                 int64_t ce;
 196                 do {
 197                     ce = left.getCE(leftIndex++);
 198                     leftCase = (uint32_t)ce;
 199                 } while((uint32_t)(ce >> 32) == 0 || leftCase == 0);
 200                 leftLower32 = leftCase;
 201                 leftCase &= 0xc000;
 202
 203                 do {
 204                     ce = right.getCE(rightIndex++);
 205                     rightCase = (uint32_t)ce;
 206                 } while((uint32_t)(ce >> 32) == 0 || rightCase == 0);
 207                 rightCase &= 0xc000;
 208             } else {
 209                 // Secondary+caseLevel: By analogy with the above,
 210                 // ignore case level weights of secondary ignorables.
 211                 //
 212                 // Note: A tertiary CE has uppercase case bits (0.0.ut)
 213                 // to keep tertiary+caseFirst well-formed.
 214                 //
 215                 // Tertiary+caseLevel: Also ignore case level weights of secondary ignorables.
 216                 // Otherwise a tertiary CE's uppercase would be no greater than
 217                 // a primary/secondary CE's uppercase.
 218                 // (See UCA well-formedness condition 2.)
 219                 // We could construct a special case weight higher than uppercase,
 220                 // but it's simpler to always ignore case weights of secondary ignorables,
 221                 // turning 0.0.ut into 0.0.0.t.
 222                 // (See LDML Collation, Case Parameters.)
 223                 do {
 224                     leftCase = (uint32_t)left.getCE(leftIndex++);
 225                 } while(leftCase <= 0xffff);
 226                 leftLower32 = leftCase;
 227                 leftCase &= 0xc000;
 228
 229                 do {
 230                     rightCase = (uint32_t)right.getCE(rightIndex++);
 231                 } while(rightCase <= 0xffff);
 232                 rightCase &= 0xc000;
 233             }
 234
 235             // No need to handle NO_CE and MERGE_SEPARATOR specially:
 236             // There is one case weight for each previous-level weight,
 237             // so level length differences were handled there.
 238             if(leftCase != rightCase) {
 239                 if((options & CollationSettings::UPPER_FIRST) == 0) {
 240                     return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER;
 241                 } else {
 242                     return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS;
 243                 }
 244             }
 245             if((leftLower32 >> 16) == Collation::NO_CE_WEIGHT16) { break; }
 246         }
 247     }
 248     if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; }
 249
 250     uint32_t tertiaryMask = CollationSettings::getTertiaryMask(options);
 251
 252     int32_t leftIndex = 0;
 253     int32_t rightIndex = 0;
 254     uint32_t anyQuaternaries = 0;
 255     for(;;) {
 256         uint32_t leftLower32, leftTertiary;
 257         do {
 258             leftLower32 = (uint32_t)left.getCE(leftIndex++);
 259             anyQuaternaries |= leftLower32;
 260             U_ASSERT((leftLower32 & Collation::ONLY_TERTIARY_MASK) != 0 ||
 261                      (leftLower32 & 0xc0c0) == 0);
 262             leftTertiary = leftLower32 & tertiaryMask;
 263         } while(leftTertiary == 0);
 264
 265         uint32_t rightLower32, rightTertiary;
 266         do {
 267             rightLower32 = (uint32_t)right.getCE(rightIndex++);
 268             anyQuaternaries |= rightLower32;
 269             U_ASSERT((rightLower32 & Collation::ONLY_TERTIARY_MASK) != 0 ||
 270                      (rightLower32 & 0xc0c0) == 0);
 271             rightTertiary = rightLower32 & tertiaryMask;
 272         } while(rightTertiary == 0);
 273
 274         if(leftTertiary != rightTertiary) {
 275             if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) {
 276                 // Pass through NO_CE and keep real tertiary weights larger than that.
 277                 // Do not change the artificial uppercase weight of a tertiary CE (0.0.ut),
 278                 // to keep tertiary CEs well-formed.
 279                 // Their case+tertiary weights must be greater than those of
 280                 // primary and secondary CEs.
 281                 if(leftTertiary > Collation::NO_CE_WEIGHT16) {
 282                     if(leftLower32 > 0xffff) {
 283                         leftTertiary ^= 0xc000;
 284                     } else {
 285                         leftTertiary += 0x4000;
 286                     }
 287                 }
 288                 if(rightTertiary > Collation::NO_CE_WEIGHT16) {
 289                     if(rightLower32 > 0xffff) {
 290                         rightTertiary ^= 0xc000;
 291                     } else {
 292                         rightTertiary += 0x4000;
 293                     }
 294                 }
 295             }
 296             return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER;
 297         }
 298         if(leftTertiary == Collation::NO_CE_WEIGHT16) { break; }
 299     }
 300     if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; }
 301
 302     if(!anyVariable && (anyQuaternaries & 0xc0) == 0) {
 303         // If there are no "variable" CEs and no non-zero quaternary weights,
 304         // then there are no quaternary differences.
 305         return UCOL_EQUAL;
 306     }
 307
 308     leftIndex = 0;
 309     rightIndex = 0;
 310     for(;;) {
 311         uint32_t leftQuaternary;
 312         do {
 313             int64_t ce = left.getCE(leftIndex++);
 314             leftQuaternary = (uint32_t)ce & 0xffff;
 315             if(leftQuaternary <= Collation::NO_CE_WEIGHT16) {
 316                 // Variable primary or completely ignorable or NO_CE.
 317                 leftQuaternary = (uint32_t)(ce >> 32);
 318             } else {
 319                 // Regular CE, not tertiary ignorable.
 320                 // Preserve the quaternary weight in bits 7..6.
 321                 leftQuaternary |= 0xffffff3f;
 322             }
 323         } while(leftQuaternary == 0);
 324
 325         uint32_t rightQuaternary;
 326         do {
 327             int64_t ce = right.getCE(rightIndex++);
 328             rightQuaternary = (uint32_t)ce & 0xffff;
 329             if(rightQuaternary <= Collation::NO_CE_WEIGHT16) {
 330                 // Variable primary or completely ignorable or NO_CE.
 331                 rightQuaternary = (uint32_t)(ce >> 32);
 332             } else {
 333                 // Regular CE, not tertiary ignorable.
 334                 // Preserve the quaternary weight in bits 7..6.
 335                 rightQuaternary |= 0xffffff3f;
 336             }
 337         } while(rightQuaternary == 0);
 338
 339         if(leftQuaternary != rightQuaternary) {
 340             // Return the difference, with script reordering.
 341             if(settings.hasReordering()) {
 342                 leftQuaternary = settings.reorder(leftQuaternary);
 343                 rightQuaternary = settings.reorder(rightQuaternary);
 344             }
 345             return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER;
 346         }
 347         if(leftQuaternary == Collation::NO_CE_PRIMARY) { break; }
 348     }
 349     return UCOL_EQUAL;
 350 }
 351
 352 U_NAMESPACE_END
 353
 354 #endif  // !UCONFIG_NO_COLLATION