| // © 2019 and later: Unicode, Inc. and others. | |
| // License & terms of use: http://www.unicode.org/copyright.html | |
| // localeprioritylist.cpp | |
| // created: 2019jul11 Markus W. Scherer | |
| #include "unicode/utypes.h" | |
| #include "unicode/localpointer.h" | |
| #include "unicode/locid.h" | |
| #include "unicode/stringpiece.h" | |
| #include "unicode/uobject.h" | |
| #include "charstr.h" | |
| #include "cmemory.h" | |
| #include "localeprioritylist.h" | |
| #include "uarrsort.h" | |
| #include "uassert.h" | |
| #include "uhash.h" | |
| U_NAMESPACE_BEGIN | |
| namespace { | |
| int32_t hashLocale(const UHashTok token) { | |
| auto *locale = static_cast<const Locale *>(token.pointer); | |
| return locale->hashCode(); | |
| } | |
| UBool compareLocales(const UHashTok t1, const UHashTok t2) { | |
| auto *l1 = static_cast<const Locale *>(t1.pointer); | |
| auto *l2 = static_cast<const Locale *>(t2.pointer); | |
| return *l1 == *l2; | |
| } | |
| constexpr int32_t WEIGHT_ONE = 1000; | |
| struct LocaleAndWeight { | |
| Locale *locale; | |
| int32_t weight; // 0..1000 = 0.0..1.0 | |
| int32_t index; // force stable sort | |
| int32_t compare(const LocaleAndWeight &other) const { | |
| int32_t diff = other.weight - weight; // descending: other-this | |
| if (diff != 0) { return diff; } | |
| return index - other.index; | |
| } | |
| }; | |
| int32_t U_CALLCONV | |
| compareLocaleAndWeight(const void * /*context*/, const void *left, const void *right) { | |
| return static_cast<const LocaleAndWeight *>(left)-> | |
| compare(*static_cast<const LocaleAndWeight *>(right)); | |
| } | |
| const char *skipSpaces(const char *p, const char *limit) { | |
| while (p < limit && *p == ' ') { ++p; } | |
| return p; | |
| } | |
| int32_t findTagLength(const char *p, const char *limit) { | |
| // Look for accept-language delimiters. | |
| // Leave other validation up to the Locale constructor. | |
| const char *q; | |
| for (q = p; q < limit; ++q) { | |
| char c = *q; | |
| if (c == ' ' || c == ',' || c == ';') { break; } | |
| } | |
| return static_cast<int32_t>(q - p); | |
| } | |
| /** | |
| * Parses and returns a qvalue weight in millis. | |
| * Advances p to after the parsed substring. | |
| * Returns a negative value if parsing fails. | |
| */ | |
| int32_t parseWeight(const char *&p, const char *limit) { | |
| p = skipSpaces(p, limit); | |
| char c; | |
| if (p == limit || ((c = *p) != '0' && c != '1')) { return -1; } | |
| int32_t weight = (c - '0') * 1000; | |
| if (++p == limit || *p != '.') { return weight; } | |
| int32_t multiplier = 100; | |
| while (++p != limit && '0' <= (c = *p) && c <= '9') { | |
| c -= '0'; | |
| if (multiplier > 0) { | |
| weight += c * multiplier; | |
| multiplier /= 10; | |
| } else if (multiplier == 0) { | |
| // round up | |
| if (c >= 5) { ++weight; } | |
| multiplier = -1; | |
| } // else ignore further fraction digits | |
| } | |
| return weight <= WEIGHT_ONE ? weight : -1; // bad if > 1.0 | |
| } | |
| } // namespace | |
| /** | |
| * Nothing but a wrapper over a MaybeStackArray of LocaleAndWeight. | |
| * | |
| * This wrapper exists (and is not in an anonymous namespace) | |
| * so that we can forward-declare it in the header file and | |
| * don't have to expose the MaybeStackArray specialization and | |
| * the LocaleAndWeight to code (like the test) that #includes localeprioritylist.h. | |
| * Also, otherwise we would have to do a platform-specific | |
| * template export declaration of some kind for the MaybeStackArray specialization | |
| * to be properly exported from the common DLL. | |
| */ | |
| struct LocaleAndWeightArray : public UMemory { | |
| MaybeStackArray<LocaleAndWeight, 20> array; | |
| }; | |
| LocalePriorityList::LocalePriorityList(StringPiece s, UErrorCode &errorCode) { | |
| if (U_FAILURE(errorCode)) { return; } | |
| list = new LocaleAndWeightArray(); | |
| if (list == nullptr) { | |
| errorCode = U_MEMORY_ALLOCATION_ERROR; | |
| return; | |
| } | |
| const char *p = s.data(); | |
| const char *limit = p + s.length(); | |
| while ((p = skipSpaces(p, limit)) != limit) { | |
| if (*p == ',') { // empty range field | |
| ++p; | |
| continue; | |
| } | |
| int32_t tagLength = findTagLength(p, limit); | |
| if (tagLength == 0) { | |
| errorCode = U_ILLEGAL_ARGUMENT_ERROR; | |
| return; | |
| } | |
| CharString tag(p, tagLength, errorCode); | |
| if (U_FAILURE(errorCode)) { return; } | |
| Locale locale = Locale(tag.data()); | |
| if (locale.isBogus()) { | |
| errorCode = U_ILLEGAL_ARGUMENT_ERROR; | |
| return; | |
| } | |
| int32_t weight = WEIGHT_ONE; | |
| if ((p = skipSpaces(p + tagLength, limit)) != limit && *p == ';') { | |
| if ((p = skipSpaces(p + 1, limit)) == limit || *p != 'q' || | |
| (p = skipSpaces(p + 1, limit)) == limit || *p != '=' || | |
| (++p, (weight = parseWeight(p, limit)) < 0)) { | |
| errorCode = U_ILLEGAL_ARGUMENT_ERROR; | |
| return; | |
| } | |
| p = skipSpaces(p, limit); | |
| } | |
| if (p != limit && *p != ',') { // trailing junk | |
| errorCode = U_ILLEGAL_ARGUMENT_ERROR; | |
| return; | |
| } | |
| add(locale, weight, errorCode); | |
| if (p == limit) { break; } | |
| ++p; | |
| } | |
| sort(errorCode); | |
| } | |
| LocalePriorityList::~LocalePriorityList() { | |
| if (list != nullptr) { | |
| for (int32_t i = 0; i < listLength; ++i) { | |
| delete list->array[i].locale; | |
| } | |
| delete list; | |
| } | |
| uhash_close(map); | |
| } | |
| const Locale *LocalePriorityList::localeAt(int32_t i) const { | |
| return list->array[i].locale; | |
| } | |
| Locale *LocalePriorityList::orphanLocaleAt(int32_t i) { | |
| if (list == nullptr) { return nullptr; } | |
| LocaleAndWeight &lw = list->array[i]; | |
| Locale *l = lw.locale; | |
| lw.locale = nullptr; | |
| return l; | |
| } | |
| bool LocalePriorityList::add(const Locale &locale, int32_t weight, UErrorCode &errorCode) { | |
| if (U_FAILURE(errorCode)) { return false; } | |
| if (map == nullptr) { | |
| if (weight <= 0) { return true; } // do not add q=0 | |
| map = uhash_open(hashLocale, compareLocales, uhash_compareLong, &errorCode); | |
| if (U_FAILURE(errorCode)) { return false; } | |
| } | |
| LocalPointer<Locale> clone; | |
| int32_t index = uhash_geti(map, &locale); | |
| if (index != 0) { | |
| // Duplicate: Remove the old item and append it anew. | |
| LocaleAndWeight &lw = list->array[index - 1]; | |
| clone.adoptInstead(lw.locale); | |
| lw.locale = nullptr; | |
| lw.weight = 0; | |
| ++numRemoved; | |
| } | |
| if (weight <= 0) { // do not add q=0 | |
| if (index != 0) { | |
| // Not strictly necessary but cleaner. | |
| uhash_removei(map, &locale); | |
| } | |
| return true; | |
| } | |
| if (clone.isNull()) { | |
| clone.adoptInstead(locale.clone()); | |
| if (clone.isNull() || (clone->isBogus() && !locale.isBogus())) { | |
| errorCode = U_MEMORY_ALLOCATION_ERROR; | |
| return false; | |
| } | |
| } | |
| if (listLength == list->array.getCapacity()) { | |
| int32_t newCapacity = listLength < 50 ? 100 : 4 * listLength; | |
| if (list->array.resize(newCapacity, listLength) == nullptr) { | |
| errorCode = U_MEMORY_ALLOCATION_ERROR; | |
| return false; | |
| } | |
| } | |
| uhash_puti(map, clone.getAlias(), listLength + 1, &errorCode); | |
| if (U_FAILURE(errorCode)) { return false; } | |
| LocaleAndWeight &lw = list->array[listLength]; | |
| lw.locale = clone.orphan(); | |
| lw.weight = weight; | |
| lw.index = listLength++; | |
| if (weight < WEIGHT_ONE) { hasWeights = true; } | |
| U_ASSERT(uhash_count(map) == getLength()); | |
| return true; | |
| } | |
| void LocalePriorityList::sort(UErrorCode &errorCode) { | |
| // Sort by descending weights if there is a mix of weights. | |
| // The comparator forces a stable sort via the item index. | |
| if (U_FAILURE(errorCode) || getLength() <= 1 || !hasWeights) { return; } | |
| uprv_sortArray(list->array.getAlias(), listLength, sizeof(LocaleAndWeight), | |
| compareLocaleAndWeight, nullptr, FALSE, &errorCode); | |
| } | |
| U_NAMESPACE_END |