Index: source/i18n/collationkeys.cpp |
diff --git a/source/i18n/collationkeys.cpp b/source/i18n/collationkeys.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..6006811377fec607d99b0f7e300033b9d5eaf399 |
--- /dev/null |
+++ b/source/i18n/collationkeys.cpp |
@@ -0,0 +1,695 @@ |
+/* |
+******************************************************************************* |
+* Copyright (C) 2012-2014, International Business Machines |
+* Corporation and others. All Rights Reserved. |
+******************************************************************************* |
+* collationkeys.cpp |
+* |
+* created on: 2012sep02 |
+* created by: Markus W. Scherer |
+*/ |
+ |
+#include "unicode/utypes.h" |
+ |
+#if !UCONFIG_NO_COLLATION |
+ |
+#include "unicode/bytestream.h" |
+#include "collation.h" |
+#include "collationiterator.h" |
+#include "collationkeys.h" |
+#include "collationsettings.h" |
+#include "uassert.h" |
+ |
+U_NAMESPACE_BEGIN |
+ |
+SortKeyByteSink::~SortKeyByteSink() {} |
+ |
+void |
+SortKeyByteSink::Append(const char *bytes, int32_t n) { |
+ if (n <= 0 || bytes == NULL) { |
+ return; |
+ } |
+ if (ignore_ > 0) { |
+ int32_t ignoreRest = ignore_ - n; |
+ if (ignoreRest >= 0) { |
+ ignore_ = ignoreRest; |
+ return; |
+ } else { |
+ bytes += ignore_; |
+ n = -ignoreRest; |
+ ignore_ = 0; |
+ } |
+ } |
+ int32_t length = appended_; |
+ appended_ += n; |
+ if ((buffer_ + length) == bytes) { |
+ return; // the caller used GetAppendBuffer() and wrote the bytes already |
+ } |
+ int32_t available = capacity_ - length; |
+ if (n <= available) { |
+ uprv_memcpy(buffer_ + length, bytes, n); |
+ } else { |
+ AppendBeyondCapacity(bytes, n, length); |
+ } |
+} |
+ |
+char * |
+SortKeyByteSink::GetAppendBuffer(int32_t min_capacity, |
+ int32_t desired_capacity_hint, |
+ char *scratch, |
+ int32_t scratch_capacity, |
+ int32_t *result_capacity) { |
+ if (min_capacity < 1 || scratch_capacity < min_capacity) { |
+ *result_capacity = 0; |
+ return NULL; |
+ } |
+ if (ignore_ > 0) { |
+ // Do not write ignored bytes right at the end of the buffer. |
+ *result_capacity = scratch_capacity; |
+ return scratch; |
+ } |
+ int32_t available = capacity_ - appended_; |
+ if (available >= min_capacity) { |
+ *result_capacity = available; |
+ return buffer_ + appended_; |
+ } else if (Resize(desired_capacity_hint, appended_)) { |
+ *result_capacity = capacity_ - appended_; |
+ return buffer_ + appended_; |
+ } else { |
+ *result_capacity = scratch_capacity; |
+ return scratch; |
+ } |
+} |
+ |
+namespace { |
+ |
+/** |
+ * uint8_t byte buffer, similar to CharString but simpler. |
+ */ |
+class SortKeyLevel : public UMemory { |
+public: |
+ SortKeyLevel() : len(0), ok(TRUE) {} |
+ ~SortKeyLevel() {} |
+ |
+ /** @return FALSE if memory allocation failed */ |
+ UBool isOk() const { return ok; } |
+ UBool isEmpty() const { return len == 0; } |
+ int32_t length() const { return len; } |
+ const uint8_t *data() const { return buffer.getAlias(); } |
+ uint8_t operator[](int32_t index) const { return buffer[index]; } |
+ |
+ uint8_t *data() { return buffer.getAlias(); } |
+ |
+ void appendByte(uint32_t b); |
+ void appendWeight16(uint32_t w); |
+ void appendWeight32(uint32_t w); |
+ void appendReverseWeight16(uint32_t w); |
+ |
+ /** Appends all but the last byte to the sink. The last byte should be the 01 terminator. */ |
+ void appendTo(ByteSink &sink) const { |
+ U_ASSERT(len > 0 && buffer[len - 1] == 1); |
+ sink.Append(reinterpret_cast<const char *>(buffer.getAlias()), len - 1); |
+ } |
+ |
+private: |
+ MaybeStackArray<uint8_t, 40> buffer; |
+ int32_t len; |
+ UBool ok; |
+ |
+ UBool ensureCapacity(int32_t appendCapacity); |
+ |
+ SortKeyLevel(const SortKeyLevel &other); // forbid copying of this class |
+ SortKeyLevel &operator=(const SortKeyLevel &other); // forbid copying of this class |
+}; |
+ |
+void SortKeyLevel::appendByte(uint32_t b) { |
+ if(len < buffer.getCapacity() || ensureCapacity(1)) { |
+ buffer[len++] = (uint8_t)b; |
+ } |
+} |
+ |
+void |
+SortKeyLevel::appendWeight16(uint32_t w) { |
+ U_ASSERT((w & 0xffff) != 0); |
+ uint8_t b0 = (uint8_t)(w >> 8); |
+ uint8_t b1 = (uint8_t)w; |
+ int32_t appendLength = (b1 == 0) ? 1 : 2; |
+ if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { |
+ buffer[len++] = b0; |
+ if(b1 != 0) { |
+ buffer[len++] = b1; |
+ } |
+ } |
+} |
+ |
+void |
+SortKeyLevel::appendWeight32(uint32_t w) { |
+ U_ASSERT(w != 0); |
+ uint8_t bytes[4] = { (uint8_t)(w >> 24), (uint8_t)(w >> 16), (uint8_t)(w >> 8), (uint8_t)w }; |
+ int32_t appendLength = (bytes[1] == 0) ? 1 : (bytes[2] == 0) ? 2 : (bytes[3] == 0) ? 3 : 4; |
+ if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { |
+ buffer[len++] = bytes[0]; |
+ if(bytes[1] != 0) { |
+ buffer[len++] = bytes[1]; |
+ if(bytes[2] != 0) { |
+ buffer[len++] = bytes[2]; |
+ if(bytes[3] != 0) { |
+ buffer[len++] = bytes[3]; |
+ } |
+ } |
+ } |
+ } |
+} |
+ |
+void |
+SortKeyLevel::appendReverseWeight16(uint32_t w) { |
+ U_ASSERT((w & 0xffff) != 0); |
+ uint8_t b0 = (uint8_t)(w >> 8); |
+ uint8_t b1 = (uint8_t)w; |
+ int32_t appendLength = (b1 == 0) ? 1 : 2; |
+ if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { |
+ if(b1 == 0) { |
+ buffer[len++] = b0; |
+ } else { |
+ buffer[len] = b1; |
+ buffer[len + 1] = b0; |
+ len += 2; |
+ } |
+ } |
+} |
+ |
+UBool SortKeyLevel::ensureCapacity(int32_t appendCapacity) { |
+ if(!ok) { |
+ return FALSE; |
+ } |
+ int32_t newCapacity = 2 * buffer.getCapacity(); |
+ int32_t altCapacity = len + 2 * appendCapacity; |
+ if (newCapacity < altCapacity) { |
+ newCapacity = altCapacity; |
+ } |
+ if (newCapacity < 200) { |
+ newCapacity = 200; |
+ } |
+ if(buffer.resize(newCapacity, len)==NULL) { |
+ return ok = FALSE; |
+ } |
+ return TRUE; |
+} |
+ |
+} // namespace |
+ |
+CollationKeys::LevelCallback::~LevelCallback() {} |
+ |
+UBool |
+CollationKeys::LevelCallback::needToWrite(Collation::Level /*level*/) { return TRUE; } |
+ |
+/** |
+ * Map from collation strength (UColAttributeValue) |
+ * to a mask of Collation::Level bits up to that strength, |
+ * excluding the CASE_LEVEL which is independent of the strength, |
+ * and excluding IDENTICAL_LEVEL which this function does not write. |
+ */ |
+static const uint32_t levelMasks[UCOL_STRENGTH_LIMIT] = { |
+ 2, // UCOL_PRIMARY -> PRIMARY_LEVEL |
+ 6, // UCOL_SECONDARY -> up to SECONDARY_LEVEL |
+ 0x16, // UCOL_TERTIARY -> up to TERTIARY_LEVEL |
+ 0x36, // UCOL_QUATERNARY -> up to QUATERNARY_LEVEL |
+ 0, 0, 0, 0, |
+ 0, 0, 0, 0, |
+ 0, 0, 0, |
+ 0x36 // UCOL_IDENTICAL -> up to QUATERNARY_LEVEL |
+}; |
+ |
+void |
+CollationKeys::writeSortKeyUpToQuaternary(CollationIterator &iter, |
+ const UBool *compressibleBytes, |
+ const CollationSettings &settings, |
+ SortKeyByteSink &sink, |
+ Collation::Level minLevel, LevelCallback &callback, |
+ UBool preflight, UErrorCode &errorCode) { |
+ if(U_FAILURE(errorCode)) { return; } |
+ |
+ int32_t options = settings.options; |
+ // Set of levels to process and write. |
+ uint32_t levels = levelMasks[CollationSettings::getStrength(options)]; |
+ if((options & CollationSettings::CASE_LEVEL) != 0) { |
+ levels |= Collation::CASE_LEVEL_FLAG; |
+ } |
+ // Minus the levels below minLevel. |
+ levels &= ~(((uint32_t)1 << minLevel) - 1); |
+ if(levels == 0) { return; } |
+ |
+ 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; |
+ } |
+ const uint8_t *reorderTable = settings.reorderTable; |
+ |
+ uint32_t tertiaryMask = CollationSettings::getTertiaryMask(options); |
+ |
+ SortKeyLevel cases; |
+ SortKeyLevel secondaries; |
+ SortKeyLevel tertiaries; |
+ SortKeyLevel quaternaries; |
+ |
+ uint32_t compressedP1 = 0; // 0==no compression; otherwise reordered compressible lead byte |
+ int32_t commonCases = 0; |
+ int32_t commonSecondaries = 0; |
+ int32_t commonTertiaries = 0; |
+ int32_t commonQuaternaries = 0; |
+ |
+ uint32_t prevSecondary = 0; |
+ UBool anyMergeSeparators = FALSE; |
+ |
+ for(;;) { |
+ // No need to keep all CEs in the buffer when we write a sort key. |
+ iter.clearCEsIfNoneRemaining(); |
+ int64_t ce = iter.nextCE(errorCode); |
+ uint32_t p = (uint32_t)(ce >> 32); |
+ if(p < variableTop && p > Collation::MERGE_SEPARATOR_PRIMARY) { |
+ // Variable CE, shift it to quaternary level. |
+ // Ignore all following primary ignorables, and shift further variable CEs. |
+ if(commonQuaternaries != 0) { |
+ --commonQuaternaries; |
+ while(commonQuaternaries >= QUAT_COMMON_MAX_COUNT) { |
+ quaternaries.appendByte(QUAT_COMMON_MIDDLE); |
+ commonQuaternaries -= QUAT_COMMON_MAX_COUNT; |
+ } |
+ // Shifted primary weights are lower than the common weight. |
+ quaternaries.appendByte(QUAT_COMMON_LOW + commonQuaternaries); |
+ commonQuaternaries = 0; |
+ } |
+ do { |
+ if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { |
+ uint32_t p1 = p >> 24; |
+ if(reorderTable != NULL) { p1 = reorderTable[p1]; } |
+ if(p1 >= QUAT_SHIFTED_LIMIT_BYTE) { |
+ // Prevent shifted primary lead bytes from |
+ // overlapping with the common compression range. |
+ quaternaries.appendByte(QUAT_SHIFTED_LIMIT_BYTE); |
+ } |
+ quaternaries.appendWeight32((p1 << 24) | (p & 0xffffff)); |
+ } |
+ do { |
+ ce = iter.nextCE(errorCode); |
+ p = (uint32_t)(ce >> 32); |
+ } while(p == 0); |
+ } while(p < variableTop && p > Collation::MERGE_SEPARATOR_PRIMARY); |
+ } |
+ // ce could be primary ignorable, or NO_CE, or the merge separator, |
+ // or a regular primary CE, but it is not variable. |
+ // If ce==NO_CE, then write nothing for the primary level but |
+ // terminate compression on all levels and then exit the loop. |
+ if(p > Collation::NO_CE_PRIMARY && (levels & Collation::PRIMARY_LEVEL_FLAG) != 0) { |
+ uint32_t p1 = p >> 24; |
+ if(reorderTable != NULL) { p1 = reorderTable[p1]; } |
+ if(p1 != compressedP1) { |
+ if(compressedP1 != 0) { |
+ if(p1 < compressedP1) { |
+ // No primary compression terminator |
+ // at the end of the level or merged segment. |
+ if(p1 > Collation::MERGE_SEPARATOR_BYTE) { |
+ sink.Append(Collation::PRIMARY_COMPRESSION_LOW_BYTE); |
+ } |
+ } else { |
+ sink.Append(Collation::PRIMARY_COMPRESSION_HIGH_BYTE); |
+ } |
+ } |
+ sink.Append(p1); |
+ // Test the un-reordered lead byte for compressibility but |
+ // remember the reordered lead byte. |
+ if(compressibleBytes[p >> 24]) { |
+ compressedP1 = p1; |
+ } else { |
+ compressedP1 = 0; |
+ } |
+ } |
+ char p2 = (char)(p >> 16); |
+ if(p2 != 0) { |
+ char buffer[3] = { p2, (char)(p >> 8), (char)p }; |
+ sink.Append(buffer, (buffer[1] == 0) ? 1 : (buffer[2] == 0) ? 2 : 3); |
+ } |
+ // Optimization for internalNextSortKeyPart(): |
+ // When the primary level overflows we can stop because we need not |
+ // calculate (preflight) the whole sort key length. |
+ if(!preflight && sink.Overflowed()) { |
+ if(U_SUCCESS(errorCode) && !sink.IsOk()) { |
+ errorCode = U_MEMORY_ALLOCATION_ERROR; |
+ } |
+ return; |
+ } |
+ } |
+ |
+ uint32_t lower32 = (uint32_t)ce; |
+ if(lower32 == 0) { continue; } // completely ignorable, no secondary/case/tertiary/quaternary |
+ |
+ if((levels & Collation::SECONDARY_LEVEL_FLAG) != 0) { |
+ uint32_t s = lower32 >> 16; |
+ if(s == 0) { |
+ // secondary ignorable |
+ } else if(s == Collation::COMMON_WEIGHT16) { |
+ ++commonSecondaries; |
+ } else if((options & CollationSettings::BACKWARD_SECONDARY) == 0) { |
+ if(commonSecondaries != 0) { |
+ --commonSecondaries; |
+ while(commonSecondaries >= SEC_COMMON_MAX_COUNT) { |
+ secondaries.appendByte(SEC_COMMON_MIDDLE); |
+ commonSecondaries -= SEC_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(s < Collation::COMMON_WEIGHT16) { |
+ b = SEC_COMMON_LOW + commonSecondaries; |
+ } else { |
+ b = SEC_COMMON_HIGH - commonSecondaries; |
+ } |
+ secondaries.appendByte(b); |
+ commonSecondaries = 0; |
+ } |
+ secondaries.appendWeight16(s); |
+ } else { |
+ if(commonSecondaries != 0) { |
+ --commonSecondaries; |
+ // Append reverse weights. The level will be re-reversed later. |
+ int32_t remainder = commonSecondaries % SEC_COMMON_MAX_COUNT; |
+ uint32_t b; |
+ if(prevSecondary < Collation::COMMON_WEIGHT16) { |
+ b = SEC_COMMON_LOW + remainder; |
+ } else { |
+ b = SEC_COMMON_HIGH - remainder; |
+ } |
+ secondaries.appendByte(b); |
+ commonSecondaries -= remainder; |
+ // commonSecondaries is now a multiple of SEC_COMMON_MAX_COUNT. |
+ while(commonSecondaries > 0) { // same as >= SEC_COMMON_MAX_COUNT |
+ secondaries.appendByte(SEC_COMMON_MIDDLE); |
+ commonSecondaries -= SEC_COMMON_MAX_COUNT; |
+ } |
+ // commonSecondaries == 0 |
+ } |
+ // Reduce separators so that we can look for byte<=1 later. |
+ if(s <= Collation::MERGE_SEPARATOR_WEIGHT16) { |
+ if(s == Collation::MERGE_SEPARATOR_WEIGHT16) { |
+ anyMergeSeparators = TRUE; |
+ } |
+ secondaries.appendByte((s >> 8) - 1); |
+ } else { |
+ secondaries.appendReverseWeight16(s); |
+ } |
+ prevSecondary = s; |
+ } |
+ } |
+ |
+ if((levels & Collation::CASE_LEVEL_FLAG) != 0) { |
+ if((CollationSettings::getStrength(options) == UCOL_PRIMARY) ? |
+ p == 0 : lower32 <= 0xffff) { |
+ // Primary+caseLevel: Ignore case level weights of primary ignorables. |
+ // Otherwise: Ignore case level weights of secondary ignorables. |
+ // For details see the comments in the CollationCompare class. |
+ } else { |
+ uint32_t c = (lower32 >> 8) & 0xff; // case bits & tertiary lead byte |
+ U_ASSERT((c & 0xc0) != 0xc0); |
+ if((c & 0xc0) == 0 && c > Collation::MERGE_SEPARATOR_BYTE) { |
+ ++commonCases; |
+ } else { |
+ if((options & CollationSettings::UPPER_FIRST) == 0) { |
+ // lowerFirst: Compress common weights to nibbles 1..7..13, mixed=14, upper=15. |
+ if(commonCases != 0) { |
+ --commonCases; |
+ while(commonCases >= CASE_LOWER_FIRST_COMMON_MAX_COUNT) { |
+ cases.appendByte(CASE_LOWER_FIRST_COMMON_MIDDLE << 4); |
+ commonCases -= CASE_LOWER_FIRST_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(c <= Collation::MERGE_SEPARATOR_BYTE) { |
+ b = CASE_LOWER_FIRST_COMMON_LOW + commonCases; |
+ } else { |
+ b = CASE_LOWER_FIRST_COMMON_HIGH - commonCases; |
+ } |
+ cases.appendByte(b << 4); |
+ commonCases = 0; |
+ } |
+ if(c > Collation::MERGE_SEPARATOR_BYTE) { |
+ c = (CASE_LOWER_FIRST_COMMON_HIGH + (c >> 6)) << 4; // 14 or 15 |
+ } |
+ } else { |
+ // upperFirst: Compress common weights to nibbles 3..15, mixed=2, upper=1. |
+ // The compressed common case weights only go up from the "low" value |
+ // because with upperFirst the common weight is the highest one. |
+ if(commonCases != 0) { |
+ --commonCases; |
+ while(commonCases >= CASE_UPPER_FIRST_COMMON_MAX_COUNT) { |
+ cases.appendByte(CASE_UPPER_FIRST_COMMON_LOW << 4); |
+ commonCases -= CASE_UPPER_FIRST_COMMON_MAX_COUNT; |
+ } |
+ cases.appendByte((CASE_UPPER_FIRST_COMMON_LOW + commonCases) << 4); |
+ commonCases = 0; |
+ } |
+ if(c > Collation::MERGE_SEPARATOR_BYTE) { |
+ c = (CASE_UPPER_FIRST_COMMON_LOW - (c >> 6)) << 4; // 2 or 1 |
+ } |
+ } |
+ // c is a separator byte 01 or 02, |
+ // or a left-shifted nibble 0x10, 0x20, ... 0xf0. |
+ cases.appendByte(c); |
+ } |
+ } |
+ } |
+ |
+ if((levels & Collation::TERTIARY_LEVEL_FLAG) != 0) { |
+ uint32_t t = lower32 & tertiaryMask; |
+ U_ASSERT((lower32 & 0xc000) != 0xc000); |
+ if(t == Collation::COMMON_WEIGHT16) { |
+ ++commonTertiaries; |
+ } else if((tertiaryMask & 0x8000) == 0) { |
+ // Tertiary weights without case bits. |
+ // Move lead bytes 06..3F to C6..FF for a large common-weight range. |
+ if(commonTertiaries != 0) { |
+ --commonTertiaries; |
+ while(commonTertiaries >= TER_ONLY_COMMON_MAX_COUNT) { |
+ tertiaries.appendByte(TER_ONLY_COMMON_MIDDLE); |
+ commonTertiaries -= TER_ONLY_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(t < Collation::COMMON_WEIGHT16) { |
+ b = TER_ONLY_COMMON_LOW + commonTertiaries; |
+ } else { |
+ b = TER_ONLY_COMMON_HIGH - commonTertiaries; |
+ } |
+ tertiaries.appendByte(b); |
+ commonTertiaries = 0; |
+ } |
+ if(t > Collation::COMMON_WEIGHT16) { t += 0xc000; } |
+ tertiaries.appendWeight16(t); |
+ } else if((options & CollationSettings::UPPER_FIRST) == 0) { |
+ // Tertiary weights with caseFirst=lowerFirst. |
+ // Move lead bytes 06..BF to 46..FF for the common-weight range. |
+ if(commonTertiaries != 0) { |
+ --commonTertiaries; |
+ while(commonTertiaries >= TER_LOWER_FIRST_COMMON_MAX_COUNT) { |
+ tertiaries.appendByte(TER_LOWER_FIRST_COMMON_MIDDLE); |
+ commonTertiaries -= TER_LOWER_FIRST_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(t < Collation::COMMON_WEIGHT16) { |
+ b = TER_LOWER_FIRST_COMMON_LOW + commonTertiaries; |
+ } else { |
+ b = TER_LOWER_FIRST_COMMON_HIGH - commonTertiaries; |
+ } |
+ tertiaries.appendByte(b); |
+ commonTertiaries = 0; |
+ } |
+ if(t > Collation::COMMON_WEIGHT16) { t += 0x4000; } |
+ tertiaries.appendWeight16(t); |
+ } else { |
+ // Tertiary weights with caseFirst=upperFirst. |
+ // 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. |
+ // |
+ // Separators 01..02 -> 01..02 (unchanged) |
+ // Lowercase 03..04 -> 83..84 (includes uncased) |
+ // Common weight 05 -> 85..C5 (common-weight compression range) |
+ // Lowercase 06..3F -> C6..FF |
+ // Mixed case 43..7F -> 43..7F |
+ // Uppercase 83..BF -> 03..3F |
+ // Tertiary CE 86..BF -> C6..FF |
+ if(t <= Collation::MERGE_SEPARATOR_WEIGHT16) { |
+ // Keep separators unchanged. |
+ } else if(lower32 > 0xffff) { |
+ // Invert case bits of primary & secondary CEs. |
+ t ^= 0xc000; |
+ if(t < (TER_UPPER_FIRST_COMMON_HIGH << 8)) { |
+ t -= 0x4000; |
+ } |
+ } else { |
+ // Keep uppercase bits of tertiary CEs. |
+ U_ASSERT(0x8600 <= t && t <= 0xbfff); |
+ t += 0x4000; |
+ } |
+ if(commonTertiaries != 0) { |
+ --commonTertiaries; |
+ while(commonTertiaries >= TER_UPPER_FIRST_COMMON_MAX_COUNT) { |
+ tertiaries.appendByte(TER_UPPER_FIRST_COMMON_MIDDLE); |
+ commonTertiaries -= TER_UPPER_FIRST_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(t < (TER_UPPER_FIRST_COMMON_LOW << 8)) { |
+ b = TER_UPPER_FIRST_COMMON_LOW + commonTertiaries; |
+ } else { |
+ b = TER_UPPER_FIRST_COMMON_HIGH - commonTertiaries; |
+ } |
+ tertiaries.appendByte(b); |
+ commonTertiaries = 0; |
+ } |
+ tertiaries.appendWeight16(t); |
+ } |
+ } |
+ |
+ if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { |
+ uint32_t q = lower32 & 0xffff; |
+ if((q & 0xc0) == 0 && q > Collation::MERGE_SEPARATOR_WEIGHT16) { |
+ ++commonQuaternaries; |
+ } else if(q <= Collation::MERGE_SEPARATOR_WEIGHT16 && |
+ (options & CollationSettings::ALTERNATE_MASK) == 0 && |
+ (quaternaries.isEmpty() || |
+ quaternaries[quaternaries.length() - 1] == Collation::MERGE_SEPARATOR_BYTE)) { |
+ // If alternate=non-ignorable and there are only |
+ // common quaternary weights between two separators, |
+ // then we need not write anything between these separators. |
+ // The only weights greater than the merge separator and less than the common weight |
+ // are shifted primary weights, which are not generated for alternate=non-ignorable. |
+ // There are also exactly as many quaternary weights as tertiary weights, |
+ // so level length differences are handled already on tertiary level. |
+ // Any above-common quaternary weight will compare greater regardless. |
+ quaternaries.appendByte(q >> 8); |
+ } else { |
+ if(q <= Collation::MERGE_SEPARATOR_WEIGHT16) { |
+ q >>= 8; |
+ } else { |
+ q = 0xfc + ((q >> 6) & 3); |
+ } |
+ if(commonQuaternaries != 0) { |
+ --commonQuaternaries; |
+ while(commonQuaternaries >= QUAT_COMMON_MAX_COUNT) { |
+ quaternaries.appendByte(QUAT_COMMON_MIDDLE); |
+ commonQuaternaries -= QUAT_COMMON_MAX_COUNT; |
+ } |
+ uint32_t b; |
+ if(q < QUAT_COMMON_LOW) { |
+ b = QUAT_COMMON_LOW + commonQuaternaries; |
+ } else { |
+ b = QUAT_COMMON_HIGH - commonQuaternaries; |
+ } |
+ quaternaries.appendByte(b); |
+ commonQuaternaries = 0; |
+ } |
+ quaternaries.appendByte(q); |
+ } |
+ } |
+ |
+ if((lower32 >> 24) == Collation::LEVEL_SEPARATOR_BYTE) { break; } // ce == NO_CE |
+ } |
+ |
+ if(U_FAILURE(errorCode)) { return; } |
+ |
+ // Append the beyond-primary levels. |
+ UBool ok = TRUE; |
+ if((levels & Collation::SECONDARY_LEVEL_FLAG) != 0) { |
+ if(!callback.needToWrite(Collation::SECONDARY_LEVEL)) { return; } |
+ ok &= secondaries.isOk(); |
+ sink.Append(Collation::LEVEL_SEPARATOR_BYTE); |
+ uint8_t *secs = secondaries.data(); |
+ int32_t length = secondaries.length() - 1; // Ignore the trailing NO_CE. |
+ if((options & CollationSettings::BACKWARD_SECONDARY) != 0) { |
+ // The backwards secondary level compares secondary weights backwards |
+ // within segments separated by the merge separator (U+FFFE, weight 02). |
+ // The separator weights 01 & 02 were reduced to 00 & 01 so that |
+ // we do not accidentally separate at a _second_ weight byte of 02. |
+ int32_t start = 0; |
+ for(;;) { |
+ // Find the merge separator or the NO_CE terminator. |
+ int32_t limit; |
+ if(anyMergeSeparators) { |
+ limit = start; |
+ while(secs[limit] > 1) { ++limit; } |
+ } else { |
+ limit = length; |
+ } |
+ // Reverse this segment. |
+ if(start < limit) { |
+ uint8_t *p = secs + start; |
+ uint8_t *q = secs + limit - 1; |
+ while(p < q) { |
+ uint8_t s = *p; |
+ *p++ = *q; |
+ *q-- = s; |
+ } |
+ } |
+ // Did we reach the end of the string? |
+ if(secs[limit] == 0) { break; } |
+ // Restore the merge separator. |
+ secs[limit] = 2; |
+ // Skip the merge separator and continue. |
+ start = limit + 1; |
+ } |
+ } |
+ sink.Append(reinterpret_cast<char *>(secs), length); |
+ } |
+ |
+ if((levels & Collation::CASE_LEVEL_FLAG) != 0) { |
+ if(!callback.needToWrite(Collation::CASE_LEVEL)) { return; } |
+ ok &= cases.isOk(); |
+ sink.Append(Collation::LEVEL_SEPARATOR_BYTE); |
+ // Write pairs of nibbles as bytes, except separator bytes as themselves. |
+ int32_t length = cases.length() - 1; // Ignore the trailing NO_CE. |
+ uint8_t b = 0; |
+ for(int32_t i = 0; i < length; ++i) { |
+ uint8_t c = (uint8_t)cases[i]; |
+ if(c <= Collation::MERGE_SEPARATOR_BYTE) { |
+ U_ASSERT(c != 0); |
+ if(b != 0) { |
+ sink.Append(b); |
+ b = 0; |
+ } |
+ sink.Append(c); |
+ } else { |
+ U_ASSERT((c & 0xf) == 0); |
+ if(b == 0) { |
+ b = c; |
+ } else { |
+ sink.Append(b | (c >> 4)); |
+ b = 0; |
+ } |
+ } |
+ } |
+ if(b != 0) { |
+ sink.Append(b); |
+ } |
+ } |
+ |
+ if((levels & Collation::TERTIARY_LEVEL_FLAG) != 0) { |
+ if(!callback.needToWrite(Collation::TERTIARY_LEVEL)) { return; } |
+ ok &= tertiaries.isOk(); |
+ sink.Append(Collation::LEVEL_SEPARATOR_BYTE); |
+ tertiaries.appendTo(sink); |
+ } |
+ |
+ if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { |
+ if(!callback.needToWrite(Collation::QUATERNARY_LEVEL)) { return; } |
+ ok &= quaternaries.isOk(); |
+ sink.Append(Collation::LEVEL_SEPARATOR_BYTE); |
+ quaternaries.appendTo(sink); |
+ } |
+ |
+ if(!ok || !sink.IsOk()) { |
+ errorCode = U_MEMORY_ALLOCATION_ERROR; |
+ } |
+} |
+ |
+U_NAMESPACE_END |
+ |
+#endif // !UCONFIG_NO_COLLATION |