icuSources/common/localeprioritylist.cpp

   1 // © 2019 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html#License
   3
   4 // localeprioritylist.cpp
   5 // created: 2019jul11 Markus W. Scherer
   6
   7 #include "unicode/utypes.h"
   8 #include "unicode/localpointer.h"
   9 #include "unicode/locid.h"
  10 #include "unicode/stringpiece.h"
  11 #include "unicode/uobject.h"
  12 #include "charstr.h"
  13 #include "cmemory.h"
  14 #include "localeprioritylist.h"
  15 #include "uarrsort.h"
  16 #include "uassert.h"
  17 #include "uhash.h"
  18
  19 U_NAMESPACE_BEGIN
  20
  21 namespace {
  22
  23 int32_t hashLocale(const UHashTok token) {
  24     auto *locale = static_cast<const Locale *>(token.pointer);
  25     return locale->hashCode();
  26 }
  27
  28 UBool compareLocales(const UHashTok t1, const UHashTok t2) {
  29     auto *l1 = static_cast<const Locale *>(t1.pointer);
  30     auto *l2 = static_cast<const Locale *>(t2.pointer);
  31     return *l1 == *l2;
  32 }
  33
  34 constexpr int32_t WEIGHT_ONE = 1000;
  35
  36 struct LocaleAndWeight {
  37     Locale *locale;
  38     int32_t weight;  // 0..1000 = 0.0..1.0
  39     int32_t index;  // force stable sort
  40
  41     int32_t compare(const LocaleAndWeight &other) const {
  42         int32_t diff = other.weight - weight;  // descending: other-this
  43         if (diff != 0) { return diff; }
  44         return index - other.index;
  45     }
  46 };
  47
  48 int32_t U_CALLCONV
  49 compareLocaleAndWeight(const void * /*context*/, const void *left, const void *right) {
  50     return static_cast<const LocaleAndWeight *>(left)->
  51         compare(*static_cast<const LocaleAndWeight *>(right));
  52 }
  53
  54 const char *skipSpaces(const char *p, const char *limit) {
  55     while (p < limit && *p == ' ') { ++p; }
  56     return p;
  57 }
  58
  59 int32_t findTagLength(const char *p, const char *limit) {
  60     // Look for accept-language delimiters.
  61     // Leave other validation up to the Locale constructor.
  62     const char *q;
  63     for (q = p; q < limit; ++q) {
  64         char c = *q;
  65         if (c == ' ' || c == ',' || c == ';') { break; }
  66     }
  67     return static_cast<int32_t>(q - p);
  68 }
  69
  70 /**
  71  * Parses and returns a qvalue weight in millis.
  72  * Advances p to after the parsed substring.
  73  * Returns a negative value if parsing fails.
  74  */
  75 int32_t parseWeight(const char *&p, const char *limit) {
  76     p = skipSpaces(p, limit);
  77     char c;
  78     if (p == limit || ((c = *p) != '0' && c != '1')) { return -1; }
  79     int32_t weight = (c - '0') * 1000;
  80     if (++p == limit || *p != '.') { return weight; }
  81     int32_t multiplier = 100;
  82     while (++p != limit && '0' <= (c = *p) && c <= '9') {
  83         c -= '0';
  84         if (multiplier > 0) {
  85             weight += c * multiplier;
  86             multiplier /= 10;
  87         } else if (multiplier == 0) {
  88             // round up
  89             if (c >= 5) { ++weight; }
  90             multiplier = -1;
  91         }  // else ignore further fraction digits
  92     }
  93     return weight <= WEIGHT_ONE ? weight : -1;  // bad if > 1.0
  94 }
  95
  96 }  // namespace
  97
  98 /**
  99  * Nothing but a wrapper over a MaybeStackArray of LocaleAndWeight.
 100  *
 101  * This wrapper exists (and is not in an anonymous namespace)
 102  * so that we can forward-declare it in the header file and
 103  * don't have to expose the MaybeStackArray specialization and
 104  * the LocaleAndWeight to code (like the test) that #includes localeprioritylist.h.
 105  * Also, otherwise we would have to do a platform-specific
 106  * template export declaration of some kind for the MaybeStackArray specialization
 107  * to be properly exported from the common DLL.
 108  */
 109 struct LocaleAndWeightArray : public UMemory {
 110     MaybeStackArray<LocaleAndWeight, 20> array;
 111 };
 112
 113 LocalePriorityList::LocalePriorityList(StringPiece s, UErrorCode &errorCode) {
 114     if (U_FAILURE(errorCode)) { return; }
 115     list = new LocaleAndWeightArray();
 116     if (list == nullptr) {
 117         errorCode = U_MEMORY_ALLOCATION_ERROR;
 118         return;
 119     }
 120     const char *p = s.data();
 121     const char *limit = p + s.length();
 122     while ((p = skipSpaces(p, limit)) != limit) {
 123         if (*p == ',') {  // empty range field
 124             ++p;
 125             continue;
 126         }
 127         int32_t tagLength = findTagLength(p, limit);
 128         if (tagLength == 0) {
 129             errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 130             return;
 131         }
 132         CharString tag(p, tagLength, errorCode);
 133         if (U_FAILURE(errorCode)) { return; }
 134         Locale locale = Locale(tag.data());
 135         if (locale.isBogus()) {
 136             errorCode = U_MEMORY_ALLOCATION_ERROR;
 137             return;
 138         }
 139         int32_t weight = WEIGHT_ONE;
 140         if ((p = skipSpaces(p + tagLength, limit)) != limit && *p == ';') {
 141             if ((p = skipSpaces(p + 1, limit)) == limit || *p != 'q' ||
 142                     (p = skipSpaces(p + 1, limit)) == limit || *p != '=' ||
 143                     (++p, (weight = parseWeight(p, limit)) < 0)) {
 144                 errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 145                 return;
 146             }
 147             p = skipSpaces(p, limit);
 148         }
 149         if (p != limit && *p != ',') {  // trailing junk
 150             errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 151             return;
 152         }
 153         add(locale, weight, errorCode);
 154         if (p == limit) { break; }
 155         ++p;
 156     }
 157     sort(errorCode);
 158 }
 159
 160 LocalePriorityList::~LocalePriorityList() {
 161     if (list != nullptr) {
 162         for (int32_t i = 0; i < listLength; ++i) {
 163             delete list->array[i].locale;
 164         }
 165         delete list;
 166     }
 167     uhash_close(map);
 168 }
 169
 170 const Locale *LocalePriorityList::localeAt(int32_t i) const {
 171     return list->array[i].locale;
 172 }
 173
 174 Locale *LocalePriorityList::orphanLocaleAt(int32_t i) {
 175     if (list == nullptr) { return nullptr; }
 176     LocaleAndWeight &lw = list->array[i];
 177     Locale *l = lw.locale;
 178     lw.locale = nullptr;
 179     return l;
 180 }
 181
 182 bool LocalePriorityList::add(const Locale &locale, int32_t weight, UErrorCode &errorCode) {
 183     if (U_FAILURE(errorCode)) { return false; }
 184     if (map == nullptr) {
 185         if (weight <= 0) { return true; }  // do not add q=0
 186         map = uhash_open(hashLocale, compareLocales, uhash_compareLong, &errorCode);
 187         if (U_FAILURE(errorCode)) { return false; }
 188     }
 189     LocalPointer<Locale> clone;
 190     int32_t index = uhash_geti(map, &locale);
 191     if (index != 0) {
 192         // Duplicate: Remove the old item and append it anew.
 193         LocaleAndWeight &lw = list->array[index - 1];
 194         clone.adoptInstead(lw.locale);
 195         lw.locale = nullptr;
 196         lw.weight = 0;
 197         ++numRemoved;
 198     }
 199     if (weight <= 0) {  // do not add q=0
 200         if (index != 0) {
 201             // Not strictly necessary but cleaner.
 202             uhash_removei(map, &locale);
 203         }
 204         return true;
 205     }
 206     if (clone.isNull()) {
 207         clone.adoptInstead(locale.clone());
 208         if (clone.isNull() || (clone->isBogus() && !locale.isBogus())) {
 209             errorCode = U_MEMORY_ALLOCATION_ERROR;
 210             return false;
 211         }
 212     }
 213     if (listLength == list->array.getCapacity()) {
 214         int32_t newCapacity = listLength < 50 ? 100 : 4 * listLength;
 215         if (list->array.resize(newCapacity, listLength) == nullptr) {
 216             errorCode = U_MEMORY_ALLOCATION_ERROR;
 217             return false;
 218         }
 219     }
 220     uhash_puti(map, clone.getAlias(), listLength + 1, &errorCode);
 221     if (U_FAILURE(errorCode)) { return false; }
 222     LocaleAndWeight &lw = list->array[listLength];
 223     lw.locale = clone.orphan();
 224     lw.weight = weight;
 225     lw.index = listLength++;
 226     if (weight < WEIGHT_ONE) { hasWeights = true; }
 227     U_ASSERT(uhash_count(map) == getLength());
 228     return true;
 229 }
 230
 231 void LocalePriorityList::sort(UErrorCode &errorCode) {
 232     // Sort by descending weights if there is a mix of weights.
 233     // The comparator forces a stable sort via the item index.
 234     if (U_FAILURE(errorCode) || getLength() <= 1 || !hasWeights) { return; }
 235     uprv_sortArray(list->array.getAlias(), listLength, sizeof(LocaleAndWeight),
 236                    compareLocaleAndWeight, nullptr, FALSE, &errorCode);
 237 }
 238
 239 U_NAMESPACE_END