localeprioritylist.cpp

// © 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