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
19U_NAMESPACE_BEGIN
20
21namespace {
22
23int32_t hashLocale(const UHashTok token) {
24 auto *locale = static_cast<const Locale *>(token.pointer);
25 return locale->hashCode();
26}
27
28UBool 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
34constexpr int32_t WEIGHT_ONE = 1000;
35
36struct 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
48int32_t U_CALLCONV
49compareLocaleAndWeight(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
54const char *skipSpaces(const char *p, const char *limit) {
55 while (p < limit && *p == ' ') { ++p; }
56 return p;
57}
58
59int32_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 */
75int32_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 */
109struct LocaleAndWeightArray : public UMemory {
110 MaybeStackArray<LocaleAndWeight, 20> array;
111};
112
113LocalePriorityList::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_ILLEGAL_ARGUMENT_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
160LocalePriorityList::~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
170const Locale *LocalePriorityList::localeAt(int32_t i) const {
171 return list->array[i].locale;
172}
173
174Locale *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
182bool 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
231void 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
239U_NAMESPACE_END
240