| // © 2016 and later: Unicode, Inc. and others. |
| // License & terms of use: http://www.unicode.org/copyright.html |
| /* |
| ******************************************************************************* |
| * Copyright (C) 1996-2015, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * collationcompare.cpp |
| * |
| * created on: 2012feb14 with new and old collation code |
| * created by: Markus W. Scherer |
| */ |
| |
| #include "unicode/utypes.h" |
| |
| #if !UCONFIG_NO_COLLATION |
| |
| #include "unicode/ucol.h" |
| #include "cmemory.h" |
| #include "collation.h" |
| #include "collationcompare.h" |
| #include "collationiterator.h" |
| #include "collationsettings.h" |
| #include "uassert.h" |
| |
| U_NAMESPACE_BEGIN |
| |
| UCollationResult |
| CollationCompare::compareUpToQuaternary(CollationIterator &left, CollationIterator &right, |
| const CollationSettings &settings, |
| UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { return UCOL_EQUAL; } |
| |
| int32_t options = settings.options; |
| uint32_t variableTop; |
| if((options & CollationSettings::ALTERNATE_MASK) == 0) { |
| variableTop = 0; |
| } else { |
| // +1 so that we can use "<" and primary ignorables test out early. |
| variableTop = settings.variableTop + 1; |
| } |
| UBool anyVariable = FALSE; |
| |
| // Fetch CEs, compare primaries, store secondary & tertiary weights. |
| for(;;) { |
| // We fetch CEs until we get a non-ignorable primary or reach the end. |
| uint32_t leftPrimary; |
| do { |
| int64_t ce = left.nextCE(errorCode); |
| leftPrimary = (uint32_t)(ce >> 32); |
| if(leftPrimary < variableTop && leftPrimary > Collation::MERGE_SEPARATOR_PRIMARY) { |
| // Variable CE, shift it to quaternary level. |
| // Ignore all following primary ignorables, and shift further variable CEs. |
| anyVariable = TRUE; |
| do { |
| // Store only the primary of the variable CE. |
| left.setCurrentCE(ce & INT64_C(0xffffffff00000000)); |
| for(;;) { |
| ce = left.nextCE(errorCode); |
| leftPrimary = (uint32_t)(ce >> 32); |
| if(leftPrimary == 0) { |
| left.setCurrentCE(0); |
| } else { |
| break; |
| } |
| } |
| } while(leftPrimary < variableTop && |
| leftPrimary > Collation::MERGE_SEPARATOR_PRIMARY); |
| } |
| } while(leftPrimary == 0); |
| |
| uint32_t rightPrimary; |
| do { |
| int64_t ce = right.nextCE(errorCode); |
| rightPrimary = (uint32_t)(ce >> 32); |
| if(rightPrimary < variableTop && rightPrimary > Collation::MERGE_SEPARATOR_PRIMARY) { |
| // Variable CE, shift it to quaternary level. |
| // Ignore all following primary ignorables, and shift further variable CEs. |
| anyVariable = TRUE; |
| do { |
| // Store only the primary of the variable CE. |
| right.setCurrentCE(ce & INT64_C(0xffffffff00000000)); |
| for(;;) { |
| ce = right.nextCE(errorCode); |
| rightPrimary = (uint32_t)(ce >> 32); |
| if(rightPrimary == 0) { |
| right.setCurrentCE(0); |
| } else { |
| break; |
| } |
| } |
| } while(rightPrimary < variableTop && |
| rightPrimary > Collation::MERGE_SEPARATOR_PRIMARY); |
| } |
| } while(rightPrimary == 0); |
| |
| if(leftPrimary != rightPrimary) { |
| // Return the primary difference, with script reordering. |
| if(settings.hasReordering()) { |
| leftPrimary = settings.reorder(leftPrimary); |
| rightPrimary = settings.reorder(rightPrimary); |
| } |
| return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPrimary == Collation::NO_CE_PRIMARY) { break; } |
| } |
| if(U_FAILURE(errorCode)) { return UCOL_EQUAL; } |
| |
| // Compare the buffered secondary & tertiary weights. |
| // We might skip the secondary level but continue with the case level |
| // which is turned on separately. |
| if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) { |
| if((options & CollationSettings::BACKWARD_SECONDARY) == 0) { |
| int32_t leftIndex = 0; |
| int32_t rightIndex = 0; |
| for(;;) { |
| uint32_t leftSecondary; |
| do { |
| leftSecondary = ((uint32_t)left.getCE(leftIndex++)) >> 16; |
| } while(leftSecondary == 0); |
| |
| uint32_t rightSecondary; |
| do { |
| rightSecondary = ((uint32_t)right.getCE(rightIndex++)) >> 16; |
| } while(rightSecondary == 0); |
| |
| if(leftSecondary != rightSecondary) { |
| return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftSecondary == Collation::NO_CE_WEIGHT16) { break; } |
| } |
| } else { |
| // The backwards secondary level compares secondary weights backwards |
| // within segments separated by the merge separator (U+FFFE, weight 02). |
| int32_t leftStart = 0; |
| int32_t rightStart = 0; |
| for(;;) { |
| // Find the merge separator or the NO_CE terminator. |
| uint32_t p; |
| int32_t leftLimit = leftStart; |
| while((p = (uint32_t)(left.getCE(leftLimit) >> 32)) > |
| Collation::MERGE_SEPARATOR_PRIMARY || |
| p == 0) { |
| ++leftLimit; |
| } |
| int32_t rightLimit = rightStart; |
| while((p = (uint32_t)(right.getCE(rightLimit) >> 32)) > |
| Collation::MERGE_SEPARATOR_PRIMARY || |
| p == 0) { |
| ++rightLimit; |
| } |
| |
| // Compare the segments. |
| int32_t leftIndex = leftLimit; |
| int32_t rightIndex = rightLimit; |
| for(;;) { |
| int32_t leftSecondary = 0; |
| while(leftSecondary == 0 && leftIndex > leftStart) { |
| leftSecondary = ((uint32_t)left.getCE(--leftIndex)) >> 16; |
| } |
| |
| int32_t rightSecondary = 0; |
| while(rightSecondary == 0 && rightIndex > rightStart) { |
| rightSecondary = ((uint32_t)right.getCE(--rightIndex)) >> 16; |
| } |
| |
| if(leftSecondary != rightSecondary) { |
| return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftSecondary == 0) { break; } |
| } |
| |
| // Did we reach the end of either string? |
| // Both strings have the same number of merge separators, |
| // or else there would have been a primary-level difference. |
| U_ASSERT(left.getCE(leftLimit) == right.getCE(rightLimit)); |
| if(p == Collation::NO_CE_PRIMARY) { break; } |
| // Skip both merge separators and continue. |
| leftStart = leftLimit + 1; |
| rightStart = rightLimit + 1; |
| } |
| } |
| } |
| |
| if((options & CollationSettings::CASE_LEVEL) != 0) { |
| int32_t strength = CollationSettings::getStrength(options); |
| int32_t leftIndex = 0; |
| int32_t rightIndex = 0; |
| for(;;) { |
| uint32_t leftCase, leftLower32, rightCase; |
| if(strength == UCOL_PRIMARY) { |
| // Primary+caseLevel: Ignore case level weights of primary ignorables. |
| // Otherwise we would get a-umlaut > a |
| // which is not desirable for accent-insensitive sorting. |
| // Check for (lower 32 bits) == 0 as well because variable CEs are stored |
| // with only primary weights. |
| int64_t ce; |
| do { |
| ce = left.getCE(leftIndex++); |
| leftCase = (uint32_t)ce; |
| } while((uint32_t)(ce >> 32) == 0 || leftCase == 0); |
| leftLower32 = leftCase; |
| leftCase &= 0xc000; |
| |
| do { |
| ce = right.getCE(rightIndex++); |
| rightCase = (uint32_t)ce; |
| } while((uint32_t)(ce >> 32) == 0 || rightCase == 0); |
| rightCase &= 0xc000; |
| } else { |
| // Secondary+caseLevel: By analogy with the above, |
| // ignore case level weights of secondary ignorables. |
| // |
| // Note: A tertiary CE has uppercase case bits (0.0.ut) |
| // to keep tertiary+caseFirst well-formed. |
| // |
| // Tertiary+caseLevel: Also ignore case level weights of secondary ignorables. |
| // Otherwise a tertiary CE's uppercase would be no greater than |
| // a primary/secondary CE's uppercase. |
| // (See UCA well-formedness condition 2.) |
| // We could construct a special case weight higher than uppercase, |
| // but it's simpler to always ignore case weights of secondary ignorables, |
| // turning 0.0.ut into 0.0.0.t. |
| // (See LDML Collation, Case Parameters.) |
| do { |
| leftCase = (uint32_t)left.getCE(leftIndex++); |
| } while(leftCase <= 0xffff); |
| leftLower32 = leftCase; |
| leftCase &= 0xc000; |
| |
| do { |
| rightCase = (uint32_t)right.getCE(rightIndex++); |
| } while(rightCase <= 0xffff); |
| rightCase &= 0xc000; |
| } |
| |
| // No need to handle NO_CE and MERGE_SEPARATOR specially: |
| // There is one case weight for each previous-level weight, |
| // so level length differences were handled there. |
| if(leftCase != rightCase) { |
| if((options & CollationSettings::UPPER_FIRST) == 0) { |
| return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER; |
| } else { |
| return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS; |
| } |
| } |
| if((leftLower32 >> 16) == Collation::NO_CE_WEIGHT16) { break; } |
| } |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; } |
| |
| uint32_t tertiaryMask = CollationSettings::getTertiaryMask(options); |
| |
| int32_t leftIndex = 0; |
| int32_t rightIndex = 0; |
| uint32_t anyQuaternaries = 0; |
| for(;;) { |
| uint32_t leftLower32, leftTertiary; |
| do { |
| leftLower32 = (uint32_t)left.getCE(leftIndex++); |
| anyQuaternaries |= leftLower32; |
| U_ASSERT((leftLower32 & Collation::ONLY_TERTIARY_MASK) != 0 || |
| (leftLower32 & 0xc0c0) == 0); |
| leftTertiary = leftLower32 & tertiaryMask; |
| } while(leftTertiary == 0); |
| |
| uint32_t rightLower32, rightTertiary; |
| do { |
| rightLower32 = (uint32_t)right.getCE(rightIndex++); |
| anyQuaternaries |= rightLower32; |
| U_ASSERT((rightLower32 & Collation::ONLY_TERTIARY_MASK) != 0 || |
| (rightLower32 & 0xc0c0) == 0); |
| rightTertiary = rightLower32 & tertiaryMask; |
| } while(rightTertiary == 0); |
| |
| if(leftTertiary != rightTertiary) { |
| if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) { |
| // Pass through NO_CE and keep real tertiary weights larger than that. |
| // Do not change the artificial uppercase weight of a tertiary CE (0.0.ut), |
| // to keep tertiary CEs well-formed. |
| // Their case+tertiary weights must be greater than those of |
| // primary and secondary CEs. |
| if(leftTertiary > Collation::NO_CE_WEIGHT16) { |
| if(leftLower32 > 0xffff) { |
| leftTertiary ^= 0xc000; |
| } else { |
| leftTertiary += 0x4000; |
| } |
| } |
| if(rightTertiary > Collation::NO_CE_WEIGHT16) { |
| if(rightLower32 > 0xffff) { |
| rightTertiary ^= 0xc000; |
| } else { |
| rightTertiary += 0x4000; |
| } |
| } |
| } |
| return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftTertiary == Collation::NO_CE_WEIGHT16) { break; } |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; } |
| |
| if(!anyVariable && (anyQuaternaries & 0xc0) == 0) { |
| // If there are no "variable" CEs and no non-zero quaternary weights, |
| // then there are no quaternary differences. |
| return UCOL_EQUAL; |
| } |
| |
| leftIndex = 0; |
| rightIndex = 0; |
| for(;;) { |
| uint32_t leftQuaternary; |
| do { |
| int64_t ce = left.getCE(leftIndex++); |
| leftQuaternary = (uint32_t)ce & 0xffff; |
| if(leftQuaternary <= Collation::NO_CE_WEIGHT16) { |
| // Variable primary or completely ignorable or NO_CE. |
| leftQuaternary = (uint32_t)(ce >> 32); |
| } else { |
| // Regular CE, not tertiary ignorable. |
| // Preserve the quaternary weight in bits 7..6. |
| leftQuaternary |= 0xffffff3f; |
| } |
| } while(leftQuaternary == 0); |
| |
| uint32_t rightQuaternary; |
| do { |
| int64_t ce = right.getCE(rightIndex++); |
| rightQuaternary = (uint32_t)ce & 0xffff; |
| if(rightQuaternary <= Collation::NO_CE_WEIGHT16) { |
| // Variable primary or completely ignorable or NO_CE. |
| rightQuaternary = (uint32_t)(ce >> 32); |
| } else { |
| // Regular CE, not tertiary ignorable. |
| // Preserve the quaternary weight in bits 7..6. |
| rightQuaternary |= 0xffffff3f; |
| } |
| } while(rightQuaternary == 0); |
| |
| if(leftQuaternary != rightQuaternary) { |
| // Return the difference, with script reordering. |
| if(settings.hasReordering()) { |
| leftQuaternary = settings.reorder(leftQuaternary); |
| rightQuaternary = settings.reorder(rightQuaternary); |
| } |
| return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftQuaternary == Collation::NO_CE_PRIMARY) { break; } |
| } |
| return UCOL_EQUAL; |
| } |
| |
| U_NAMESPACE_END |
| |
| #endif // !UCONFIG_NO_COLLATION |
