// © 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) {
const auto* locale =
static_cast<
const Locale*>(token.pointer);
return locale->hashCode();
}
UBool compareLocales(
const UHashTok t1,
const UHashTok t2) {
const auto* l1 =
static_cast<
const Locale*>(t1.pointer);
const 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;
UBool found =
false;
int32_t index = uhash_getiAndFound(map, &locale, &found);
if (found) {
// Duplicate: Remove the old item and append it anew.
LocaleAndWeight &lw = list->array[index];
clone.adoptInstead(lw.locale);
lw.locale = nullptr;
lw.weight = 0;
++numRemoved;
}
if (weight <= 0) {
// do not add q=0
if (found) {
// 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_putiAllowZero(map, clone.getAlias(), listLength, &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
