1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 * Copyright (C) 2010-2012, International Business Machines
6 * Corporation and others. All Rights Reserved.
7 *******************************************************************************
8 * file name: ucharstriebuilder.h
9 * encoding: UTF-8
10 * tab size: 8 (not used)
11 * indentation:4
12 *
13 * created on: 2010nov14
14 * created by: Markus W. Scherer
15 */
16
17 #include "unicode/utypes.h"
18 #include "unicode/ucharstrie.h"
19 #include "unicode/ucharstriebuilder.h"
20 #include "unicode/unistr.h"
21 #include "unicode/ustring.h"
22 #include "cmemory.h"
23 #include "uarrsort.h"
24 #include "uassert.h"
25 #include "uhash.h"
26 #include "ustr_imp.h"
27
28 U_NAMESPACE_BEGIN
29
30 /*
31 * Note: This builder implementation stores (string, value) pairs with full copies
32 * of the 16-bit-unit sequences, until the UCharsTrie is built.
33 * It might(!) take less memory if we collected the data in a temporary, dynamic trie.
34 */
35
36 class UCharsTrieElement : public UMemory {
37 public:
38 // Use compiler's default constructor, initializes nothing.
39
40 void setTo(const UnicodeString &s, int32_t val, UnicodeString &strings, UErrorCode &errorCode);
41
getString(const UnicodeString & strings) const42 UnicodeString getString(const UnicodeString &strings) const {
43 int32_t length=strings[stringOffset];
44 return strings.tempSubString(stringOffset+1, length);
45 }
getStringLength(const UnicodeString & strings) const46 int32_t getStringLength(const UnicodeString &strings) const {
47 return strings[stringOffset];
48 }
49
charAt(int32_t index,const UnicodeString & strings) const50 UChar charAt(int32_t index, const UnicodeString &strings) const {
51 return strings[stringOffset+1+index];
52 }
53
getValue() const54 int32_t getValue() const { return value; }
55
56 int32_t compareStringTo(const UCharsTrieElement &o, const UnicodeString &strings) const;
57
58 private:
59 // The first strings unit contains the string length.
60 // (Compared with a stringLength field here, this saves 2 bytes per string.)
61 int32_t stringOffset;
62 int32_t value;
63 };
64
65 void
setTo(const UnicodeString & s,int32_t val,UnicodeString & strings,UErrorCode & errorCode)66 UCharsTrieElement::setTo(const UnicodeString &s, int32_t val,
67 UnicodeString &strings, UErrorCode &errorCode) {
68 if(U_FAILURE(errorCode)) {
69 return;
70 }
71 int32_t length=s.length();
72 if(length>0xffff) {
73 // Too long: We store the length in 1 unit.
74 errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
75 return;
76 }
77 stringOffset=strings.length();
78 strings.append((UChar)length);
79 value=val;
80 strings.append(s);
81 }
82
83 int32_t
compareStringTo(const UCharsTrieElement & other,const UnicodeString & strings) const84 UCharsTrieElement::compareStringTo(const UCharsTrieElement &other, const UnicodeString &strings) const {
85 return getString(strings).compare(other.getString(strings));
86 }
87
UCharsTrieBuilder(UErrorCode &)88 UCharsTrieBuilder::UCharsTrieBuilder(UErrorCode & /*errorCode*/)
89 : elements(NULL), elementsCapacity(0), elementsLength(0),
90 uchars(NULL), ucharsCapacity(0), ucharsLength(0) {}
91
~UCharsTrieBuilder()92 UCharsTrieBuilder::~UCharsTrieBuilder() {
93 delete[] elements;
94 uprv_free(uchars);
95 }
96
97 UCharsTrieBuilder &
add(const UnicodeString & s,int32_t value,UErrorCode & errorCode)98 UCharsTrieBuilder::add(const UnicodeString &s, int32_t value, UErrorCode &errorCode) {
99 if(U_FAILURE(errorCode)) {
100 return *this;
101 }
102 if(ucharsLength>0) {
103 // Cannot add elements after building.
104 errorCode=U_NO_WRITE_PERMISSION;
105 return *this;
106 }
107 if(elementsLength==elementsCapacity) {
108 int32_t newCapacity;
109 if(elementsCapacity==0) {
110 newCapacity=1024;
111 } else {
112 newCapacity=4*elementsCapacity;
113 }
114 UCharsTrieElement *newElements=new UCharsTrieElement[newCapacity];
115 if(newElements==NULL) {
116 errorCode=U_MEMORY_ALLOCATION_ERROR;
117 return *this;
118 }
119 if(elementsLength>0) {
120 uprv_memcpy(newElements, elements, (size_t)elementsLength*sizeof(UCharsTrieElement));
121 }
122 delete[] elements;
123 elements=newElements;
124 elementsCapacity=newCapacity;
125 }
126 elements[elementsLength++].setTo(s, value, strings, errorCode);
127 if(U_SUCCESS(errorCode) && strings.isBogus()) {
128 errorCode=U_MEMORY_ALLOCATION_ERROR;
129 }
130 return *this;
131 }
132
133 U_CDECL_BEGIN
134
135 static int32_t U_CALLCONV
compareElementStrings(const void * context,const void * left,const void * right)136 compareElementStrings(const void *context, const void *left, const void *right) {
137 const UnicodeString *strings=static_cast<const UnicodeString *>(context);
138 const UCharsTrieElement *leftElement=static_cast<const UCharsTrieElement *>(left);
139 const UCharsTrieElement *rightElement=static_cast<const UCharsTrieElement *>(right);
140 return leftElement->compareStringTo(*rightElement, *strings);
141 }
142
143 U_CDECL_END
144
145 UCharsTrie *
build(UStringTrieBuildOption buildOption,UErrorCode & errorCode)146 UCharsTrieBuilder::build(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
147 buildUChars(buildOption, errorCode);
148 UCharsTrie *newTrie=NULL;
149 if(U_SUCCESS(errorCode)) {
150 newTrie=new UCharsTrie(uchars, uchars+(ucharsCapacity-ucharsLength));
151 if(newTrie==NULL) {
152 errorCode=U_MEMORY_ALLOCATION_ERROR;
153 } else {
154 uchars=NULL; // The new trie now owns the array.
155 ucharsCapacity=0;
156 }
157 }
158 return newTrie;
159 }
160
161 UnicodeString &
buildUnicodeString(UStringTrieBuildOption buildOption,UnicodeString & result,UErrorCode & errorCode)162 UCharsTrieBuilder::buildUnicodeString(UStringTrieBuildOption buildOption, UnicodeString &result,
163 UErrorCode &errorCode) {
164 buildUChars(buildOption, errorCode);
165 if(U_SUCCESS(errorCode)) {
166 result.setTo(FALSE, uchars+(ucharsCapacity-ucharsLength), ucharsLength);
167 }
168 return result;
169 }
170
171 void
buildUChars(UStringTrieBuildOption buildOption,UErrorCode & errorCode)172 UCharsTrieBuilder::buildUChars(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
173 if(U_FAILURE(errorCode)) {
174 return;
175 }
176 if(uchars!=NULL && ucharsLength>0) {
177 // Already built.
178 return;
179 }
180 if(ucharsLength==0) {
181 if(elementsLength==0) {
182 errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
183 return;
184 }
185 if(strings.isBogus()) {
186 errorCode=U_MEMORY_ALLOCATION_ERROR;
187 return;
188 }
189 uprv_sortArray(elements, elementsLength, (int32_t)sizeof(UCharsTrieElement),
190 compareElementStrings, &strings,
191 FALSE, // need not be a stable sort
192 &errorCode);
193 if(U_FAILURE(errorCode)) {
194 return;
195 }
196 // Duplicate strings are not allowed.
197 UnicodeString prev=elements[0].getString(strings);
198 for(int32_t i=1; i<elementsLength; ++i) {
199 UnicodeString current=elements[i].getString(strings);
200 if(prev==current) {
201 errorCode=U_ILLEGAL_ARGUMENT_ERROR;
202 return;
203 }
204 prev.fastCopyFrom(current);
205 }
206 }
207 // Create and UChar-serialize the trie for the elements.
208 ucharsLength=0;
209 int32_t capacity=strings.length();
210 if(capacity<1024) {
211 capacity=1024;
212 }
213 if(ucharsCapacity<capacity) {
214 uprv_free(uchars);
215 uchars=static_cast<UChar *>(uprv_malloc(capacity*2));
216 if(uchars==NULL) {
217 errorCode=U_MEMORY_ALLOCATION_ERROR;
218 ucharsCapacity=0;
219 return;
220 }
221 ucharsCapacity=capacity;
222 }
223 StringTrieBuilder::build(buildOption, elementsLength, errorCode);
224 if(uchars==NULL) {
225 errorCode=U_MEMORY_ALLOCATION_ERROR;
226 }
227 }
228
229 int32_t
getElementStringLength(int32_t i) const230 UCharsTrieBuilder::getElementStringLength(int32_t i) const {
231 return elements[i].getStringLength(strings);
232 }
233
234 UChar
getElementUnit(int32_t i,int32_t unitIndex) const235 UCharsTrieBuilder::getElementUnit(int32_t i, int32_t unitIndex) const {
236 return elements[i].charAt(unitIndex, strings);
237 }
238
239 int32_t
getElementValue(int32_t i) const240 UCharsTrieBuilder::getElementValue(int32_t i) const {
241 return elements[i].getValue();
242 }
243
244 int32_t
getLimitOfLinearMatch(int32_t first,int32_t last,int32_t unitIndex) const245 UCharsTrieBuilder::getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const {
246 const UCharsTrieElement &firstElement=elements[first];
247 const UCharsTrieElement &lastElement=elements[last];
248 int32_t minStringLength=firstElement.getStringLength(strings);
249 while(++unitIndex<minStringLength &&
250 firstElement.charAt(unitIndex, strings)==
251 lastElement.charAt(unitIndex, strings)) {}
252 return unitIndex;
253 }
254
255 int32_t
countElementUnits(int32_t start,int32_t limit,int32_t unitIndex) const256 UCharsTrieBuilder::countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const {
257 int32_t length=0; // Number of different units at unitIndex.
258 int32_t i=start;
259 do {
260 UChar unit=elements[i++].charAt(unitIndex, strings);
261 while(i<limit && unit==elements[i].charAt(unitIndex, strings)) {
262 ++i;
263 }
264 ++length;
265 } while(i<limit);
266 return length;
267 }
268
269 int32_t
skipElementsBySomeUnits(int32_t i,int32_t unitIndex,int32_t count) const270 UCharsTrieBuilder::skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const {
271 do {
272 UChar unit=elements[i++].charAt(unitIndex, strings);
273 while(unit==elements[i].charAt(unitIndex, strings)) {
274 ++i;
275 }
276 } while(--count>0);
277 return i;
278 }
279
280 int32_t
indexOfElementWithNextUnit(int32_t i,int32_t unitIndex,UChar unit) const281 UCharsTrieBuilder::indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, UChar unit) const {
282 while(unit==elements[i].charAt(unitIndex, strings)) {
283 ++i;
284 }
285 return i;
286 }
287
UCTLinearMatchNode(const UChar * units,int32_t len,Node * nextNode)288 UCharsTrieBuilder::UCTLinearMatchNode::UCTLinearMatchNode(const UChar *units, int32_t len, Node *nextNode)
289 : LinearMatchNode(len, nextNode), s(units) {
290 hash=hash*37u+ustr_hashUCharsN(units, len);
291 }
292
293 UBool
operator ==(const Node & other) const294 UCharsTrieBuilder::UCTLinearMatchNode::operator==(const Node &other) const {
295 if(this==&other) {
296 return TRUE;
297 }
298 if(!LinearMatchNode::operator==(other)) {
299 return FALSE;
300 }
301 const UCTLinearMatchNode &o=(const UCTLinearMatchNode &)other;
302 return 0==u_memcmp(s, o.s, length);
303 }
304
305 void
write(StringTrieBuilder & builder)306 UCharsTrieBuilder::UCTLinearMatchNode::write(StringTrieBuilder &builder) {
307 UCharsTrieBuilder &b=(UCharsTrieBuilder &)builder;
308 next->write(builder);
309 b.write(s, length);
310 offset=b.writeValueAndType(hasValue, value, b.getMinLinearMatch()+length-1);
311 }
312
313 StringTrieBuilder::Node *
createLinearMatchNode(int32_t i,int32_t unitIndex,int32_t length,Node * nextNode) const314 UCharsTrieBuilder::createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
315 Node *nextNode) const {
316 return new UCTLinearMatchNode(
317 elements[i].getString(strings).getBuffer()+unitIndex,
318 length,
319 nextNode);
320 }
321
322 UBool
ensureCapacity(int32_t length)323 UCharsTrieBuilder::ensureCapacity(int32_t length) {
324 if(uchars==NULL) {
325 return FALSE; // previous memory allocation had failed
326 }
327 if(length>ucharsCapacity) {
328 int32_t newCapacity=ucharsCapacity;
329 do {
330 newCapacity*=2;
331 } while(newCapacity<=length);
332 UChar *newUChars=static_cast<UChar *>(uprv_malloc(newCapacity*2));
333 if(newUChars==NULL) {
334 // unable to allocate memory
335 uprv_free(uchars);
336 uchars=NULL;
337 ucharsCapacity=0;
338 return FALSE;
339 }
340 u_memcpy(newUChars+(newCapacity-ucharsLength),
341 uchars+(ucharsCapacity-ucharsLength), ucharsLength);
342 uprv_free(uchars);
343 uchars=newUChars;
344 ucharsCapacity=newCapacity;
345 }
346 return TRUE;
347 }
348
349 int32_t
write(int32_t unit)350 UCharsTrieBuilder::write(int32_t unit) {
351 int32_t newLength=ucharsLength+1;
352 if(ensureCapacity(newLength)) {
353 ucharsLength=newLength;
354 uchars[ucharsCapacity-ucharsLength]=(UChar)unit;
355 }
356 return ucharsLength;
357 }
358
359 int32_t
write(const UChar * s,int32_t length)360 UCharsTrieBuilder::write(const UChar *s, int32_t length) {
361 int32_t newLength=ucharsLength+length;
362 if(ensureCapacity(newLength)) {
363 ucharsLength=newLength;
364 u_memcpy(uchars+(ucharsCapacity-ucharsLength), s, length);
365 }
366 return ucharsLength;
367 }
368
369 int32_t
writeElementUnits(int32_t i,int32_t unitIndex,int32_t length)370 UCharsTrieBuilder::writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) {
371 return write(elements[i].getString(strings).getBuffer()+unitIndex, length);
372 }
373
374 int32_t
writeValueAndFinal(int32_t i,UBool isFinal)375 UCharsTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
376 if(0<=i && i<=UCharsTrie::kMaxOneUnitValue) {
377 return write(i|(isFinal<<15));
378 }
379 UChar intUnits[3];
380 int32_t length;
381 if(i<0 || i>UCharsTrie::kMaxTwoUnitValue) {
382 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitValueLead);
383 intUnits[1]=(UChar)((uint32_t)i>>16);
384 intUnits[2]=(UChar)i;
385 length=3;
386 // } else if(i<=UCharsTrie::kMaxOneUnitValue) {
387 // intUnits[0]=(UChar)(i);
388 // length=1;
389 } else {
390 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitValueLead+(i>>16));
391 intUnits[1]=(UChar)i;
392 length=2;
393 }
394 intUnits[0]=(UChar)(intUnits[0]|(isFinal<<15));
395 return write(intUnits, length);
396 }
397
398 int32_t
writeValueAndType(UBool hasValue,int32_t value,int32_t node)399 UCharsTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
400 if(!hasValue) {
401 return write(node);
402 }
403 UChar intUnits[3];
404 int32_t length;
405 if(value<0 || value>UCharsTrie::kMaxTwoUnitNodeValue) {
406 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitNodeValueLead);
407 intUnits[1]=(UChar)((uint32_t)value>>16);
408 intUnits[2]=(UChar)value;
409 length=3;
410 } else if(value<=UCharsTrie::kMaxOneUnitNodeValue) {
411 intUnits[0]=(UChar)((value+1)<<6);
412 length=1;
413 } else {
414 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitNodeValueLead+((value>>10)&0x7fc0));
415 intUnits[1]=(UChar)value;
416 length=2;
417 }
418 intUnits[0]|=(UChar)node;
419 return write(intUnits, length);
420 }
421
422 int32_t
writeDeltaTo(int32_t jumpTarget)423 UCharsTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
424 int32_t i=ucharsLength-jumpTarget;
425 U_ASSERT(i>=0);
426 if(i<=UCharsTrie::kMaxOneUnitDelta) {
427 return write(i);
428 }
429 UChar intUnits[3];
430 int32_t length;
431 if(i<=UCharsTrie::kMaxTwoUnitDelta) {
432 intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitDeltaLead+(i>>16));
433 length=1;
434 } else {
435 intUnits[0]=(UChar)(UCharsTrie::kThreeUnitDeltaLead);
436 intUnits[1]=(UChar)(i>>16);
437 length=2;
438 }
439 intUnits[length++]=(UChar)i;
440 return write(intUnits, length);
441 }
442
443 U_NAMESPACE_END
444